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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

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

Wir beweisen nun, dass die Ordnung total ist, und zwar beweisen wir durch Induktion über die Aussage, dass für jedes die Aussage oder wahr ist. Bei gilt die erste Alternative für jedes und damit die Gesamtaussage. Sei nun die Aussage für schon bewiesen und betrachten wir und ein beliebiges . Nach Induktionsvoraussetzung ist oder . Bei ist auch und also wegen der Transitivität. Sei also . Bei sind wir wieder im ersten Fall, so dass wir also annehmen dürfen. Daher ist mit einer nichtleeren Strichkette , und damit ist auch ein sukzessiver Nachfolger von , also .