Numérotation des nombres rationnels
Un ensemble E est dit dénombrable si et seulement si il existe une bijection entre l’ensemble des entiers
naturels et E . Cette bijection permet alors de numéroter les éléments de E .
Partie I
1. Montrer que les ensembles * et P = {2k / k ∈ } sont dénombrables.
2. Dans cette question, on désire établir que est dénombrable.
Pour cela on introduit l’application ϕ : → définie par :
ϕ (n ) = n 2 si n est pair et ϕ (n ) = − (n + 1) 2 si n est impair.
2.a Calculer ϕ (n ) pour n allant de 0 à 5.
2.b Montrer que l’application ϕ est bien définie.
2.c Etablir que ϕ est bijective.
3. Dans cette question, on désire établir que 2 est dénombrable.
Pour cela on introduit l’application ϕ : 2 → * définie par :
ϕ (p ,q ) = 2p (2q + 1)
3.a Montrer que ϕ est bien définie et qu’elle est injective.
3.b En observant, pour tout n ∈ * , l’existence d’une plus grande puissance de 2 divisant n , établir que ϕ
est surjective.
3.c Conclure que 2 est dénombrable et qu’il en est de même de 2 .
4. Dans cette question, on désire établir que est dénombrable.
4.a Exhiber une injection de dans .
4.b On appelle représentant irréductible d’un nombre rationnel r l’unique fraction irréductible p q égale à
r avec p ∈ et q ∈ * .
Observer que l’application ϕ : → × * qui à r ∈ associe le couple (p ,q ) ∈ × * avec p q le
représentant irréductible est injective. Est-elle surjective ?
4.c Former une injection de dans .
On peut alors conclure que est dénombrable à l’aide du théorème de Cantor-Bernstein dont la démonstration
est l’objet de la partie suivante.
Partie II
On veut démontrer le résultat suivant :
Etant donnés deux ensembles E et F , s’il existe une injection de E dans F et une injection de F dans
E alors il existe une bijection entre E et F .
Supposons que f : E → F et g : F → E soient deux applications injectives.
On forme h = g f : E → E et on note R = CE (Im g ) .
1. On forme P = {M ∈ P (E ) / R ⊂ M et h (M ) ⊂ M } .
1.a Observer que l’ensemble P est non vide.
1.b Soit M ∈ P . Montrer que h (R ) ⊂ h (M ) et que h (h (M )) ⊂ h (M ) .
En déduire que R ∪ h (M ) ∈ P .
2. On forme A = ∩ M . On remarque que A
M ∈P
est inclus dans tout ensemble M appartenant à P .
2.a Montrer que A ∈ P .
2.b En exploitant II.1.b, établir que A ⊂ R ∪ h (A) puis que A = R ∪ h (A) .
2.c Montrer que g −1 (A) = f (A) .
3. On pose A′ = f (A) , B = CE A et B ′ = g −1 (B ) .
On considère ensuite les applications f ′ : A → A′ et g ′ : B ′ → B induites par f et g .
3.a Observer que f ′ et g ′ sont bijectives.
3.b Montrer que B ′ = CF A′
4. On introduit enfin l’application ϕ : E → F définie par :
f ′(x ) si x ∈ A
ϕ (x ) = −1 .
g ′ (x ) sinon
Montrer que ϕ est bijective.