2019/20 - M51 - Groupes, anneaux, corps

——
TD1 - Ensembles, relations, dénombrabilité

Ensembles et applications
Notation : étant donnés des ensembles E et F, on note P(E) l’ensemble des parties de E et F (E, F)
l’ensemble des applications de E vers F.

Cours.
Rappeler les définitions d’une application, de l’image d’une partie par une application, de l’image ré-
ciproque d’une partie par une application, de la (co)restriction d’une application.

Exercice 1.
Soit f : E → F une application. Soient A, B deux parties de E et C, D deux parties de F.
a. Montrer que A ⊂ f −1 ( f (A)) avec égalité lorsque f est injective.
b. Montrer que f ( f −1 (C)) ⊂ C avec égalité lorsque f est surjective.
c. Montrer que f (A ∪ B) = f (A) ∪ f (B).
d. Montrer que f (A ∩ B) ⊂ f (A) ∩ f (B) avec égalité lorsque f est injective.
e. Montrer que f −1 (C ∪ D) = f −1(C) ∪ f −1 (D).
f. Montrer que f −1 (C ∩ D) = f −1(C) ∩ f −1 (D).

Exercice 2.
Que dire de l’ensemble F (E, F) lorsque E = ∅ ou F = ∅ ?

Exercice 3.
Soit E un ensemble. La fonction caractéristique d’une partie A de E est l’application χA : E → {0, 1}
définie par χA (x) = 1 si x ∈ A et χA (x) = 0 si x < A.
Montrer que l’application χ : P(E) → F (E, {0, 1}), définie par A 7→ χA , est une bijection.

Exercice 4.
Soit E un ensemble. Montrer qu’il n’existe pas d’application surjective f : E → P(E).
Indication : considérer l’ensemble X = {x ∈ E | x < f (x)}.

Exercice 5.
On se propose de montrer le théorème de Cantor-Bernstein :
Soient E et F deux ensembles. S’il existe une injection de E vers F et une injection de F vers E, alors
il existe une bijection de E sur F.
a. Soit G : P(E) → P(E) une application croissante, c’est-à-dire telle que : A ⊂ B ⇒ G(A) ⊂ G(B).
Montrer que G admet un point fixe : il existe M ∈ P(E) tel que G(M) = M.
Indication : considérer M = ∪A∈S A où S = {A ∈ P(E) | A ⊂ G(A)}.
b. Soient f : E → F et g : F → E deux injections. Montrer que l’application G : P(E) → P(E), définie
par

G(A) = E \ g F \ f (A) ,
est croissante. Soit M un point fixe de G. Vérifier que g établie une bijection entre F \ f (M) et E \ M.
En déduire que l’application h : E → F définie par

f (x) 

 si x ∈ M,
h(x) =  |E\M −1
g

|F\ f (M)(x) si x ∈ E \ M,
est bijective.
Relations d’équivalences
Cours.
Rappeler les définitions d’une relation et de son graphe, d’une relation d’équivalence, d’une partition,
de la relation d’équivalence associée à une application, de la décomposition canonique d’une applica-
tion.

Exercice 6.
La relation R = {(1, 1), (2, 3), (3, 2)} sur {1, 2, 3} est-elle réflexive, symétrique, transitive ?

Exercice 7.
Reconnaître la relation sur un ensemble E dont le graphe est la diagonale ∆E = {(x, x) | x ∈ E} ⊂ E × E.

Exercice 8.
Soit R la relation sur R définie par xRy si x2 − y2 = x − y.
a. Montrer que R est une relation d’équivalence.
b. Déterminer le graphe de la relation R.
c. Décrire les classes d’équivalence des nombres 0, 1 et 1/2.

Exercice 9.
Soit R la relation sur N2 définie par (x, y)R(x′ , y′ ) si x + y′ = x′ + y.
a. Montrer que R est une relation d’équivalence.
b. Déterminer une bijection entre N2 /R et Z.

Exercice 10.
Soit R la relation sur Z × N∗ définie par (p, q)R(p′, q′ ) si pq′ = p′ q.
a. Montrer que R est une relation d’équivalence.
b. Reconnaître l’ensemble quotient (Z × N∗ )/R.

Exercice 11.
Soient A une partie d’une ensemble E et R la relation sur P(E) définie par XRY si X ∩ A = Y ∩ A.
a. Montrer que R est une relation d’équivalence.
b. Décrire la classe d’équivalence de ∅ et celle de E.
c. Déterminer une bijection entre P(E)/R et P(A).

Exercice 12.
Soit R une relation d’équivalence sur un ensemble E.
a. Montrer l’ensemble quotient E/R forme une partition de E.
b. Montrer que si E est un ensemble fini, alors
X
card(E) = card(C).
C∈E/R

Exercice 13.
Déterminer la décomposition canonique de l’application f : R → C définie par f (x) = eix pour x ∈ R.

Exercice 14.
Soit n ≥ 1 un entier. Déterminer la décomposition canonique de l’application g : Z → N qui à tout
k ∈ Z associe le reste de la division euclidienne de k par n.

Exercice 15.
Montrer qu’une application de R dans R périodique de période 1 induit une application de R/Z dans R.
Dénombrabilité
Cours.
Rappeler les définitions d’un ensemble dénombrable, d’un ensemble au plus dénombrable.

Exercice 16.
Montrer que si E est un ensemble infini, alors il existe une injection de N dans E.

Exercice 17.
Soit f : N × N → N∗ l’application définie par f (k, n) = (2k + 1)2n pour tout (k, n) ∈ N × N.
a. Montrer que f est bijective.
b. En déduire que N × N est dénombrable.
c. Montrer que pour tout entier m ≥ 1, les ensembles Nm et Zm sont dénombrables.

Exercice 18.
Montrer que l’ensemble Q des nombres rationnels est dénombrable.

Exercice 19.
a. Montrer que P(N) n’est pas dénombrable.
Indication : utiliser l’exercice 4.
b. Montrer que l’ensemble Pf (N) des parties finies de N est dénombrable.
Indication : considérer, pour n ∈ N, l’ensemble Pn (N) des parties de N de cardinal n.

Exercice 20.
Montrer que l’ensemble F (N, N) des applications de N dans N n’est pas dénombrable.
Indication : étant donné une suite ( fn : N → N)n∈N , considérer l’application f : N → N définie par
f (n) = fn (n) + 1 pour n ∈ N.

Exercice 21.
Le but de l’exercice est de montrer qu’il existe une bijection entre P(N) et R.
a. Montrer que toute partie de R contenant un intervalle ouvert non vide est en bijection avec R.
b. Montrer que l’application φ : P(N) → R, définie par
∞
X χA (n)
φ(A) =
n=0
3n
où χA est la fonction caractéristique de A (voir l’exercice 3), est bien définie et injective.
c. Le développement dyadique (xn )n∈N d’un nombre réel x ∈ [0, 1[ est défini récursivement par
n
  
 n+1  X x k

x0 = [2x] et xn+1 = 2 2x − k 
 ,
k=0
2
où [u] désigne la partie entière d’un réel u. Montrer que c’est une suite de 0 et de 1 telle que
∞
X xn
x= .
n=0
2n+1
En déduire que l’application [0, 1[→ P(N), définie par x 7→ {n ∈ N | xn = 1}, est injective.
d. Conclure.
e. Application : en déduire que R n’est pas dénombrable.