Exercices corrigés : théorie des ensembles et relations (201-N11)

a) $A = \{2,4,6,8,10\}$ et $B = \{1,2,3,4,5\}$. La définition en compréhension donne la règle, l'extension donne la liste : passer de l'une à l'autre est le premier réflexe du chapitre, parce qu'une propriété se vérifie beaucoup plus vite sur une liste.

b) $3 \notin A$, car 3 est impair. $\{3\} \subset B$, car l'unique élément de $\{3\}$ est dans $B$. $3 \in B$. $\{2,4\} \subset A$. Le point à ne pas manquer : $3$ et $\{3\}$ ne sont pas la même chose. Le premier est un nombre, le second est un ensemble contenant ce nombre. On écrit $3 \in B$ mais $\{3\} \subset B$, et jamais l'inverse.

c) $\mathcal{P}(\{a,b,c\}) = \{\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$, soit 8 parties. On les énumère par taille croissante : c'est la seule façon de n'en oublier aucune, et le compte par taille doit donner $1, 3, 3, 1$.

d) Chaque élément de $X$ est soit pris, soit laissé, indépendamment des autres : cela fait $2$ choix répétés $n$ fois, donc $\lvert \mathcal{P}(X) \rvert = 2^{n}$. Pour $E$, qui compte 10 éléments, $2^{10} = 1024$ parties. Le lien avec le chapitre précédent est direct : une partie de $X$ est exactement un mot binaire de $n$ bits, où le bit de rang $k$ dit si l'élément $k$ est pris.

e) $\varnothing \notin A$ : les éléments de $A$ sont des nombres, pas des ensembles. Mais $\varnothing \subset A$ : l'inclusion demande que tout élément de $\varnothing$ soit dans $A$, ce qui est vrai à vide puisqu'il n'y a aucun élément à vérifier. Et $\varnothing \in \mathcal{P}(A)$, puisque $\mathcal{P}(A)$ est l'ensemble des parties de $A$ et que $\varnothing$ en est une. Les trois réponses diffèrent, et c'est ce qui rend l'exemple utile.

a) $A \cup B = \{1,2,3,4,5,6,7,8\}$ : tous les éléments qui sont dans l'un OU dans l'autre, comptés une seule fois. $A \cap B = \{4,5,6\}$ : ceux qui sont dans les deux. $A \setminus B = \{1,2,3\}$ : dans $A$ mais pas dans $B$. $B \setminus A = \{7,8\}$. Notez que $A \setminus B$ et $B \setminus A$ n'ont rien à voir : la différence n'est pas symétrique.

b) $\overline{A} = \{7,8,9,10\}$ et $\overline{B} = \{1,2,3,9,10\}$. Le complémentaire n'a de sens que relativement à un ensemble de référence : sans $E$, l'écriture $\overline{A}$ ne veut rien dire. Contrôle : $\lvert A \rvert + \lvert \overline{A} \rvert = 6+4 = 10 = \lvert E \rvert$.

c) $A \times B$ est l'ensemble des couples ORDONNÉS $(a,b)$ avec $a \in A$ et $b \in B$ : il en compte $6 \times 5 = 30$. Par exemple $(1,4)$, $(3,8)$ et $(6,5)$. Le produit cartésien fabrique des couples, pas des éléments : $(1,4)$ n'est ni un nombre ni un ensemble à deux éléments.

d) $A \setminus B = \{1,2,3\}$ et $A \cap B = \{4,5,6\}$ ; leur réunion vaut $\{1,2,3,4,5,6\} = A$. L'identité est générale : tout élément de $A$ est soit dans $B$, soit pas, et ces deux cas donnent précisément les deux morceaux. C'est une partition de $A$ en deux parties disjointes, ce qui explique pourquoi les cardinaux s'additionnent ici sans correction.

