Bizonyítás
Tegyük fel indirekt, hogy P egy olyan galád nemüres részhalmaza \N-nek, amelynek nincs minimuma. Jelöljük ezenkívül Q-val \N-nek azt a részhalmazát, amely pontosan azokat a természetes számokat tartalmazza, amelyek kisebbek P minden eleménél. Azaz egyrészt minden Q-beli q elemre teljesül, hogy minden P-beli p elem esetén q\lt p, másrészt semmilyen Q halmazon kívüli elemre nem tejesül ez a tulajdonság. Ez a szituáció látható a 17.3. ábrán.
Egyelőre még nem tudjuk, hogy mely természetes számok tartoznak P-be, és melyek Q-ba. Az viszont bizonyos, hogy ha egy q természetes szám Q-ba tartozik, akkor nem tartozhat egyúttal P-be is, máskülönben teljesülne a q\lt q reláció. Ez viszont lehetetlen, hiszen a 15.18. Tétel alapján ekkor léteznie kéne egy olyan k\neq 0 természetes számnak, amelyre q+k=q teljesül. Mindkét oldalból q-t kivonva k=0 adódna, ami ellentmond k\neq 0-nak.
Azt kell megmutatnunk, hogy valójában minden természetes szám Q-ba tartozik, azaz Q=\N, hiszen ebből következne, hogy – indirekt feltételezésünkkel ellentétben – P csak az üres halmaz lehet. Ezt teljes indukcióval fogjuk bizonyítani, amelyre a Peano-axiómarendszer 11.1. Definíciójának 4. pontja ad lehetőséget.
Kezdjük a 0-val. Tegyük fel indirekt, hogy a 0 nincs benne Q-ban, azaz létezik olyan P-beli p elem, amelyre nem teljesül a 0\lt p reláció. Ekkor viszont az egész számok rendezésének trichotómiája miatt szükségképpen teljesülne a p\leq 0 reláció. Ez a 15.18. Tétel miatt azt jelentené, hogy létezik olyan k természetes szám, amelyre p+k=0. A 12.19. Lemma alapján azonban a természetes számok körében egy összeg csak úgy lehet 0, ha mindkét tagja 0, és így p=0 lenne.
Abból az indirekt feltételezésből tehát, miszerint a 0 nincs benne Q-ban az következik, hogy benne van P-ben. Ez viszont lehetetlen, hiszen bármely n természetes számra teljesül 0\leq n reláció, és így P-nek a 0 minimuma lenne, márpedig P-ről a bizonyítás elején feltettük, hogy nincs minimuma. A 0-nak tehát szükségképpen Q-ban kell lennie.
Tegyük most fel, hogy egy valamilyen n természetes számról már tudjuk, hogy Q-ban van – mint például a 0, amiről ezt az imént láttunk be. Azt szeretnénk megmutatni, hogy ekkor s(n) – azaz n-nek a 11.1. Definíció szerinti rákövetkezője – is benne van a Q-ban.
Ezt ismét indirekt módon bizonyítjuk. Tegyük ezért fel az állítás ellenkezőjét, azaz hogy s(n) nincs benne a Q halmazban. Egyrészt ez azt jelentené, hogy létezne olyan P-beli p elem, amelyre nem teljesül az s(n)\lt p reláció. Ismét a trichotómia miatt ekkor szükségképpen teljesülne a p\leq s(n) reláció. Másrészt, mivel ugye n az indukciós feltétel miatt benne van a Q halmazban, így teljesül az n\lt p reláció is. Azaz összefoglalva:
Ebből viszont a 17.14. Lemma miatt az következik, hogy s(n) benne van a P halmazban, mivel:
Egyrészt tehát azt kaptuk, hogy ha s(n) nem lenne Q-ban, akkor szükségképpen P-ben kellene lennie. Másrészt viszont az iménti gondolatmenetet bármely P-beli x elemre megismételve azt kapnánk, hogy x\leq s(n) csak úgy teljesülhet, ha x=s(n). Így tehát a P halmaznak mégiscsak lenne minimuma, nevezetesen s(n). Tehát hibás volt az indirekt feltételezésünk, ezért ha n benne van Q-ban, akkor az ő rákövetkezője is szükségképpen Q-ban kell legyen.
Ezzel kész a teljes indukció, hiszen láttuk, hogy a 0 benne van Q-ban, így az iménti gondolatmenet alapján az ő rákövetkezője is, majd annak a rákövetkezője, és így tovább a végtelenségig. A 11.1. Definíció 4. pontja alapján így minden természetes számot lefedünk, azaz Q=\N. Ekkor P csak az üres halmaz lehet, azaz valóban nem létezik olyan nemüres részhalmaza \N-nek, amelynek nincs minimuma – épp ahogyan a tétel állítja.
∎