L'appartenance est un bon ordre sur ω

Transitivité et irréflexivité. Si $k \in m$ et $m \in n$, alors $k \in n$ car $n$ est transitif. Et $n \notin n$ par fondation.

Deux lemmes. (a) Pour tout $n$, on a $0 = n$ ou $0 \in n$ : c'est vrai pour $0$, et si c'est vrai pour $n$, alors $0 \in S(n)$ puisque $n \in S(n)$ et $n \subset S(n)$.

(b) Si $m \in n$, alors $S(m) = n$ ou $S(m) \in n$ : par récurrence sur $n$, le cas $n = 0$ est vide ; si $m \in S(n)$, ou bien $m \in n$ et l'hypothèse donne $S(m) \in S(n)$, ou bien $m = n$ et $S(m) = S(n)$.

Trichotomie. Montrons par récurrence sur $m$ que, pour tout $n$, on a $m \in n$, $m = n$ ou $n \in m$. Pour $m = 0$, c'est le lemme (a). Supposons-le pour $m$, et soit $n$. Si $n \in m$ ou $n = m$, alors $n \in S(m)$. Si $m \in n$, le lemme (b) donne $S(m) = n$ ou $S(m) \in n$.

Bon ordre. Soit $A \subset \omega$ non vide. Par fondation, il existe $m \in A$ tel que $m \cap A = \varnothing$. Pour tout $a \in A$, on a $a \notin m$, donc $m = a$ ou $m \in a$ par trichotomie : $m$ est le plus petit élément de $A$.

Inclusion. Si $m \in n$, alors $m \subset n$ par transitivité, et $m \neq n$ car $n \notin n$. Réciproquement, si $m \subsetneq n$ et que l'on avait $n \in m$ ou $n = m$, on aurait $n \in n$ ou $m = n$.

Ordinal. Tout élément d'un entier est un entier (Entiers transitifs) : $\omega$ est transitif, et $\in$ y est un bon ordre strict par ce qui précède, donc $\omega$ est un ordinal. Pour la même raison, les éléments de $n$ sont exactement les entiers $m < n$.