Algèbre et Arithmétique - Relations et Structures I

08 février 2021

Partie B : Relations et structures

1 Relations
1.1 Définitions et exemples
Définition 1. Soit E un ensemble (qu’on suppose non vide). Une relation (binaire) R sur E est une
propriété (qui peut donc être vraie ou fausse) portant sur les couples d’éléments de E. La notation xRy
signifie que la propriété est vérifiée pour le couple (x, y).

Quelques exemples :

• Sur E = R, les signes =, <, ≥ sont des relations ;

• Si A est un ensemble, et si E = P(A) désigne l’ensemble des parties de A, le signe ⊆ est une relation
sur E ;

• Si E désigne l’ensemble des droites du plan, les symboles // (”être parallèle à (ou confondue avec)”)
ou ⊥ (”être perpendiculaire à”) sont des relations sur E.

On va donner maintenant quelques propriétés pouvant (ou non) être vérifiées par une relation binaire
sur un ensemble E.

Définition 2. Soit E un ensemble, et R une relation binaire sur E. On dit que R est :

• réflexive si, pour tout x ∈ E, on a xRx (autrement dit si la relation R est vérifiée pour tous les
couples (x, x), où x est un élément de E) ;

• symétrique si, pour tous (x, y) ∈ E 2 , on a xRy ⇒ yRx (autrement dit la relation R est symétrique
si, à chaque fois que la propriété est vraie pour le couple (x, y), elle est également vraie pour le couple
(y, x)) ;

• anti-symétrique si, pour tous (x, y) ∈ E 2 , on a (xRy et yRx) ⇒ x = y (autrement dit la relation
R est anti-symétrique si le fait d’avoir la propriété vérifiée à la fois pour le couple (x, y) et le couple
(y, x) entraı̂ne x = y, ce qui par contraposée peut aussi se traduire en disant que si on a x 6= y on
ne peut pas avoir à la fois xRy et yRx) ;

• transitive si pour tous (x, y, z) ∈ E 3 on a (xRy et yRz) ⇒ xRz (autrement dit la relation R est
transitive si le fait d’avoir la propriété vraie pour les couples (x, y) et (y, z) entraı̂ne forcément que
la propriété est vraie pour le couple (x, z), on peut voir ça comme une sorte de ”relation de Chasles”
satisfaite par R).

Exemples : Reprenons les exemples précédents, vous êtes invités à vérifier et vous convaincre des
affirmations ci-dessous :

• Sur E = R, la relation = est à la fois réflexive, symétrique, anti-symétrique et transitive.

1
 • Sur E = R, la relation < est transitive et anti-symétrique (en effet, si P est toujours fausse
l’implication P ⇒ Q (qui correspond à non(P ) ou Q) est vraie. Ici on n’a jamais x < y et y < x,
donc la relation < est anti-symétrique), mais n’est ni réflexive ni symétrique.

• Sur E = R, la relation ≥ est réflexive, anti-symétrique et transitive, mais n’est pas symétrique.

• Sur P(A), où A est un ensemble, la relation ⊆ est réflexive, anti-symétrique et transitive, mais n’est
pas symétrique.

• sur l’ensemble des droites du plan, la relation // est réflexive, symétrique et transitive, mais n’est
pas anti-symétrique ;

• sur l’ensemble des droites du plan, la relation ⊥ est symétrique, mais n’est ni réflexive, ni anti-
symétrique, ni transitive.

1.2 Relations d’équivalence

On va désormais définir et étudier les propriétés de certaines relations binaires particulières, les relations
d’équivalence. Comme on va le voir, elles vont jouer un rôle important dans la suite de ce cours.

Définition 3. Soit E un ensemble, et R une relation binaire sur E. On dit que R est une relation
d’équivalence sur E si R est à la fois réflexive, symétrique et transitive.

Donnons quelques exemples, plus ou moins élaborés, de relations d’équivalence.

Exemples de relations d’équivalence :

1. sur l’ensemble des droites du plan, la relation // est une relation d’équivalence ;

2. sur l’ensemble des étudiants de l’UCA, la relation R=”avoir le même prénom que” (autrement dit,
si a et b désignent deux étudiants de l’UCA, on dit que aRb lorsque a a le même prénom que b) est
une relation d’équivalence ;

3. sur l’ensemble des étudiants de L2 Maths de l’année 2020-2021 qui suivent l’UE Algèbre et Arithmétique,
la relation R=”être dans le même groupe de TD en Algèbre et Arithmétique que” est une relation
d’équivalence ;

4. plus généralement (cet exemple généralise en effet par exemple les deux précédents) si A et B sont
deux ensembles et si f : A → B est une application (c’est-à-dire une fonction dont l’ensemble de
définition est l’ensemble A entier), la relation R définie sur A par a1 Ra2 lorsque f (a1 ) = f (a2 ) est
une relation d’équivalence sur A ;

