Théorie des ensembles et relations
1. Introduction
On travaille dans un ensemble $E$. Dans les schémas, il sera symbolisé par le grand rectangle.
La notion d’appartenance à un sous-ensemble de $E$, disons $A$, ne se définit pas. On écrit $x \in A$ ou $x \notin A$.
Un ensemble peut être décrit :
- de façon extensive : $A = \left\{ 2; 4; 6 \right\}$ ;
- de façon compréhensive : $A = \left\{ x \in \mathbb N, 2 \le x \le 6 \wedge x \text{pair} \right\}$ ou $E = \left\{ x \in \mathbb N, x~\text{étant pair}\right\}$.
L’ensemble qui ne contient aucun élément est noté $\emptyset$.
2. Liens avec la logique
2.1. Négation
Si $A$ est un sous-ensemble de $E$, $A$ peut être noté :
$$ A = \left\{ x \in E, x \in A \right\}$$
Si $P$ est la proposition «$x \in A$», alors $\overline P$ est «$x \notin A$». $\overline A$ est donc :
$$ \overline A = \left\{ x \in E, x \notin A \right\}$$
Rappels :
| $P$ | $\overline P$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
Remarque : $ \overline {\overline A} = A$.
2.2. Union et intersection
Si $A$ et $B$ sont deux sous-ensembles de $E$, on note :
$$ A \cap B = \left\{ x \in E, x \in A \wedge x \in B \right\} $$ $$ A \cup B = \left\{ x \in E, x \in A \vee x \in B \right\} $$
$\cap$ se lit « inter », et $\cup$ se lit « union ».
Le résultat de ces opérations est un nouvel ensemble.
Rappels :
| $P$ | $Q$ | $P \wedge Q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| $P$ | $Q$ | $P \vee Q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Remarques :
- Attention au « et » du langage courant.
- Comme $P \wedge \overline P = F$, $A$ et $\overline A$ sont disjoints (leur intersection est vide).
- Comme $P \vee \overline P = V$, $A$ et $\overline A$ recouvrent $E$ (leur union vaut $E$).
2.3. Égalité et inclusion
Si $A$ et $B$ sont deux sous-ensembles de $E$, on note :
- $ A = B $ signifie que pour tout élément $x$ de $E$, $x \in A \Leftrightarrow x \in B$. Attention, il ne suffit pas que les « aires » des ensembles soient égales.
- $ A \subset B $ ($A$ inclus dans $B$) signifie que pour tout élément $x$ de $E$, $x \in A \Rightarrow x \in B$.
Le résultat de ces opérations est un booléen.
Schéma
Rappels :
| $P$ | $Q$ | $P \Leftrightarrow Q$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| $P$ | $Q$ | $P \Rightarrow Q$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2.4. Quelques calculs de base
$A$ est un sous-ensemble de $E$. Faire une figure.
Simplifier les expressions suivantes et réfléchir aux éléments neutres ou absorbant de l’intersection et de l’union.
- $\overline E$ et $\overline \emptyset$
- $A \cap E$ et $A \cup E$
- $A \cap \emptyset$ et $A \cup \emptyset$
- Sachant que $A \subset B$, simplifier $A \cap B$ et $A \cup B$.
2.5. Cardinal
Le nombre d’éléments d’un ensemble s’appelle le cardinal de cet ensemble.
Exemples :
- Le cardinal de $\emptyset$ est 0.
- Le cardinal de $\left\{ 2; 4; 6 \right\}$ est 3.
2.6. Subtilités de notation
2.6.1. Entre l’appartenance et l’inclusion
- $x \in E$ se lit « un élément $x$ appartient à $B$ »
- $A \subset E$ se lit « un ensemble $A$ est inclus dans $B$ »
$$ \begin{aligned} \text{élément} &\in \text{ensemble} \\\\ \text{ensemble} &\subset \text{ensemble} \end{aligned}$$
Exemple :
En géométrie, les éléments sont en général des points. Si $M$ est un point, $D$ une droite et $P$ un plan, on peut écrire :
- $M \in D$ ou $M \notin D$, mais pas utiliser $\subset$,
- $M \in P$ ou $M \notin P$, mais pas utiliser $\subset$,
- $D \subset P$ ou $D \not\subset P$, mais pas utiliser $\in$.
2.6.2. Complication avec les ensembles d’ensembles
On note $\mathscr P (E)$ l’ensemble des parties de $E$, c’est-à-dire l’ensemble composé de tous les sous-ensembles de $E$. On a :
$$ A \in \mathscr P (E) \Leftrightarrow A \subset E $$
Exemple : Trouvez tous les sous-ensembles de $\left\{ 1; 2; 3\right\}$.
On a donc $\mathscr P (\left\{1;2;3\right\}) = \left\{\emptyset, \left\{1\right\}, \left\{2\right\}, \left\{3\right\}, \left\{1;2\right\},\left\{1;3\right\},\left\{2;3\right\}, \left\{1;2;3\right\} \right\}$.
Pour tout ensemble $E$, on a (notez l’utilisation de $\in$) :
- $\emptyset \in \mathscr P (E)$
- $E \in \mathscr P (E)$
- pour tout $x$ de $E$, $\left\{ x \right\} \in \mathscr P (E)$
Un ensemble à $n$ éléments a $2^n$ parties.
3. Produit cartésien
3.1. Définition
Le produit cartésien de deux ensembles $E$ et $F$ est l’ensemble de tous les couples $(x,y)$ (dans cet ordre) tels que $x \in E$ et $y \in F$.
On note :
$$E×F = \left\{ (x,y), x \in E \wedge y \in F \right\}$$
On prononce : « E croix F ».
Notation : Si $E=F$, on note $E×E=E^2$.
3.2. Exemples
- Si $E = \left\{ \text{Amédé}, \text{Basile} \right\}$ et
$F = \left\{ \text{Cerise}, \text{Domitille}, \text{Églantine} \right\}$,
alors $E×F = \left\{ (a,c), (a,d), (a,e), (b,c), (b,d), (b,e) \right\}$.
Notez bien qu’il est judicieux d’écrire un tel ensemble en s’organisant et en utilisant un certain ordre. - Si $E=F= \mathbb R$, alors
$E×F = \mathbb R × \mathbb R = \mathbb R ^2 = \left\{ (x;y), x \in \mathbb R, y \in \mathbb R \right\}$.
C’est l’ensemble des coordonnées des points du plan.
3.3. Produit cartésien de plusieurs ensembles
On peut définir le produit cartésien de $n$ ensembles. Ses éléments sont des $n$-uplets, ou tuples.
3.4. Cardinal du produit cartésien
Le cardinal du produit cartésien de deux ensembles est le produit des cardinaux de ces ensembles.
$$\mathbf{card}(E×F) = \mathbf{card}(E) × \mathbf{card}(F)$$
Cette formule se généralise au produit cartésien de plusieurs ensembles.
Attention : le sens des mots « produit » peuvent être différents (produit d’ensembles, produit de nombres). Idem pour les symboles « × ».
4. Relations binaires
4.1. Définition
Une relation binaire $\mathscr R$ d’un ensemble $E$ vers un ensemble $F$ est la donnée de :
- l’ensemble $E$,
- l’ensemble $F$,
- une partie (un sous-ensemble) noté $G$ ou $\Gamma$ de $E×F$, appelée le graphe de $\mathscr R$.
Pour $x \in E$ et $y \in F$, $x \mathscr R y$ signifie $(x,y) \in G$.
Cette année, nous aurons toujours $E=F$, c’est-à-dire :
Une relation binaire $\mathscr R$ sur un ensemble $E$ est la donnée de :
- l’ensemble $E$,
- une partie (un sous-ensemble) noté $G$ ou $\Gamma$ de $E×E$, appelée le graphe de $\mathscr R$.
Pour $x \in E$ et $y \in F$, $x \mathscr R y$ signifie $(x,y) \in G$.
C’est donc très similaire aux graphes.
4.2. Sur l’exemple
Prenons $E = \left\{ a,b,c,d,e \right\}$ et $\mathscr R$ la relation : « … aime le prénom de … ».
4.2.1. Avec un tableau
| a | b | c | d | e |
|---|---|---|---|---|
| b,c | a | a,d,e | b,c,d |
4.2.2. Avec un diagramme sagittal
Dans le cas ou $F = E$, ne dessiner qu'un seul ensemble.
4.2.3. Avec une matrice
4.2.4. Avec le graphe de la relation
Rappel :
$$ \begin{aligned} E×E = \left\{ \right. & (a,a), (a,b), ... , (a,e), \\\\ & (b,a), (b,b), ... , (b,e), \\\\ & ... \\\\ & (e,a), (e,b), ... , (e,e) \left. \right\} \end{aligned}$$
$$ \begin{aligned} G = \left\{ \right. & (a,b), (a,c), \\\\ & (b,a), \\\\ & (d,a), (d,d), (d,e), \\\\ & (e,b), (e,c), (e,d) \left. \right\} \end{aligned}$$
Que l’on peut bien sûr écrire sur une seule ligne.
4.3. Autres exemples
Représentez chacun des exemples suivants avec :
- un tableau
- un diagramme sagittal
- une matrice
- un graphe
Les exemples classiques :
- Égalité dans $E$ :
$x \mathscr R y \Leftrightarrow x=y$ - Inégalité large dans $\mathbb R$ :
$x \mathscr R y \Leftrightarrow x \ge y$ - Inégalité stricte dans $\mathbb R$ :
$x \mathscr R y \Leftrightarrow x < y$ - Divisibilité dans $\mathbb N ^*$ :
$x \mathscr R y \Leftrightarrow x ~\text{divise}~ y$ - Congruence dans $\mathbb N ^*$ :
$x \mathscr R y \Leftrightarrow x \equiv y [n]$ - Si $P$ est un plan géométrique et $E = \mathscr P (P)$ (ensembles de $P$),
$A \mathscr R B \Leftrightarrow A \subset B$
4.4. Propriétés des relations binaires
4.4.1. Réflexivité
$\mathscr R$ est dite réflexive si $\forall x \in E, x \mathscr R x$.
Autrement dit, si tout élément est en relation avec lui-même.
Parmi les exemples précédents, seule $<$ ne l’est pas.
4.4.2. Symétrie
$\mathscr R$ est dite symétrique si $\forall (x,y) \in E^2, x \mathscr R y \Rightarrow y \mathscr R x$.
Autrement dit, si un premier élément est en relation avec un second, alors le second est aussi en relation avec le premier.
Parmi les exemples précédents, seules $=$ et $\equiv$ le sont.
4.4.3. Antisymétrie
$\mathscr R$ est dite antisymétrique si $\forall (x,y) \in E^2, \left( x \mathscr R y \right) \wedge \left( y \mathscr R x \right) \Rightarrow x = y$.
Autrement dit, si deux éléments sont en relation dans les deux sens, alors c’était en fait le même élément.
Parmi les exemples précédents, $<$ et $\equiv$ ne le sont pas.
En effet, cela n’a pas vraiment de sens pour $<$ et on peut trouver des contre-exemples pour $\equiv$.
D’un autre côté, $\ge$ l’est car si $x \ge y$ et $y \ge x$, alors $x=y$.
Démontrez que $\subset$ l’est aussi.
4.4.4. Transitivité
$\mathscr R$ est dite transitive si $\forall (x,y,z) \in E^3, \left( x \mathscr R y \right) \wedge \left( y \mathscr R z \right) \Rightarrow x \mathscr R z$.
Autrement dit, si un premier élément est en relation avec un deuxième, et si ce deuxième est en relation avec un troisième, alors le premier est aussi en relation avec le troisième.
Parmi les exemples précédents, toutes le sont.
4.4.5. Point méthode
Pour montrer qu’une relation est…
- réflexive : un élément suffit, comme face à un miroir qui réfléchit ;
- symétrique : il faut deux éléments ;
- antisymétrique (ce n’est pas le contraire de la symétrie) : il faut deux éléments ;
- TRansitive : il faut TRois éléments.
4.5. Relations d’équivalence, relations d’ordre
$\mathscr R$ est une relation d’équivalence si elle est :
- réflexive
- symétrique
- transivite
C’est le cas de $=$ et de $\equiv$.
$\mathscr R$ est une relation d’ordre si elle est :
- réflexive
- antisymétrique
- transivite
Elles le sont toutes sauf $<$ et $\equiv$.
4.6. Ordre total, ordre partiel
Si $\mathscr R$ est une relation d’ordre, on dit que l’ordre est total si $$\forall (x,y) \in \mathbb E ^2, \left( x \mathscr R y \right) \vee \left( y \mathscr R x \right)$$
Exemple : dans la cour de récréation, quand deux enfants comparent leur taille, ils s’attendent à ce que l’un des deux soit le plus grand.
Méthode : Pour nier le caractère total d’une relation d’ordre, il faut nier un « quelque soit… et… ». On cherche donc un contre-exemple : « il existe… ou… ».
Quart d’heure philosophique : on ne peut pas toujours classer les êtres humains !
5. Fonctions et applications
Soit deux ensembles $E$ et $F$.
$E$ sera souvent appelé « ensemble de départ » et $F$ « ensemble d’arrivée ».
5.1. Définitions
Une fonction de $E$ dans $F$ est la donnée d’un ensemble $\Gamma$ de couples $(x,y)$ inclus dans $E×F$ tel que pour chaque $x$ de $E$ il n’y a pas plus d’un couple $(x,y)$.
Une application est une fonction pour laquelle chaque $x$ de $E$ a exactement un couple $(x,y)$.
Dans les deux cas, si la fonction ou l’application est notée $f$ et si $(x,y)$ est dans $\Gamma$, on peut noter $f(x)=y$, et on dira « l’image de $x$ est $y$ » (noter l’article défini).
De plus, si $y$ est un élément de $F$, on appelle un antécédent de $y$ tout $x$ de $E$ tel que $f(x) = y$.
Exemple
Prenons $E = \left\{ a,b,c,d,e \right\}$, $F = \left\{ f,g,h,i \right\}$ et $\Gamma = \left\{ (a,g);(b,f);(c,g);(d,i);(e,g) \right\}$.
(Schéma à faire)
- $a$ a pour image $g$
- $b$ a pour image $f$
- $f$ a pour antécédent $b$
- $g$ a pour antécédents $a$, $c$ et $e$
- $h$ n’a pas d’antécédent
5.2. Ensemble image et ensemble image réciproque
Si $A \subset E$ ($A$ est un sous-ensemble de $E$), on appelle image de $A$ l’ensemble noté $f(A)$ défini par :
$$f(A) = \left\{ y \in F, \exists x \in A, f(x)=y \right\}$$
Si $B \subset F$ ($B$ est un sous-ensemble de $F$), on appelle image réciproque de $B$ l’ensemble noté $f^{-1}(B)$ défini par :
$$f^{-1}(B) = \left\{ x \in E, \exists y \in B, f(x)=y \right\}$$
Sur l’exemple
- $f(A) = B$
- $f(\left\{ c;d;e \right\}) = \left\{ g;i \right\}$
- $f^{-1}(B) = \left\{ g;i \right\}$
Remarque
$f^{-1}(\left\{ y \right\})$ est l’ensemble des antécédents de $y$.
Dans l’exemple, on a $f^{-1}(\left\{ h \right\}) = \emptyset$.
6. Injection, surjection et bijection
6.1. Injectivité
$f$ est une application injective si :
- deux éléments distincts de $E$ ont des images distinctes
- un élément de $F$ a au plus un antécédent
Autrement dit,
- $x \neq x' \Leftrightarrow f(x) \neq f(x')$
- $f(x) = f(x') \Leftrightarrow x=x'$
On remarque ce ces deux propositions sont contraposées.
6.2. Surjectivité
$f$ est une application surjective si tout élément de $F$ a au moins un antécédent.
Autrement dit,
$\forall y \in F, \exists x \in E ~\text{tel que}~ f(x) = y$
6.3. Bijectivité
$f$ est une application bijective si elle est à la fois injective et surjective, c’est-à-dire si tout élément de $F$ a exactement un antécédent.
7. Composition
À suivre…