Välordningsaxiomet
Välordningsaxiomet är en princip inom matematik, som säger att varje icke-tom delmängd av positiva heltal har ett minsta element, det vill säga att de positiva heltalen är en välordnad mängd. Välordningsaxiomet används ofta som en del av definitionen av heltalen.
Bevis
Vi börjar med visa att välordningsaxiomet gäller för alla ändliga delmängder av de positiva heltalen genom induktionsbevis på antalet element som finns i mängden M. Antag att välordningsaxiomet gäller för alla mängder med n element och låt M vara en mängd med n + 1 element. Låter vi x vara ett element i M och betraktar vi nu mängden A = M \ {x}. A har nu ett minsta element, kalla det för y, då gäller antingen att y är mindre än x eller x är mindre än y. Om y är mindre än x så har vi att y är det minsta elementet i mängden A, i båda fall har vi alltid ett minsta element och eftersom M är godtyckligt vald så gäller det att för alla mängder med n stycken element så gäller även för alla mängder för n + 1 element. induktionsbevis säger alltså att välordningsaxiomet gäller för alla ändliga mängder.
Exempel
Låt A vara mängden av de positiva heltal som ligger mellan 0 och 1. Vi vill visa att denna mängd är tom.
Antag att mängden inte är tom. Det finns då ett minsta element i A, som kan kallas a. Härav följer att även a2, vilket är mindre än a, tillhör A. Detta strider dock mot definitionen av a, vilket medför att mängden är tom.
Induktion
Välordningsaxiomet gör induktionsbevis tillåtna. Omvänt kan man från antagandet att induktionsbevis är tillåtna visa att välordningsaxiomet gäller för de positiva heltalen.
Källor
- Karl Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.
- Stefan Lemurell, Johan Jonasson, Algebra och Diskret Matematik, Studentlitteratur, Göteborg 2003