5. sur R, la relation R définie par θ1 Rθ2 lorsqu’il existe k ∈ Z tel que θ2 = θ1 + k(2π) (cette relation
est notée en trigonométrie θ1 ≡ θ2 [2π]) est une relation d’équivalence sur R (on peut d’ailleurs
remarquer que cet exemple est un cas particulier du point précédent, en prenant A = R, B = C et
f : R → C l’application définie par f (θ) = eiθ ) ;

6. sur l’ensemble Z × Z \ {0} (ensemble donc constitué des couples (a, b) où a ∈ Z et où b ∈ Z est
non-nul), la relation R définie par (a, b)R(c, d) lorsque ad = bc est une relation d’équivalence (pour
prouver la transitivité, on pourra remarquer que si ad = bc et cf = ed avec b, d et f non nuls, on a
d(af − be) = (ad)f − b(ed) = bcf − bcf = 0, donc af = be puisque d est non nul) ;

7. (plus dur, mais géométriquement intéressant) notons E l’ensemble des couples de points du plan
(E est donc l’ensemble constitué des couples (A, B) où A et B sont des points du plan), la relation
R définie par (A, B)R(D, C) lorsque le milieu du segment [AC] est le même point que le milieu
du segment [BD] (ce qui revient à dire que le quadrilatère ABCD est un parallélogramme) est
une relation d’équivalence sur E. Il est simple de montrer la réflexivité et la symétrie. Pour la

2
 transitivité, on remarque que si (A, B)R(D, C) et (D, C)R(E, F ) alors ABCD et CDEF sont
des parallélogrammes, donc on a (AB)//(CD) et (CD)//(EF ) et AB = CD et CD = EF . On
en déduit que (AB)//(EF ) et AB = EF , donc ABF E est un parallélogramme, ce qui montre
(A, B)R(E, F ) et prouve ainsi la transitivité de R.
Souvent, la réflexivité et la symétrie sont assez rapides et simples à vérifier, et la difficulté se concentre
en général sur la transitivité (comme le montrent les deux derniers exemples). Voici un exemple de relation
réflexive et symétrique qui n’est pas transitive :

Contre-exemple :
Prenons E l’ensemble des lycéens, et définissons sur E la relation R par aRb lorsque a pratique le
même sport que b. Cette relation est bien réflexive et symétrique, MAIS elle n’est pas transitive (en effet,
soit b un lycéen qui fait à la fois du rugby et du cyclisme, en choisissant a un rugbyman non cycliste et c
un cycliste qui ne pratique pas le rugby, on a aRb et bRc mais pas aRc).

On introduit maintenant la définition de classes d’équivalence, notion très importante qui donne tout
son intérêt à ce chapitre et se retrouve dans tous les domaines des mathématiques, et on étudie les
propriétés essentielles des classes d’équivalence pour une relation d’équivalence.
Définition 4. Soit E un ensemble et R une relation d’équivalence sur E. Soit a ∈ E. On appelle classe
d’équivalence de a la partie de E, notée C(a), définie par

C(a) = {x ∈ E tel que aRx}.

On dit qu’une partie C ⊆ E est une classe d’équivalence pour R s’il existe a ∈ E tel que C = C(a).

Quelques exemples :
• pour la relation // sur les droites du plan, la classe d’équivalence de l’axe des abscisses est constitué
de l’ensemble des droites horizontales du plan, autrement dit l’ensemble {Dk ; k ∈ R} où Dk est la
droite d’équation y = k.

• pour la relation ”être dans le même groupe de TD en Algèbre et Arithmétique que” sur l’ensemble
des étudiants de L2 Maths de l’année 2020-2021 qui suivent l’UE Algèbre et Arithmétique, la classe
d’équivalence d’un étudiant du groupe de TD numéro 3 est l’ensemble des étudiants du groupe de
TD numéro 3 ;

• pour la relation définie dans l’exemple 6. précédent sur Z × Z \ {0}, la classe d’équivalence du couple
(−2; 4) est {(−k; 2k); k ∈ Z \ {0}} ;

• pour la relation d’équivalence donnée dans l’exemple 4. précédent, si a ∈ A la classe d’équivalence

de a est l’ensemble f −1 ({f (a)}) = {b ∈ A tel que f (b) = f (a)}.
Voyons désormais quelques propriétés vérifiées par les classes d’équivalence pour une relation d’équivalence.
Proposition 5. Soit E un ensemble (non vide), R une relation d’équivalence sur E. Alors on a les
propriétés suivantes :
1. Pour tout a ∈ E, C(a) 6= ∅ ;

2. si (a, b) ∈ E 2 vérifient aRb, alors on a C(a) = C(b) ;

3. si (a, b) ∈ E 2 vérifient non(aRb), alors on a C(a) C(b) = ∅ ;

