Ensembles finis et principe des tiroirs

(i) Récurrence sur $n$. Il n'y a aucune application de $1 = \{0\}$ dans $0 = \varnothing$.

Supposons le résultat vrai pour $n$, et soit $f : n + 2 \to n + 1$ injective. Si $n$ n'est pas valeur de $f$ sur $n + 1$, la restriction de $f$ à $n + 1$ est une injection dans $n$.

Sinon, $f(k) = n$ pour un $k \leqslant n$, et l'on pose $g(j) = f(j)$ pour $j \leqslant n$, $j \neq k$, et $g(k) = f(n + 1)$ ; comme $f$ est injective, $f(n + 1) \neq f(k) = n$, et $g$ est une injection de $n + 1$ dans $n$. Les deux cas contredisent l'hypothèse.

Si $m > n$, alors $m = n + k$ avec $k \neq 0$ (Propriétés des opérations, (iii)), et $k = S(k')$ (Axiomes de Peano) ; ainsi $m = n + (1 + k') = (n + 1) + k'$ par (i) du même nœud, et $n + 1 \leqslant m$, donc $n + 1 \subset m$ (Bon ordre sur ℕ), et une injection de $m$ dans $n$ se restreindrait en une injection de $n + 1$ dans $n$.

(ii) Si $E$ est équipotent à $m$ et à $n$, alors $m$ et $n$ sont équipotents (Équipotence), et (i) interdit $m > n$ comme $n > m$.

(iii) Il suffit de traiter $E = n$, par récurrence sur $n$. Pour $n = 0$, $A = \varnothing$.

Soit $A \subset n + 1$. Si $n \notin A$, alors $A \subset n$, et par hypothèse $|A| \leqslant n < n + 1$.

Si $n \in A$, alors $A \setminus \{n\} \subset n$ a $k \leqslant n$ éléments, et l'on prolonge une bijection $k \to A \setminus \{n\}$ en envoyant $k$ sur $n$ : $|A| = k + 1 \leqslant n + 1$, avec égalité seulement si $k = n$, c'est-à-dire, par récurrence, si $A \setminus \{n\} = n$, soit $A = n + 1$.

(iv) Supposons d'abord $A \cap B = \varnothing$, et soient $f : m \to A$ et $g : l \to B$ des bijections, avec $m = |A|$ et $l = |B|$. Tout $k < m + l$ vérifie $k < m$ ou $m \leqslant k$, l'ordre étant total (Bon ordre sur ℕ) ; dans le second cas, $k = m + i$ pour un unique $i$, par le point (iii) du nœud Propriétés des opérations, et $i < l$, sans quoi le point (iv) du même nœud, avec la commutativité de (i), donnerait $m + l \leqslant m + i = k$. On pose $h(k) = f(k)$ dans le premier cas et $h(k) = g(i)$ dans le second. L'application $h : m + l \to A \cup B$ est surjective : tout élément de $A$ est un $f(k)$ avec $k < m \leqslant m + l$, et tout élément de $B$ un $g(i)$ avec $i < l$, image de $m + i$, qui vérifie $m + i < m + l$ par le même point (iv) ; elle est injective, puisque $f$ et $g$ le sont, que $A$ et $B$ sont disjoints, et que $m + i = m + i'$ entraîne $i = i'$. Donc $|A \cup B| = m + l$.

En général, $A \cup B$ est la réunion disjointe de $A$ et de $B \setminus A$, partie de $B$, finie avec $|B \setminus A| \leqslant |B|$ par (iii). Le cas disjoint donne $|A \cup B| = |A| + |B \setminus A|$, qui est au plus $|A| + |B|$ par le point (iv) de Propriétés des opérations.

(v) Tout entier $n$ est fini au sens de Tarski, par récurrence sur $n$ : $0 = \varnothing$ l'est, et si $n$ l'est, $S(n) = n \cup \{n\}$ l'est aussi (Ensembles finis, sans les entiers, (iii)). Si $f : n \to E$ est une bijection, chaque $x \in n$ a un unique $y \in E$ tel que $(x, y) \in f$, et $E$ est l'ensemble de ces $y$, puisque $f$ est surjective : il est fini au sens de Tarski par le point (iv) du même nœud.

Réciproquement, soit $E$ fini au sens de Tarski. Appliquons la récurrence sur les parties de $E$ (Ensembles finis, sans les entiers, (ii)) à la formule « $B$ est équipotent à un entier », de variable $B$. Elle est vraie pour $B = \varnothing$, équipotent à $0$. Supposons-la vraie pour $B \subset E$, et soit $x \in E \setminus B$ ; soit $g : n \to B$ une bijection. Comme $n \notin n$ (Pas de x ∈ x), l'ensemble $g \cup \{(n, x)\}$ est une application de $S(n) = n \cup \{n\}$ dans $B \cup \{x\}$, et c'est une bijection, puisque $x \notin B$. Comme $S(n) = n + 1$ (Addition, multiplication), la formule est vraie pour $B \cup \{x\}$, donc pour $E$.

Aucun choix n'intervient : la récurrence porte sur un énoncé d'existence, et chaque pas n'emploie qu'une bijection, dont l'existence est l'hypothèse du pas ; on ne choisit pas une bijection pour chaque partie de $E$.