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

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 ${}n$, wobei die zu beweisende Aussage die Form ${}A(n)=$ für jedes ${}k\in N$ mit ${}k\geq n$ und ${}n\geq k$ gilt ${}n=k$. Es sei ${}n=0$. Bei ${}k\neq 0$ ist ${}k\in N\setminus \{k\}$, und diese Menge haben wir im Beweis zu Fakt als induktiv abgeschlossen nachgewiesen. Daher ist ${}0\not \in N_{\geq k}$. Es sei nun angenommen, dass ${}A(n)$ schon bewiesen ist und betrachten wir ${}n'$. Es sei ${}k$ gegeben mit ${}k\geq n'$ und ${}n'\geq k$. Bei ${}k=0$ erhalten wir aus der ersten Bedingung einen Widerspruch, da ${}0\not \in N_{\geq n'}$ gilt. Also ist ${}k=\ell '$. Aufgrund von Fakt gilt dann ${}\ell \geq n$ und ${}n\geq \ell$. Die Induktionsvoraussetzung impliziert dann ${}n=\ell$ und damit ${}n'=\ell '=k$.

Wir beweisen nun, ebenfalls durch Induktion nach ${}n$, dass eine totale Ordnung vorliegt, wobei wir die Aussage ${}A(n)=$ für alle ${}k$ ist ${}k\geq n$ oder ${}n\geq k$ zugrunde legen. Bei ${}n=0$ erhalten wir wegen ${}k\in N_{\geq 0}=N$ sofort ${}k\geq 0$. Es sei also die Aussage für ${}n$ schon bewiesen und betrachten wir ${}n'$. Es sei ${}k$ gegeben. Bei ${}k=0$ ist ${}k\leq n'$. Andernfalls ist ${}k=\ell '$ und dann gilt nach Induktionsvoraussetzung ${}\ell \geq n$ oder ${}\ell \leq n$, was die Vergleichbarkeit von ${}k$ mit ${}n'$ impliziert.

Zur bewiesenen Aussage