Ensembles
Notions fondamentales
La théorie des ensembles est une branche fondamentale des mathématiques qui traite des collections d’objets. Voici les concepts de base :
- Ensemble : Un ensemble est une collection bien définie d’objets, appelés éléments. « Bien définie » signifie qu’il existe un critère clair et non ambigu pour déterminer si un objet appartient ou non à l’ensemble.
- Élément : Les objets qui composent un ensemble.
- Appartenance (\( \in \)) : Si un objet \(x\) est un élément d’un ensemble \(A\), on dit que \(x\) appartient à \(A\), et on note \(x \in A\). Dans le cas contraire, on note \(x \notin A\).
- Exemple : Si \(A = \{1, 2, 3\}\), alors \(1 \in A\), mais \(4 \notin A\).
- Inclusion (\( \subset \)) : Un ensemble \(A\) est inclus dans un ensemble \(B\) (ou est un sous-ensemble de \(B\)), si tous les éléments de \(A\) sont aussi des éléments de \(B\). On note \(A \subset B\). Formellement : \(A \subset B \iff (\forall x, x \in A \Rightarrow x \in B)\).
- Exemple: Si \(A = \{1, 2\}\) et \(B = \{1, 2, 3\}\), alors \(A \subset B\).
- Note : L’inclusion n’exclut pas l’égalité. Si \(A \subset B\) et \(B \subset A\), alors \(A = B\).
- Égalité d’ensembles : Deux ensembles \(A\) et \(B\) sont égaux si et seulement s’ils contiennent exactement les mêmes éléments. Formellement : \(A = B \iff (A \subset B \text{ et } B \subset A)\).
- Exemple: Si \(A = \{1, 2, 3\}\) et \(B = \{3, 1, 2\}\), alors \(A = B\) (l’ordre des éléments n’importe pas).
- Ensemble vide (\( \emptyset \) ou \(\{\}\)) : L’ensemble vide est l’unique ensemble qui ne contient aucun élément. Il est un sous-ensemble de tout ensemble.
- Singleton : Un ensemble contenant exactement un seul élément. Par exemple, \(\{5\}\) est un singleton.
- Paire : Un ensemble contenant exactement deux éléments. Par exemple, \(\{a, b\}\) est une paire.
- n-uplet : Une généralisation de la notion de paire. Un n-uplet est une séquence ordonnée de \(n\) éléments. Par exemple, \((a, b, c)\) est un triplet (3-uplet). La différence principale avec un ensemble est que l’ordre compte, et les répétitions sont significatives. \(\{1, 1, 2\}\) est égal à \(\{2, 1, 1\}\) et à \(\{1,2\}\) en tant qu’ensembles, mais en tant que triplets (3-uplet), \((1, 1, 2)\), \((1, 2, 1)\) et\((2,1,1)\) sont distinct.
Opérations sur les ensembles
Plusieurs opérations peuvent être effectuées sur les ensembles :
- Union (\( \cup \)) : L’union de deux ensembles \(A\) et \(B\), notée \(A \cup B\), est l’ensemble de tous les éléments qui appartiennent à \(A\) ou à \(B\) (ou aux deux). Formellement : \(A \cup B = \{x \mid x \in A \text{ ou } x \in B\}\).
- Exemple: Si \(A = \{1, 2, 3\}\) et \(B = \{3, 4, 5\}\), alors \(A \cup B = \{1, 2, 3, 4, 5\}\).
- Intersection (\( \cap \)) : L’intersection de deux ensembles \(A\) et \(B\), notée \(A \cap B\), est l’ensemble de tous les éléments qui appartiennent à la fois à \(A\) et à \(B\). Formellement : \(A \cap B = \{x \mid x \in A \text{ et } x \in B\}\).
- Exemple: Si \(A = \{1, 2, 3\}\) et \(B = \{3, 4, 5\}\), alors \(A \cap B = \{3\}\).
- Si \(A \cap B = \emptyset\), on dit que \(A\) et \(B\) sont disjoints.
- Différence (\(\setminus\) ou \(-\)) : La différence entre \(A\) et \(B\), notée \(A \setminus B\) (ou \(A – B\)), est l’ensemble des éléments qui appartiennent à \(A\) mais pas à \(B\). Formellement : \(A \setminus B = \{x \mid x \in A \text{ et } x \notin B\}\).
- Exemple: Si \(A = \{1, 2, 3\}\) et \(B = \{3, 4, 5\}\), alors \(A \setminus B = \{1, 2\}\).
- Note: \(A \setminus B\) est différent de \(B \setminus A\).
- Différence symétrique (\( \Delta \)) : La différence symétrique de deux ensembles \(A\) et \(B\), notée \(A \Delta B\), est l’ensemble des éléments qui appartiennent à \(A\) ou à \(B\), mais pas à leur intersection. Formellement: \(A \Delta B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\).
- Exemple: Si \(A = \{1, 2, 3\}\) et \(B = \{3, 4, 5\}\), alors \(A \Delta B = \{1, 2, 4, 5\}\).
- Complémentaire : Si \(A\) est un sous-ensemble d’un ensemble universel \(U\), le complémentaire de \(A\) (dans \(U\)), noté \(A^c\) ou \(\overline{A}\) ou \(C_U A\) , est l’ensemble de tous les éléments de \(U\) qui n’appartiennent pas à \(A\). Formellement: \(A^c = \{x \in U \mid x \notin A\} = U \setminus A\).
- Exemple: Si \(U = \{1, 2, 3, 4, 5, 6\}\) et \(A = \{1, 2, 3\}\), alors \(A^c = \{4, 5, 6\}\).
Ensemble des parties
Ensemble des parties (\( \mathcal{P}(E) \)) : L’ensemble des parties d’un ensemble \(E\), noté \(\mathcal{P}(E)\), est l’ensemble de tous les sous-ensembles de \(E\), y compris l’ensemble vide et \(E\) lui-même. Formellement: \(\mathcal{P}(E) = \{A \mid A \subset E\}\).
- Exemple: Si \(E = \{1, 2\}\), alors \(\mathcal{P}(E) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\).
- Si \(E\) a \(n\) éléments, alors \(\mathcal{P}(E)\) a \(2^n\) éléments.
Voici un tableau récapitulatif des notations pour l’ensemble des parties, avec des exemples concrets :
| Ensemble E | Notation de l’ensemble des parties | Ensemble des parties \(\mathcal{P}(E)\) | Cardinalité de \(\mathcal{P}(E)\) |
|---|---|---|---|
| \(E = \{a\}\) | \(\mathcal{P}(E)\) | \(\{\emptyset, \{a\}\}\) | \(2^1 = 2\) |
| \(E = \{a, b\}\) | \(\mathcal{P}(E)\) | \(\{\emptyset, \{a\}, \{b\}, \{a, b\}\}\) | \(2^2 = 4\) |
| \(E = \{a, b, c\}\) | \(\mathcal{P}(E)\) | \(\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}\) | \(2^3 = 8\) |
| \(E = \emptyset\) | \(\mathcal{P}(E)\) | \(\{ \emptyset \}\) | \(2^0 = 1\) |
Cardinalité
La cardinalité d’un ensemble mesure sa « taille », c’est-à-dire le nombre d’éléments qu’il contient. On distingue les ensembles finis et infinis, et parmi les infinis, les dénombrables et non dénombrables.
- Cardinal d’un ensemble fini : Si \(A\) est un ensemble fini, son cardinal, noté \(|A|\) ou \(\text{card}(A)\), est le nombre d’éléments de \(A\).
- Exemple : Si \(A = \{a, b, c\}\), alors \(|A| = 3\).
- Cardinal d’un ensemble infini : Pour les ensembles infinis, la notion de « nombre d’éléments » est plus subtile. On utilise des bijections pour comparer la taille des ensembles. Deux ensembles \(A\) et \(B\) ont la même cardinalité s’il existe une bijection (une fonction injective et surjective) de \(A\) vers \(B\).
- Ensemble dénombrable : Un ensemble est dénombrable s’il a la même cardinalité que l’ensemble des entiers naturels \(\mathbb{N}\). Cela signifie qu’on peut « numéroter » les éléments de l’ensemble avec des entiers naturels (il existe une bijection entre l’ensemble et \(\mathbb{N}\)).
- Exemples : \(\mathbb{N}\), \(\mathbb{Z}\) (l’ensemble des entiers relatifs), \(\mathbb{Q}\) (l’ensemble des nombres rationnels) sont dénombrables.
- Un ensemble infini qui n’est pas dénombrable est dit non dénombrable.
- Ensemble non dénombrable: Un ensemble est dit non dénombrable s’il est infini et qu’il n’existe pas de bijection entre cet ensemble et l’ensemble des entiers naturels \( \mathbb{N} \).
- L’exemple le plus célèbre est l’ensemble des nombres réels, \( \mathbb{R} \).
- Théorème de Cantor : Ce théorème fondamental stipule que pour tout ensemble \(A\), l’ensemble des parties de \(A\), noté \(\mathcal{P}(A)\), a une cardinalité strictement supérieure à celle de \(A\). Formellement : \(|A| < |\mathcal{P}(A)|\).
- Conséquence importante : Il n’existe pas de « plus grand cardinal ». Il y a une infinité de cardinaux infinis différents. Par exemple, \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \dots\)
- Démonstration (diagonale de Cantor) : La preuve la plus connue utilise l’argument diagonal de Cantor. Pour montrer que \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\), on suppose qu'il existe une bijection entre \(\mathbb{N}\) et \(\mathcal{P}(\mathbb{N})\), puis on construit un sous-ensemble de \(\mathbb{N}\) qui ne peut pas être associé à un entier naturel par cette bijection, ce qui contredit l'hypothèse de départ. Le même argument peut être adapté pour montrer que \(|A| < |\mathcal{P}(A)|\) pour tout ensemble \(A\).
Axiome du choix
Énoncé : L’axiome du choix est un axiome de la théorie des ensembles qui a des implications importantes en mathématiques. Il existe plusieurs formulations équivalentes, mais l’une des plus courantes est la suivante :
Étant donné une famille \((E_i)_{i \in I}\) d’ensembles non vides et deux à deux disjoints, il existe un ensemble \(C\) contenant exactement un élément de chaque \(E_i\). Autrement dit, on peut « choisir » un élément dans chaque ensemble de la famille.
Formulation équivalente (avec une fonction de choix): Pour toute famille \((E_i)_{i\in I}\) d’ensembles non vides (pas nécessairement disjoints), il existe une fonction \(f\), appelée fonction de choix, définie sur \(I\) telle que pour tout \(i \in I\), \(f(i) \in E_i\).
Implications :
- L’axiome du choix semble intuitif, mais il a des conséquences non intuitives et parfois controversées.
- Il est indépendant des autres axiomes de la théorie des ensembles ZFC (Zermelo-Fraenkel avec l’axiome du choix). Cela signifie qu’on ne peut ni le prouver ni le réfuter à partir des autres axiomes.
- Il est utilisé dans de nombreuses démonstrations en mathématiques, notamment en analyse et en topologie.
Lemme de Zorn : Le lemme de Zorn est une conséquence de l’axiome du choix (en fait, il lui est équivalent). C’est un outil puissant pour démontrer l’existence d’objets mathématiques.
Énoncé du lemme de Zorn : Soit \((E, \leq)\) un ensemble ordonné non vide. Si toute partie non vide totalement ordonnée de \(E\) (aussi appelée chaîne) admet un majorant dans \(E\), alors \(E\) admet un élément maximal.
- Ensemble ordonné: Un ensemble muni d’une relation d’ordre (réflexive, antisymétrique et transitive).
- Partie totalement ordonnée (chaîne): Un sous-ensemble où deux éléments quelconques sont comparables par la relation d’ordre.
- Majorant: Soit \(A\) une partie de \(E\). Un élément \(m \in E\) est un majorant de A si, pour tout \(x \in A\), \(x \leq m\).
- Élément maximal: Un élément \(m \in E\) est dit maximal si, pour tout \(x \in E\), \(m \leq x\) implique \(x = m\). (Il n’y a pas d’élément « strictement plus grand » que \(m\)).
Exemple d’utilisation : Le lemme de Zorn est souvent utilisé pour montrer l’existence de bases dans les espaces vectoriels de dimension infinie.
Types d’ensembles
- Ensembles finis : Un ensemble est fini s’il existe une bijection entre cet ensemble et un ensemble de la forme \(\{1, 2, …, n\}\) pour un certain entier naturel \(n\).
- Ensembles infinis : Un ensemble qui n’est pas fini.
- Ensembles ordonnés : Un ensemble \(E\) muni d’une relation d’ordre \(\leq\). Une relation d’ordre est une relation binaire qui est réflexive (\(x \leq x\)), antisymétrique (\(x \leq y\) et \(y \leq x\) implique \(x = y\)), et transitive (\(x \leq y\) et \(y \leq z\) implique \(x \leq z\)).
- Exemple : \((\mathbb{R}, \leq)\) (les nombres réels avec l’ordre usuel) est un ensemble ordonné.
- Exemple : \((\mathcal{P}(A), \subset)\) (l’ensemble des parties d’un ensemble \(A\) avec l’inclusion) est un ensemble ordonné.
- Ensembles bien ordonnés : Un ensemble ordonné \((E, \leq)\) est bien ordonné si toute partie non vide de \(E\) admet un plus petit élément.
- Exemple : \((\mathbb{N}, \leq)\) est bien ordonné.
- Contre-exemple : \((\mathbb{Z}, \leq)\) n’est pas bien ordonné (par exemple, \(\mathbb{Z}\) lui-même n’a pas de plus petit élément).
- Contre-exemple : \((]0, 1], \leq)\) (l’intervalle ouvert-fermé des réels entre 0 et 1) n’est pas bien ordonné (par exemple, \(]0, 1]\) lui-même n’a pas de plus petit élément).
- Principe de bon ordre : Tout ensemble peut être bien ordonné. Ce principe est équivalent à l’axiome du choix.
Applications
Notions fondamentales
Une application (ou fonction) \(f\) d’un ensemble \(E\) vers un ensemble \(F\) est une correspondance qui associe à chaque élément \(x\) de \(E\) un unique élément \(y\) de \(F\). On note cela \(f : E \to F\).
- Domaine : L’ensemble de départ \(E\) est appelé le domaine de \(f\).
- Codomaine : L’ensemble d’arrivée \(F\) est appelé le codomaine de \(f\).
- Image : L’image d’un élément \(x \in E\) par \(f\), notée \(f(x)\), est l’unique élément \(y \in F\) associé à \(x\) par la fonction \(f\). L’image de l’ensemble \(E\) par \(f\), notée \(f(E)\) ou \(\text{Im}(f)\), est l’ensemble de toutes les images des éléments de \(E\) : \(f(E) = \{f(x) \mid x \in E\}\). \(f(E)\) est un sous-ensemble de \(F\).
- Antécédent : Si \(f(x) = y\), alors \(x\) est un antécédent de \(y\) par \(f\). Un élément \(y\) de \(F\) peut avoir un ou plusieurs antécédents, ou n’en avoir aucun.
- Image réciproque : Soit \(B\) un sous-ensemble de \(F\). L’image réciproque de \(B\) par \(f\), notée \(f^{-1}(B)\), est l’ensemble de tous les antécédents des éléments de \(B\) : \(f^{-1}(B) = \{x \in E \mid f(x) \in B\}\). Notez que \(f^{-1}(B)\) est un sous-ensemble de \(E\), et que l’écriture \(f^{-1}\) dans ce contexte ne signifie pas nécessairement que \(f\) est une bijection (voir plus loin).
- Exemple : Soit \(f : \mathbb{R} \to \mathbb{R}\) définie par \(f(x) = x^2\).
- Domaine : \(\mathbb{R}\)
- Codomaine : \(\mathbb{R}\)
- Image : \(f(\mathbb{R}) = [0, +\infty[\) (l’ensemble des réels positifs ou nuls).
- Antécédents de 4 : 2 et -2.
- Image réciproque de \([1, 4]\) : \(f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]\).
- Image réciproque de \([-1, 4]\) : \(f^{-1}([-1, 4]) = [-2, 2]\).
- Image réciproque de \([-2, -1]\) : \(f^{-1}([-2, -1]) = \emptyset \).
Types d’applications
- Application injective (ou injection) : Une application \(f : E \to F\) est injective si des éléments distincts de \(E\) ont des images distinctes dans \(F\). Formellement : \(\forall x_1, x_2 \in E, \text{ si } x_1 \neq x_2, \text{ alors } f(x_1) \neq f(x_2)\). De manière équivalente : \(\forall x_1, x_2 \in E, \text{ si } f(x_1) = f(x_2), \text{ alors } x_1 = x_2\).
- Exemple : \(f : \mathbb{R} \to \mathbb{R}, f(x) = 2x + 1\) est injective.
- Contre-exemple : \(f : \mathbb{R} \to \mathbb{R}, f(x) = x^2\) n’est pas injective (car \(f(-1) = f(1) = 1\)).
- Application surjective (ou surjection) : Une application \(f : E \to F\) est surjective si tout élément de \(F\) a au moins un antécédent dans \(E\). Formellement : \(\forall y \in F, \exists x \in E \text{ tel que } f(x) = y\). De manière équivalente : \(f(E) = F\).
- Exemple : \(f : \mathbb{R} \to [0, +\infty[ , f(x) = x^2\) est surjective.
- Contre-exemple : \(f : \mathbb{R} \to \mathbb{R}, f(x) = x^2\) n’est pas surjective (car les réels négatifs n’ont pas d’antécédents).
- Application bijective (ou bijection) : Une application \(f : E \to F\) est bijective si elle est à la fois injective et surjective. Cela signifie que chaque élément de \(F\) a exactement un antécédent dans \(E\).
- Exemple : \(f : \mathbb{R} \to \mathbb{R}, f(x) = 2x + 1\) est bijective.
- Permutation : Une permutation d’un ensemble \(E\) est une bijection de \(E\) vers \(E\).
Composition d’applications
Soient \(f : E \to F\) et \(g : F \to G\) deux applications. La composée de \(f\) et \(g\), notée \(g \circ f\), est l’application de \(E\) vers \(G\) définie par \((g \circ f)(x) = g(f(x))\) pour tout \(x \in E\).
- Associativité : La composition d’applications est associative. Cela signifie que si nous avons trois applications \(f : E \to F\), \(g : F \to G\), et \(h : G \to H\), alors \((h \circ g) \circ f = h \circ (g \circ f)\). On peut donc écrire \(h \circ g \circ f\) sans ambiguïté.
- Exemple : Soient \(f : \mathbb{R} \to \mathbb{R}, f(x) = x^2\) et \(g : \mathbb{R} \to \mathbb{R}, g(x) = x + 1\). Alors \((g \circ f)(x) = g(f(x)) = g(x^2) = x^2 + 1\), et \((f \circ g)(x) = f(g(x)) = f(x + 1) = (x + 1)^2 = x^2 + 2x + 1\). Notez que \(g \circ f \neq f \circ g\) en général.
Application réciproque
Soit \(f : E \to F\) une application bijective. L’application réciproque de \(f\), notée \(f^{-1}\), est l’application de \(F\) vers \(E\) qui associe à chaque élément \(y\) de \(F\) son unique antécédent \(x\) par \(f\). Autrement dit, \(f^{-1}(y) = x\) si et seulement si \(f(x) = y\).
- Existence et propriétés:
- Une application admet une application réciproque si et seulement si elle est bijective.
- Si \(f\) est bijective, alors \(f^{-1}\) est également bijective.
- \((f^{-1})^{-1} = f\).
- \(f^{-1} \circ f = \text{Id}_E\) (l’application identité sur \(E\), qui à chaque élément de \(E\) associe lui-même).
- \(f \circ f^{-1} = \text{Id}_F\) (l’application identité sur \(F\)).
- Exemple : Soit \(f : \mathbb{R} \to \mathbb{R}, f(x) = 2x + 1\). \(f\) est bijective. Pour trouver \(f^{-1}\), on résout \(y = 2x + 1\) pour \(x\) : \(x = (y – 1) / 2\). Donc \(f^{-1}(y) = (y – 1) / 2\).
Fonction indicatrice (ou caractéristique)
Soit \(A\) un sous-ensemble d’un ensemble \(E\). La fonction indicatrice (ou fonction caractéristique) de \(A\), notée \(\mathbb{1}_A\) ou \(\chi_A\), est l’application de \(E\) vers \(\{0, 1\}\) définie par :
\[ \mathbb{1}_A(x) = \begin{cases} 1 & \text{si } x \in A \\ 0 & \text{si } x \notin A \end{cases} \]- Exemple: Soit \(E = \{1, 2, 3, 4, 5\}\) et \(A = \{2, 4\}\). Alors :
- \(\mathbb{1}_A(1) = 0\)
- \(\mathbb{1}_A(2) = 1\)
- \(\mathbb{1}_A(3) = 0\)
- \(\mathbb{1}_A(4) = 1\)
- \(\mathbb{1}_A(5) = 0\)
Partitions et relations d’équivalence
Une partition d’un ensemble \(E\) est une famille de sous-ensembles non vides de \(E\), deux à deux disjoints, et dont la réunion est \(E\). Autrement dit, chaque élément de \(E\) appartient à exactement un sous-ensemble de la partition.
Une relation d’équivalence sur un ensemble E est une relation binaire réflexive, symétrique et transitive.
- Réflexive: \( \forall x \in E, x \mathcal{R} x \)
- Symétrique: \( \forall x,y \in E, x \mathcal{R} y \Rightarrow y \mathcal{R} x\)
- Transitive:\( \forall x,y,z \in E, (x \mathcal{R} y \text{ et } y \mathcal{R} z) \Rightarrow x\mathcal{R}z \)
Lien entre partitions et relations d’équivalence :
- Si \(\mathcal{R}\) est une relation d’équivalence sur \(E\), alors les classes d’équivalence de \(\mathcal{R}\) forment une partition de \(E\). La classe d’équivalence d’un élément \(x \in E\) est l’ensemble de tous les éléments de \(E\) qui sont en relation avec \(x\) : \([x] = \{y \in E \mid y \mathcal{R} x\}\).
- Inversement, si l’on a une partition de \(E\), on peut définir une relation d’équivalence sur \(E\) en disant que deux éléments sont en relation si et seulement s’ils appartiennent au même sous-ensemble de la partition.
- Exemple : Soit \(E = \{1, 2, 3, 4, 5\}\). La relation « avoir le même reste dans la division euclidienne par 2 » est une relation d’équivalence. Les classes d’équivalence sont \(\{1, 3, 5\}\) (les nombres impairs) et \(\{2, 4\}\) (les nombres pairs), qui forment une partition de \(E\).
Relations
Notions fondamentales
Une relation binaire \( \mathcal{R} \) sur un ensemble \(E\) est une correspondance entre des éléments de \(E\). Formellement, c’est un sous-ensemble du produit cartésien \(E \times E\). Si un couple \((x, y)\) appartient à ce sous-ensemble, on dit que \(x\) est en relation avec \(y\), et on note \(x \mathcal{R} y\). Si \((x, y) \notin \mathcal{R}\), on dit que x n’est pas en relation avec y.
- Graphe d’une relation : Le graphe d’une relation binaire \(\mathcal{R}\) sur \(E\) est l’ensemble des couples \((x, y)\) tels que \(x \mathcal{R} y\). C’est donc le sous-ensemble de \(E \times E\) qui définit la relation.
- Domaine : Le domaine d’une relation binaire \(\mathcal{R}\) sur E est l’ensemble des éléments x de E tels qu’il existe au moins un y dans E vérifiant \(x \mathcal{R} y\). Formellement, \(\text{Dom}(\mathcal{R}) = \{x \in E \mid \exists y \in E, x \mathcal{R} y\}\).
- Image : L’image d’une relation binaire \(\mathcal{R}\) sur \(E\) est l’ensemble des éléments \(y\) de \(E\) tels qu’il existe au moins un \(x\) dans \(E\) tel que \(x \mathcal{R} y\). Formellement, \(\text{Im}(\mathcal{R}) = \{y \in E \mid \exists x \in E, x \mathcal{R} y\}\).
- Relation n-aire : Une généralisation des relations binaires. Une relation n-aire sur des ensembles \(E_1, E_2, \dots, E_n\) est un sous-ensemble du produit cartésien \(E_1 \times E_2 \times \dots \times E_n\). Les relations binaires sont des relations 2-aires.
- Exemple : Soit \(E = \{1, 2, 3\}\). Considérons la relation \(\mathcal{R}\) sur \(E\) définie par « est strictement inférieur à ».
- Graphe de \(\mathcal{R}\) : \(\{(1, 2), (1, 3), (2, 3)\}\).
- Domaine de \(\mathcal{R}\) : \(\{1, 2\}\).
- Image de \(\mathcal{R}\) : \(\{2, 3\}\).
Propriétés des relations
Une relation binaire \(\mathcal{R}\) sur un ensemble \(E\) peut avoir les propriétés suivantes :
- Réflexive : \(\forall x \in E, x \mathcal{R} x\). Tout élément est en relation avec lui-même.
- Symétrique : \(\forall x, y \in E, \text{ si } x \mathcal{R} y, \text{ alors } y \mathcal{R} x\). Si \(x\) est en relation avec \(y\), alors \(y\) est en relation avec \(x\).
- Antisymétrique : \(\forall x, y \in E, \text{ si } x \mathcal{R} y \text{ et } y \mathcal{R} x, \text{ alors } x = y\). Si \(x\) est en relation avec \(y\) et \(y\) est en relation avec \(x\), alors \(x\) et \(y\) sont égaux.
- Transitive : \(\forall x, y, z \in E, \text{ si } x \mathcal{R} y \text{ et } y \mathcal{R} z, \text{ alors } x \mathcal{R} z\). Si \(x\) est en relation avec \(y\) et \(y\) est en relation avec \(z\), alors \(x\) est en relation avec \(z\).
Exemples :
| Relation | Réflexive | Symétrique | Antisymétrique | Transitive |
|---|---|---|---|---|
| « \(=\) » sur \(\mathbb{R}\) | Oui | Oui | Oui | Oui |
| « \(\leq\) » sur \(\mathbb{R}\) | Oui | Non | Oui | Oui |
| « \(<\)" sur \(\mathbb{R}\) | Non | Non | Oui | Oui |
| « est ami avec » sur un ensemble de personnes | Non (en général) | Oui (en général) | Non | Non (en général) |
| \(\subset\) sur \(\mathcal{P}(E)\) | Oui | Non | Oui | Oui |
Types de relations
- Relation d’ordre : Une relation binaire qui est réflexive, antisymétrique et transitive.
- Ordre partiel : Une relation d’ordre quelconque. Exemple : la relation d’inclusion « \(\subset\) » sur l’ensemble des parties d’un ensemble.
- Ordre total : Une relation d’ordre où deux éléments quelconques sont toujours comparables. C’est-à-dire : \(\forall x, y \in E, x \mathcal{R} y \text{ ou } y \mathcal{R} x\). Exemple : la relation « \(\leq\) » sur l’ensemble des nombres réels.
- Relation d’équivalence : Une relation binaire qui est réflexive, symétrique et transitive. Exemple : la relation de congruence modulo \(n\) sur l’ensemble des entiers.
- Relation de préordre : Une relation binaire qui est réflexive et transitive.
Classes d’équivalence
Soit \(\mathcal{R}\) une relation d’équivalence sur un ensemble \(E\). La classe d’équivalence d’un élément \(x \in E\), notée \([x]\) ou \(\overline{x}\) ou \(cl(x)\), est l’ensemble de tous les éléments de \(E\) qui sont en relation avec \(x\) : \([x] = \{y \in E \mid x \mathcal{R} y\}\).
- Propriétés des classes d’équivalence:
- \(x \in [x]\) (conséquence de la réflexivité).
- Si \(x \mathcal{R} y\), alors \([x] = [y]\).
- Si \(x\) n’est pas en relation avec y (\(\lnot (x\mathcal{R} y)\)), alors \([x] \cap [y] = \emptyset \)
- Ensemble quotient : L’ensemble quotient de \(E\) par \(\mathcal{R}\), noté \(E / \mathcal{R}\), est l’ensemble de toutes les classes d’équivalence de \(\mathcal{R}\). C’est un ensemble de sous-ensembles de E.
- Partition induite par une relation d’équivalence : Les classes d’équivalence d’une relation d’équivalence sur \(E\) forment une partition de \(E\). Cela signifie que :
- Les classes d’équivalence sont non vides.
- Deux classes d’équivalence distinctes sont disjointes.
- La réunion de toutes les classes d’équivalence est égale à \(E\).
- Exemple : Soit \(\mathcal{R}\) la relation sur \(\mathbb{Z}\) définie par \(x \mathcal{R} y\) si et seulement si \(x – y\) est divisible par 3 (congruence modulo 3).
- \(\mathcal{R}\) est une relation d’équivalence.
- Les classes d’équivalence sont :
- \([0] = \{\dots, -6, -3, 0, 3, 6, \dots\}\)
- \([1] = \{\dots, -5, -2, 1, 4, 7, \dots\}\)
- \([2] = \{\dots, -4, -1, 2, 5, 8, \dots\}\)
- L’ensemble quotient \(\mathbb{Z} / \mathcal{R}\) est \(\{[0], [1], [2]\}\). On le note souvent \(\mathbb{Z}3\mathbb{Z}\).