e) $\lvert A \rvert = 6$, $\lvert B \rvert = 5$, $\lvert A \cap B \rvert = 3$, donc la formule donne $6+5-3 = 8$. Et $\lvert A \cup B \rvert = \lvert \{1,\dots,8\} \rvert = 8$. La formule marche. La raison est qu'en additionnant $\lvert A \rvert$ et $\lvert B \rvert$, on compte deux fois les éléments communs : il faut donc en retrancher une copie.

f) Non. $A \times B$ contient $(1,4)$, mais pas $(4,1)$, puisque $1 \notin B$. Or $(4,1) \in B \times A$. Les deux produits ont le même cardinal, 30, mais ce ne sont pas les mêmes couples. Un couple est ordonné, c'est toute la différence avec une paire : $(a,b) = (c,d)$ exige $a=c$ ET $b=d$.

a) Sens direct. Soit $x \in \overline{A \cup B}$. Alors $x \notin A \cup B$, donc $x$ n'est ni dans $A$ ni dans $B$ ; d'où $x \in \overline{A}$ et $x \in \overline{B}$, c'est-à-dire $x \in \overline{A} \cap \overline{B}$. Sens réciproque. Soit $x \in \overline{A} \cap \overline{B}$. Alors $x \notin A$ et $x \notin B$, donc $x$ n'est dans aucun des deux, donc $x \notin A \cup B$, c'est-à-dire $x \in \overline{A \cup B}$. Les deux inclusions donnent l'égalité. C'est exactement la loi de De Morgan de la logique, transportée aux ensembles : la négation d'un OU est un ET de négations.

b) Quatre lignes, selon que $x$ appartient ou non à $A$ et à $B$. Colonnes $(x \in A, x \in B)$, puis $A \cap B$, puis $\overline{A \cap B}$, puis $\overline{A}$, $\overline{B}$ et leur réunion. Ligne $(1,1)$ : $A \cap B$ vaut 1, son complémentaire 0 ; $\overline{A} \cup \overline{B}$ vaut $0 \cup 0 = 0$. Ligne $(1,0)$ : $0$, donc $1$ ; et $0 \cup 1 = 1$. Ligne $(0,1)$ : $0$, donc $1$ ; et $1 \cup 0 = 1$. Ligne $(0,0)$ : $0$, donc $1$ ; et $1 \cup 1 = 1$. Les deux colonnes finales sont identiques sur les quatre lignes : l'égalité est établie. La table est plus rapide que la double inclusion, mais elle ne se généralise proprement qu'aux identités portant sur un petit nombre d'ensembles.

c) $x \in A \setminus B$ signifie $x \in A$ et $x \notin B$, ce qui s'écrit $x \in A$ et $x \in \overline{B}$, c'est-à-dire $x \in A \cap \overline{B}$. Les deux écritures traduisent la même phrase, l'équivalence est donc immédiate dans les deux sens. Cette identité est celle qui permet d'éliminer partout le symbole de différence et de ne travailler qu'avec réunion, intersection et complémentaire.

d) $A \setminus B$ et $B \setminus A$ sont disjoints, donc les cardinaux s'additionnent : $\lvert A \Delta B \rvert = \lvert A \setminus B \rvert + \lvert B \setminus A \rvert$. Or $\lvert A \setminus B \rvert = \lvert A \rvert - \lvert A \cap B \rvert$ et de même pour l'autre. D'où $\lvert A \Delta B \rvert = \lvert A \rvert + \lvert B \rvert - 2\lvert A \cap B \rvert$. Le facteur 2 est le point à comprendre : on retire l'intersection deux fois, une fois de chaque côté, parce qu'elle est justement ce que la différence symétrique exclut. Sur l'exemple de l'exercice précédent : $6+5-2(3) = 5$, et en effet $A \Delta B = \{1,2,3,7,8\}$.

e) Non. Contre-exemple : $A = \{1\}$, $B = \{2\}$, $C = \{1\}$. À gauche, $B \setminus C = \{2\}$ et $A \setminus \{2\} = \{1\}$. À droite, $A \setminus B = \{1\}$ puis $\{1\} \setminus C = \varnothing$. On obtient $\{1\}$ d'un côté et $\varnothing$ de l'autre : la différence n'est pas associative. Un seul contre-exemple suffit à réfuter une identité annoncée pour tous les ensembles, et il vaut mieux le chercher avec des ensembles à un élément, où tout se vérifie de tête.

