Introduction à la théorie des ensembles

On montre l'égalité en prouvant les deux inclusions, mais ici tout est en fait une chaîne d'équivalences (encore mieux). Pour \(x\in E\) :

\[ x\in(A\cap B)^c \iff x\notin A\cap B \iff \operatorname{non}(x\in A\text{ et }x\in B). \]

Par la loi de De Morgan logique :

\[ \iff (x\notin A\ \text{ou}\ x\notin B) \iff (x\in A^c\ \text{ou}\ x\in B^c) \iff x\in A^c\cup B^c. \]

Récurrence sur \(n=\operatorname{card}(E)\). Posons \(P(n)\) : « tout ensemble à \(n\) éléments a \(2^n\) parties ».

Init. \(n=0\) : le seul ensemble est \(\varnothing\), dont \(\mathcal P(\varnothing)=\{\varnothing\}\) a \(1=2^0\) élément. ✓

Héréd. Soit \(E\) à \(n+1\) éléments. Fixons \(a\in E\) et posons \(E'=E\setminus\{a\}\) (\(n\) éléments). Les parties de \(E\) se scindent en deux familles disjointes :

• celles qui ne contiennent pas \(a\) : ce sont exactement les parties de \(E'\), au nombre de \(2^n\) (hyp.) ;
• celles qui contiennent \(a\) : chacune s'écrit \(F\cup\{a\}\) avec \(F\subseteq E'\), à nouveau \(2^n\).

D'où \(\operatorname{card}(\mathcal P(E))=2^n+2^n=2^{n+1}\).

\(A\subseteq B\Rightarrow A\cup B=B\).

Toujours \(B\subseteq A\cup B\). Réciproquement, soit \(x\in A\cup B\) : si \(x\in B\) c'est fini ; si \(x\in A\subseteq B\) alors \(x\in B\). Donc \(A\cup B\subseteq B\), d'où \(A\cup B=B\).

\(A\cup B=B\Rightarrow A\cap B=A\).

Toujours \(A\cap B\subseteq A\). Réciproquement soit \(x\in A\) : alors \(x\in A\cup B=B\), donc \(x\in A\cap B\). Ainsi \(A\subseteq A\cap B\), d'où \(A\cap B=A\).

\(A\cap B=A\Rightarrow A\subseteq B\).

Si \(A\cap B=A\), soit \(x\in A=A\cap B\), alors \(x\in B\). Donc \(A\subseteq B\).

(a) \(A=\{x\in\mathbb N\mid x=2\}\)

\(A=\{2\}\)

(b) \(B=\{x\in\mathbb N\mid x\leqslant 6\text{ et }x\text{ pair}\}\)

\(B=\{0,2,4,6\}\) (\(0\) est pair et \(\in\mathbb N\))

(c) \(C=\{x\in\mathbb Z\mid -3\leqslant x\leqslant 3\}\)

\(C=\{-3,-2,-1,0,1,2,3\}\)

(d) \(D=\{x\in\mathbb N\mid x=n^2,\ n\in\{1,2,3,4\}\}\)

\(D=\{1,4,9,16\}\)

(e) \(E=\{x\in\mathbb N\mid x\text{ multiple de }3,\ x<20\}\)

\(E=\{0,3,6,9,12,15,18\}\)

(f) \(F=\{x\in\mathbb R\mid x^2+x+1\geqslant 0\}\)

Le trinôme a pour discriminant \(\Delta=1-4=-3<0\) et un coefficient dominant \(>0\) : il est strictement positif partout.

\(F=\mathbb R\)

(a) \(A=\varnothing\)

\(A=\{x\in\mathbb R\mid x^2<0\}\) (ou \(\{x\in\mathbb N\mid x\neq x\}\))

(b) \(B=\{\pi\}\)

\(B=\{x\in\mathbb R\mid x=\pi\}\)

(c) \(C=\{1,3,5,7,9\}\)

\(C=\{2k+1\mid k\in\{0,1,2,3,4\}\}=\{x\in\mathbb N\mid x\text{ impair et }x\leqslant 9\}\)

(d) \(D=\{2,4,8,16,32\}\)

\(D=\{2^n\mid n\in\{1,2,3,4,5\}\}\)

(e) \(E=\{\{1\}\}\)

\(E=\{x\mid x=\{1\}\}\) (singleton dont l'unique élément est l'ensemble \(\{1\}\))

(f) \(F=\{\varnothing\}\)

\(F=\{x\mid x=\varnothing\}=\mathcal P(\varnothing)\)

(a) \(x\in\{x\}\)

Vrai : \(x\) est l'élément du singleton \(\{x\}\).

(b) \(\{x\}\in\{x\}\)

Faux (en général) : le seul élément de \(\{x\}\) est \(x\), et \(\{x\}\neq x\).

(c) \(x\in\{\{x\}\}\)

Faux : le seul élément de \(\{\{x\}\}\) est \(\{x\}\), pas \(x\).

(d) \(\{x\}\in\{\{x\}\}\)

Vrai : \(\{x\}\) est bien l'élément de \(\{\{x\}\}\).

(e) \(x\subseteq\{x\}\)

Faux (en général) : \(\subseteq\) exige que \(x\) soit un ensemble et que ses éléments soient dans \(\{x\}\) ; rien ne le garantit (ex. \(x=1\)).

(f) \(\{x\}\subseteq\{x\}\)

Vrai : réflexivité de l'inclusion (tout élément de \(\{x\}\) est dans \(\{x\}\)).

(g) \(x\subseteq\{\{x\}\}\)

Faux (en général), même raison qu'en (e).

(h) \(\{x\}\subseteq\{\{x\}\}\)

Faux : il faudrait \(x\in\{\{x\}\}\), c.-à-d. \(x=\{x\}\), ce qui est impossible.

(a) \(A\in B\)

Faux en général : être une partie n'est pas être un élément (ex. \(A=\{1\}\subseteq B=\{1,2\}\) mais \(\{1\}\notin B\)).

(b) \(A\subseteq\mathcal P(B)\)

Faux : les éléments de \(A\) sont des éléments de \(B\), pas des parties de \(B\) (ex. \(1\in A\) mais \(1\notin\mathcal P(B)\)).

(c) \(A\subseteq B\)

Vrai : c'est l'hypothèse.

(d) \(A\in\mathcal P(B)\)

Vrai : par définition \(A\in\mathcal P(B)\iff A\subseteq B\), ce qui est donné.

(a) \(A=\{0,1,2\}\) \((2^3=8)\)

\(\mathcal P(A)=\{\varnothing,\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}\}\)

