Bizonyítás

Indirekt bizonyítást fogunk alkalmazni, azaz nem közvetlenül a tételt bizonyítjuk, hanem megmutatjuk, miért nem lehet hamis. Tegyük fel ezért, hogy nem igaz a tétel, vagyis hogy az $\N$ halmazban léteznek olyan galád $a$ és $b$ természetes számok, amelyek között egyik irányban sem áll fenn a $\leq$ reláció, azaz $a\nleq b$ és $b\nleq a$.

Ebből az következik, hogy egyikük sem lehet $0$, hiszen ha például $a=0$ lenne, akkor a 12.15. Definíció miatt $\underbrace{0}_{=a}\leq b$ teljesülne, ugyanis létezne olyan természetes szám, amelyet $a=0$-hoz adva $b$-t kapnánk, nevezetesen $b$, hiszen $0+b=b$. Ha meg $b=0$ lenne, akkor pedig ugyanezen okok miatt $\underbrace{0}_{=b}\leq a$ teljesülne, ugyanis $0+a=a$.

Ha viszont egyikük sem $0$, akkor a 11.1. Definíció 3. pontja miatt mindkettőhöz létezik egy-egy olyan természetes szám, amelyeknek épp ők a rákövetkezői. Jelöljük ezt a két természetes számot $a_1$-gyel és $b_1$-gyel, amelyekre tehát teljesül, hogy $s(a_1)=a$ és $s(b_1)=b$.

Mármost ha $a$ és $b$ között nem teljesül a $\leq$ reláció egyik irányban sem, akkor a 12.21. Lemma miatt utóbbiak között sem fog – azaz $a_1\nleq b_1$ és $b_1\nleq a_1$.

De ekkor ugyanezen gondolatmenet alapján léteznie kell egy $a_2$ és egy $b_2$ természetes számnak is, amelyek rákövetkezői épp az $a_1$ és $b_1$ természetes számok, és amelyek közül szintén egyik sem $0$. És így tovább, ezt a gondolatmenetet a végtelenségig folytathatjuk, mindig találunk újabb és újabb nem $0$ természetes számokat, amelyek rákövetkezői épp az előző lépésben megtalált természetes számok.

Kapunk tehát két végtelen sorozatot, amely sorozatokban sehol nem szerepel a $0$, és a 12.4. ábrán látható rákövetkezőségi viszonyok állnak fenn közöttük:

Ez viszont lehetetlen, hiszen a 11.1. Definíció 4. pontja kimondja, hogy a $0$-ból kiindulva a rákövetkezési függvény mentén az összes természetes számhoz el kell jutnunk előbb-utóbb. Márpedig egy ilyen útvonalon az ábrán lévő két sorozat tagjai biztosan nem lennének benne.

Ebből viszont az következik, hogy az $a\leq b$ és a $b\leq a$ relációk közül legalább az egyiknek teljesülnie kell tetszőleges $a$ és $b$ esetén, máskülönben ellentmondásba kerülnénk a 4. Peano-axiómával.

∎