Natürliche Zahlen/Ordnung/Total/Aus Nachfolgerbeziehung/Fakt/Beweis

Beweis

Die Reflexivität und die Transitivität sind klar. Zum Beweis der Antisymmetrie sei ${}x\leq y$ und ${}y\leq x$, es gibt also endliche Nachfolgerketten ${}\alpha$ und ${}\beta$ (also endliche Strichketten ${}\prime \prime \prime \ldots \prime \prime \prime$) mit ${}y=x^{\alpha }$ und ${}x=y^{\beta }$. Damit ist ${}x^{\alpha \beta }=x$, wobei ${}\gamma =\alpha \beta$ einfach die Hintereinanderkettung der Strichketten bedeutet. Wir haben zu zeigen, dass ${}\gamma$ die leere Strichkette ist (dann ist auch ${}\alpha$ die leere Strichkette und somit ${}x=y$.). Wir zeigen durch Induktion, dass aus ${}x^{\gamma }=x$ folgt, dass ${}\gamma =\emptyset$ ist. Bei ${}x=0$ wäre andernfalls ${}x=x^{\gamma }=(x^{\delta })^{\prime }$, wobei ${}\delta$ aus ${}\gamma$ dadurch entsteht, dass man einen Strich weglässt, was man kann, sobald es mindestens einen Strich in ${}\gamma$ gibt. Doch dann wäre ${}0$ ein Nachfolger. Es sei die Aussage nun für ${}x$ bewiesen und sei ${}x^{\prime }=(x^{\prime })^{\gamma }$. Dies kann man schreiben als ${}x^{\prime }=x^{\gamma \prime }=(x^{\gamma })^{\prime }$. Wegen der Injektivität der Nachfolgerabbildung folgt ${}x=x^{\gamma }$, also ${}\gamma =\emptyset$ nach Induktionsvoraussetzung.

Wir beweisen nun, dass die Ordnung total ist, und zwar beweisen wir durch Induktion über ${}n$ die Aussage, dass für jedes ${}x\in \mathbb {N}$ die Aussage ${}x\geq n$ oder ${}n\geq x$ wahr ist. Bei ${}n=0$ gilt die erste Alternative für jedes ${}x$ und damit die Gesamtaussage. Es sei nun die Aussage für ${}n$ schon bewiesen und betrachten wir ${}n^{\prime }$ und ein beliebiges ${}x$. Nach Induktionsvoraussetzung ist ${}x\geq n$ oder ${}n\geq x$. Bei ${}n\geq x$ ist auch ${}n^{\prime }\geq n\geq x$ und also ${}n^{\prime }\geq x$ wegen der Transitivität. Es sei also ${}n\leq x$. Bei ${}n=x$ sind wir wieder im ersten Fall, sodass wir also ${}n<x$ annehmen dürfen. Daher ist ${}x=n^{\alpha }$ mit einer nichtleeren Strichkette ${}\alpha$, und damit ist ${}x$ auch ein sukzessiver Nachfolger von ${}n^{\prime }$, also ${}x\geq n^{\prime }$.

Zur bewiesenen Aussage