T

4. soit C une classe d’équivalence pour R. Pour tout a ∈ C on a C = C(a) ;

T
5. soit C1 et C2 deux classes d’équivalence pour R. On a soit C1 = C2 , soit C1 C2 = ∅ (autrement
dit, deux classes d’équivalence pour R sont soit confondues soit disjointes, c’est-à-dire sans aucun
élément en commun).

3
 Démonstration (type 1) :
1. Soit a ∈ E. Par définition R est réflexive, on a donc aRa ce qui montre que a ∈ C(a), donc C(a)
est non vide.

2. Soit (a, b) ∈ E 2 , supposons que aRb. On veut ici montrer l’égalité de deux parties de E. Comme
souvent, le plus simple est de procéder par double inclusion. La démarche pour montrer une inclusion
d’ensembles du type A ⊆ B est en effet claire, on procédera toujours de la façon suivante : ”soit
x ∈ A, alors... (démo)... donc x ∈ B, ce qui prouve que A ⊆ B”. Montrer directement l’égalité
A = B nécessite de raisonner par équivalence, ce qui est souvent plus périlleux (mais parfois possible)
car il faut s’assurer que TOUTES les étapes de la démonstration sont réversibles. Montrons que
C(a) ⊆ C(b). Soit x ∈ C(a). Par définition, cela signifie que aRx. Par hypothèse, on a aRb, donc
(puisque R est symétrique) on a bRa. Par transitivité de R, vu qu’on a à la fois bRa et aRx, on
en déduit que bRx, ce qui par définition montre que x ∈ C(b). Ainsi on a montré que C(a) ⊆ C(b).
Par symétrie de R, on peut dans le raisonnement précédent inverser le rôle de a et b, et donc cela
montre que C(b) ⊆ C(a), ce qui au final montre que C(a) = C(b).

3. Soit (a, b) ∈ E 2 . On va ici raisonner

T par contraposée. En effet, ce qu’on doit montrer est
l’implication non(aRb)
T ⇒ C(a) C(b) = ∅. Par contraposée,
T montrer ce résultat revient à mon-
trer que C(a)
T C(b) 6
= ∅ ⇒ aRb. On suppose que C(a) C(b) 6= ∅, ce qui signifie qu’il existe
x ∈ C(a) C(b), autrement dit il existe un élément x ∈ E appartenant à la fois à C(a) et à C(b).
Comme x ∈ C(a) on a aRx. Comme x ∈ C(b) on a bRx donc xRb par symétrie de R. Par
transitivité de R, vu que aRx et xRb, on a aRb. Par contraposée, on a montré le résultat voulu.

4. Soit C une classe d’équivalence pour R, soit x ∈ E un élément tel que C = C(x). Soit a ∈ C.
Comme a ∈ C(x) on a xRa donc d’après 2. on a C(a) = C(x) = C. On a donc bien C = C(a).

5. Soit C1 et C2 deux classes d’équivalences pour R. Soit a ∈ C1 et b ∈ C2 , d’après 4. on a C1 = C(a)

et C2 = C(b). Deux cas sont possibles :

• soit on a aRb, auquel cas d’après 2. on a C1 = C2 ;

• soit on a non(aRB), auquel cas d’après 3. on a C1 C2 = ∅.
T

Cela prouve ainsi le point 5.

