2. Cardinaux – Ensembles infinis
Attention. Les égalités a + c = b + c ou ac = bc n’impliquent pas a = b, comme
le montrent les résultats ci-dessous.
Proposition 2.3. L’ensemble N × N est équipotent à N.
Démonstration. Pour tout n ∈ N, on pose u n = 1 + 2 + . . . + n. On considère
l’application f : N × N −→ N définie par f (x, y) = y + u x+y . Montrons que f est
bijective. L’application n → u n est strictement croissante. On en déduit que pour
tout élément a de N, il existe un unique entier p tel que u p a < u p+1 . Posons
y = a− u p : on a 0 y < u p+1 − u p = p +1. En posant x = p − y, on a f (x, y) = a,
ce qui prouve que f est surjective. Soient x et y des entiers, a = f (x, y), p l’unique
entier tel que u p a < u p+1 . On a u x+y a a+ x+1 = u x+y+1 , d’où p = x+ y.
Alors y = a − u p et x = p − y et f est injective.
On peut faire une autre démonstration, en utilisant l’ordre lexicogaphique sur
N 2 et la bijection « diagonale » (cf. [1]).
Théorème 2.2. Pour tout cardinal infini a, on a a 2 = a.
Démonstration. Soit E un ensemble de cardinal a. D’après la proposition (2.2), il
existe une partie F de E équipotente à N et, d’après la proposition (2.3), il existe
une application bijective f de F sur F × F . On considère l’ensemble des couples
(X, g), où X est une partie de E contenant F et g est une application bijective
de X sur X × X prolongeant f . Cet ensemble est non vide, car il contient (F, f ),
et est ordonné par la relation
[(X, g) (X
, g
)] ⇐⇒ [X ⊂ X
et g
est un prolongement de g].
C’est un ensemble inductif ; il existe donc, d’après le lemme de Zorn (théorème 1.1), un élément maximal (Y, h). Posons Card(Y ) = b.
Supposons que b soit strictement inférieur à a.
Puisque b = b 2 est infini, on a b 2b 3b b 2 = b. En effet, il existe une
application injective Y
Y Y→ Y × Y , d’où 2b b 2 et, de même, 2b 3b
b 3 = b 2 = b. On a donc b = 2b et b = 3b. L’hypothèse b < a entraîne que
Card(E \ Y ) > b, car sinon on aurait Card(E) 2b = b ce qui est impossible
(utiliser le fait que E = Y
(E \ Y ), d’où Card(E) = Card(Y ) + Card(E \ Y )).
Il existe donc une partie Z ⊂ (E \ Y ) équipotente à Y . Posons T = Y ∪ Z. On a
T × T = (Y × Y ) ∪ (Y × Z) ∪ (Z × Y ) ∪ (Z × Z).
445
Attention. Les égalités a + c = b + c ou ac = bc n’impliquent pas a = b, comme
le montrent les résultats ci-dessous.
Proposition 2.3. L’ensemble N × N est équipotent à N.
Démonstration. Pour tout n ∈ N, on pose u n = 1 + 2 + . . . + n. On considère
l’application f : N × N −→ N définie par f (x, y) = y + u x+y . Montrons que f est
bijective. L’application n → u n est strictement croissante. On en déduit que pour
tout élément a de N, il existe un unique entier p tel que u p a < u p+1 . Posons
y = a− u p : on a 0 y < u p+1 − u p = p +1. En posant x = p − y, on a f (x, y) = a,
ce qui prouve que f est surjective. Soient x et y des entiers, a = f (x, y), p l’unique
entier tel que u p a < u p+1 . On a u x+y a a+ x+1 = u x+y+1 , d’où p = x+ y.
Alors y = a − u p et x = p − y et f est injective.
On peut faire une autre démonstration, en utilisant l’ordre lexicogaphique sur
N 2 et la bijection « diagonale » (cf. [1]).
Théorème 2.2. Pour tout cardinal infini a, on a a 2 = a.
Démonstration. Soit E un ensemble de cardinal a. D’après la proposition (2.2), il
existe une partie F de E équipotente à N et, d’après la proposition (2.3), il existe
une application bijective f de F sur F × F . On considère l’ensemble des couples
(X, g), où X est une partie de E contenant F et g est une application bijective
de X sur X × X prolongeant f . Cet ensemble est non vide, car il contient (F, f ),
et est ordonné par la relation
[(X, g) (X
, g
)] ⇐⇒ [X ⊂ X
et g
est un prolongement de g].
C’est un ensemble inductif ; il existe donc, d’après le lemme de Zorn (théorème 1.1), un élément maximal (Y, h). Posons Card(Y ) = b.
Supposons que b soit strictement inférieur à a.
Puisque b = b 2 est infini, on a b 2b 3b b 2 = b. En effet, il existe une
application injective Y
Y Y→ Y × Y , d’où 2b b 2 et, de même, 2b 3b
b 3 = b 2 = b. On a donc b = 2b et b = 3b. L’hypothèse b < a entraîne que
Card(E \ Y ) > b, car sinon on aurait Card(E) 2b = b ce qui est impossible
(utiliser le fait que E = Y
(E \ Y ), d’où Card(E) = Card(Y ) + Card(E \ Y )).
Il existe donc une partie Z ⊂ (E \ Y ) équipotente à Y . Posons T = Y ∪ Z. On a
T × T = (Y × Y ) ∪ (Y × Z) ∪ (Z × Y ) ∪ (Z × Z).
445