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.

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.

∎