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\ge n$ und $n\ge k$ gilt $n=k$. Es sei $n=0$. Bei $k\ne 0$ ist $k\in N\setminus \{k\}$, und diese Menge haben wir im Beweis zu Fakt als induktiv abgeschlossen nachgewiesen. Daher ist $0\in ̸N_{\ge k}$. Es sei nun angenommen, dass $A(n)$ schon bewiesen ist und betrachten wir $n^{\prime }$. Es sei $k$ gegeben mit $k\ge n^{\prime }$ und $n^{\prime }\ge k$. Bei $k=0$ erhalten wir aus der ersten Bedingung einen Widerspruch, da $0\in ̸N_{\ge n^{\prime }}$ gilt. Also ist $k={\ell }^{\prime }$. Aufgrund von Fakt gilt dann $\ell \ge n$ und $n\ge \ell$. Die Induktionsvoraussetzung impliziert dann $n=\ell$ und damit $n^{\prime }={\ell }^{\prime }=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\ge n$ oder $n\ge k$ zugrunde legen. Bei $n=0$ erhalten wir wegen $k\in N_{\ge 0}=N$ sofort $k\ge 0$. Es sei also die Aussage für $n$ schon bewiesen und betrachten wir $n^{\prime }$. Es sei $k$ gegeben. Bei $k=0$ ist $k\le n^{\prime }$. Andernfalls ist $k={\ell }^{\prime }$ und dann gilt nach Induktionsvoraussetzung $\ell \ge n$ oder $\ell \le n$, was die Vergleichbarkeit von $k$ mit $n^{\prime }$ impliziert.

Zur bewiesenen Aussage