DL 2
Ensembles équipotents
Définition$:: Deux ensembles E et F sont dits équipotents s’il existe une bijection de E dans F .
Théorème de Cantor-Bernstein : Soient A et B deux ensembles. Si l’on suppose qu’il existe deux
applications injectives f : E −→ F et g : F −→ E, alors il existe une bijection h : E −→ F.
Partie 1 : Théorème de Cantor-Bernstein
Le but de cette partie le théorème de Cantor-Bernstein.
On introduit d’abord quelques définitions :
— Un élément x ∈ E (resp. y ∈ F ) a un parent s’il a un antécédent par g( resp. par f ). Un tel
antécédent est nécessairement unique : on l’appellera le parent de x (resp. de y ).
— Pour tout n ∈ N, on définit récursivement le nombre d’ancêtres d’un élément de E ou de F :
— Les éléments ayant 0 ancêtre sont ceux n’ayant pas de parent.
— Pour tout n ∈ N∗ , les éléments ayant (exactement) n ancêtres sont ceux ayant un parent, et dont
le parent a n − 1 ancêtres.
— Les éléments restants ont une infinité d’ancêtres.
— Pour tout n ∈ N, on note En (resp. Fn ) les éléments de E (resp. de F ) ayant n ancêtres.
— On note E∞ (resp. F∞ ) les éléments de E (resp. de F ) ayant une infinité d’ancêtres.
1. Montrer que
[
E= En
n∈N∪{∞}
et que cette union est disjointe. On admettra le résultat analogue pour F .
2. Soit n ∈ N. Montrer que f (En ) = Fn+1 et que g (Fn ) = En+1 . En déduire que
f|En : En → Fn+1 et g|Fn : Fn → En+1
sont des bijections.
3. Montrer que f (E∞ ) = F∞ et en déduire que f|E∞ : E∞ → F∞ est une bijection.
4. Conclure.
Partie 2 : Ensembles infinis dénombrables
Définition : Un ensemble est infini dénombrable s’il est en bijection avec N.
Dans cette partie, on donne des exemples élémentaires de cette notion.
1. Montrer que Z est infini dénombrable.
2. En utilisant l’application ψ : N2 → N, définie par ψ(n, p) = 2n (2p + 1) − 1, montrer que N2 est infini
dénombrable.
3. En déduire que, pour tout k ∈ N∗ , Nk est infini dénombrable.
4. On admet les propriétés élémentaires de N. Montrer que toute partie infinie de N est infinie
dénombrable.
5. En déduire qu’une partie infinie d’un ensemble infini dénombrable est infinie dénombrable.
6. Montrer que Q est infini dénombrable.
1
Partie 3 :
Le but de cette partie est de montrer que R et P(N) sont équipotents.
1. Construction d’une injection de P(N) dans R.
(a) Soit A une partie de N. On définit la suite (Sn )n∈N par
n
1A (k)3−k
X
Sn =
k=0
où 1A (k) = 1 si k ∈ A, 0 sinon. Montrer que (Sn ) est une suite croissante majorée.
(b) En déduire qu’elle admet une limite finie.
X
On notera 3−n cette limite dans la suite.
n∈A
(c) On définit l’application ϕ : P(N) → R, par
X
ϕ(A) = 3−n
n∈A
Montrer que ϕ est une injection.
2. Construction d’une injection de ]10−1 , 1[ dans P(N).
Soit x un réel dans ]10−1 , 1[.
(a) Pour tout n ≥ 1, on pose xn = ⌊10n x⌋, où ⌊·⌋ désigne la partie entière. Ainsi, xn est l’unique
entier naturel tel que
xn ≤ 10n x < xn + 1
Montrer que pour tout n ≥ 1, xn ∈ [10n−1 , 10n [.
xn
(b) Montrer que la suite 10 n n∈N∗ converge vers x.
(c) On définit ψ :]10 , 1[→ P(N) par
−1
∀x ∈]10−1 , 1 [, ψ(x) = {xn , n ∈ N∗ } .
Montrer que ψ est une injection.
3. Montrer qu’il existe une bijection de ]10−1 , 1[ dans R.
4. Conclure, en utilisant le théorème de Cantor-Bernstein.
5. En déduire que R n’est pas infini dénombrable.