Université Toulouse III Année 2022-2023

C-TD Ensemble 2 (Printemps) Feuille n◦ 1

Ensembles dénombrables

On rappelle qu’un ensemble E est fini s’il existe un entier n ∈ N tel que E est en bijection avec l’ensemble
J1, nK = {1, . . . , n}. L’entier n est alors appelé le cardinal de E. S’il existe une bijection d’un ensemble fini E
dans F, alors les deux ensembles ont le même cardinal.
On souhaite comparer des ensembles infinis. On dit que les ensemble E et F sont équipotents s’il existe une
bijection de E dans F.

1 Critère de dénombrabilité
Définition 1 (Ensemble dénombrable). Un ensemble est dénombrable s’il est fini ou s’il est en bijection avec N.
Exercice 1 - Premiers exemples d’ensembles dénombrables. Montrer que les ensembles suivants sont dénombrables
en exhibant une bijection avec N:

1. l’ensemble des entiers naturels non nuls noté N \ {0};

2. l’ensemble des entiers naturels pairs 2N;
3. l’ensemble des entiers naturels impairs 2N + 1;

4. l’ensemble des nombres entiers multiples de 3 noté 3N;

5. l’ensemble des entiers relatifs Z;
6. l’ensemble des couples d’entiers naturels noté N2 (on pourra considérer la fonction ( p, q) 7−→ 2 p (2q +
1) − 1 ou bien énumérer les cases d’une grille infinie).

Exercice 2 - Critères de dénombrabilité. Dans cet exercice, on cherche à déterminer des critères pour montrer
qu’un ensemble est dénombrable.

1. Montrer que si X ⊆ N alors X est dénombrable. On pourra considérer l’application suivante qui est
définie si X est infinie:

ϕ(0) = min{ x ∈ X } et ϕ(n + 1) = min{ x ∈ X : x > ϕ(n)} pour n ≥ 1.

2. Soit X un ensemble et f : X → N injective. Montrer que X est dénombrable.

3. Utiliser ce critère pour montrer que l’ensemble Nk pour k ∈ N r {0} est dénombrable.
4. Soit X un ensemble et f : N → X surjective. Montrer que X est dénombrable. On pourra montrer que
g : X → N définie par g( x ) = min{y ∈ N : f (y) = x } est injective.

5. Utiliser ce critère pour montrer que l’ensemble des nombres rationnels, noté Q, est dénombrable.
6. Soient ( Ai )i∈N une famille d’ensembles dénombrables indexés par N. Montrer que l’union
S
n ∈N An est
dénombrable.
7. Utiliser ce critère pour montrer que l’ensemble des parties finies de N est dénombrable.

Nous avons donc les critères suivants pour montrer qu’un ensemble est démombrable.
Théorème 1
Soit X un ensemble, les trois propositions suivantes sont équivalentes:
 • X est dénombrable;
• il existe une surjection de N dans X;
• il existe une injection de X dans N.

Par ailleurs, on peut énoncer les résultats suivants

Proposition 2
Les ensembles suivants sont dénombrables: Nk avec k ∈ N, Q l’ensemble des rationnels et l’ensemble des
parties finies de N.

Proposition 3
Soient A1 , A2 , . . . , Ak des ensembles dénombrables, l’ensemble A1 × A2 × · · · × Ak est dénombrable.

Proposition 4
Soient ( Ai )i∈N une famille d’ensembles dénombrables indexés par N, l’ensemble
S
n ∈N An est dénombrable.

2 Ensembles non dénombrables

Etant donné un ensemble E, on note P ( E) l’ensemble des parties de E.
Théorème 5 (Cantor 1845-1918)
Soit E un ensemble, il n’existe pas d’application bijective de E dans P ( E).

Exercice 3 - E et P ( E) ne sont pas en bijection. Soient E un ensemble non vide et f : E → P ( E) une applica-
tion.
1. On définit l’ensemble de Cantor associé à f par

A = {x ∈ E : x ∈
/ f ( x )}.

Soit x ∈ E, montrer que x ∈ f ( x ) ∪ A et que x ∈

/ f ( x ) ∩ A.
2. Montrer que l’application f ne peut pas être surjective.
3. En déduire que E et P ( E) ne sont pas équipotents.
4. Donner un exemple d’ensemble qui n’est pas dénombrable.