(b) \(B=\{\{0,1,2\}\}\) \((2^1=2)\)

\(B\) n'a qu'un élément (l'ensemble \(\{0,1,2\}\)).

\(\mathcal P(B)=\big\{\varnothing,\ \{\{0,1,2\}\}\big\}\)

(c) \(C=\{a,b,c,d\}\) \((2^4=16)\)

\(\mathcal P(C)=\big\{\varnothing,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\},\{a,b,c,d\}\big\}\)

(d) \(D=\varnothing\)

\(\mathcal P(\varnothing)=\{\varnothing\}\)

(e) \(E=\mathcal P(\varnothing)=\{\varnothing\}\)

\(\mathcal P(E)=\big\{\varnothing,\{\varnothing\}\big\}\)

(f) \(F=\mathcal P(\mathcal P(\varnothing))=\{\varnothing,\{\varnothing\}\}\)

\(\mathcal P(F)=\big\{\varnothing,\ \{\varnothing\},\ \{\{\varnothing\}\},\ \{\varnothing,\{\varnothing\}\}\big\}\) \((2^2=4)\)

(a) \(\mathcal P(A\cup B)\) vs \(\mathcal P(A)\cup\mathcal P(B)\)

Conjecture avec \(A=\{1,2\},\ B=\{1,3\}\), \(A\cup B=\{1,2,3\}\) : \(\mathcal P(A\cup B)\) a \(8\) éléments, tandis que \(\mathcal P(A)\cup\mathcal P(B)=\{\varnothing,\{1\},\{2\},\{1,2\},\{3\},\{1,3\}\}\) n'en a que \(6\) (il manque \(\{2,3\}\) et \(\{1,2,3\}\)).

