Eléments de correction du TD 1

Exercice 1
On a X ∈ 2X ⇒ X ∈ 2Y donc X est une partie de Y c’est-à-dire X ⊂ Y , et de même Y ⊂ X donc X = Y .

Exercice 2
-) Si X = ∅, alors pour tout couple d’ensembles Z et Y , on a X ×Y = ∅ et X ×Z = ∅ donc X ×Y = X×Z
Y = Z.
-) Si X = ∅ fixons alors a ∈ X. Ainsi ∀y ∈ Y , on a :
(a, y) ∈ X × Y ⇒ (a, y) ∈ X × Z ⇒ y ∈ Z, donc Y ⊂ Z et de même Z ⊂ Y d’où Y = Z.

Exercice 3
On a X = (X \ Y ) ∪ (X ∩ Y ) et Y = (Y \ X) ∪ (X ∩ Y ) donc :
X ∪ Y = (X \ Y ) ∪ (Y \ X) ∪ (X ∩ Y ) et puisque X ∪ Y = [(X ∪ Y ) \ (X ∩ Y )] ∪ (X ∩ Y ), alors on en déduit
que :
(X \ Y ) ∪ (Y \ X) = (X ∪ Y ) \ (X ∩ Y ) .

Exercice 4
1) A est l’ensemble des puissances de 2 inférieures ou égales à 64.
B est l’ensemble des diviseurs positifs de 14.
2) A = {2, −7} .
B = {2} .

Exercice 5
a) Soit f ∈ F (N∗ , N∗ ) définie par : 
∀n ∈ N∗ , f (n) = 2n; clairement f n’est pas surjective et est injective.
 g (1) = 1
b) Soit g ∈ F (N∗ , N∗ ) définie par : ∀n ≥ 1, g (2n) = n . On a g (1) = 1 = g (3) donc g n’est pas injective,

∀n ≥ 1, g (2n + 1) = n
alors que clairement g est surjective.

Exercice 6
• Supposons f injective.
Si g1 = g2 , alors il existe z ∈ Z tel que g1 (z) = g2 (z) donc (f ◦ g1 ) (z) = (f ◦ g2 ) (z) car f est injective donc f ◦ g1
et f ◦ g2 sont des applications distinctes.
• Supposons que pour tout couple d’applications distinctes g1 et g2 , f ◦ g1 = f ◦ g2 . On raisonne par l’absurde en
supposant f non injective.
Puisque f n’est pas injective alors il existe (x, x′ ) ∈ X 2 tel que x = x′ et f (x) = f (x′ ). Choisissons alors Z = {1}
et définissons g1 et g2 applications de Z dans X par g1 (1) = x et g2 (1) = x′ . Alors g1 = g2 mais f ◦ g1 = f ◦ g2 ,
ce qui est contradictoire donc f est injective.

Exercice 7
Soit y ∈ ]−1, 1[; on a :
x x2
y = 1+|x| ⇔ y + |x| y = x ⇔ y = x − |x| y, donc puisque x et y ont même signe car xy = 1+|x| ≥ 0, on a :
y y
• y ≥ 0 ⇒ x ≥ 0 ⇒ y = x − xy = x (1 − y) ⇒ x = 1−y = 1−|y| , et :
y y
• y < 0 ⇒ x < 0, y = − |y| ⇒ y = x + xy = x (1 + y) ⇒ x = 1+y = 1−|y| ;
−1
ainsi f est bijective car l’équation y = f (x) a une unique solution et f :]−1, 1[→ R .
y
y →
1−|y|

Exercice 8
-) Montrons que f est bijective.
• Soit y ∈ F ; puisque f ◦ g ◦ f est bijective donc surjective alors il existe x ∈ E tel que :
y = (f ◦ g ◦ f) (x) = f [(g ◦ f) (x)], d’où puisque (g ◦ f ) (x) ∈ E alors on conclut que f est surjective.
• Soit (x, x′ ) ∈ E 2 tel que f (x) = f (x′ ) alors par composition par f ◦ g on a (f ◦ g ◦ f) (x) = (f ◦ g ◦ f ) (x′ )
donc x = x′ car f ◦ g ◦ f est bijective, ce qui assure que f est injective.
Ce qui précède prouve que f est bijective.
-) Montrons que g est bijective.
Soit f −1 la bijection réciproque de f ; on a g = f −1 ◦ (f ◦ g ◦ f ) ◦ f −1 donc puisque la composée de bijections est
une bijection alors g est bijective.

Exercice 9
Supposons l’existence d’une telle application. Puisque f est surjective, alors f ◦ f est aussi surjective donc il existe
x ∈ R tel que −1 = (f ◦ f) (x) = f (f (x)) = (f (x))2 , ce qui est absurde. Ainsi une telle application ne peut exister.