Théorème 6 (Cantor)
L’ensemble [0, 1[ n’est pas dénombrable.

Exercice 4. Soit f : N −→ R une application. On définit (un )n∈N∗ la suite à valeur dans {0, 1, . . . , 9} tel que
un est la nème décimale de f (n).
On définit le nombre réel r = 0, v1 v2 v3 . . . vn . . . tels que pour tout n ∈ N∗ on a vn = 1 si un = 0 et vn = 0 si
un 6= 0.

1. Montrer que r n’a pas d’antécédent par f .

2. En déduire que [0, 1[ n’est pas dénombrable.

Exercice 5 - Existence de nombres transcendants. √ Un nombre (réel ou complexe) est algébrique s’il est racine
d’un polynôme à coefficients entiers. Par exemple 2 est algébrique car racine de X 2 − 2, i est algébrique car
racine de X 2 + 1...
Un nombre est transcendant s’il n’est pas algébrique. Le but de l’exercice est de montrer l’existence de nombre
transcendant. En général il est difficile de montrer qu’un nombre est transcendant.
 1. On note Zn [ X ] ⊆ Z[ X ] l’ensemble des polynômes entiers de degré inférieur ou égal à n. Montrer que
Zn [ X ] est dénombrable.
2. Montrer que l’ensemble des nombres algébriques est dénombrable.
3. En déduire l’existence de nombres transcendants.

Remarque: On peut montrer par des méthodes avancées que π et e sont transcendants.

3 Théorème de Cantor-Schröder-Bernstein
Pour montrer que deux ensembles E et F sont équipotents, il est souvent difficile d’exhiber une bijection. Le
théorème suivant dit qu’il suffit d’exhiber une injection de E dans F et une autre de F dans E.
Théorème 7 (Théorème de Cantor-Schröder-Bernstein)
S’il existe une application injective de E vers F et une application injective de F vers E, alors il existe une
application bijective de E vers F.

Exercice 6 - Exemples d’ensembles non dénombrables. Le théorème suivant est très utile pour montrer que
deux ensembles sont équipotents.
En utilisant ce théorème, montrer que [0, 1], ]0, 1[, ]0, 1[2 , R et P (N) sont équipotents deux à deux.
Exercice 7 - (Preuve du théorème de Cantor-Schröder-Bernstein). Le but de cet exercice est de démontrer
le théorème de Cantor et Bernstein. On se donne donc deux ensembles E et F et deux applications injectives
i : E −→ F et j : F −→ E. On note par ailleurs

A0 = E \ j ( F ), A1 = j ◦ i ( A0 ), ..., A n +1 = j ◦ i ( A n )

et [
B= An , C = E \ B.
n ≥0

1. Construction de l’application.

(a) Démontrer que pour tout x ∈ C, il existe un unique z ∈ F tel que x = j(z). On notera cet élément
ϕ ( x ).
(b) Pour x ∈ B, on note ϕ( x ) = i ( x ). Démontrer que l’on a ainsi bien défini une application ϕ : E −→ F.
2. Un exemple. On considère E = N, F = {n ∈ N : n ≥ 2} et

i: E −→ F j: F −→ E
n 7−→ n + 4 n 7−→ n

Déterminer les ensembles An , B, C et l’application ϕ.

3. Injectivité de ϕ.
(a) Démontrer que les restrictions de ϕ à B et à C sont injectives.
(b) Considérons maintenant x ∈ C et y ∈ B tels que ϕ( x ) = ϕ(y). Démontrer que x = j ◦ i (y).
(c) En déduire que ϕ est injective.

4. Surjectivité de ϕ. Démontrer la surjectivité de ϕ.

5. Conclusion. En déduire le théorème de Cantor-Schröder-Bernstein
 Université Toulouse III Année 2022-2023
C-TD Ensemble 2 (Printemps) Feuille n◦ 1

Ensembles dénombrables (Méthodes)

Z Comment montrer qu’un ensemble est dénombrable?

Soit X un ensemble, il y a essentiellement quatre méthodes pour montrer que X est dénombrable:

• on montre qu’il est fini ou on exhibe une bijection entre X et N;

• on exhibe une injection de X dans N;
• on exhibe une surjection de N dans X;
• on exprime X comme un produit fini d’ensembles dénombrables ou comme union dénombrable d’ensembles
dénombrables.

Z Comment montrer qu’un ensemble n’est pas dénombrable?

On montre que cet ensemble est en bijection avec un ensemble non-dénombrable.

Z Comment montrer que deux ensembles sont équipotents?

Pour montrer que deux ensembles A et B sont équipotent (ou on même cardinal), il y a essentiellement deux
méthodes:

• on exhibe une bijection de A dans B;

• on exhibe une injection de A dans B et une injection de B dans A;