On a toujours l'inclusion \(\mathcal P(A)\cup\mathcal P(B)\subseteq\mathcal P(A\cup B)\) : si \(X\subseteq A\) ou \(X\subseteq B\), alors \(X\subseteq A\cup B\). Mais l'égalité est fausse en général (un sous-ensemble de \(A\cup B\) peut piocher à la fois dans \(A\) et \(B\)).

(b) \(\mathcal P(A\cap B)\) vs \(\mathcal P(A)\cap\mathcal P(B)\)

Chaîne d'équivalences, pour tout ensemble \(X\) :

\[ X\in\mathcal P(A\cap B)\iff X\subseteq A\cap B\iff(X\subseteq A\text{ et }X\subseteq B)\iff X\in\mathcal P(A)\cap\mathcal P(B). \]

(a) \(A=X\cup Y\)

\([-5,7]\)

(b) \(B=X\cap Z\)

Entiers naturels de \([4,7]\).

\(\{4,5,6,7\}\)

(c) \(C=X\cap Z^c\)

On retire de \([4,7]\) les entiers \(4,5,6,7\) :

\(C=\left]4,5\right[\cup\left]5,6\right[\cup\left]6,7\right[\)

(d) \(D=(X\cup Y)\cap Z\)

\([-5,7]\cap\mathbb N\) :

\(\{0,1,2,3,4,5,6,7\}\)

(e) \(E=X\cup(Y\cap Z)\)

\(Y\cap Z=[-5,5]\cap\mathbb N=\{0,1,2,3,4,5\}\), puis on réunit avec \([4,7]\) (qui absorbe \(4,5\)) :

\(E=\{0,1,2,3\}\cup[4,7]\)

(f) \(F=X^c\cap(Y^c\cup Z)\)

\(X^c=\left]-\infty,4\right[\cup\left]7,+\infty\right[\), \(Y^c=\left]-\infty,-5\right[\cup\left]5,+\infty\right[\). Donc \(Y^c\cup Z=\left]-\infty,-5\right[\cup\{0,1,2,3,4,5\}\cup\left]5,+\infty\right[\). En intersectant avec \(X^c\) (qui exclut \([4,7]\)) : on garde \(\left]-\infty,-5\right[\), on ne garde de \(\{0,..,5\}\) que \(0,1,2,3\) (car \(4,5\in[4,7]\)), et \(\left]5,+\infty\right[\cap X^c=\left]7,+\infty\right[\).

\(F=\left]-\infty,-5\right[\cup\{0,1,2,3\}\cup\left]7,+\infty\right[\)

(a) \(A\setminus(B\setminus C)=(A\setminus B)\cup(A\cap C)\)

Pour tout \(x\) :

\[ x\in A\setminus(B\setminus C)\iff x\in A\ \text{et}\ x\notin(B\setminus C)\iff x\in A\ \text{et}\ \operatorname{non}(x\in B\text{ et }x\notin C). \] \[ \iff x\in A\ \text{et}\ (x\notin B\ \text{ou}\ x\in C)\iff (x\in A\text{ et }x\notin B)\ \text{ou}\ (x\in A\text{ et }x\in C). \]

\(=(A\setminus B)\cup(A\cap C)\). ∎

(b) \(A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)\)