Exercice 10
1) a) On a : x ∈ A ⇒ f (x) ∈ f (A) ⇒ x ∈ f −1 (f (A)) par définition de f −1 (f (A)), ce qui assure que
A ⊂ f −1 (f (A)).
1) b) On a : x ∈ f −1 (f (A)) ⇒ f (x) ∈ f (A) donc il existe x′ ∈ A tel que f (x) = f (x′ ) ⇒ x = x′ car f est injec-
tive, et donc x ∈ A, ce qui assure que f −1 (f (A)) ⊂ A. Ainsi d’après 1) a) on conclut que A = f −1 (f (A)).
1) c) On sait que x est antécédent de f (x); supposons que f (x) ait un autre antécédent x′ , alors on a :
f (x′ ) = f (x) ⇒ x′ ∈ f −1 (f ({x})) = {x} ⇒ x′ = x, donc f (x) a un seul antécédent qui est x.
1) d) • Supposons f injective.
D’après 1) b) pour tout X ∈ 2E on a : f −1 (f (X)) = X.
• Supposons que pour tout X ∈ 2E , on a f −1 (f (X)) = X.
Soit x ∈ E; posons X = {x}, alors par hypothèse on a f −1 (f (X)) = X donc d’après 1) c) x est l’unique antécédent
de f (x) ce qui signifie que f est injective.    
2) a) On a : x ∈ f −1 (B) ⇒ f (x) ∈ B donc f f −1 (B) = f (x) , x ∈ f −1 (B) ⊂ B.  −1 
−1
2) b) Soit x ∈ B; comme f est surjective, alors il existe y ∈ E tel
 que x = f (y) ⇒ y ∈ f (B) ⇒ x ∈ f f (B)
donc B ⊂ f  f −1 (B) ,et d’après 2) a) on a finalement B = f f −1 (B) .
2) c) On a f f −1 ({y}) = {y} donc f −1 ({y}) = ∅, ce qui assure que y a au moins un antécédent.
2) d) • Supposons f surjective.  
D’après 2) b) pour tout Y ∈ 2F on a : f f −1(Y ) = Y .
• Supposons que pour tout Y ∈ 2F , on a f f −1 (Y ) = Y . 
Soit y ∈ F ; posons Y = {y}, alors par hypothèse on a f f −1 ({y}) = {y} donc d’après 2) c) y a au moins un an-
técédent, ce qui assure que f est surjective.

Exercice 11
D’après le cours on résout l’équation t2 − 33t + +200 = 0 dont les racines sont t1 = 8 et t2 = 25, ce qui entraîne que
n n
n est de la forme α8 + β25 . On détermine α et β en résolvant le système
u
α + β = u0 = 17
⇒ α = 16, β = 1.
8α + 25β = u1 = 153
n n
Ainsi un = 16 × 8 + 25 .

Exercice 12 n n
1) Pour n ∈ N soit Pn la proposition ≪ Sn = 2min(i,j) = 6 × 2n − 2n − 5 ≫.
i=0 j=0
• P0 est vraie car S0 = 20 = 1 et 6 × 20 − 2 × 0 − 5 = 1.
• Supposons Pn vraie à un rang n, n ≥ 0. On a :
n n n+1 n n+1    
Sn+1 = ( 2min(i,j) +2min(i,n+1) )+ 2min(n+1,j) = Sn + 2i + 2j = Sn + 2n+1 − 1 + 2n+2 − 1 ,
i=0 j=0 j=0 i=0 j=0
donc par hypothèse de récurrence :
Sn+1 = 6 × 2n − 2n − 5 + 3 × 2n+1 − 2 = (6 + 6) × 2n − 2 (n + 1) − 5 = 6 × 2n+1 − 2 (n + 1) − 5 donc Pn+1
n n
est vraie ce qui assure d’après le théorème de la récurrence que pour tout n ≥ 0, 2min(i,j) = 6 × 2n − 2n − 5.
i=0 j=0
n n
max(i,j) n+1
2) Pour n ∈ N soit Qn la proposition ≪ Tn = 2 = (2n − 1) 2 + 3 ≫.
i=0 j=0
• Q0 est vraie car T0 = 20 = 1 et (2 × 0 − 1) 21 + 3 = 1.
• Supposons Qn vraie à un rang n, n ≥ 0. On a :
n n n+1 n n+1
Tn+1 = ( 2max(i,j) + 2max(i,n+1) ) + 2max(n+1,j) = Tn + 2n+1 + 2n+1
i=0 j=0 j=0 i=0 j=0
= Tn + (n + 1) 2n+1 + (n + 2) 2n+1 ,
donc par hypothèse de récurrence :
Tn+1 = (2n − 1) 2n+1 + 3 + (2n + 3) 2n+1 = (4n + 2) 2n+1 + 3 = (2 (n + 1) − 1) 2n+1+1 + 3 donc Qn+1 est vraie
n n
ce qui assure d’après le théorème de la récurrence que pour tout n ≥ 0, 2max(i,j) = (2n − 1) 2n+1 + 3.
i=0 j=0