a) On part TOUJOURS du centre, sinon on soustrait des quantités déjà retirées. Centre : $\lvert A \cap B \cap C \rvert = 3$. Région $A \cap B$ seule : $8 - 3 = 5$. Région $A \cap C$ seule : $10 - 3 = 7$. Région $B \cap C$ seule : $7 - 3 = 4$. Région $A$ seule : $27 - 5 - 7 - 3 = 12$. Région $B$ seule : $20 - 5 - 4 - 3 = 8$. Région $C$ seule : $29 - 7 - 4 - 3 = 15$. Extérieur : $60 - (12+8+15+5+7+4+3) = 60 - 54 = 6$. Contrôle : la somme des huit régions vaut 60, le cardinal de $E$.

b) $\lvert A \cup B \cup C \rvert = 27+20+29-8-10-7+3 = 54$. Sur le diagramme, la réunion est la somme des sept régions intérieures : $12+8+15+5+7+4+3 = 54$. Les deux méthodes coïncident, et c'est ce double calcul qui sécurise le résultat.

c) $60 - 54 = 6$ éléments sont hors de la réunion. C'est la région extérieure du diagramme, celle qu'on oublie systématiquement quand on ne dessine pas le rectangle de l'univers.

d) Exactement deux : ce sont les trois régions en croissant, $5 + 7 + 4 = 16$ éléments. Attention à la formulation : $\lvert A \cap B \rvert = 8$ compte aussi les 3 éléments du centre, qui sont dans TROIS ensembles. « Dans exactement deux » n'est pas « dans $A \cap B$ », et cette nuance est le piège classique des problèmes de sondage.

e) Parce que les éléments du centre sont comptés trois fois par $\lvert A \rvert + \lvert B \rvert + \lvert C \rvert$, puis retirés trois fois par les trois intersections deux à deux : leur solde est nul, alors qu'ils doivent compter une fois. On les rajoute donc une fois. Le même raisonnement de compensation, appliqué à un élément situé dans exactement deux ensembles, donne $2 - 1 = 1$ : il est bien compté une fois, et rien à corriger pour lui.

a) $R = \{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}$, soit 8 couples. On les trouve en balayant les 16 couples possibles et en gardant ceux où la division tombe juste : 1 divise tout le monde, 2 divise 2 et 4, 3 divise 3, et 4 divise 4.

b) Une relation sur $E$ est une partie de $E \times E$, qui compte $4 \times 4 = 16$ couples. Il y a donc $2^{16} = 65\,536$ relations possibles, une par sous-ensemble de couples. Le lien avec l'exercice 1 est direct : on choisit chaque couple ou non, ce qui est un mot de 16 bits.

c) En rangeant les indices de 1 à 4 : $M = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$. La première ligne est pleine, parce que 1 divise tout ; la matrice est triangulaire supérieure, parce qu'un diviseur d'un nombre non nul lui est inférieur ou égal. Contrôle : la matrice compte 8 coefficients à 1, autant que $R$ a de couples.

d) L'image de 2 est $\{y : 2\,R\,y\} = \{2,4\}$, c'est-à-dire les 1 de la deuxième LIGNE. Les antécédents de 4 sont $\{x : x\,R\,4\} = \{1,2,4\}$, c'est-à-dire les 1 de la quatrième COLONNE. Lire une ligne ou une colonne ne donne pas la même chose, et c'est la première source d'erreur sur les matrices de relations.

e) Non. Une fonction associe à chaque élément de départ AU PLUS une image, or 1 est en relation avec 1, 2, 3 et 4 : quatre images. Une relation est une fonction exactement quand chaque ligne de sa matrice contient au plus un 1 ; ici la première ligne en contient quatre. C'est la différence essentielle entre les deux notions : une fonction est un cas très particulier de relation.

