1.2 Cardinaux et entiers naturels

1.2.1 Notion de cardinal

Définition 1.2.1 On dit que deux ensembles E et F ont même cardinal s’il existe une bijection de E sur F. On notera \mathop{Card}E ou encore |E| le cardinal d’un ensemble E.

Remarque 1.2.1 La relation il existe une bijection de E sur F est bien entendu une relation d’équivalence ; les cardinaux sont en quelque sorte les classes d’équivalence pour cette relation (pas tout à fait puisque l’ensemble de tous les ensembles n’existe pas).

Définition 1.2.2 On définit alors des opérations sur les cardinaux en posant

\begin{eqnarray*} \mathop{Card}A +\mathop{ Card}B& =& \mathop{Card}A ×\{0\} ∪ B ×\{1\}%& \\ \mathop{Card}A.\mathop{Card}B& =& \mathop{Card}A × B %& \\ \end{eqnarray*}

Remarque 1.2.2 Cette définition est justifiée par le fait que si on a \mathop{Card}A =\mathop{ Card}A' et \mathop{Card}B =\mathop{ Card}B', on a aussi

\mathop{Card}A ×\{0\} ∪ B ×\{1\} =\mathop{ Card}A' ×\{0\} ∪ B' ×\{1\}

et \mathop{Card}A × B =\mathop{ Card}A' × B', comme on le vérifie facilement en construisant les bijections appropriées.

Définition 1.2.3 On pose \mathop{Card}A ≤\mathop{ Card}B s’il existe une injection de A dans B.

On admettra que c’est une relation d’ordre total sur les cardinaux ; les seuls points non évidents sont l’antisymétrie et la totalité : l’antisymétrie constitue le théorème de Cantor-Bernstein qui dit que s’il existe une injection de A dans B et une injection de B dans A, alors il existe une bijection de A sur B ; la totalité résulte assez facilement de l’axiome de Zorn.

1.2.2 Les entiers naturels

On dira qu’un ensemble A est fini si \mathop{Card}A <\mathop{ Card}A + 1 (c’est équivalent à : il n’existe pas de bijection de A sur une partie stricte de A). L’ensemble des cardinaux finis forme alors un ensemble totalement ordonné appelé ensemble des entiers naturels et noté . Il vérifie les propriétés suivantes qui le caractérisent à un isomorphime près d’ensembles ordonnés

Axiome 1.2.1 (de Peano) est un ensemble infini où toute partie non vide a un plus petit élément et où toute partie non vide majorée a un plus grand élément

On en déduit immédiatement l’existence d’un successeur de tout élément a de et on montre en théorie des cardinaux que ce n’est autre que a + 1.

L’existence d’un plus petit élément pour toute partie non vide conduit immédiatement aux deux résultats suivants :

Théorème 1.2.1 (Principe de récurrence forte) Soit P(n) une propriété qui peut être vraie ou fausse pour tout entier naturel n. On suppose que P({n}_{0}) est vraie et que si P(n) est vraie, alors P(n + 1) est vraie. Alors P(n) est vraie pour tout n ≥ {n}_{0}.

Démonstration Soit en effet X l’ensemble des n ≥ {n}_{0} tels que P(n) soit fausse et supposons que X est non vide ; alors il admet un plus petit élément {n}_{1} ∈X. Comme {n}_{0}\mathrel{∉}X, on a {n}_{1} > {n}_{0} ; mais alors {n}_{1} − 1\mathrel{∉}X et {n}_{1} − 1 ≥ {n}_{0} ; donc P({n}_{1} − 1) est vraie, et il en est de même de P(({n}_{1} − 1) + 1) = P({n}_{1}), soit {n}_{1}\mathrel{∉}X. C’est absurde. Donc X = ∅, et par conséquent, P(n) est vraie pour tout n ≥ {n}_{0}.

Théorème 1.2.2 (Principe de récurrence faible) On suppose que P({n}_{0}) est vraie et que si P({n}_{0} + 1),P({n}_{0} + 2),\mathop{\mathop{…}},P(n) sont vraies, alors P(n + 1) est vraie. Alors P(n) est vraie pour tout n ≥ {n}_{0}.

Démonstration Soit en effet X l’ensemble des n ≥ {n}_{0} tels que P(n) soit fausse et supposons que X est non vide ; alors il admet un plus petit élément {n}_{1} ∈X. Comme {n}_{0}\mathrel{∉}X, on a {n}_{1} > {n}_{0} ; mais alors {n}_{0},\mathop{\mathop{…}},{n}_{1} − 1\mathrel{∉}X et donc P({n}_{0}),\mathop{\mathop{…}},P({n}_{1} − 1) sont vraies ; il en est donc de même de P({n}_{1}), soit {n}_{1}\mathrel{∉}X. C’est absurde. Donc X = ∅, et par conséquent, P(n) est vraie pour tout n ≥ {n}_{0}.