Lycée Louis-Le-Grand, Paris Pour le 30/09/2013

MPSI 4 – Mathématiques
A. Troesch

Correction du DM no 2 : Ensembles, applications

Correction de l’exercice 1 –
1. (a) Soit A un sous-ensemble de E, et x ∈ A. Alors, f (x) ∈ f (A), par définition, et donc x est l’antécédent par
f d’un élément de f (A), donc x ∈ f −1 (f (A)). On en déduit que A ⊂ f −1 (f (A)) .
(b) On montre les deux implications.
• Supposons que f est injective. Soit alors A un sous-ensemble de E.
∗ D’après la question précédente, A ⊂ f −1 (f (A)).
∗ Soit x ∈ f −1 (f (A)). Alors f (x) ∈ f (A). Il existe donc par définition x′ ∈ A tel que f (x) = f (x′ ).
Comme f est injective, on en déduit que x = x′ , puis que x ∈ A. Ainsi, f −1 (f (A)) ⊂ A.
Les deux inclusions ci-dessus amènent l’égalité : A = f −1 (f (A)).
• On suppose que pour tout A ∈ P(E), f −1 (f (A)) = A. Soit alors x et y dans E tels que f (x) = f (y).
Ainsi, y ∈ f −1 (f (x)) = f −1 (f ({x})). D’après l’hypothèse, f −1 (f ({x})) = {x}, donc y ∈ {x}, puis y = x.
Ainsi, f est injective.
Ainsi f est injective si et seulement si : ∀A ∈ P(E), A = f −1 (f (A)) .
2. (a) Soit A′ un sous-ensemble de E ′ , et soit y ∈ f (f −1 (A′ )). Ainsi, il existe x ∈ f −1 (A′ ) tel que f (x) = y. Or,
puisque x ∈ f −1 (A′ ), on a f (x) ∈ A′ . Ainsi, y ∈ A′ . On a montré : f (f −1 (A′ )) ⊂ A′ .
(b) • Supposons que f est surjective. Soit alors A′ une sous-ensemble de E, et montrons que l’on a : A′ ⊂
f (f −1 (A′ )). Pour ce faire, considérons y ∈ A′ . Alors, comme f est surjective, il existe x ∈ E tel que f (x) =
y. Comme y ∈ A′ , il en résulte que x ∈ f −1 (A′ ). Ainsi, f (x) ∈ f (f −1 (A′ )), donc y ∈ f (f −1 (A′ )). Nous
avons donc démontré que A′ ⊂ f (f −1 (A′ )). L’inclusion réciproque provenant de la question précédente,
on en déduit l’égalité.
• Supposons que pour tout A′ ⊂ E, f (f −1 (A′ )) = A′ . Il s’agit de montrer que f est surjective, donc que :
∀y ∈ E ′ , ∃x ∈ E, f (x) = y. Soit donc y ∈ E ′ . D’après l’hypothèse, on a : f (f −1 ({y})) = {y}. En
particulier, f −1 ({y}) 6= ∅, puisque f (∅) = ∅. Ainsi, y admet un antécédent x au moins. Cela prouve la
surjectivité de f .
Ainsi, f est surjective si et seulement si : ∀A′ ∈ P(E ′ ), f (f −1 (A′ )) = A′ .
3. (a) Soit A un sous-ensemble de E.
• D’après la question 2(a), on a f (f −1 (f (A))) ⊂ f (A).
• Par ailleurs, d’après la question (a), A ⊂ f −1 (f (A)), donc de façon évidente, il vient : f (A) ⊂ f (f −1 (f (A)).
Les deux inclusions ci-dessus montrent l’égalité : f (f −1 (f (A))) = f (A) .
(b) Soit A′ un sous-ensemble de E ′ .
• D’après la question 2(a), f −1 (A′ ) ⊂ f −1 (f (f −1 (A′ ))).
• D’après la question 3(a), f (f −1 (A′ )) ⊂ A′ , donc f −1 (f (f −1 (A′ ))) ⊂ f −1 (A′ ).
Les deux inclusions ci-dessous amènent : f −1 (f (f −1 (A′ ))) = f −1 (A′ ) .
4. Soit A un sous-ensemble de E et A′ un sous-ensemble de E ′ .
• Puisque A ∩ f −1 (f (A′ )) ⊂ A, f (A ∩ f −1 f (A′ )) ⊂ f (A) ∩ f (f −1 (A′ )), puis, d’après la question 3(a) :
f (A ∩ f −1 f (A′ )) ⊂ f (A) ∩ A′ .
• Soit y ∈ f (A) ∩ A′ . Alors y ∈ f (A), donc il existe x ∈ A tel que f (x) = y. Comme y ∈ A′ , on a alors aussi
x ∈ f −1 (A′ ). Ainsi, x ∈ A ∩ f −1 (A′ ), puis y ∈ f (A ∩ f −1 (A′ ). On a donc montré : f (A) ∩ A′ ⊂ f (A ∩ f −1 (A′ )).
Les deux inclusions ci-dessus amènent l’égalité : f (A ∩ f −1 f (A′ )) = f (A) ∩ A′ .
5. (a) Soit A ∈ P(E). Procédons par double inclusion.
• Soit y ∈ (g ◦ f )(A). Alors il existe x ∈ A tel que y = g ◦ f (x) = g(f (x)). Ainsi, il existe z dans f (A) (par
exemple z = f (x)) tel que y = f (z). Par conséquent, y ∈ g(f (A)). Ainsi, (g ◦ f )(A) ⊂ g(f (A)).

1
 • Soit y ∈ g(f (A)). Ainsi, il existe z ∈ f (A) tel que y = g(z). Comme z ∈ f (A), il existe x ∈ A tel que
z = f (x). Ainsi, y = g(f (x)) = g ◦ f (x). On en conclut que y ∈ (g ◦ f )(A). D’où : g(f (A)) ⊂ (g ◦ f )(A).
Les deux inégalités précédentes amènent l’égalité (g ◦ f )(A) = g(f (A)) .
(b) Soit A′′ ∈ P(G).
• Soit x ∈ (g ◦ f )−1 (A′′ ). Ainsi g ◦ f (x) ∈ A′′ , donc g(f (x)) ∈ A′′ . On en déduit que f (x) ∈ g −1 (A′′ ), puis
x ∈ f −1 (g −1 (A′′ )). Ainsi, (g ◦ f )−1 (A′′ ) ⊂ f −1 (g −1 (A′′ )).
• Soit x ∈ f −1 (g −1 (A′′ )). Alors f (x) ∈ g −1 (A′′ ), donc g ◦ f (x) ∈ A′′ . Ainsi, x ∈ (g ◦ f )−1 (A′′ ). Par
conséquent, f −1 (g −1 (A′′ )) ⊂ (g ◦ f )(A′′ ).
Les deux inclusions ci-dessus prouvent l’égalité : (g ◦ f )−1 (A′′ ) = f −1 (g −1 (A′′ )).

Correction de l’exercice 2 –
1. (a) La proposition x ∈ ∅ étant fausse pour tout x, l’implication x ∈ ∅ =⇒ x ⊂ ∅ est vraie pour tout x. Ainsi,
E1 = ∅ est transitif .
(b) Soit X ∈ E2 , Alors X = ∅. Or, l’ensemble vide est inclus dans tout ensemble, donc ∅ ⊂ E2 , donc X ⊂ E2 .
Ainsi, E2 est transitif .
(c) Soit X ∈ E3 :
• soit X = ∅ et par conséquent, X ⊂ E3 , pour la même raison que précédemment ;
• soit X = {∅}, et comme ∅ ∈ E3 (l’ensemble vide est un élément de E3 ), on en déduit que {∅} ⊂ E3
({∅} désigne le singleton de E3 constitué de son élément égal à l’ensemble vide).
Ainsi : ∀X, X ∈ E3 =⇒ X ⊂ E3 . L’ensemble E3 est transitif .
(d) Soit E4 = {{∅}}, et soit X ∈ E4 . Alors, puisque E4 ne contient qu’un élément, X = {∅}. Or, ∅ 6∈ E4 ,
donc {∅} 6⊂ E4 . Ainsi, E4 n’est pas transitif .
2. (a) Commençons par déterminer P1 (X) = P(X) = {∅, {1}, {2}, {1, 2}}. Ainsi :
n
P2 (X) = ∅, {∅}, {{1}}, {{2}}, {{1, 2}}, {∅, {1}}, {∅, {2}}, {∅, {1, 2}}, {{1}, {2}}, {{1}, {1, 2}},
o
{{2}, {1, 2}}, {{1}, {2}, {1, 2}}, {∅{2}, {1, 2}}, {∅{1}, {1, 2}}, {∅{1}, {2}}, {∅, {1}, {2}, {1, 2}} .
n o
(b) P1 (∅) = {∅} , P2 (∅) = {∅, {∅}} , P3 (∅) = ∅, {∅}, {{∅}}, {∅, {∅}} .

(c) Soit X un ensemble transitif. Montrons que P(X) est transitif, donc que :

∀A, A ∈ P(X) =⇒ A ⊂ P(X).

Soit donc A ∈ P(X). Alors, par définition A ⊂ X. Ainsi :

∀x, x ∈ A =⇒ x ∈ X,

et d’après la propriété de transitivité de X :

∀x, x ∈ A =⇒ x ⊂ X.

Or, pour tout x, x ⊂ X est équivalent à x ∈ P(X), par définition de P(X). Ainsi :

∀x, x ∈ A =⇒ x ∈ P(X).

Cela signifie que A ⊂ P(X).

Ainsi, on a montré : ∀A, A ∈ P(X) =⇒ A ⊂ P(X).
L’ensemble P(X) est donc transitif .
(d) Soit X un ensemble transitif.
Soit, pour tout n dans N, la propriété Q(n): Pn (X) est transitif.
Q(0) est vrai, car P0 (X) = X est transitif par hypothèse.
Soit n ∈ N tel que Q(n) est vrai, donc Pn (X) est transitif. Alors, d’après la question 2(d), P(Pn (X)) est
transitif, donc Pn+1 (X) est transitif, ce qui correspond à Q(n + 1).
Par conséquent, Q(0) est vraie, et pour tout n dans N, Q(n) entraîne Q(n + 1). D’après le principe de
récurrence, Q(n) est vraie pour tout n dans N.
On peut conclure : pour tout n ∈ N, Pn (X) est transitif.

2
 3. Soit E un ensemble transitif, et soit F = E ∪ {E}. Soit x ∈ F .
• Soit x ∈ E, et dans ce cas, x ⊂ E par transitivité de E, puis x ⊂ F , puisque E ⊂ F ;
• soit x ∈ {E}, donc x = E, donc x ⊂ F .
Ainsi, dans tous les cas, x ⊂ F . On en déduit que F est transitif.
4. Soit (Ei )i∈I une famille (finie ou infinie) d’ensembles transitifs.
S
• Soit F = Ei , et soit x ∈ F . Alors il existe i ∈ I tel que x ∈ Ei . Comme Ei est transitif, x ⊂ Ei , et comme
i∈I
Ei ⊂ F , on en déduit que x ⊂ F .
S
Ainsi, Ei est transitif .
i∈I
T
• Soit G = Ei , et soit x ∈ F . Alors pour tout i ∈ I, x ∈ Ei . Comme pour tout i ∈ I, Ei est transitif, pour
i∈I T
tout i ∈ I, x ⊂ Ei , donc x ⊂ Ei = G.
i∈I
T
Ainsi, Ei est transitif .
i∈I

Correction de l’exercice 3 – On raisonne par récurrence sur n, en montrant le lemme suivant :

Lemme 1 : Soit (E, 6) un ensemble ordonné non vide et fini. Alors E admet au moins un élément maximal.

Démontration du lemme 1 :
On raisonne par l’absurde. Supposons que E n’admette pas d’élément maximal. Soit alors x0 un élément quelconque
de E. Comme x0 n’est pas maximal, il existe x1 ∈ E tel que x1 > x0 . L’élément x1 lui-même n’est pas maximal, donc
il existe x2 ∈ E tel que x2 > x1 > x0 . On peut alors construire par récurrence sur N une famille (xn )n∈N d’éléments
de E tels que
· · · > xn > xn−1 > · · · > x1 > x0 .

Ces éléments sont alors 2 à 2 distincts, et en nombre infini, ce qui contredit le fait que E est un ensemble fini.
Ainsi, E admet un élément maximal .

Démontration du lemme de Spilrajn-Marczewski :

On raisonne par récurrence sur n ∈ N∗ (le cas n = 0 étant vide de sens !)
Soit, pour tout n dans N∗ , la propriété P(n): « pour tout ensemble ordonné fini (E, 6) de cardinal n, il existe une
bijection ϕ : [[1, n]] −→ E. » de réciproque strictement croissante.
• Pour n = 1, il n’y a pas grand chose à prouver.
• Soit n ∈ N∗ . Supposons que P(n) est vrai. Considérons alors un ensemble ordonné (E, 6) de cardinal n + 1. D’après
le lemme 1, E admet un élément maximal x0 . Soit E ′ = E \ {x0 }, muni de la relation d’ordre obtenue par restriction
de celle de E. D’après l’hypothèse de récurrence, il existe une bijection strictement croissante ψ : [[1, n]] −→ E ′ . On
définit alors :
ϕ : [[1, n + 1]] −→ E
k 6= n + 1 7−→ ψ(k)
n + 1 7−→ x0 .
∗ Montrons que ϕ est une bijection. Pour cela, considérons x ∈ E. Alors :
– si x ∈ E ′ , ϕ−1 ({x}) = ψ −1 ({x}), et donc, ψ étant bijective, x admet un et un seul antécédent par ϕ ;
– si x 6∈ E, donc si x = x0 , puisque x0 n’est pas dans l’image de ψ, ϕ−1 ({x0 }) = {n+1}, donc x0 admet également
un unique antécédent par ϕ.
Ainsi, ϕ est bijective
∗ Montrons que ϕ−1 est strictement croissante. Soit (x, y) ∈ E 2 tel que x < y. Alors x 6= x0 (car x0 est maximal).
il reste donc les deux cas suivants :
– soit (x, y) ∈ (E ′ )2 . Dans ce cas, la fonction ψ étant strictement croissante, il vient

ψ −1 (x) < ψ −1 (y) donc: ϕ−1 (x) < ϕ−1 (y);

– soit x ∈ E ′ et y = x0 . Alors ψ −1 étant à valeurs dans [[1, n]], il vient :

ϕ−1 (x) = ψ −1 (x) 6 n < n + 1 = ϕ−1 (x0 ) = ϕ−1 (y).

3
 Ainsi, ϕ−1 est strictement croissante .
Par conséquent, P(1) est vraie, et pour tout n dans N∗ , P(n) entraîne P(n + 1). D’après le principe de récurrence,
P(n) est vraie pour tout n dans N∗ .

Correction du problème 1 – Tout d’abord, remarquez que tout ce qu’on expose se passe dans Ω : on n’étudie pas
les relations ∼ et R sur tous les ensembles. En effet, par définition, une relation est définie sur un ensemble, (ou entre
deux ensembles). Or, la collection de tous les ensembles ne forme pas un ensemble. C’est la raison de la restriction de
l’étude à Ω.
1. (a) Montrons que ∼ est une relation reflexive, symétrique et transitive :
• Reflexivité : Soit E un ensemble de Ω. Alors idE : E → E est une bijection, donc E ∼ E.
• Symétrie : Soit E et F deux ensembles de Ω tels que E ∼ F . Il existe alors une bijection ϕ : E −→ F .
On a alors une bijection ϕ−1 : F −→ E, ce qui prouve que F ∼ E.
• Transitivité : soit E, F et G des ensembles de Ω tels que E ∼ F et F ∼ G. Alors il existe deux bijections
ϕ : E → F et ψF → G. La composée de deux bijections étant une bijection, ψ ◦ ϕ est une bijection de E
dans G. Ainsi, E ∼ G.
Par conséquent, ∼ est une relation d’équivalence sur Ω.
Pour l’étude de R je me contente d’une réponse partielle, un réponse complète nécessitant en fait d’utiliser le
théorème de Bernstein. Dans la plupart des cas, R n’est ni une relation d’ordre, ni une relation d’équivalence
car :
• la transitivité n’est pas assurée : deux ensembles E et F entre lesquels il existe une bijection vérifieront
ERF et F RE, mais on peut avoir E = F ;
• l’antisymétrie n’est pas assurée : d’après le théorème de bernstein ci-dessous, si ERF et F RE, tout ce
qu’on peut en déduire, c’est que E ∼ F , mais pas E = F .
Dans certains cas particuliers (si Ω est tel que chaque classe d’équivalence pour ∼ est constituée d’un seul
élément), on peut avoir une relation d’ordre, ou (s’il n’existe qu’un classe d’équivalence pour ∼) une relation
d’équivalence.
(b) Soit (E, E ′ , F, F ′ ) ∈ Ω4 tels que E ∼ E ′ et F ∼ F ′ , et ERF . Alors, il existe deux bijections ϕ : E −→ E ′ et
ψ : F −→ F ′ , ainsi qu’une injection i : E −→ F . On obtient alors une injection j : E ′ −→ F en considérant
la composition suivante, constituée de fonctions injectives (les bijections étant des injections :

ϕ−1 i ψ
E ′ −→ E −→ F −→ F ′ .

Ainsi, E ′ RF ′ .
(c) On définit sur Ω̃ la relation S par :

∀(X, Y ) ∈ Ω̃, XSY ⇐⇒ ERF,

où E et F sont des représentants quelconques des classes X et Y (c’est-à-dire E ∈ X et F ∈ Y , X et

Y étant deux classes d’équivalences pour la relation ∼). Cela définit correctement la relation S car cette
définition est indépendante du choix des repréentant E et F des classes d’équivalence X et Y , d’après la
question précédente.
2. Soit E et F deux ensembles.
• Supposons que E est moins puissant que F . Il existe donc une injection f : E −→ F . On veut montrer qu’alors
il existe une surjection g : F −→ E. Essayons de construire une telle surjection à l’aide de f .
L’idée est de construire une réciproque de f ; mais cela n’est possible que sur l’image de F , qui n’est a priori
pas égale à tout F . On enverra alors les autres éléments de F sur n’importe quel élément de E.
Tout d’abord, E n’est pas vide, sinon il n’existe pas d’application f de E vers F . Soit alors x0 un élément
quelconque de E. On définit g de la manière suivante :

g: F −→ E
(
l’unique antécédent de y par f si y ∈ Im(f )
y 7−→
x0 si y ∈
6 Im(f ).

4
 Cela définit sans ambiguïté g, l’unicité de l’antécédent provenant de l’injectivité de f .
Montrons que cela définit une surjection. Soit x ∈ E, il s’agit de montrer qu’il existe y ∈ F tel que g(y) = x.
Soit y = f (x). Alors y est dans Im(f ), et x est l’unique antécédent de y par f . Ainsi, g(y) = x. Par conséquent,
g est surjective. Donc F est plus puissant que E .
• Supposons que F est plus puissant que E, donc qu’il existe une surjection g : F −→ E. Construisons alors
une injection f : E → F . On va, a chaque élément x de E, définir f (x) par le choix d’un antécédent quel-
conque de x par g. On peut faire ce choix du fait que tout x ∈ E admet un antécédent, puisque g est
surjective. Soit f construite ainsi. Montrons qu’elle est injective. Soit x et y dans E tels que f (x) = f (y).
Alors z = f (x) est un antécédent à la fois de x et de y par g, donc x = g(z) = y. Ainsi, f est injective. Donc
E est moins puissant que F .
3. Quelques exemples
(a) • Soit f : N −→ N∗ définie pour tout n ∈ N par f (n) = n + 1, et g : N∗ −→ N définie pour tout n ∈ N∗ par
g(n) = n − 1. Alors f et g sont réciproques l’une de l’autre donc bijectives.
Ainsi, N et N∗ sont équipotents .
• Soit f : N −→ 3N définie pour tout n ∈ N par f (n) = 3n, et g : 3N −→ N définie pour tout n ∈ 3N par
g(n) = n3 . Alors f et g sont réciproques l’une de l’autre donc bijectives.
Ainsi, N et 3N sont équipotents .
• Soit f : N −→ Z définie pour tout n ∈ N par f (n) = p, si n = 2p et f (n) = −p si n = 2p − 1 ; et soit
g : Z −→ N définie pour tout p ∈ Z par g(p) = 2p si p > 0 et g(p) = −2p − 1 si p < 0. Alors f et g sont
réciproques l’une de l’autre donc bijectives.
Ainsi, N et Z sont équipotents .
La transitivité de la relation d’équipotence permet alors de conclure que N, N∗ , 3N et Z sont deux-à-deux
équipotents.
(b) On définit une application g : N × N de la manière suivante :
(p + q)(p + q + 1)
∀(p, q) ∈ N2 , g(p, q) = + p.
2
• Pour tout n ∈ N, soit k tel que n ∈ [[ k(k+1)
2 , (k+1)(k+2)
2 − 1]] ; on a :
 
k(k + 1) k(k + 1)
g ◦ f (n) = g n − ,k − n +
2 2
k(k + 1) k(k + 1)
= +n− = n.
2 2
(p+q)(p+q+1)
• Pour tout (p, q) ∈ N2 , soit n = g(p, q) = 2 + p. Comme 0 6 p 6 p + q,

(p + q)(p + q + 1) (p + q)(p + q + 1)
6n6 +p+q
2 2
(p + q)(p + q + 1) (p + q + 1)(p + q + 2)
< +p+q+1= .
2 2
Ainsi,
 
(p + q)(p + q + 1) (p + q)(p + q + 1) (p + q)(p + q + 1) (p + q)(p + q + 1)
f (n) = +p− ,p + q − −p+
2 2 2 2
= (p, q).

Ainsi, f et g sont réciproques l’une de l’autre, donc f est une bijection.

Par conséquent, N et N × N sont équipotents .
La fonction f définie ici n’est rien d’autre que l’explicitation de la numérotation en diagonales vue dans le
cours.
4. Un résultat de Cantor
Soit E un ensemble.
(a) On définit une application f : E −→ P(E) par :

∀x ∈ E, f (x) = {x}.

5
 Ainsi, à un élément x de E, on associe le singleton {x}. Cette application est clairement injective. En effet,
si x et y sont tels que f (x) = f (y), alors {x} = {y}, puis x = y.
Ainsi, il existe une injection de E dans P(E), donc E est moins puissant que P(E) .
(b) Soit f : E −→ P(E) une application, et A = {x ∈ E | x 6∈ f (x)}, A ⊂ E.
Raisonnons par l’absurde en supposons que A ∈ f (E). Alors, il existe x ∈ E tel que f (x) = A. On a deux
possibilités :
• soit x ∈ A, et dans ce cas, x ∈ f (x), et par définition de A, x 6∈ A, d’où une contradiction ;
• soit x 6∈ A, et dans ce cas, x 6∈ f (x), et par définition de A, x ∈ A, d’où une contradiction.
Ainsi, l’hypothèse A ∈ f (E) est absurde. Par conséquent, A 6∈ f (E) .
(c) Par conséquent, étant donné une application f : E −→ P(E), cette application n’est pas surjective, étant
donné que A n’est pas dans son image. E ne peut pas être plus puissant que P(E). En particulier, il
ne peut pas exister de bijection de E sur P(E), une telle bijection étant nécessairement surjective. Donc
E et P(E) ne peuvent pas être équipotents .
Ce qu’on vient de démontrer, c’est que pour tout ensemble X, Card(X) < Card(P(X)) .
5. Théorème de Bernstein
Soit E et F deux ensembles. Le but de cette question est de montrer que si E est moins puissant que F , et si F
est moins puissant que E, alors E et F sont équipotents (théorème de Bernstein).
Soit f : E −→ F et g : F −→ E deux injections. On note :
\
h = g ◦ f, R = E \ g(F ), F = {M ∈ P(E) | R ∪ h(M ) ⊂ M }, et A= M.
M ∈F

(a) • Il faut montrer que R ∪ h(E) ⊂ E. Cela est évident, car R ⊂ E, et h étant une application de E dans
E, son image h(E) vérifie h(E) ⊂ E. Ainsi, l’union de ces deux ensembles vérifie encore : R ∪ h(E) ⊂ E.
Cela prouve que E est dans F .
• Montrons que R ∪ h(A) ⊂ A.
∗ Soit M ∈ F. Alors, par définition de F, R ∪ h(M ) ⊂ M . En particulier, R ⊂ M . Cette inclusion étant
T
vraie pour tout M ∈ F, on en déduit que R ⊂ M = A.
M ∈F
∗ Soit y ∈ h(A). Alors, il existe x ∈ A tel que y = h(x). Par définition de A, pour tout M ∈ F, y ∈ M . Or,
pour tout M ∈ F, h(M ) ⊂ M par définition de F, donc h(x) ∈ M . Ainsi, h(x) est dans l’intersection
de tous les M de F, soit : y ∈ A. On a montré que h(A) ⊂ A.
∗ Les deux inclusions R ⊂ A et h(A) ⊂ A amènent : R ∪ h(A) ⊂ A, donc A ∈ F .
(b) Soit M ∈ F, et soit M ′ = R ∪ h(M ). De manière évidente, R ⊂ M ′ . De plus, soit y ∈ h(M ′ ). Il existe
x ∈ M ′ tel que h(x) = y. Comme M ∈ F, on a M ′ ⊂ M , donc x ∈ M . Ainsi, y ∈ h(M ), donc y ∈ M ′ .
Ainsi, h(M ′ ) ⊂ M ′ .
Par conséquent, les deux inclusions R ⊂ M ′ et h(M ′ ) ⊂ M ′ amènent R ∪ h(M ′ ) ⊂ M ′ , donc M ′ ∈ F .
(c) On note B = ∁E A, A′ = f (A) et B ′ = g −1 (B).
• D’après la question (a), on sait déjà que R ∪ h(A) ⊂ A. Supposons qu’on n’ait pas l’égalité. Soit M ′ =
R ∪ h(A). Comme A ∈ F, alors, d’après (b), M ′ ∈ F, et M ′ est strictement inclus dans A. Alors :
\
A⊂ M ⊂ M ′ A.
M ∈F

On obtient donc une inclusion stricte de A dans A, ce qui est absurde. Ainsi, l’hypothèse de la démon-
stration par l’absurde est fausse, on a donc l’égalité R ∪ h(A) = A .
• On montre la double-incusion :
∗ Soit x ∈ B ′ . Alors g(x) ∈ B, donc g(x) ∈ ∁E A. Or, d’après le point précédent, en prenant les complé-
mentaires :
∁E A = ∁E R ∩ ∁E h(A) = g(F ) ∩ ∁E h(A).

Ainsi, g(x) ∈ g(F ) ∩ ∁E h(A), et notamment, g(x) 6 inh(A) = g ◦ f (A). Par conséquent, x 6∈ f (A), donc
x 6∈ A′ , donc x ∈ ∁F A′ .
Par conséquent, B ′ ⊂ ∁F A′

6
 ∗ Réciproquement, soit x 6 inA′ . Alors x 6∈ f (A), donc g(x) 6∈ h(A). De plus, g(x) ∈ g(F ), donc par
définition de R, g(x) 6∈ R. Ainsi, g(x) 6∈ R∪h(A) = A, d’où g(x) ∈ B. Par conséquent, x ∈ g −1 (B) = B ′ .
Ainsi, ∁F A′ ⊂ B ′ .
Les deux inclusions précédentes montrent que B ′ = ∁F A′ .
(d) • Tout d’abord f est bien définie, puisque f (A) ⊂ A′ . On a même f (A) = A′ , par définition de A′ , donc
f ′ (A) = A′ , ce qui prouve la surjectivité de f ′ . D’autre part, f ′ étant la restriction d’une application
injective, elle est aussi injective. Ainsi, f ′ est bijective .
• Faisons de même pour g. Tout d’abord, B ′ = g −1 (B), donc g(B ′ ) ⊂ B. Ainsi, g ′ est bien définie. De plus,
g ′ étant la restriction d’une application injective, elle est encore injective. Enfin, soit y ∈ B. Or :

B = ∁E A = ∁E (R ∪ h(A)) = g(F ) ∩ ∁E h(A).

En particulier, y ∈ g(F ), donc g −1 ({y}) 6= ∅. Or, g −1 ({y}) ⊂ g −1 (B) = B ′ . Donc il existe x ∈ B ′ tel que
g(x) = y. Cela montre la surjectivité de g ′ .
On en déduit que g ′ est bijective .
(e) Soit :
ϕ: E −→ F
(
f ′ (x) si x ∈ A
x 7−→
(g ′ )−1 (x) si x ∈ B.

Cette application est bien définie du fait que A et B sont complémentaires l’un de l’autre, et que g ′−1 est
bien définie, puisque g ′ est bijective.
De plus, on peut en définir une réciproque ψ :

ψ: F −→ E
(
(f ′ )−1 (y) si y ∈ A′
y 7−→
g ′ (y) si y ∈ B ′ .

L’application ψ est bien définie car B ′ = ∁F A′ . De plus :

• ∗ si x ∈ A, alors ϕ(x) = f ′ (x) ∈ A′ , donc ψ ◦ ϕ(x) = (f ′ )−1 ◦ f ′ (x) = x ;
∗ si x ∈ B, alors ϕ(x) = (g ′ )−1 (x) ∈ B ′ , donc ψ ◦ ϕ(x) = g ′ ◦ (g ′ )−1 (x) = x ;
ainsi, pour tout x ∈ E, ψ ◦ ϕ(x) = x ;
• ∗ si x ∈ A′ , alors ψ(x) = (f ′ )−1 (x) ∈ A, donc ϕ ◦ ψ(x) = f ′ ◦ (f ′ )−1 (x) = x ;
∗ si x ∈ B ′ , alors ψ(x) = g ′ (x) ∈ B, donc ϕ ◦ ψ(x) = (g ′ )−1 ◦ g ′ (x) = x ;
ainsi, pour tout x ∈ E, ϕ ◦ ψ(x) = x.
Par conséquent, ϕ et ψ sont réciproques l’une de l’autre, ce qui justifie que ϕ est une bijection .
La conclusion est bien que E et F sont équipotents.
6. Soit X et Y dans Ω̃ et E et F des représentants des classes d’équivalences X et Y . On a alors :
• Reflexivité : Soit X ∈ Ω̃, et E un représentant de la classe X. La fonction idE : E −→ E est injective, donc
ERE donc XSX.
• Antisymétrie : Soit X et Y dans Ω̃ et E et F des représentants des classes d’équivalences X et Y . Supposons
que XSY et Y SX. Il existe donc deux injections i : E −→ F et j : F −→ E. D’après la question précédente,
on en déduit que E et F sont équipotents, donc E ∼ F , donc X = Y .
• Transitivité : soit X, Y et Z dans Ω̃, de représentants E, F et G. On suppose que XSY et Y SZ. Alors il
existe des injections i : E −→ F et j : F −→ G. Ainsi, j ◦ i est une injection de E dans G, donc ERG, donc
XSZ.
Ainsi, S est une relation d’ordre .
7. Cardinal de R et cardinal de P(n).


(a) La fonction x 7→ tan πx + 12 est strictement croissante sur ]0, 1[, continue, de limites respectives −∞ et
+∞ en 0 et 1. Ainsi, il s’agit d’une bijection de ]0, 1[ sur R, d’après le théorème de la bijection. On en
déduit que ]0, 1[ et R sont équipotents, donc que [0, 1] est plus puissant que R. L’injection canonique de
[0, 1] dans R montre que [0, 1] est moins puissant que R. Ainsi [0, 1] et R sont équipotents.

7
 (b) Soit A un sous-ensemble de N. On définit f (A) le réel dont le développement en base 2 est donné par :

f (A) = 0.x0 x1 . . . xn . . .2 ,

où pour tout i ∈ N, xi = 1A (i). Ainsi, le chiffre d’indice i est égal à 1 si et seulement si i ∈ A. Cela définit
une fonction f : P(N) −→ [0, 1]
Cette fonction est surjective, car étant donné un réel x dont le (ou plutôt « un » développement binaire)
est
x = 0.x0 x1 . . . xn . . .2 ,

on peut considérer l’ensemble A des indices i tels que xi = 1. On a alors A ⊂ N, et f (A) = x.

En revanche, f n’est pas injective, du fait de l’existence de deux développements binaires possibles de
certains nombres (comme pour les décimaux), l’un terminant par une infinité de 0, l’autre par une infinité
de 1.
(c) On construit g : P(N) −→ [0, 1] par
3
g(A) = 0.x0 x2 . . . xn . . . ,

où comme précédement, xi est égal à 1 si et seulement si i ∈ A, et à 0 sinon.

Cette fois, g n’est évidemment pas surjective (tous les nombres ayant un 2 dans leur développement ternaire,
et ne terminant pas par une infinité de 2 ne sont clairement pas dans l’image de g)
En revanche, g est injective, car pour chaque nombre pouvant admettre 2 représentations ternaires différentes
(l’une terminant par des 0, l’autre terminant par des 2), seule une de ces deux représentations est dans
l’image de g.
(d) La fonction f étant surjective, P(N) est plus puissant que [0, 1]. La fonction g étant injective, P(N) est
moins puissant que [0, 1]. On en déduit que P(N) et [0, 1] sont équipotents, et donc, d’après la question 6a,
P(N) et R sont équipotents .
8. (Question facultative, nécessite l’axiome du choix)
Soit F l’ensemble des fonctions f , définies sur un sous-ensemble Ef de E, et injectives de Ef dans F . on définit
sur F une relation 6 par :
f 6 g si et seulement si Ef ⊂ Eg et g|Ef = f.

(a) Tout d’abord, montrons que 6 est bien une relation d’ordre sur F. Soit (f, g, h) ∈ F 3 .
• On a Ef ⊂ Ef , et f|Ef = f , donc f 6 f . Donc 6 est reflexive.
• Si f 6 g et g 6 f , alors Ef ⊂ Eg et Eg ⊂ Ef , donc, d’après le principe de double-inclusion, Ef = Eg .
Par ailleurs, on a alors
g = g|Eg = g|Ef = f.

Ainsi, f = g. On en déduit que 6 est antisymétrique.

• Si f 6 g et g 6 h. Alors Ef ⊂ Eg ⊂ Eh , donc Ef ⊂ Eh . De plus,

∀x ∈ Ef , h(x) = g(x) = f (x),

la première égalité provenant du fait que x ∈ Eg et h|Eg = g, la seconde provenant du fait que g|Ef = f .
Ainsi, f 6 h. Donc 6 est transitive.
On en déduit que 6 est une relation d’ordre sur F.
Soit maintenant un sous-ensemble G totalement ordonné de F. Définissons :
[
E0 = Eg .
g∈G

Soit alors f0 la fonction définie sur E0 de la façon suivante : soit x ∈ E0 . Il existe alors g ∈ G tel que x ∈ Eg .
On définit f0 (x) = g(x). Cette définition ne dépend pas du choix de g, car si h est une autre fonction de G
telle que x ∈ Eh , on aura soit g 6 h, soit h 6 g, donc, dans les deux cas, g et h coïncident sur Eg ∩ Eh .
Comme x ∈ Eg ∩ Eh , on a bien g(x) = h(x). Ainsi, la fonction f0 est bien définie, et cela indépendamment
du choix de g effectué.

8
 Par ailleurs, f est injective, car si x et y sont dans E0 et tels que f (x) = f (y), on a l’existence de g et h
dans G tels que x ∈ Eg et y ∈ Eh . Comme g 6 h ou h 6 g, on a soit Eg ⊂ Eh , soit Eh ⊂ Eg . Pour se
fixer les idées, supposons que Eg ⊂ Eh , l’autre cas étant similaire. On a alors (x, y) ∈ Eh2 , et h(x) = h(y).
Comme h est injective, x = y. Ainsi, f est injective.
Par construction pour tout g ∈ G, Eg ⊂ E0 = Ef0 . De plus, ce qu’on vient de faire montre que pour tout
x ∈ Eg , f0 (x) = g(x), donc f0 | Eg = g. On a donc montré que pour tout g ∈ G, g 6 f0 . Ainsi, f0 est un
majorant de G.
Par conséquent, F est inductif .
On déduit alors du lemme de Zorn que F admet un élément maximal f
(b) Soit f l’élément maximal de F trouvé dans la question précédente.
• Si Ef = E, alors f est une fonction injective de E dans F . On en déduit que E est moins puissant que
F , donc ERF .
• Sinon, on montre par l’absurde que f est surjective. En effet, supposons que f ne soit pas surjective.
Comme Ef 6= E, il existe x0 tel que x0 ∈ E \ Ef ; comme f n’est pas surjective, il existe y0 ∈ F | Im(f ).
Alors on construit un prolongement f˜ de f sur Ef ∪ {x0 } par :

f (x) si x ∈ E
f
∀x ∈ Ef ∪ {x0 }, f˜(x) =
 y0 si x = x0 .

Alors f˜ est clairement injective. On a donc f˜ ∈ F, et le façon immédiate, on obtient f 6 f˜, et f 6= f˜.
cela contredit la maximalité de f .
Ainsi, f est surjective, donc F RE.
Concusion : ERF ou F RE .
(c) On en déduit évidemment que pour toutes classes cardinales E et F , on a soit ESF ou F SE. On savait
déjà que S est un ordre. On en déduit donc que c’est un ordre total .
Ce résultat est faux si on ne suppose pas l’axiome du choix.

Correction du problème 2 – Généralisation des notions d’injectivité et de surjectivité à des relations

quelconques
1. Soit A et B deux sous-ensembles de E.
(a) Supposons que A ⊂ B. Montrons qu’alors R+ (A) ⊂ R+ (B). Pour cela, considérons un élément y ∈ R+ (A).
Par définition, il existe a ∈ A tel que aRy. Comme A ⊂ B, a est aussi dans b, donc il existe b ∈ B tel que
bRy. Ainsi, y ∈ R+ (B). On en déduit que R+ (A) ⊂ R+ (B) .
(b) Soit y ∈ R+ (A ∪ B). Ainsi, il existe a ∈ A ∪ B tel que aRy. Alors :
• Soit a ∈ A, et dans ce cas, y ∈ R+ (A) ;
• Soit a ∈ B, et dans ce cas, y ∈ R+ (B).
(Ces deux éventualités ne sont pas exclusives).
On en déduit que y ∈ R+ (A) ∪ R+ (B).
Ainsi, on a montré : R+ (A ∪ B) ⊂ R+ (A) ∪ R+ (B) .
(c) Soit y ∈ R+ (A ∩ B). Ainsi, il existe a ∈ A ∩ B tel que aRy. Alors :
• on a : a ∈ A, et donc, y ∈ R+ (A) ;
• on a : a ∈ B, et donc, y ∈ R+ (B).
On en déduit que y ∈ R+ (A) ∩ R+ (B).
Ainsi, on a montré : R+ (A ∩ B) ⊂ R+ (A) ∩ R+ (B) .
2. Considérons la relation R−1 de F vers E. Alors, pour tout sous-ensemble L de F :

R− (L) = {x ∈ E, ∃ℓ ∈ L, xRℓ} = {x ∈ E, ∃ℓ ∈ L, ℓR−1 x} = (R−1 )− (L).

Les points (a), (b) et (c) résultent de manière immédiate de cette remarque et de la question 1.
3. (a) Soit R une relation de type 1 et 2. Alors tout élément de E est en relation avec un et un seul élément de
F . On reconnaît la définition d’une application de E dans F .

9
 (b) Soit R une relation définissant une application f (donc R est de type 1 et 2).
• Supposons que R soit de type 3. Ainsi, tout élément de F est en relation avec au plus un élément de E,
autrement dit, tout élément de F admet au plus un antécédent par f . L’application f est donc injective .
• De même, si R est de type 4, tout élément de F admet au moins un antécédent par f , donc f est surjective .
(c) Tout d’abord T définit une application. On montre cela en deux temps.
• R et S de type 1 =⇒ T de type 1.
En effet, supposons que R et S sont de type 1. Soit x ∈ E. Soit x n’est en relation par T avec aucun
élément de G, soit il existe z ∈ G tel que xT z. Dans ce dernier cas, montrons que z est unique. Soit un
tel élément z. Il existe donc y ∈ F tel que xRy et ySz. Soit z ′ un autre élément de G tel que xT z ′ . Il
existe donc y ′ ∈ F tel que xRy ′ et y ′ Rz ′ . Comme R est de type 1, y ′ = y, puis, comme S est de type 1,
z ′ = z. Ainsi, z est le seul élément de G en relation avec x.
• R et S de type 2 =⇒ T de type 2.
En effet, soit x ∈ E. Il existe y tel que xRy, puis z tel que yRz (car R et S sont de type 2). Donc il
existe z tel que xT z, ce qui signifie que T est de type 2.
Ainsi, T est à la fois de type 1 et de type 2 ; il s’agit donc d’une application.
Par ailleurs, soit x ∈ E, et z l’unique élément de G tel que xT z. D’après ce qui précède, il existe un unique
y ∈ F tel que xRy et yRz. La première correspondance amène : y = f (x) ; la seconde amène : z = g(y).
Ainsi, on a bien z = g ◦ f (x), ce qui prouve que T est la relation associée à l’application g ◦ f .
(d) On a déjà montré dans la question précédente que la composée de deux relations de type 1 (resp. de
type 2) est une relation de type 1 (resp. de type 2). Étudions donc le cas des types 3 et 4. On note comme
précédemment T la composée de R et S.
• Supposons que R et S sont de type 3. Soit z ∈ F . Montrons que s’il existe un élément x ∈ E tel que xT z,
alors cet élément est unique. Soit donc x et x′ deux tels éléments. Il s’agit de montrer que x = x′ . Par
définition de T , il existe y ∈ F tel que xRy et ySz, et il existe y ′ tel que x′ Ry ′ et y ′ Sx. Puisque S est de
type 3, y = y ′ (unicité d’un « antécédent » de z). Par conséquent, R étant de type 3, x′ = x (unicité d’un
« antécédent » de y). D’où l’unicité de x, sous réserve d’existence. La relation T est donc de type 3 .
• Supposons que R et S sont de type 4. Soit z ∈ G. Comme S est de type 4, il existe y ∈ F tel que ySz.
Soit un tel y. Comme R est de type 4, il existe x ∈ E tel que xRy. Alors, par définition de T , un tel x
vérifie xT z. Ainsi, pour tout z ∈ G, il existe x ∈ E tel que xT z. On en déduit que T est de type 4 .
4. Montrons que les propositions suivantes sont équivalentes :
(i) R est du type 3
(ii) ∀(A, B) ∈ (P(E))2 , R+ (A ∩ B) = R+ (A) ∩ R+ (B)
(iii) ∀A ∈ P(E), R− (R+ (A)) ⊂ A


(iv) ∀A ∈ P(E), R+ ∁E A ⊂ ∁F (R+ (A)).
• (i) =⇒ (ii)
Supposons que R est de type 3. Soit A et B deux sous-ensembles de E. Il s’agit de montrer que R+ (A ∩ B) =
R+ (A) ∩ R+ (B).
∗ D’après 1(c), R+ (A ∩ B) ⊂ R+ (A) ∩ R+ (B).
∗ Soit y ∈ R+ (A) ∩ R+ (B). Alors y ∈ R+ (A), donc il existe a ∈ A tel que aRy. De même y ∈ R+ (B), donc il
existe b ∈ B tel que bRy. Comme R est de type 3, a = b, et donc a ∈ A ∩ B. Par conséquent, y ∈ R+ (A ∩ B).
Les deux inclusions ci-dessus montrent l’égalité.
• (ii) =⇒ (iii)
Supposons que (ii) est vérifié. Soit A un sous-ensemble de E. Soit x ∈ R− (R+ (A)). Ainsi, il existe y ∈ R+ (A)
tel que xRy. Soit une tel y. D’après (ii),

R+ ({x} ∩ A) = R+ ({x}) ∩ R+ (A).

Or y étant en relation avec x, on a y ∈ R+ ({x}), et par définition de y, y ∈ R+ (A). Par conséquent,

R+ ({x}) ∩ R+ (A) 6= ∅ puis: R+ ({x} ∩ A) 6= ∅ puis: {x} ∩ A 6= ∅.

Cette dernière propriété signifie que x ∈ A. Ainsi, R− (R+ (A)) ⊂ A.

10
 • (iii) =⇒ (iv)


Supposons que (iii) est vérifié. Soit A un sous-ensemble de E, et supposons que R+ ∁E A ∩ R+ A 6= ∅.
Soit y dans cette intersection. Alors il existe x ∈ A tel que xRy, et il existe x′ ∈ ∁E A, tel que x′ Ry. Comme
A ∩ ∁E A = ∅, x 6= x′ . Soit B = {x}. Comme xRy, on a y ∈ R+ ({x}), et donc, comme x′ Ry, x′ ∈ R− R+ ({x}).
Or, d’après (iii), R− R+ ({x}) ⊂ {x}, donc x = x′ , d’où une contradiction. Ainsi,



R+ ∁E A ∩ R+ A = ∅, donc: R+ ∁E A ⊂ ∁F (R+ A).

• (iv) =⇒ (i)
Supposons que (iv) est vérifié. Soit y un élément de F . Si y est en relation avec au moins un élément x de
E, montrons que cet élément est unique. Soit x et x′ deux éléments en relation avec y. Il s’agit de montrer


que x = x′ . En prenant A = {x} dans (iv), R+ ∁E {x} ⊂ ∁F (R+ {x}). Or, si x′ 6= x, x′ ∈ ∁E {x}, et


donc y ∈ R+ ∁E {x} , puisque x′ Ry. Ainsi, y ∈ ∁F (R+ {x}). Mais comme on a également xRy, on a aussi
y ∈ R+ {x}, d’où une contradiction. Ainsi, x = x′ . Cela montre que R est de type 3.
On remarque que R est de type 1 si et seulement si R−1 est de type 3. On en déduit donc que les propriétés
suivantes sont équivalentes :
(i) R est du type 1
(ii) ∀(L, M ) ∈ (P(F ))2 , R− (L ∩ M ) = R− (L) ∩ R− (M )
(iii) ∀L ∈ P(F ), R+ (R− (L)) ⊂ L


(iv) ∀L ∈ P(F ), R− ∁F L ⊂ ∁E (R− (L)).
5. Montrons que les propriétés suivantes sont équivalentes :
(i) R est du type 4
(ii) R+ (E) = F
(iii) ∀L ∈ P(F ), L ⊂ R+ (R− (L))


(iv) ∀A ∈ P(E), ∁F (R+ (A)) ⊂ R+ ∁E (A) .
• (i) =⇒ (ii)
Supposons que R est de type 4. Par définition, R+ (E) ⊂ F . Montrons qu’on a égalité. Pour cela, considérons
un élément y de F , et montrons qu’il est dans R+ (E). Comme R est de type 4, par définition, il existe au
moins un élément x ∈ E tel que xRy. Ainsi, y ∈ R+ (E).
• (ii) =⇒ (iii)
Supposons (ii). Soit L un sous-ensemble de F . Soit y ∈ L ⊂ F . Comme R+ (E) = F , y ∈ R+ (E), donc il
existe x ∈ E tel que xRy. Comme y ∈ L, on a x ∈ R− (L). Alors, la relation (xRy) ∧ (x ∈ R− (L)) amène
y ∈ R+ (R− (L)). Ainsi, L ⊂ R+ (R− (L)).
• (iii) =⇒ (iv)



Supposons (iii). D’après (iii) avec L = ∁F (R+ A), on a : ∁F (R+ A) ⊂ R+ R− ∁F (R+ A) .



Par ailleurs, on a R− ∁F (R+ A) ⊂ ∁E A. En effet, soit x ∈ R− ∁F R+ A . Alors, il existe y ∈ ∁F (R+ A) tel
que xRy. Comme y 6∈ R+ (A), il est nécessaire que x 6∈ A. Ainsi, x ∈ ∁E A.


L’inclusion R− ∁F (R+ A) ⊂ ∁E A amène, d’après la question 1(a) :





R+ R− ∁F (R+ A) ⊂ R+ ∁E A puis: ∁F (R+ A) ⊂ R+ ∁E A .

• (iv) =⇒ (i)
Supposons (iv). Appliquons (iv) avec A = ∅. On obtient :


∁F (R+ (∅)) ⊂ R+ ∁E ∅ soit: F ⊂ R+ (E).

Ainsi, R+ (E) = F . Soit y ∈ F , comme y ∈ R+ (E), il existe donc x ∈ E tel que xRy. Cela montre que R est
de type 4.
En remarquant que R est de type 2 si et seulement si R−1 est de type 4, on obtient une liste de propriétés
équivalentes :
(i) R est du type 2
(ii) R− (F ) = E

11
 (iii) ∀A ∈ P(E), A ⊂ R− (R+ (A))


(iv) ∀L ∈ P(F ), ∁E (R− (L)) ⊂ R− ∁F (L) .
6. (a) On vérifie que 6 est une relation reflexive, antisymétrique et transitive.
b Pour tout (x, y) ∈ E 2 , xRy entraîne xRy, donc R 6 R. Ainsi, 6 est reflexive.
• Soit R ∈ E.
• Soit R et S deux relations telles que R 6 S et S 6 R. Alors, pour tout (x, y) ∈ E 2 , xRy =⇒ xSy et
xSy =⇒ xRy, donc xRy ⇐⇒ xSy. Soit G et G′ les graphes associés à R et S. L’équivalence précédente
implique que (x, y) ∈ G équivaut à (x, y) ∈ G′ , ainsi, G = G′ , donc R = S. Par conséquent, 6 est
antisymétrique.
• Soit R, S et T trois relations telles que R 6 S, et S 6 T . Pour tout (x, y) ∈ E 2 , on a xRy =⇒ xSy et
xSy =⇒ xT y. Par transitivité de l’implication, on obtient, pour tout (x, y) ∈ E 2 , xRy =⇒ xT y. Ainsi,
R 6 T . Par conséquent, 6 est transitive.
b.
La relation 6 étant réflexive, antisymétrique et transitive, c’est une relation d’ordre sur E
(b) • Supposons que R est de type 1. Tout d’abord, il s’agit de comprendre la notation R ◦ R−1 , que l’on
n’a pas explicitement définie (et notamment le sens dans lequel se font les compositions). Afin que la
notation de la composition coïncide avec la notation utilisée pour les applications, R ◦ S doit déisgner la
composition de S avec R. Ainsi, si T désigne la relation R ◦ R−1 , xT y si et seulement s’il existe z dans E
tel que xR−1 z et zRy, donc zRx et zRy. Comme R est de type 1, z est en relation avec un seul élément
à sa droite, donc x = y. Or, soit U la relation associée à l’application IdE (ainsi xU y si et seulement si
x = y). On en déduit que si xT y, alors xU y. Ainsi, R ◦ R−1 6 IdE .
• Supposons que T 6 U . Soit z un élément de E admettant au moins une image. Montrons qu’elle est
unique. Soit x et y dans E tels que zRx et zRy. Alors xR−1 z et zRy, donc xT y, donc xU y, puis x = y.
Ainsi, z ne peut pas admettre deux images distinctes. On en déduit que R est de type 1.
Ainsi, R est de type 1 si et seulement si R ◦ R−1 6 IdE .
(c) • ∗ Supposons que R est de type 2. Soit x et y tels que xU y, donc x = y. Or, x est en relation avec au
moins un élément z de F , car R est de type 2. Ainsi, xRz et zR−1 x, donc zR−1 y. Ainsi, x(R−1 ◦ R)y.
Donc IdE 6 R−1 ◦ R.
∗ Réciproquement, si IdE 6 R−1 ◦ R, alors, pour tout x ∈ E, xU x, donc x(R−1 ◦ R)x, donc il existe
z ∈ F tel que xRz et zR−1 x. Ainsi, x est en relation avec au moins un élément z de F . Par conséquent,
R est de type 2.
On en déduit que R est de type 2 si et seulement si IdE 6 R−1 ◦ R
• R est de type 3 si et seulement si R−1 est de type 1 si et seulement si R−1 ◦ R 6 IdE .
• R est de type 4 si et seulement si R−1 est de type 2 si et seulement si IdE 6 R ◦ R−1 .
(d) • Si R ◦ R−1 = R−1 ◦ R = IdE , alors les quatre inégalités de la question précédente sont vérifiées, donc R
est de types 1, 2, 3 et 4. Étant de types 1 et 2, il s’agit d’une application. Étant de types 3 et 4, cette
application est à la fois injective et surjective. C’est donc une bijection.
• Réciproquement, si R est une application bijective, donc est de types 1 et 2 (car c’est une application), 3
et 4 (car elle est injective et surjective). Ainsi, les quatre inégalités de la question précédente sont vérifiées.
En particulier :
∗ IdE 6 R ◦ R−1 et R ◦ R−1 6 IdE , donc IdE = R ◦ R−1 par antisymétrie ;
∗ IdE 6 R−1 ◦ R et R−1 ◦ R 6 IdE , donc IdE = R−1 ◦ R par antisymétrie ;
Ainsi, R ◦ R−1 = R−1 ◦ R = IdE si et seulement si R est une application bijective.

12