Exercice 13
Pour n ≥ 1 soit Pn la proposition :
2
≪ Si n1 , ..., nk sont des entiers non nuls tels que n1 + ... + nk = n alors n21 + ... + n2k ≤ (n − k + 1) + k − 1 ≫.
2
• P1 est vraie car k = 1 et donc n1 = 1 d’où n21 = 1 ≤ (1 − 1 + 1) + 1 − 1.
• Supposons Pn−1 vraie à un rang n − 1, n ≥ 2; soient n1 , ..., nk des entiers tous non nuls tels que n1 + ... + nk = n.
2
-) Si k = n alors n1 = ... = nn = 1 et donc n21 + ... + n2n = n ≤ (n − n + 1) + n − 1 , ce qui assure que Pn+1 est
vraie.
-) Si k < n alors un des ni est supérieur ou égal à 2; quitte à les renommer on peut supposer nk ≥ 2. On a
n − 1 = n1 + ... + nk−1 + (nk − 1) et puisque n1 ≥ 1, ..., nk−1 ≥ 1, (nk − 1) ≥ 1, alors par hypothèse de
récurrence on a :
2 2 2
n21 + ... + n2k−1 + (nk − 1) ≤ ((n − 1) − k + 1) + k − 1 = (n − k) + k − 1
⇒ (1) n21 + ... + n2k ≤ (n − k)2 + 2nk + k − 2.
Or pour 1 ≤ i ≤ k − 1 on a ni ≥ 1 donc on a n = n1 + ... + nk−1 + nk ≥ (k − 1) + nk ⇒ (2) nk ≤ n − k + 1.
Ainsi de (1) et de (2), on a :
n21 + ... + n2k ≤ (n − k)2 + 2 (n − k + 1) + k − 2 = (n − k)2 + 2 (n − k) + 1 + k − 1 = (n − k + 1)2 + k − 1, ce
qui assure que Pn+1 est vraie.
Ainsi d’après le théorème de la récurrence, Pn est vraie pour tout n ≥ 1.

Exercice 14
L’erreur vient du fait que lorsqu’on dit que d1 et dn−2 se coupent en un seul point, on suppose n − 2 > 1 donc n > 3,
or on n’a pas démontré que la proposition est vraie au rang 3.

Exercice 15
a) Il est clair que R ◦ R = R.
b) Soit (x, z) ∈ N2 tel que xR ◦ Rz, alors il existe y ∈ N tel que x ≤ y et y ≤ z donc x ≤ z soit xRz.
Soit (x, z) ∈ N2 tel que xRz, alors on a x ≤ z et puisque z ≤ z donc on a xR ◦ Rz.
Ainsi on conclut que R ◦ R = R.
c) Soit (x, z) ∈ R2 tel que xR ◦ Rz, alors il existe y ∈ R tel que x < y et y < z donc x < z soit xRz.
Soit (x, z) ∈ R2 tel que xRz, alors on a x < z donc il existe y ∈ R tel que x < y et y < z soit xR ◦ Rz.
Ainsi on conclut que R ◦ R = R.

Exercice 16
Il est immédiat qu’on a une relation d’équivalence. Les classes d’équivalence sont repérées par un couple de chiffres;
l’ensemble constitué par les classes d’équivalence est {(x, y) /x et y sont des entiers naturels compris entre 0 et 9}. Il
y a 100 classes d’équivalence.

Exercice 17
La matrice d’adjacence d’une relation réflexive a des 1 sur sa diagonale.
La matrice d’adjacence d’une relation symétrique est une matrice symétrique.

Exercice 18
Soient R et S deux relations d’équivalence sur un ensemble X. Montrons que R ◦ S n’est pas une relation d’équiva-
lence si R ◦ S = S ◦ R.
Comme R ◦ S = S ◦ R alors il existe y ∈ X tel que xR ◦ Sy soit vrai et xS ◦ Ry soit faux.
Ainsi si R ◦ S était symétrique, alors on aurait yR ◦ Sx ce qui implique l’existence de z ∈ X tel que yRz et zSx. Or
R et S étant symétriques on a xSz et zRy donc xS ◦ Ry, ce qui est contadictoire.

Exercice 19
Il y a 5 possibilités correspondant aux 5 cas :
1) On a 3 éléments maximaux et donc nécessairement 3 éléments minimaux et le diagramme de Hasse est :
• • •
2) On a 2 éléments maximaux et 2 éléments minimaux et le diagramme de Hasse est :
•
↑
• •
3) On a 2 éléments maximaux et 1 élément minimal et le diagramme de Hasse est :
• •
տ ր
•
4) On a 1 élément maximal et 2 éléments minimaux et le diagramme de Hasse est :
•
ր տ
• •
5) On a 1 élément maximal et 1 élément minimal et le diagramme de Hasse est :
• −→ • −→ •