\[ x\in A\setminus(B\cap C)\iff x\in A\ \text{et}\ (x\notin B\text{ ou }x\notin C)\iff(x\in A\setminus B)\text{ ou }(x\in A\setminus C). \]

\(=(A\setminus B)\cup(A\setminus C)\). ∎ (De Morgan appliqué à \(x\notin B\cap C\).)

(c) \(A\cup B=B\cap C\iff A\subseteq B\subseteq C\)

\(\Leftarrow\) : si \(A\subseteq B\subseteq C\), alors \(A\cup B=B\) (car \(A\subseteq B\)) et \(B\cap C=B\) (car \(B\subseteq C\)), donc \(A\cup B=B=B\cap C\).

\(\Rightarrow\) : supposons \(A\cup B=B\cap C\). Or \(B\cap C\subseteq B\subseteq A\cup B\). L'hypothèse écrase toute la chaîne : \(A\cup B=B\cap C\subseteq B\subseteq A\cup B\), donc tout est égal : \(A\cup B=B=B\cap C\). De \(A\cup B=B\) on tire \(A\subseteq B\) ; de \(B=B\cap C\) on tire \(B\subseteq C\).

\(A\subseteq B\subseteq C\). ∎

(d) \((A\cap B^c)\cup(A^c\cap B)=B\iff A=\varnothing\)

Le membre de gauche est exactement \(A\,\Delta\,B\). L'équation est donc \(A\,\Delta\,B=B\).

\(\Leftarrow\) : si \(A=\varnothing\), \(\varnothing\,\Delta\,B=B\) ✓.