a) Réflexive : tout entier se divise lui-même, les quatre couples $(x,x)$ sont là. Symétrique : non, $(1,2) \in R_{1}$ mais $(2,1) \notin R_{1}$, un contre-exemple suffit. Antisymétrique : si $x$ divise $y$ et $y$ divise $x$ avec $x,y$ positifs, alors $x=y$ ; on peut aussi le vérifier couple par couple, aucun couple symétrique n'apparaît hors de la diagonale. Transitive : si $x$ divise $y$ et $y$ divise $z$, alors $x$ divise $z$. Réflexive, antisymétrique et transitive : $R_{1}$ est une relation d'ORDRE, et cet ordre est partiel puisque 2 et 3 ne sont pas comparables.

b) Réflexive : non, $(1,1) \notin R_{2}$. Symétrique : oui, $(1,2)$ et $(2,1)$ sont tous deux présents, et $(3,3)$ est son propre symétrique. Antisymétrique : non, $(1,2)$ et $(2,1)$ sont là alors que $1 \neq 2$. Transitive : non, $(1,2)$ et $(2,1)$ devraient forcer $(1,1)$, qui manque. $R_{2}$ n'est donc ni un ordre ni une équivalence : ce n'est qu'une relation quelconque, et c'est le cas le plus fréquent.

c) Réflexive : $x+x = 2x$ est pair, donc oui. Symétrique : $x+y = y+x$, donc oui. Antisymétrique : non, $(1,3)$ et $(3,1)$ sont là avec $1 \neq 3$. Transitive : si $x+y$ et $y+z$ sont pairs, alors $x$ et $y$ ont la même parité, et $y$ et $z$ aussi, donc $x$ et $z$ également, donc $x+z$ est pair. Réflexive, symétrique et transitive : $R_{3}$ est une relation d'ÉQUIVALENCE, celle qui classe les entiers par parité.

d) Oui, mais cela contraint beaucoup : si $(x,y) \in R$ avec $x \neq y$, la symétrie impose $(y,x) \in R$ et l'antisymétrie impose alors $x=y$, contradiction. Une relation à la fois symétrique et antisymétrique ne contient donc que des couples de la diagonale. Exemple : l'égalité, $R = \{(x,x) : x \in E\}$. Symétrique et antisymétrique ne sont pas des contraires : ce sont deux conditions indépendantes qui peuvent être vraies ensemble, fausses ensemble, ou l'une sans l'autre.

e) Réflexive : la diagonale ne contient que des 1. Symétrique : la matrice est égale à sa transposée. Antisymétrique : hors de la diagonale, jamais $M_{ij}$ et $M_{ji}$ simultanément à 1. Transitive : le carré booléen $M^{2}$ n'a aucun 1 là où $M$ a un 0, ce qui s'écrit $M^{2} \le M$. Cette dernière lecture fait le pont avec le chapitre des matrices : un 1 en position $(i,j)$ dans $M^{2}$ signale un chemin de longueur 2, et la transitivité demande qu'un tel chemin ait toujours son raccourci direct.

a) Réflexive : $x$ a évidemment le même reste que lui-même. Symétrique : si $x$ et $y$ ont le même reste, alors $y$ et $x$ aussi, la condition est symétrique dans son écriture. Transitive : si $x$ et $y$ ont le même reste $r$, et $y$ et $z$ le même reste, ce reste est encore $r$, donc $x$ et $z$ ont le même reste. Les trois propriétés sont vérifiées : $\sim$ est une équivalence. Aucune de ces vérifications ne demande de calcul, parce que la relation est définie par l'égalité d'une quantité, et l'égalité est toujours une équivalence.

b) Classe de 0 : $\{0,5,10\}$. Classe de 1 : $\{1,6,11\}$. Classe de 2 : $\{2,7,12\}$. Classe de 3 : $\{3,8,13\}$. Classe de 4 : $\{4,9,14\}$. On note $\overline{r}$ la classe du reste $r$ ; par exemple $\overline{2} = \{2,7,12\}$, et $\overline{7}$ désigne le MÊME ensemble. Une classe a autant de noms que d'éléments, ce qui déroute au début mais ne pose aucun problème une fois admis.

