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. Es 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. Es 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. Es sei also
. Bei
sind wir wieder im ersten Fall, sodass wir also
annehmen dürfen. Daher ist
mit einer nichtleeren Strichkette
, und damit ist
auch ein sukzessiver Nachfolger von
, also
.