\(\Rightarrow\) : en composant par \(\Delta B\) (avec \(B\,\Delta\,B=\varnothing\) et l'associativité) : \(A\,\Delta\,B=B\Rightarrow A\,\Delta\,B\,\Delta\,B=B\,\Delta\,B\Rightarrow A\,\Delta\,\varnothing=\varnothing\Rightarrow A=\varnothing\).

\(A=\varnothing\). ∎

(a) \(A=(X\cap Y)\cap(X\cap Y^c)=X\cap(Y\cap Y^c)=X\cap\varnothing\)

\(A=\varnothing\)

(b) \(B=(X\cap Y)\cup(X\cap Y^c)=X\cap(Y\cup Y^c)=X\cap\Omega\)

\(B=X\)

(c) \(C=(X\cup Y)\cap(X\cup Y^c)=X\cup(Y\cap Y^c)=X\cup\varnothing\)

\(C=X\)

(d) \(D=(X\cap Y)\cup(X\cap Y^c)\cup(X^c\cap Y)\)

Les deux premiers termes donnent \(X\) (cf. b), d'où \(D=X\cup(X^c\cap Y)=(X\cup X^c)\cap(X\cup Y)=\Omega\cap(X\cup Y)\).

\(D=X\cup Y\)

(e) \(E=\) les quatre cases réunies

C'est la réunion de la partition entière de \(\Omega\).

\(E=\Omega\)

(f) \(F=(X\cup Y)\cap(X\cup Y^c)\cap(X^c\cup Y)\cap(X^c\cup Y^c)\)

Les deux premiers facteurs valent \(X\) (cf. c) ; les deux derniers : \((X^c\cup Y)\cap(X^c\cup Y^c)=X^c\cup(Y\cap Y^c)=X^c\). Donc \(F=X\cap X^c\).

\(F=\varnothing\)

(a) Exprimer \(A^c\)

\(A\odot A=(A\cup A)^c=A^c\).

\(A^c=A\odot A\)

(b) Calculer \((A\odot A)\odot(B\odot B)\)

\((A\odot A)\odot(B\odot B)=A^c\odot B^c=(A^c\cup B^c)^c=(A\cap B)\) par De Morgan.

\((A\odot A)\odot(B\odot B)=A\cap B\)

(c) Exprimer \(A\cup B\) et \(A\setminus B\)

\(A\cup B=\big((A\cup B)^c\big)^c=(A\odot B)^c=(A\odot B)\odot(A\odot B)\).

\(A\cup B=(A\odot B)\odot(A\odot B)\)

\(A\setminus B=A\cap B^c\). Or \(B^c=B\odot B\), et \((A\odot A)\odot B=A^c\odot B=(A^c\cup B)^c=A\cap B^c\).

\(A\setminus B=(A\odot A)\odot B\)

(a) \(A\,\Delta\,A=(A\setminus A)\cup(A\setminus A)=\varnothing\cup\varnothing\)

\(=\varnothing\)

(b) \(A\,\Delta\,\varnothing=(A\setminus\varnothing)\cup(\varnothing\setminus A)=A\cup\varnothing\)

\(=A\)

(c) \(A\,\Delta\,B=B\,\Delta\,A\)

\((A\setminus B)\cup(B\setminus A)=(B\setminus A)\cup(A\setminus B)\) : commutativité de \(\cup\). ✓

(d) \(A\,\Delta\,B=A^c\,\Delta\,B^c\)

\(A^c\,\Delta\,B^c=(A^c\setminus B^c)\cup(B^c\setminus A^c)=(A^c\cap B)\cup(B^c\cap A)=(B\setminus A)\cup(A\setminus B)=A\,\Delta\,B\). ✓ (car \(A^c\setminus B^c=A^c\cap(B^c)^c=A^c\cap B\)).

(e) \(A\,\Delta\,B=(A\setminus B)\cup(B\setminus A)\)

C'est la définition équivalente ; on vérifie \((A\cup B)\setminus(A\cap B)=(A\setminus B)\cup(B\setminus A)\) : « dans exactement l'un des deux ». ✓

(f) \((A\,\Delta\,B)\,\Delta\,C=A\,\Delta\,(B\,\Delta\,C)\) (associativité)

On utilise la fonction indicatrice \(\mathbf 1_E\). On vérifie que \(\mathbf 1_{A\Delta B}=\mathbf 1_A+\mathbf 1_B\ (\mathrm{mod}\ 2)\) (le « ou exclusif »). Alors :

\[ \mathbf 1_{(A\Delta B)\Delta C}=\mathbf 1_A+\mathbf 1_B+\mathbf 1_C=\mathbf 1_{A\Delta(B\Delta C)}\quad(\mathrm{mod}\ 2). \]

Autrement dit, \(x\) appartient à \(A\,\Delta\,B\,\Delta\,C\) ssi il appartient à un nombre impair des ensembles \(A,B,C\) — description symétrique, indépendante du parenthésage.

\((A\,\Delta\,B)\,\Delta\,C=A\,\Delta\,(B\,\Delta\,C)\). ∎

(a) \(X\setminus A=B\)

Or \(X\setminus A\subseteq A^c\), donc toute solution vérifie \(B\cap A=\varnothing\). Mais \(A\subsetneq B\) donne \(A\subseteq B\), soit \(A\cap B=A\). Il faudrait \(A=\varnothing\), ce qui contredit... non : \(A=\varnothing\) est compatible avec \(A\subsetneq B\) (si \(B\neq\varnothing\)). Bilan :

• Si \(A\neq\varnothing\) : aucune solution (un élément de \(A\subseteq B\) devrait être hors de \(A\)).
• Si \(A=\varnothing\) : \(X\setminus\varnothing=X=B\), solution unique \(X=B\).

\(A\neq\varnothing\Rightarrow S=\varnothing\) ; \(A=\varnothing\Rightarrow S=\{B\}\).

(b) \(X\cup A=B\)

Nécessairement \(X\subseteq B\) et \(X\) doit contenir \(B\setminus A\) (les éléments de \(B\) hors de \(A\)), les éléments de \(A\) restant libres. On vérifie que tout \(X\) avec \(B\setminus A\subseteq X\subseteq B\) donne \(X\cup A=B\).

\(S=\{X\in\mathcal P(\Omega)\mid B\setminus A\subseteq X\subseteq B\}\)

(c) \(X\cap A=B\)

\(X\cap A\subseteq A\), donc toute solution impose \(B\subseteq A\). Or \(A\subsetneq B\) donne \(A\subseteq B\) et \(A\neq B\) ; combiné à \(B\subseteq A\), on aurait \(A=B\) : contradiction.

\(S=\varnothing\) (aucune solution).

(d) \(X\,\Delta\,A=B\)

\(\Delta\) est « inversible » (chaque ensemble est son propre inverse) : en composant par \(\Delta A\), \(X=X\,\Delta\,A\,\Delta\,A=B\,\Delta\,A\).

Solution unique \(X=A\,\Delta\,B\).

(a) \(A=\{1,2\}\times\{1,3\}\)

\(\{(1,1),(1,3),(2,1),(2,3)\}\)

(b) \(B=\{2,1\}\times\{1,3\}\)

L'ordre d'écriture des éléments d'un ensemble ne compte pas : \(\{2,1\}=\{1,2\}\).

\(B=\{(1,1),(1,3),(2,1),(2,3)\}=A\)

(c) \(C=\{1\}\times\{1,2\}\times\{1,2,3\}\) \((1\cdot 2\cdot 3=6)\)

\(\{(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3)\}\)

(d) \(D=\{1,2,3\}\times\{1\}\times\{1,2\}\) \((3\cdot 1\cdot 2=6)\)

\(\{(1,1,1),(1,1,2),(2,1,1),(2,1,2),(3,1,1),(3,1,2)\}\)

(a) \(A=[0,1]\times[0,1]\)

Carré unité plein : tous les points \((x,y)\) avec \(0\leqslant x\leqslant 1\) et \(0\leqslant y\leqslant 1\) (bords inclus).

(b) \(B=([0,1]\cup[2,3])\times[0,3]\)

Deux bandes verticales : \(x\in[0,1]\) et \(x\in[2,3]\), chacune de hauteur \(y\in[0,3]\) — deux rectangles \(1\times 3\) séparés par la bande \(1

(c) \(C=\mathbb R\times\mathbb R\)

Le plan tout entier \(\mathbb R^2\).

(d) \(D=\mathbb Z\times\mathbb Z\)

Le réseau des points à coordonnées entières (grille de points isolés, un à chaque nœud).

(a) \(\mathcal A=\{\Omega\}\)

Oui : un seul bloc, non vide, de réunion \(\Omega\) (partition triviale).

(b) \(\mathcal B=\{\{1,2\},\{3,4\}\}\)

Oui : blocs non vides, disjoints, réunion \(\{1,2,3,4\}=\Omega\).

(c) \(\mathcal C=\{\{1,2\},\{2,3\},\{4\}\}\)

Non : \(\{1,2\}\cap\{2,3\}=\{2\}\neq\varnothing\) (pas disjoints ; l'élément \(2\) est compté deux fois).

(d) \(\mathcal D=\{\{1\},\{2\},\{3\},\{4\}\}\)

Oui : les singletons, disjoints, de réunion \(\Omega\) (partition « discrète »).

Méthode 1 — choix successifs puis correction de l'ordre. On forme d'abord des groupes ordonnés :

\[ \binom{6}{2}\times\binom{4}{2}\times\binom{2}{2}=15\times 6\times 1=90. \]

Mais les \(3\) groupes n'étant pas distinguables, chaque répartition a été comptée \(3!=6\) fois (une pour chaque ordre des trois groupes). On divise :

\[ \frac{90}{3!}=\frac{90}{6}=15. \]

Méthode 2 — formule des partitions. Nombre de partitions de \(6\) objets en \(3\) paires :

\[ \frac{6!}{(2!)^3\,\cdot\,3!}=\frac{720}{8\times 6}=15. \]