1) Produit cartésien de deux ensembles.
Définition.
Si $E$ et $F$ sont des ensembles. On note $E \times F$ l'ensemble des couples $(x,y)$ avec $x \in E$ et $y \in F$.
On représente un couple $(x,y)$ par un point de coordonnées $x$ et $y$.
Exemple :
Si on pose $E = \{1,2,3\}$ et $F = \{-1,13\}$ alors $E \times F = \{(1,-1)$ ; $(1,13)$ ; $(2,-1)$ ; $(2,13)$ ; $(3,-1)$ ; $(3,13)\}$.
Remarque :
- $(2,3) \neq (3,2)$ et il est possible que l'abscisse soit égale à l'ordonnée c'est-à-dire on peut avoir le couple $(7,7)$. Dans un couple, l'ordre (des coordonnées) est important et il y a des répétitions (des coordonnées).
- Ne pas confondre un couple qui est un élément et une paire qui est un ensemble ayant deux éléments : $(2,3) \neq \{2,3\}$.
Définition.
Si $E=F$ on note $E \times E$ par $E^2$.
On a donc $E^2 = \{(x,y) \mid x\in E \mbox{ et }y\in E\}$.
2) Relation sur un ensemble.
Définition.
Soit $E$ un ensemble. Une relation sur $E$ est une partie $R$ de $E^2$.
Si $(a,b) \in R$, on dit que $a$ est en relation avec $b$ et on note $a R b$.
Exemple :
$E = \{1,2,3\}$. On définit $R = \{(1,1)$ ; $(2,2)$ ; $(1,2)$ ; $(2,1)$ ; $(1,3)$ ; $(3,1)\}$.
On a $1$ est en relation avec $1$ ce que l'on note par $1 R 1$.
On a de même $2 R 2$, $1 R 2$, $2 R 1$, $1 R 3$ et $3 R 1$.
$3$ n'est pas en relation avec $3$ ; $2$ n'est pas en relation avec $3$ et $3$ n'est pas en relation avec $2$.
Exemple :
La relation divise sur ${\Bbb N}$. On dit que $a$ divise $b$ et on note $a \mid b$ s'il existe un entier $c$ tel que $b = ac$. Cela définit une relation $R$ sur ${\Bbb N}^2$.
On a $R = \{(a,b) \in {\Bbb N}^2 \mid a \mbox{ divise }b\}$.
Par exemple, $3 \mid 6$ donc $3$ est en relation avec $6$ mais $3$ n'est pas en relation avec $5$ car $3$ ne divise par $5$.
Définition.
Soit $R$ une relation sur l'ensemble $E$.
- $R$ est réflexive si : $\forall x \in E$, $x R x$.
- $R$ est symétrique si : $\forall (x,y) \in E^2$, $x R y \Rightarrow y R x$.
- $R$ est antisymétrique si : $\forall (x,y) \in E^2$, $x R y \mbox{ et } y R x \Rightarrow x = y$.
- $R$ est transitive si : $\forall (x,y,z) \in E^3$, $(x R y \mbox{ et } y R z) \Rightarrow x = z$.
Exemples :
On reprend l'exemple $E = \{1,2,3\}$ avec $R = \{(1,1)$ ; $(2,2)$ ; $(1,2)$ ; $(2,1)$ ; $(1,3)$ ; $(3,1)\}$. Cette relation n'est pas réflexive car $(3,3) \notin R$.
$R$ n'est pas transitive car $3 R 1$ et $1 R 3$ mais $(3,3) \notin R$ c'est-à-dire $3$ n'est pas en relation avec $3$.
$R$ n'est pas antisymétrique car on a par exemple $1 R 2$ et $2 R 1$ mais $1 \neq 2$.
$R$ est symétrique car comme on a $1 R 2$ et $2 R 1$ d'une part et $1 R 3$ et $3 R 1$ d'autre part, on a bien $\forall (x,y) \in E^2$, $x R y \Rightarrow y R x$.
Reprenons le deuxième exemple, $R = \{(a,b) \in {\Bbb N}^2 \mid a \mbox{ divise }b\}$. Cette relation est réflexive, antisymétrique et transitive.
3) Relation d'ordre et d'équivalence.
- $R$ est une relation d'ordre si $R$ est réflexive, antisymétrique et transitive.
- $R$ est une relation d'équivalence si $R$ est réflexive, symétrique et transitive.
Exemple :
La relation << divise >> sur ${\Bbb N}$ est une relation d'ordre.
Soit $E = \{1,2,3\}$ muni de la relation $R = \{(1,1)$ ; $(2,2)$ ; $(3,3)$ ; $(1,2)$ ; $(2,1)$ ; $(1,3)$ ; $(3,1)\}$. Cette relation est une relation d'équivalence.
Définition.
Soit $E$ un ensemble muni d'une relation d'équivalence. Soit $x \in E$. La classe d'équivalence de $x$ est l'ensemble $\{y \in E \mid y R x\}$.
Dans l'exemple précédent, la classe d'équivalence de $1$ est $\{1,2,3\}$.
