Tegyük fel indirekt, hogy P egy olyan galád részhalmaza \N-nek, amelynek nincs minimuma. Jelöljük ezen kívül Q-val \N-nek azt a részhalmazát, amely minden olyan természetes számot tartalmaz, amely kisebb P bármely eleménél. Azaz egyrészt a Q halmaz minden q elemére teljesül, hogy bármely 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. 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ó, ami a 12.13. Definíció alapján lehetetlen. A következő tehát a szituáció:

Azt kell megmutatnunk, hogy valójában minden természetes szám Q-ba tartozik, azaz Q=\N, hiszen ebből következne, hogy 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 a rendezési reláció trichotómiája miatt (lásd a 12.20. Tételt) szükségképpen teljesülne a p\leq 0 reláció. Ez a 12.13. Definíció miatt azt jelentené, hogy létezik olyan k természetes szám, amelyre p+k=0. A 12.17. 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.

Azt kaptuk tehát, hogy ha a 0 nem lenne benne Q-ban, akkor szükségképpen benne kellene lennie 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. Tehát hibás volt az indirekt feltételezésünk, így a 0-nak 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 (az előbb láttuk, hogy a 0 például ilyen). Azt szeretnénk megmutatni, hogy ekkor s(n) (azaz n 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. Ez egyrészt azt jelentené, hogy létezne olyan p-vel jelölt elem a P halmazban, 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ó. Azaz összefoglalva:

n\lt p\leq s(n)

Egyrészt a baloldali \lt reláció a 12.13. Definíció miatt azt jelenti, hogy n+k_1=p teljesül valamilyen k_1\neq 0 természetes számra. Másrészt a Peano-összeadás 11.4. Definíciója miatt a jobboldali kifejezés így írható át: s(n)=s(n+0)=n+s(0). Ezt kapjuk tehát:

\underbrace{n+k_1}_{=p} \leq n+s(0)

Ez ismét a 12.13. Definíció miatt azt jelenti, hogy létezik olyan k_2 természetes szám, amelyre teljesül az alábbi egyenlet:

\underbrace{n+k_1}_{=p} + k_2 = n+s(0)

A 12.16. Lemma alapján mindkét oldalt egyszerűsíthetjük n-nel, így ezt kapjuk:

k_1+k_2=s(0)

Azonban tudjuk, hogy k_1\neq 0, így a Peano-axiómarendszer 11.1. Definíciójának 3. pontja alapján van olyan k_0 természetes szám, aminek k_1 a rákövetkezője, azaz s(k_0)=k_1. Így:

\underbrace{s(k_0)}_{=k_1} + k_2=s(k_0+k_2)=s(0)

A Peano-axiómarendszer 11.1. Definíciójának 2. pontja miatt ekkor k_0+k_2=0 adódik, amelyből a 12.17. Lemma alapján k_0=0 és k_2=0 következik. Így tehát k_1=s(k_0)=s(0). Azaz:

\overbrace{n+\underbrace{s(0)}_{=k_1}}^{=p}+\underbrace{0}_{=k_2}=n+s(0)=s(n)

És így:

p+0=p=s(n)

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 Peano-axiómarendszer 11.1. Definíció 4. pontja alapján így minden természetes számot lefedünk, azaz Q=\N. A bizonyítás elején azonban láttuk, hogy 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.