Définition 6. Soit E un ensemble. Soit {Ai }i∈I un ensemble de parties de E. On dit que {Ai }i∈I est
une partition de E si on a
• pour tout i ∈ I on a Ai 6= ∅ ;
[
• E= Ai ;
i∈I

• pour tous i 6= j éléments de I, on a Ai

T
Aj = ∅.
Ainsi, une partition est un ensemble de parties de E, 2 à 2 disjointes, dont la réunion est E tout entier.
Autrement dit, pour tout x ∈ E, il existe un unique i ∈ I tel que x ∈ Ai .
F
Notation : On utilisera le symbole ” ” lorsqu’on effectue une réunion disjointe d’éléments de E.
Autrement
G dit, un ensemble {Ai }i∈I de parties non vides de E est une partition de E si et seulement si
T
E= Ai (la notation utilisée implique qu’on a, pour tous i 6= j éléments de I, Ai Aj = ∅).
i∈I

Quelques exemples :
1. Soit E l’ensemble des gens vivant en France, soit I l’ensemble des lettres de l’alphabet, et pour i ∈ I
notons Ai la sous-partie de E constituée des gens dont le prénom commence par la lettre i. Alors
l’ensemble {Ai }i∈I est une partition de E.

4
 2. Soit E = Z, A0 l’ensemble des entiers relatifs pairs et A1 l’ensemble des entiers relatifs impairs.
Alors {A0 ; A1 } est une partition de E.

3. Soit E l’ensemble des étudiants de L2 Maths de l’année 2020-2021 qui suivent l’UE Algèbre et
Arithmétique, soit I = {1; 2; 3; 4} et Ai l’ensemble des étudiants appartenant au groupe de TD
numéro i en Algèbre et Arithmétique. Alors {A1 ; A2 ; A3 ; A4 } est une partition de E ;

On va maintenant énoncer des résultats reliant la notion de partition et de relation d’équivalence.

Proposition 7. Soit E un ensemble, et R une relation d’équivalence sur E. Notons {Ci }i∈I l’ensemble
des classes d’équivalence pour R. Alors l’ensemble {Ci }i∈I est une partition de E.

Démonstration (type 1) : On utilise ici les résultats montrés dans la proposition 5. D’abord Ton a vu
que deux classes d’équivalence différentes sont disjointes, on en déduit donc que si i 6= j on a Ci Cj = ∅
(point 5 de la proposition 5). De plus, toutes les classes d’équivalences sont non vides (puisque si C est
une classe d’équivalence, par définition il existe a ∈ E tel que C = C(a) [et on a vu que a ∈ C(a)). Enfin,
chaque classe d’équivalence est contenue dans E, ce qui montre que Ci ⊆ E. Réciproquement, soit
[ i∈I
[ [
a ∈ E, alors a ∈ C(a) donc a ∈ Ci . Ainsi pour tout a ∈ E on a a ∈ Ci , ce qui montre que E ⊆ Ci
i∈I [ i∈I i∈I
et par double inclusion on obtient l’égalité Ci = E. On a ainsi montré que la famille {Ci }i∈I constituée
i∈I
de l’ensemble des classes d’équivalences pour R forme une partition de E.
Ce résultat montre que chaque relation d’équivalence fournit une partition de E, constituée de la famille
des classes d’équivalences pour R. Dans la proposition suivante, on va voir que l’inverse est également
vérifié : chaque partition de E correspond à la famille des classes d’équivalences pour une certaine relation
d’équivalence R.

Proposition 8. Soit E un ensemble, et soit {Ai }i∈I une partition de E. On définit la relation R sur
E de la façon suivante : pour tous x, y éléments de E, on a xRy lorsqu’il existe j ∈ I tel que x et y
appartiennent tous deux à Aj . Alors :

1. la relation R est une relation d’équivalence sur E ;

2. la famille des classes d’équivalences pour R est la famille {Ai }i∈I .

La relation R ainsi définie est appelée la relation d’équivalence associée à la partition {Ai }i∈I

Démonstration (type 1) : Montrons d’abord que R est bien une relation d’équivalence sur E.

• R est réflexive : en effet, soit a ∈ E, montrons que aRa. Vu que par hypothèse la famille {Ai }i∈I
forme une partition de E il existe (un unique) i0 ∈ I tel que a ∈ Ai0 , et on a bien sûr aRa (puisque
a et a appartiennent à Ai0 ).

• R est (clairement) symétrique : en effet, soit (a, b) ∈ E 2 , supposons aRb. Alors par définition il
existe j ∈ I tel que a et b appartiennent tous deux à Aj , d’où bRa.

• R est transitive : en effet, soit (a, b, c) ∈ E 3 et supposons aRb et bRc. Par définition, il existe
alors un indice j1 ∈ I tel que a et b appartiennent tous deux à Aj1 , et il existe un indice j2 ∈ I
tel que b et c appartiennent tous deux à Aj2 . Montrons par un raisonnement par l’absurde qu’on a
j1 =Tj2 . Supposons qu’on a j1 6= j2 . AlorsTpuisque la famille {Ai }i∈I forme une partition de E on a
Aj1 Aj2 = ∅. Or par hypothèse b ∈ Aj1 Aj2 , ce qui donne une contradiction. On a donc montré
quej1 = j2 , et donc a, b et c appartiennent tous trois à Aj1 = Aj2 , ce qui entraı̂ne en particulier
aRc et montre la transitivité de R.

5
 Ainsi, R est une relation d’équivalence sur E. De plus, soit a ∈ E, alors la classe d’équivalence de
a est définie par C(a) = {x ∈ E; il existe j ∈ I tel que x et a appartiennent tous deux à Aj }. Or vu
que la famille {Ai }i∈I forme une partition de E il existe un unique i0 ∈ I tel que a ∈ Ai0 . On en déduit
alors que C(a) = {x ∈ E; x ∈ Ai0 } = Ai0 . De plus, pour tout i ∈ I, Ai 6= ∅ par hypothèse et d’après le
raisonnement précédent on a, pour tout b ∈ Ai , Ai = C(b). Ainsi on en déduit que la famille des classes
d’équivalences pour R est la famille {Ai }i∈I .

La fois prochaine, on va voir quelques définitions complémentaires sur les relations d’équivalence puis
entamer le chapitre sur les groupes.