c) Trois conditions. Aucune classe n'est vide : chacune compte trois éléments. Elles sont deux à deux disjointes : deux restes différents ne peuvent pas coexister pour un même nombre, puisque le reste de la division euclidienne est unique. Leur réunion vaut $E$ : tout entier de $E$ a un reste, donc appartient à une classe. C'est bien une partition.

d) Cinq classes, autant que de restes possibles $0, 1, 2, 3, 4$, avec 3 éléments chacune. Contrôle : $5 \times 3 = 15 = \lvert E \rvert$. Cette régularité vient de ce que $E$ contient exactement trois blocs consécutifs de 5 entiers ; sur $\{0,\dots,13\}$ les classes n'auraient plus toutes le même effectif.

e) Chaque classe est le contenu d'une alvéole : les éléments qui entrent en collision sont exactement ceux qui sont équivalents modulo 5. Le nombre d'alvéoles est le nombre de classes, et l'uniformité des effectifs est précisément ce qu'on demande à une bonne fonction de hachage. Si les données présentaient toutes le même reste, tout atterrirait dans la même alvéole et la recherche redeviendrait linéaire.

f) Non. Si $z$ appartient à la classe de $x$ et à celle de $y$, alors $x \sim z$ et $z \sim y$, donc $x \sim y$ par transitivité, et les deux classes contiennent exactement les mêmes éléments. Deux classes sont donc soit égales, soit disjointes, jamais partiellement superposées. C'est cette dichotomie qui garantit qu'on obtient une partition, et elle repose entièrement sur la transitivité.

1) FAUX. C'est l'inclusion qui est universelle, pas l'appartenance : $\varnothing \subset A$ pour tout $A$, mais $\varnothing \in A$ seulement si $A$ contient l'ensemble vide comme élément. Contre-exemple : $A = \{1,2\}$ ne contient que les nombres 1 et 2. Énoncé correct : $\varnothing \subset A$ toujours, et $\varnothing \in \mathcal{P}(A)$ toujours, mais $\varnothing \in A$ presque jamais.

2) FAUX. Le nombre de parties double à chaque élément ajouté, il ne s'ajoute pas : c'est $2^{n}$, pas $2n$. Contre-exemple : pour $n=3$, on a compté 8 parties, alors que $2n = 6$. Énoncé correct : $\lvert \mathcal{P}(X) \rvert = 2^{\lvert X \rvert}$, parce que chaque élément est pris ou laissé indépendamment des autres.

3) FAUX. Les deux propriétés sont indépendantes, et une relation peut ne vérifier ni l'une ni l'autre. Contre-exemple : $R = \{(1,2),(2,1),(1,3)\}$ sur $\{1,2,3\}$ n'est pas symétrique, car $(3,1)$ manque, et n'est pas antisymétrique, car $(1,2)$ et $(2,1)$ coexistent avec $1 \neq 2$. Énoncé correct : symétrique et antisymétrique sont deux conditions distinctes ; leur négation ne se déduit pas l'une de l'autre.

4) FAUX. Les éléments communs seraient comptés deux fois. Contre-exemple : $A = \{1,2\}$ et $B = \{2,3\}$ donnent $\lvert A \cup B \rvert = 3$ alors que $\lvert A \rvert + \lvert B \rvert = 4$. Énoncé correct : $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$, et l'égalité simple n'est vraie que si $A$ et $B$ sont disjoints.

5) FAUX. Un produit cartésien est fait de couples ORDONNÉS. Contre-exemple : avec $A = \{1\}$ et $B = \{2\}$, on a $A \times B = \{(1,2)\}$ et $B \times A = \{(2,1)\}$, deux ensembles sans aucun élément commun. Énoncé correct : $A \times B$ et $B \times A$ ont toujours le même cardinal, $\lvert A \rvert \times \lvert B \rvert$, mais ils ne sont égaux que si $A = B$ ou si l'un des deux est vide.