Natürliche Zahlen/Ordnung/Mengentheoretisch/Total/Fakt/Beweis

Aus Wikiversity
Beweis

Die Reflexivität und die Transitivität folgen aus der Charakterisierung in Fakt und aus den entsprechenden Eigenschaften der Inklusion.

Die Antisymmetrie beweisen wir durch Induktion über , wobei die zu beweisende Aussage die Form für jedes mit und gilt . Es sei . Bei ist , und diese Menge haben wir im Beweis zu Fakt als induktiv abgeschlossen nachgewiesen. Daher ist . Es sei nun angenommen, dass schon bewiesen ist und betrachten wir . Es sei gegeben mit und . Bei erhalten wir aus der ersten Bedingung einen Widerspruch, da gilt. Also ist . Aufgrund von Fakt gilt dann und . Die Induktionsvoraussetzung impliziert dann und damit .

Wir beweisen nun, ebenfalls durch Induktion nach , dass eine totale Ordnung vorliegt, wobei wir die Aussage für alle ist oder zugrunde legen. Bei erhalten wir wegen sofort . Es sei also die Aussage für schon bewiesen und betrachten wir . Es sei gegeben. Bei ist . Andernfalls ist und dann gilt nach Induktionsvoraussetzung oder , was die Vergleichbarkeit von mit impliziert.