Éléments de la Théorie des Ensembles

---

A. Produit Cartésien de 2 Ensembles

Définition

Le produit cartésien d'un ensemble $E$ par un ensemble $F$ est l'ensemble de tous les couples $(a ; b)$ où $a$ appartient à $E$ et $b$ appartient à $F$.

$E \times F = \{(a, b) \mid a \in E \text{ et } b \in F\}$

Exemple

Soit $E = \{1 ; 2\}$ et $F = \{1 ; 2 ; 3\}$

$E \times F = \{(1,1) ; (1,2) ; (1,3) ; (2,1) ; (2,2) ; (2,3)\}$

$F \times E = \{(1,1) ; (1,2) ; (2,1) ; (2,2) ; (3,1) ; (3,2)\}$

Remarque : $E \times F \neq F \times E$ (le produit cartésien n'est pas commutatif)

Propriété

$E$ et $F$ étant finis :

$\text{Card}(E \times F) = \text{Card}(E) \times \text{Card}(F)$

Card = nombre d'éléments

---

B. Relation Binaire

Définition

Une relation binaire $\mathcal{R}$ d'un ensemble $E$ vers $F$ est définie par la donnée de :

• l'ensemble de départ $E$
• l'ensemble d'arrivée $F$
• une partie $G$ du produit cartésien $E \times F$ (appelée graphe de la relation binaire)

Notation

$x \mathcal{R} y \quad \text{où } x \in E,\ y \in F$

signifie que le couple $(x, y)$ appartient à $G$.

Cas particulier : $E = F$ (relation binaire sur un même ensemble)

---

C. Propriétés d'une Relation Binaire (cas $E = F$)

Soit $\mathcal{R}$ une relation binaire sur $E$ (i.e. $E = F$) :

---

D. Exemples et Diagrammes Sagittaux

Exemple 1

Soit $E = \{1 ; 2 ; 3 ; 4\}$, relation $\mathcal{R}$ définie par :

$G = \{(1,1) ; (1,2) ; (2,1) ; (3,3) ; (3,4) ; (4,3) ; (2,2) ; (4,4)\}$

Représenter le diagramme sagittal de $\mathcal{R}$.

Analyse des propriétés :

• $\{(1,1) ; (2,2) ; (3,3) ; (4,4)\} \subset G$ → $\mathcal{R}$ est réflexive
• $(1,2)$ et $(2,1)$ sont dans $G$, $(3,4)$ et $(4,3)$ sont dans $G$ → $\mathcal{R}$ est symétrique
• $\forall x, y, z \in E^3,\ (x \mathcal{R} y) \wedge (y \mathcal{R} z) \Rightarrow x \mathcal{R} z$ → $\mathcal{R}$ est transitive

Exemple 2

Soit $E = \{0 ; 1 ; 4 ; 7 ; 8 ; 11\}$

$x \mathcal{R} y \iff x + y \text{ est pair}$

(Le diagramme sagittal montre deux groupes : les nombres pairs entre eux et les impairs entre eux, tous reliés dans leur groupe.)

---

E. Relations d'Équivalence et d'Ordre

Relation d'Équivalence

Définition : Une relation binaire $\mathcal{R}$ définie sur un ensemble $E$ non vide est une relation d'équivalence ssi elle est :

• réflexive
• symétrique
• transitive

Relation d'Ordre

Définition : Une relation binaire est une relation d'ordre ssi elle est :

• réflexive
• transitive
• antisymétrique

Classe d'Équivalence

La classe d'équivalence de $E$ est l'ensemble des éléments de $E$ qui sont en relation d'équivalence entre eux.

---

F. Exemple : Relation d'Équivalence sur $\mathbb{Z}$

Exemple 4

On définit sur $\mathbb{Z}^2$ la relation $\mathcal{R}$ par :

$\forall (x, y) \in \mathbb{Z}^2,\quad x \mathcal{R} y \iff x^2 \equiv y^2 \pmod{5}$

Vérification des propriétés :

Réflexivité :
$x^2 \equiv x^2 \pmod{5} \implies x \mathcal{R} x \quad \checkmark$

Symétrie :
$\forall (x, y) \in \mathbb{Z}^2,\quad x \mathcal{R} y \implies y \mathcal{R} x \quad \checkmark$

Vérification : $12 \equiv 2 \pmod{5}$ et $2 \equiv 12 \pmod{5}$

Transitivité :
$\forall (x, y, z) \in \mathbb{Z}^3,\quad (x \mathcal{R} y) \wedge (y \mathcal{R} z) \implies x \mathcal{R} z \quad \checkmark$

Conclusion : $\mathcal{R}$ est réflexive, symétrique et transitive → $\mathcal{R}$ est une relation d'équivalence.

Classes d'équivalence

Calcul des restes de $n^2 \pmod{5}$ :

Les 3 classes d'équivalence sont : $\{0\}$, $\{1\}$, $\{4\}$

(i.e. les éléments dont le carré est congru à $0$, $1$ ou $4$ modulo $5$)