CommeUnJeu · L1 MPSI

Ensembles

⌚ ~323 min ▢ 40 blocs ✓ 128 exercices ➣ Prérequis : Logique

Un ensemble est, intuitivement, un sac de billes --- une collection d'objets dont l'identité est fixée par la liste (ou la règle) de ses éléments. Nous avons tous manipulé des ensembles, souvent sans les nommer : $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ sont des ensembles ; un intervalle $[0, 1]$ est un ensemble ; les solutions d'une équation forment un ensemble ; un graphe est un ensemble de points. Ce chapitre précise le vocabulaire de base.
Le plan a deux parties. La première met en place le langage : comment spécifier un ensemble (en listant ses éléments, ou par une propriété définissante), ce que signifie qu'un ensemble est contenu dans un autre, et le très important ensemble des parties $\mathcal{P}(E)$ d'un ensemble $E$. La seconde introduit les opérations : réunion, intersection, différence, complémentaire, produit cartésien. Les deux lois de De Morgan et la distributivité de $\cap$ et $\cup$ sont énoncées et démontrées une fois pour toutes --- elles seront invoquées partout par la suite.
Un fil rouge : la théorie des ensembles et la logique se reflètent l'une l'autre. Chaque construction ensembliste correspond à un connecteur logique ($\cap \leftrightarrow \wedge$, $\cup \leftrightarrow \vee$, $\complement \leftrightarrow \neg$, $\subset \leftrightarrow \Rightarrow$, $= \leftrightarrow \Leftrightarrow$). Toute identité ensembliste est, finalement, une identité entre propositions sur l'appartenance. Une fois ce pont posé, les démonstrations ensemblistes deviennent une application mécanique du chapitre de logique.

I Appartenance et inclusion

On commence par poser le vocabulaire de base : ce qu'est un ensemble, comment on désigne ses éléments, et comment deux ensembles se relient par inclusion. Trois opérations sur le langage lui-même --- la liste des éléments (extension), leur spécification par une propriété (compréhension), et la considération de toutes les parties possibles ($\mathcal{P}(E)$) --- ferment la section.

I.1 Ensembles$\virgule$ éléments$\virgule$ ensemble vide

La notion d'ensemble est prise comme primitive : nous ne la définirons pas à partir d'objets plus élémentaires. L'image intuitive --- un sac de billes, les billes étant les éléments --- suffit. Ce que nous définissons soigneusement, c'est la relation entre un élément et l'ensemble qui le contient.

Définition — Ensemble$\virgule$ élément$\virgule$ appartenance

Un ensemble est une collection d'objets appelés ses éléments. Pour un élément $x$ et un ensemble $E$ :

$x \in E$ se lit « $x$ appartient à $E$ » ou « $x$ est un élément de $E$ ».
$x \notin E$ est la négation : « $x$ n'appartient pas à $E$ ».

Deux ensembles $E$ et $F$ sont égaux, et l'on note $E = F$, lorsqu'ils ont exactement les mêmes éléments : $$ E = F \ \iff \ \forall x, \ (x \in E \iff x \in F). $$

Exemple

Pour l'ensemble $E = \{1, 2, 3, 4, 5, 6\}$ des résultats d'un dé : $$ 2 \in E, \qquad 7 \notin E, \qquad \pi \notin E. $$ L'ordre des éléments listés n'a pas d'importance, et les répétitions sont ignorées : $$ \{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}. $$

Exemple

Un ensemble $E$ se représente comme une région du plan, chaque élément étant dessiné comme un point à l'intérieur. Un élément $x \in E$ se trouve dans la région ; un élément $y \notin E$ se trouve à l'extérieur.

Définition — Ensemble vide

Il existe un unique ensemble sans élément, appelé l'ensemble vide et noté $\emptyset$ (ou $\{\}$). Formellement : $$ \forall x, \ x \notin \emptyset. $$

Exemple

L'ensemble des réels $x$ tels que $x^2 = -1$ est vide : un carré est positif, donc aucun tel $x$ n'existe. Concrètement, $\{ x \in \mathbb{R} \ \mid \ x^2 = -1 \} = \emptyset$. À l'inverse, $\{ x \in \mathbb{C} \ \mid \ x^2 = -1 \} = \{i, -i\}$ est non vide.

Compétences à pratiquer

Décider si $x \in E$
Identifier quand un ensemble défini est vide
Reconnaître des ensembles égaux

I.2 Définition en extension et en compréhension

Un ensemble peut être spécifié de deux manières complémentaires. L'extension est la liste explicite des éléments : $\{1, 2, 3\}$. Elle ne fonctionne que pour les ensembles finis. La compréhension spécifie les éléments par une propriété qu'ils vérifient : $\{x \in \mathbb{R} \ \mid \ x^2 \le 1\}$. Ce second style est le pilier des mathématiques --- il permet de parler d'ensembles infinis, et de désigner « l'ensemble de tous les $x$ tels que $\dots$ » sans en écrire les éléments.

Définition — Définition en extension et en compréhension

Soit $E$ un ensemble et $\mathcal{P}(x)$ un prédicat d'une variable $x$.

Extension. On liste les éléments entre accolades : $\{a_1, a_2, \dots, a_n\}$ désigne l'ensemble dont les éléments sont exactement $a_1, \dots, a_n$. Un ensemble de la forme $\{a\}$ est un singleton ; un ensemble $\{a, b\}$ avec $a \ne b$ est une paire.
Compréhension. La notation $$ \{ x \in E \ \mid \ \mathcal{P}(x) \} $$ désigne l'ensemble des éléments de $E$ qui vérifient $\mathcal{P}$. Pour une famille $(x_i)_{i \in I}$ indexée par un ensemble $I$, on écrit aussi $\{ x_i \ \mid \ i \in I \}$ pour l'ensemble des valeurs prises.

Un même ensemble peut admettre les deux descriptions : $\{0, 1\} = \{ n \in \mathbb{N} \ \mid \ n^2 = n \}$.

Exemple

En extension : $\{ 1, 4, 9, 16, 25 \}$.
En compréhension : $\{ n^2 \ \mid \ n \in \{1, 2, 3, 4, 5\} \}$.
En compréhension : $\{ n \in \mathbb{N}^* \ \mid \ \sqrt{n} \in \mathbb{N} \text{ et } n \le 25 \}$.

Les trois notations décrivent le même ensemble. Le choix dépend de ce que l'on veut mettre en avant : les valeurs explicites, la règle de construction, ou la propriété définissante.

Compétences à pratiquer

Passer de la compréhension à l'extension
Passer de l'extension à la compréhension
Traduire en mots une notation par compréhension

I.3 Cardinal d'un ensemble fini

Compter les éléments d'un ensemble fini est l'opération la plus élémentaire que l'on puisse y effectuer. Le nombre d'éléments est appelé le cardinal ; c'est le pont entre le langage ensembliste et l'arithmétique des entiers.

Définition — Cardinal d'un ensemble fini

Un ensemble est fini s'il a un nombre fini d'éléments. Le nombre d'éléments est appelé le cardinal de l'ensemble, noté $|E|$ ou $\mathrm{card}(E)$. Par convention, $|\emptyset| = 0$.

Exemple

$|\{a, b, c\}| = 3$.
$|\{0, 1, 2, \dots, 10\}| = 11$.
$|\{ n \in \mathbb{N} \ \mid \ n^2 \le 100 \}| = 11$ (les éléments sont $0, 1, \dots, 10$).
$\mathbb{N}, \mathbb{Z}, \mathbb{R}$ ne sont pas finis, donc $|E|$ n'est pas défini ici pour ces ensembles (l'« infini » sera précisé dans un autre chapitre).

Compétences à pratiquer

Compter les éléments directement
Compter des éléments définis par compréhension
Compter une liste avec répétitions

I.4 Inclusion et sous-ensembles

Deux ensembles se rapportent l'un à l'autre de deux manières fondamentalement différentes. Ils peuvent être égaux (avoir les mêmes éléments), ou l'un peut être contenu dans l'autre (tout élément du plus petit est élément du plus grand). Cette dernière relation est l'inclusion. Nous nous en servirons constamment pour démontrer des égalités d'ensembles, selon le slogan « montrer deux inclusions ».

Définition — Inclusion$\virgule$ sous-ensemble

Soient $E$ et $F$ deux ensembles. On dit que $E$ est inclus dans $F$, ou que $E$ est une partie (ou sous-ensemble) de $F$, et l'on note $E \subset F$, si tout élément de $E$ est élément de $F$ : $$ E \subset F \ \iff \ \forall x, \ (x \in E \implies x \in F). $$ La négation est notée $E \not\subset F$ et signifie $\exists x \in E, \ x \notin F$.

Exemple

La chaîne classique des ensembles de nombres : $$ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}. $$

Tout entier est rationnel ($n = n/1$) ; tout rationnel est réel ; tout réel est complexe (de partie imaginaire nulle). Les inclusions sont strictes : $-1 \in \mathbb{Z}$ mais $-1 \notin \mathbb{N}$ ; $\tfrac{1}{2} \in \mathbb{Q}$ mais $\tfrac{1}{2} \notin \mathbb{Z}$ ; $\sqrt{2} \in \mathbb{R}$ mais $\sqrt{2} \notin \mathbb{Q}$ ; $i \in \mathbb{C}$ mais $i \notin \mathbb{R}$.

Exemple

$A \subset E$ signifie que tout élément de $A$ appartient aussi à $E$. Visuellement, la région de $A$ est incluse dans la région de $E$. Le point $x$ appartient à $A$ (donc à $E$) ; le point $y$ appartient à $E$ mais pas à $A$.

Appartenance $\ne$ Inclusion

Les deux relations $\in$ et $\subset$ ne doivent pas être confondues. $\in$ relie un élément à un ensemble ; $\subset$ relie un ensemble à un ensemble. L'image : $-1 \in \mathbb{Z}$ mais $-1 \not\subset \mathbb{Z}$ ($-1$ est une bille du sac, pas un sous-sac) ; $\mathbb{N} \subset \mathbb{Z}$ mais $\mathbb{N} \notin \mathbb{Z}$ ($\mathbb{N}$ est un sous-sac de $\mathbb{Z}$, pas une bille de $\mathbb{Z}$).

Proposition — Égalité par double inclusion

Pour tous ensembles $E$ et $F$ : $$ E = F \ \iff \ \big( E \subset F \big) \wedge \big( F \subset E \big). $$ Cette caractérisation est la technique universelle pour démontrer une égalité d'ensembles : démontrer $E \subset F$, puis démontrer $F \subset E$.

Preuve

Par définition, $E = F$ signifie $\forall x, \ (x \in E \iff x \in F)$. La biconditionnelle $A \iff B$ est par définition $(A \implies B) \wedge (B \implies A)$. En substituant : $$ \begin{aligned} E = F &\iff \forall x, \ \big( (x \in E \implies x \in F) \wedge (x \in F \implies x \in E) \big) && \text{(développement de $\iff$)} \\ &\iff \big( \forall x, \ x \in E \implies x \in F \big) \wedge \big( \forall x, \ x \in F \implies x \in E \big) && \text{($\forall$ distribue sur $\wedge$)} \\ &\iff (E \subset F) \wedge (F \subset E) && \text{(définition de $\subset$)}. \end{aligned} $$

Exemple

Démontrer que $\{ x \in \mathbb{R} \ \mid \ x^2 = x \} = \{0, 1\}$.

Correction

On démontre les deux inclusions.

($\subset$) Soit $x \in \{ x \in \mathbb{R} \ \mid \ x^2 = x \}$. Alors $x^2 = x$, donc $x(x - 1) = 0$, soit $x = 0$ ou $x = 1$. Donc $x \in \{0, 1\}$.
($\supset$) Soit $x \in \{0, 1\}$. Si $x = 0$, alors $x^2 = 0 = x$, OK. Si $x = 1$, alors $x^2 = 1 = x$, OK. Dans les deux cas, $x$ vérifie $x^2 = x$.

Par double inclusion, les deux ensembles sont égaux.

Proposition — L'ensemble vide est inclus dans tout ensemble

Pour tout ensemble $E$ : $$ \emptyset \subset E. $$

Preuve

Il faut montrer $\forall x, \ x \in \emptyset \implies x \in E$. Soit $x$ quelconque. L'hypothèse $x \in \emptyset$ est fausse (aucun élément n'appartient à $\emptyset$), donc l'implication est automatiquement vraie (vérité par défaut).

Compétences à pratiquer

Décider si $A \subset B$
Démontrer une inclusion par argument direct
Démontrer une égalité par double inclusion

I.5 Ensemble des parties

Étant donné un ensemble $E$, on peut former un nouvel ensemble dont les éléments sont les parties (sous-ensembles) de $E$. C'est l'ensemble des parties $\mathcal{P}(E)$. La construction monte d'un cran d'abstraction : les éléments de $\mathcal{P}(E)$ sont eux-mêmes des ensembles. Cette distinction de niveau --- une partie de $E$ est un élément de $\mathcal{P}(E)$ --- est l'opération mentale la plus subtile du chapitre. Visualisez $E$ comme un sac de billes ; alors $\mathcal{P}(E)$ est un sac de sacs, chaque sac étant une sous-collection de billes de $E$.

Définition — Ensemble des parties

Pour tout ensemble $E$, l'ensemble des parties de $E$ est l'ensemble de tous les sous-ensembles de $E$ : $$ \mathcal{P}(E) = \{ A \ \mid \ A \subset E \}. $$ Pour tout ensemble $A$ : $$ A \in \mathcal{P}(E) \ \iff \ A \subset E. $$

Exemple

Pour $E = \{0, 1, 2\}$ : $$ \mathcal{P}(E) = \big\{ \, \emptyset, \ \{0\}, \ \{1\}, \ \{2\}, \ \{0, 1\}, \ \{0, 2\}, \ \{1, 2\}, \ \{0, 1, 2\} \, \big\}. $$ $\mathcal{P}(E)$ a $8 = 2^3$ éléments : un de cardinal $0$ ($\emptyset$), trois de cardinal $1$, trois de cardinal $2$, un de cardinal $3$ ($E$ lui-même). En général, pour un ensemble fini $E$ de cardinal $n$, $\mathcal{P}(E)$ a pour cardinal $2^n$ --- résultat que nous redémontrerons rigoureusement dans un chapitre ultérieur sur le dénombrement.

Exemple

Pour tout ensemble $E$, $\emptyset$ et $E$ lui-même sont éléments de $\mathcal{P}(E)$ : $$ \emptyset \in \mathcal{P}(E) \quad \text{et} \quad E \in \mathcal{P}(E). $$ Le premier tient car $\emptyset \subset E$ (Proposition précédente). Le second tient car $E \subset E$ (tout élément de $E$ est élément de $E$ --- tautologie).

Exemple

Pour $E = \{a, b, c\}$, l'ensemble des parties $\mathcal{P}(E)$ a $2^3 = 8$ éléments. On peut les organiser par inclusion (une arête $X \to Y$ signifie $X \subset Y$ sans ensemble intermédiaire) :

Compétences à pratiquer

Lister tous les éléments de $\mathcal{P}(E)$ pour $E$ petit
Calculer $|\mathcal{P}(E)|$
Décider si $X \in \mathcal{P}(E)$

I.6 Intervalles d'entiers

Les entiers $\{0, 1, 2, \dots, n\}$ forment l'ensemble d'indices canonique des mathématiques --- il indexe les sommes, les produits, les récurrences, les familles, les $n$-uplets. On lui donne une notation dédiée et on calcule son cardinal une fois pour toutes. Cette notation ne doit pas être confondue avec l'intervalle réel de mêmes bornes : $[0, 3]$ contient $\sqrt{2}$, $\llbracket 0, 3 \rrbracket$ ne le contient pas.

Définition — Intervalle d'entiers

Pour deux entiers $a, b \in \mathbb{Z}$, l'intervalle d'entiers $\llbracket a, b \rrbracket$ est l'ensemble des entiers compris entre $a$ et $b$ au sens large : $$ \llbracket a, b \rrbracket = \{ n \in \mathbb{Z} \ \mid \ a \leq n \leq b \}. $$ Par convention, $\llbracket a, b \rrbracket = \emptyset$ lorsque $a > b$. Les variantes semi-ouverte et ouverte sont définies de manière analogue : $\llbracket a, b \llbracket \, = \{n \in \mathbb{Z} \mid a \leq n < b\}$.

Exemple

Trois cas concrets : $$ \llbracket 0, 3 \rrbracket = \{0, 1, 2, 3\}, \qquad \llbracket -2, 1 \rrbracket = \{-2, -1, 0, 1\}, \qquad \llbracket 5, 5 \rrbracket = \{5\}. $$ Et un cas limite : $\llbracket 7, 4 \rrbracket = \emptyset$ (puisque $7 > 4$).

Proposition — Cardinal d'un intervalle d'entiers

Pour tous $a, b \in \mathbb{Z}$ avec $a \leq b$ : $$ |\llbracket a, b \rrbracket| = b - a + 1. $$ En particulier, $|\llbracket 1, n \rrbracket| = n$ et $|\llbracket 0, n \rrbracket| = n + 1$.

Preuve

L'application $\varphi : k \mapsto a + k$ envoie $\llbracket 0, b - a \rrbracket$ sur $\llbracket a, b \rrbracket$ de manière bijective (sa réciproque est $n \mapsto n - a$), donc les deux ensembles ont même cardinal. Il reste à dénombrer $\llbracket 0, b - a \rrbracket = \{0, 1, \dots, b - a\}$, qui a $b - a + 1$ éléments.
Le « $+ 1$ » est la classique règle des piquets : entre deux piquets numérotés $a$ et $b$ il y a $b - a$ intervalles mais $b - a + 1$ piquets.

Exemple

Les tâches de dénombrement deviennent des « one-liners » :

Le nombre d'entiers de $17$ à $42$ inclus est $42 - 17 + 1 = 26$.
Le nombre d'entiers strictement compris entre $a$ et $b$, i.e.\ dans $\llbracket a + 1, b - 1 \rrbracket$, vaut $b - a - 1$ (lorsque $b > a + 1$).
Le nombre d'entiers pairs dans $\llbracket 1, 2n \rrbracket$ est $n$, puisqu'ils forment l'image bijective $\{2, 4, \dots, 2n\}$ de $\llbracket 1, n \rrbracket$ par $k \mapsto 2k$.

Compétences à pratiquer

Calculer le cardinal d'un intervalle d'entiers
Compter des entiers sous contrainte
Comparer intervalles d'entiers et intervalles réels

II Opérations sur les ensembles

On aborde à présent les constructions qui fabriquent de nouveaux ensembles à partir d'anciens : réunion, intersection, différence, complémentaire, produit cartésien. Chaque construction reflète un connecteur logique, et les identités algébriques attendues (commutativité, associativité, distributivité, De Morgan) sont toutes vraies. On énonce et démontre les centrales, puis on clôt par trois notions plus avancées : recouvrement disjoint (partition), produit cartésien et fonction indicatrice.

Avant d'énumérer les opérations une par une, voici le récapitulatif d'un coup d'œil --- une seule image par relation, toutes dans le même ensemble ambiant $E$ (dessiné comme le rectangle). \renewcommand{\arraystretch}{1.6}

Notation	Signification	Diagramme de Venn
$\overline{A}$	Complémentaire de $A$ dans $E$
$A \subset B$	$A$ est inclus dans $B$
$A \cup B$	Réunion : dans $A$ ou dans $B$
$A \cap B$	Intersection : dans $A$ et dans $B$
$A \setminus B$	Différence : dans $A$ mais pas dans $B$
$A \cap B = \emptyset$	$A$ et $B$ sont disjoints

\renewcommand{\arraystretch}{1} Les sous-sections suivantes donnent la définition formelle de chaque construction, la caractérisation par appartenance (qui n'est que le connecteur logique correspondant sur $\in$) et les lois algébriques.

II.1 Réunion et intersection

Les deux opérations binaires $\cup$ et $\cap$ sont les images des connecteurs logiques $\vee$ et $\wedge$. Elles se généralisent naturellement aux familles indexées arbitraires, donnant $\bigcup$ et $\bigcap$. Les lois d'associativité, de commutativité et de distributivité découlent des lois correspondantes de la logique.

Définition — Réunion et intersection (binaires)

Soient $A$ et $B$ deux ensembles.

La réunion de $A$ et $B$ est l'ensemble $$ A \cup B = \{ x \ \mid \ x \in A \ \vee \ x \in B \}. $$
L'intersection de $A$ et $B$ est l'ensemble $$ A \cap B = \{ x \ \mid \ x \in A \ \wedge \ x \in B \}. $$

Le moyen mnémotechnique : $\cup$ correspond à « ou » / $\vee$ / $\exists$ ; $\cap$ correspond à « et » / $\wedge$ / $\forall$.

Exemple

$\{1, 2, 3\} \cup \{2, 4\} = \{1, 2, 3, 4\}$ (réunion).
$\{1, 2, 3\} \cap \{2, 4\} = \{2\}$ (intersection).
$[0, 2] \cup [1, 3] = [0, 3]$ et $[0, 2] \cap [1, 3] = [1, 2]$.
$\mathbb{N} \cup \mathbb{Z} = \mathbb{Z}$ et $\mathbb{N} \cap \mathbb{Z} = \mathbb{N}$ (puisque $\mathbb{N} \subset \mathbb{Z}$).

Exemple

La réunion $A \cup B$ est la région totale grisée ; l'intersection $A \cap B$ est la lentille centrale. Le moyen mnémotechnique : $\cup$ correspond à « ou » / $\vee$ ; $\cap$ correspond à « et » / $\wedge$.

Définition — Réunion et intersection d'une famille indexée

Soient $I$ un ensemble non vide et, pour chaque $i \in I$, $A_i$ un ensemble.

La réunion de la famille est $$ \bigcup_{i \in I} A_i = \{ x \ \mid \ \exists i \in I, \ x \in A_i \}. $$
L'intersection de la famille est $$ \bigcap_{i \in I} A_i = \{ x \ \mid \ \forall i \in I, \ x \in A_i \}. $$

Exemple

Pour chaque $n \in \mathbb{N}^*$, posons $I_n = [-1/n, 1/n] \subset \mathbb{R}$. Alors : $$ \bigcup_{n \in \mathbb{N}^*} I_n = [-1, 1] \quad \text{et} \quad \bigcap_{n \in \mathbb{N}^*} I_n = \{0\}. $$ L'intersection se réduit à un seul point car, plus $n$ est grand, plus $I_n$ est étroit autour de $0$. Visuellement, les intervalles s'emboîtent vers $\{0\}$.

Proposition — Distributivité de $\cap$ et $\cup$

Pour tout ensemble $B$ et toute famille indexée $(A_i)_{i \in I}$ (avec $I$ non vide) : $$ B \cap \bigcup_{i \in I} A_i = \bigcup_{i \in I} (B \cap A_i) \qquad B \cup \bigcap_{i \in I} A_i = \bigcap_{i \in I} (B \cup A_i). $$

Preuve

On démontre la première identité par équivalence directe sur l'appartenance ; la seconde est duale. Pour tout $x$ : $$ \begin{aligned} x \in B \cap \bigcup_{i \in I} A_i &\iff x \in B \wedge x \in \bigcup_{i \in I} A_i && \text{(définition de $\cap$)} \\ &\iff x \in B \wedge \big( \exists i \in I, \ x \in A_i \big) && \text{(définition de $\bigcup$)} \\ &\iff \exists i \in I, \ \big( x \in B \wedge x \in A_i \big) && \text{($B$ ne dépend pas de $i$, $\wedge$ commute avec $\exists$)} \\ &\iff \exists i \in I, \ x \in B \cap A_i && \text{(définition de $\cap$)} \\ &\iff x \in \bigcup_{i \in I} (B \cap A_i) && \text{(définition de $\bigcup$)}. \end{aligned} $$ Les deux ensembles ont la même caractérisation par appartenance, donc sont égaux.

Exemple

La distributivité en image : la région grisée de $A \cap (B \cup C)$ est exactement la réunion de $A \cap B$ et $A \cap C$. Lire l'image est une démonstration visuelle de l'identité.

Proposition — Inclusion caractérisée par réunion ou intersection

Pour tous ensembles $A$ et $B$, les énoncés suivants sont équivalents : $$ A \subset B \quad \iff \quad A \cup B = B \quad \iff \quad A \cap B = A. $$

Preuve

On démontre un cycle de trois implications.

($A \subset B \implies A \cup B = B$). Supposons $A \subset B$. Alors pour tout $x$ : $x \in A \cup B \iff x \in A \vee x \in B \iff x \in B$ (car $x \in A$ entraîne déjà $x \in B$). Donc $A \cup B = B$.
($A \cup B = B \implies A \cap B = A$). Supposons $A \cup B = B$. Alors $A \subset A \cup B = B$ (tout élément de $A$ est dans $A \cup B$). Donc pour tout $x$ : $x \in A \cap B \iff x \in A \wedge x \in B \iff x \in A$ (car $x \in A$ entraîne $x \in B$). Donc $A \cap B = A$.
($A \cap B = A \implies A \subset B$). Supposons $A \cap B = A$. Alors $A = A \cap B \subset B$.

Compétences à pratiquer

Calculer $A \cup B$ et $A \cap B$ pour de petits ensembles
Calculer des réunions et intersections d'intervalles
Calculer des réunions et intersections indexées
Appliquer les lois de base de $\cup$ et $\cap$

II.2 Différence et complémentaire

La différence $A \setminus B$ rassemble ce qui est dans $A$ mais pas dans $B$. Quand $A$ est fixé comme ensemble ambiant $E$, la différence $E \setminus A$ est appelée le complémentaire de $A$ et notée $\complement A$ ou $\overline{A}$. Le complémentaire, appliqué aux opérations $\cup$ et $\cap$, vérifie les lois de De Morgan --- l'image ensembliste des lois de De Morgan de la logique.

Définition — Différence$\virgule$ complémentaire

Soient $A$ et $B$ deux ensembles.

La différence $A$ privé de $B$ est $$ A \setminus B = \{ x \ \mid \ x \in A \ \wedge \ x \notin B \}. $$
Soit $E$ un ensemble et $A \subset E$. Le complémentaire de $A$ dans $E$ est l'ensemble $E \setminus A$, noté $\overline{A}$ ou $\complement_E A$ ou $A^c$ lorsque $E$ est clair par le contexte.

Exemple

$\{1, 2, 3, 4\} \setminus \{2, 4\} = \{1, 3\}$.
$\mathbb{R} \setminus \mathbb{Q}$ est l'ensemble des nombres irrationnels ; $\sqrt{2}, \pi, e \in \mathbb{R} \setminus \mathbb{Q}$.
Dans $E = \mathbb{R}$ : $\overline{[0, 1]} = \, ]-\infty, 0[ \, \cup \, ]1, +\infty[$.
Pour tout $E$ et $A \subset E$ : $A \cap \overline{A} = \emptyset$ et $A \cup \overline{A} = E$.

Exemple

À gauche, $A \setminus B$ est la partie de $A$ qui n'appartient pas à $B$. À droite, $\complement_E A$ (aussi noté $E \setminus A$ ou $\bar A$) est la partie de $E$ en dehors de $A$.

Proposition — Double complémentaire

Soit $E$ un ensemble et $A \subset E$. Alors $$ \overline{\overline{A}} = A. $$

Preuve

Par définition, $x \in \overline{A}$ signifie $x \in E \wedge x \notin A$. Donc : $$ x \in \overline{\overline{A}} \iff x \in E \wedge \neg(x \in \overline{A}) \iff x \in E \wedge \neg(x \in E \wedge x \notin A). $$ Par De Morgan et double négation : $\neg(x \in E \wedge x \notin A) \iff x \notin E \vee x \in A$. Combiné à $x \in E$, la disjonction se réduit à $x \in A$. Donc $x \in \overline{\overline{A}} \iff x \in A$, soit $\overline{\overline{A}} = A$.

Compétences à pratiquer

Calculer $A \setminus B$
Calculer le complémentaire $\complement_E A$
Utiliser le double complémentaire
Utiliser l'identité $A \setminus B \equal A \cap \overline{B}$

II.3 Lois de De Morgan ensemblistes

Les lois de De Morgan de la logique se traduisent verbatim en théorie des ensembles : le complémentaire transforme la réunion en intersection, et l'intersection en réunion. On les énonce sous la forme générale indexée pour qu'elles s'appliquent directement à des familles.

Proposition — De Morgan pour les ensembles

Soit $E$ un ensemble et $(A_i)_{i \in I}$ une famille de parties de $E$ (avec $I$ non vide). Alors : $$ \overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i} \qquad \overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}. $$ Le complémentaire d'une réunion est l'intersection des complémentaires, et réciproquement.

Preuve

On démontre la première identité ; la seconde est duale (appliquer la première aux complémentaires $\overline{A_i}$ et utiliser le double complémentaire). Pour tout $x \in E$ : $$ \begin{aligned} x \in \overline{\bigcup_{i \in I} A_i} &\iff x \notin \bigcup_{i \in I} A_i && \text{(définition de $\overline{\phantom{X}}$)} \\ &\iff \neg \big( \exists i \in I, \ x \in A_i \big) && \text{(définition de $\bigcup$)} \\ &\iff \forall i \in I, \ x \notin A_i && \text{(négation du $\exists$)} \\ &\iff \forall i \in I, \ x \in \overline{A_i} && \text{(définition de $\overline{\phantom{X}}$)} \\ &\iff x \in \bigcap_{i \in I} \overline{A_i} && \text{(définition de $\bigcap$)}. \end{aligned} $$

Exemple

Dans $E = \mathbb{R}$, avec $A = \, ]-\infty, 0]$ et $B = [1, +\infty[$ : $$ A \cup B = \, ]-\infty, 0] \cup [1, +\infty[, \qquad \overline{A \cup B} = \, ]0, 1[. $$ D'autre part, $\overline{A} = \, ]0, +\infty[$ et $\overline{B} = \, ]-\infty, 1[$, donc $\overline{A} \cap \overline{B} = \, ]0, 1[$. Les deux calculs concordent, confirmant De Morgan.

Exemple

De Morgan en image : les régions grisées coïncident. Le complémentaire d'une réunion est l'intersection des complémen\-taires.

Compétences à pratiquer

Appliquer De Morgan à des ensembles concrets
Simplifier des expressions avec De Morgan
Démontrer des identités mêlant distributivité et De Morgan

II.4 Ensembles disjoints$\virgule$ recouvrement disjoint$\virgule$ partition

Deux ensembles sont disjoints lorsqu'ils n'ont aucun élément commun. Une famille d'ensembles deux à deux disjoints qui ensemble remplissent un ensemble ambiant $E$ est appelée recouvrement disjoint ; si aucune pièce n'est vide, on parle de partition. Les partitions sont la forme ensembliste de « découper un problème en cas » : diviser $E$ en morceaux disjoints, traiter chacun, et recombiner.

Définition — Ensembles disjoints$\virgule$ recouvrement disjoint$\virgule$ partition

Soit $E$ un ensemble.

Deux parties $A, B \subset E$ sont disjointes lorsque $A \cap B = \emptyset$. Une famille $(A_i)_{i \in I}$ de parties est deux à deux disjointe lorsque $\forall i, j \in I, \ i \ne j \implies A_i \cap A_j = \emptyset$. La réunion d'une famille deux à deux disjointe est parfois notée $\bigsqcup_{i \in I} A_i$ pour souligner la disjonction.
Une famille $(A_i)_{i \in I}$ de parties de $E$ est un recouvrement disjoint de $E$ lorsque : $$ E = \bigsqcup_{i \in I} A_i $$ c'est-à-dire que les $A_i$ sont deux à deux disjointes et leur réunion vaut $E$.
Un recouvrement disjoint est une partition lorsque, de plus, chaque $A_i$ est non vide.

Exemple

Pour $A \subset E$, le couple $\{A, \overline{A}\}$ est un recouvrement disjoint de $E$. C'est une partition si $A \ne \emptyset$ et $A \ne E$.
Dans $\mathbb{Z}$, le couple $\{2 \mathbb{Z}, 2 \mathbb{Z} + 1\}$ (pairs, impairs) est une partition.
Dans $\mathbb{Z}$, la famille $\{3 \mathbb{Z}, 3 \mathbb{Z} + 1, 3 \mathbb{Z} + 2\}$ (résidus modulo $3$) est une partition à trois morceaux.
Pour tout ensemble $E$, la famille des singletons $\{ \{x\} \ \mid \ x \in E \}$ est une partition de $E$ (la « plus fine »).

Exemple

À gauche, deux ensembles disjoints : $A \cap B = \emptyset$. À droite, une partition de $E$ en quatre morceaux $A_1, A_2, A_3, A_4$ : deux à deux disjoints, tous non vides, et recouvrant $E$.

Compétences à pratiquer

Décider si deux ensembles sont disjoints
Vérifier qu'une famille est une partition
Construire une partition
Utiliser la caractérisation ponctuelle
Mêler intervalles d'entiers et opérations ensemblistes

II.5 Produit cartésien

Le produit cartésien de deux ensembles associe chaque élément du premier à chaque élément du second. C'est la construction qui sous-tend les coordonnées dans le plan ($\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$) et les $n$-uplets en général. Deux distinctions importantes dès le début : l'ordre compte dans un $n$-uplet ($(1, 2) \ne (2, 1)$), à la différence d'un ensemble ; et un $n$-uplet peut avoir des répétitions ($(1, 1, 2)$), à la différence d'un ensemble où chaque élément n'est listé qu'une fois.

Définition — Produit cartésien

Soient $E_1, E_2, \dots, E_n$ des ensembles ($n \ge 1$). Le produit cartésien de $E_1, \dots, E_n$ est l'ensemble des $n$-uplets dont la $i$-ième composante est dans $E_i$ : $$ E_1 \times E_2 \times \dots \times E_n = \{ (x_1, x_2, \dots, x_n) \ \mid \ \forall i \in \{1, \dots, n\}, \ x_i \in E_i \}. $$ Lorsque tous les $E_i$ sont égaux à un même ensemble $E$, on note $E^n$ au lieu de $E \times \dots \times E$.

Exemple

$\{1, 2, 3\} \times \{a, b\} = \{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) \}$ --- six couples.
$\mathbb{R}^2 = \{ (x, y) \ \mid \ x, y \in \mathbb{R} \}$, les points du plan.
$\mathbb{R}^3 = \{ (x, y, z) \ \mid \ x, y, z \in \mathbb{R} \}$, les points de l'espace.
Pour des ensembles finis, $|E_1 \times E_2| = |E_1| \times |E_2|$ --- le cardinal se multiplie.

Exemple

Pour $A = \{1, 2, 3, 4\}$ et $B = \{1, 2, 3\}$, le produit cartésien $A \times B$ est l'ensemble des $4 \times 3 = 12$ couples $(a, b)$. Le représenter en grille est le modèle standard pour démontrer $|A \times B| = |A| \cdot |B|$.

$n$-uplet $\ne$ Ensemble

Un $n$-uplet $(x_1, \dots, x_n)$ n'est pas un ensemble $\{x_1, \dots, x_n\}$. Deux différences clés :

Ordre. $(1, 2) \ne (2, 1)$ mais $\{1, 2\} = \{2, 1\}$.
Répétitions. $(1, 1, 2)$ est un $3$-uplet à deux premières composantes égales, tandis que $\{1, 1, 2\} = \{1, 2\}$ est un ensemble à $2$ éléments.

Le produit cartésien fabrique des $n$-uplets ; la réunion fabrique des ensembles. Confondre les deux mène à des erreurs --- par exemple écrire $\{x, y\}$ pour désigner le couple $(x, y)$.

Compétences à pratiquer

Lister les éléments de $A \times B$
Calculer $|A \times B|$
Distinguer $n$-uplets et ensembles

II.6 Fonction indicatrice

La fonction indicatrice transforme la question ensembliste « $x$ appartient-il à $A$ ? » en une réponse numérique ($0$ ou $1$). C'est le pont entre l'algèbre ensembliste et l'arithmétique ordinaire : $\cap$ devient un produit, $\cup$ devient une somme (presque), $\overline{\phantom{X}}$ devient $1 - \cdot$. Conséquence : toute identité ensembliste devient une identité polynomiale entre fonctions à valeurs dans $\{0, 1\}$, vérifiable mécaniquement.

Définition — Fonction indicatrice

Soit $E$ un ensemble et $A \subset E$. La fonction indicatrice de $A$ est la fonction $$ \mathbf{1}_A : E \longrightarrow \{0, 1\}, \qquad \mathbf{1}_A(x) = \begin{cases} 1 & \text{si } x \in A, \\ 0 & \text{si } x \notin A. \end{cases} $$ On l'appelle aussi fonction caractéristique de $A$ dans $E$ (notée $\chi_A$ dans certains ouvrages).

Exemple

Avec $E = \mathbb{R}$ et $A = [0, 1]$, la fonction indicatrice $\mathbf{1}_A$ est le créneau égal à $1$ sur $[0, 1]$ et $0$ ailleurs :

Avec $E = \mathbb{N}$ et $A = 2\mathbb{N}$ les entiers pairs, $\mathbf{1}_A(n) = 1$ si $n$ est pair, $0$ si $n$ est impair. Les deux cas extrêmes : $\mathbf{1}_E$ est la fonction constante $1$, et $\mathbf{1}_{\emptyset}$ est la fonction constante $0$.

Proposition — Algèbre ensembliste en indicatrices

Soit $E$ un ensemble et $A, B \subset E$. En tant que fonctions de $E$ dans $\{0, 1\}$ : $$ \begin{aligned} \mathbf{1}_{A \cap B} &= \mathbf{1}_A \cdot \mathbf{1}_B, \\ \mathbf{1}_{\overline{A}} &= 1 - \mathbf{1}_A, \\ \mathbf{1}_{A \cup B} &= \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot \mathbf{1}_B, \\ \mathbf{1}_{A \setminus B} &= \mathbf{1}_A \cdot (1 - \mathbf{1}_B), \\ \mathbf{1}_A^2 &= \mathbf{1}_A. \end{aligned} $$ Et la caractérisation : $$ A \subset B \iff \mathbf{1}_A \leq \mathbf{1}_B, \qquad A = B \iff \mathbf{1}_A = \mathbf{1}_B. $$

Preuve

Toutes les identités se vérifient ponctuellement : pour $x \in E$, les deux membres prennent la même valeur dans $\{0, 1\}$.

Intersection. $\mathbf{1}_{A \cap B}(x) = 1 \iff x \in A \wedge x \in B \iff \mathbf{1}_A(x) = 1 \wedge \mathbf{1}_B(x) = 1 \iff \mathbf{1}_A(x) \cdot \mathbf{1}_B(x) = 1$ (puisque les valeurs sont dans $\{0, 1\}$).
Complémentaire. $\mathbf{1}_{\overline{A}}(x) = 1 \iff x \notin A \iff \mathbf{1}_A(x) = 0 \iff 1 - \mathbf{1}_A(x) = 1$.
Réunion. Par De Morgan, $A \cup B = \overline{\overline{A} \cap \overline{B}}$, donc $$ \mathbf{1}_{A \cup B} = 1 - \mathbf{1}_{\overline{A}} \cdot \mathbf{1}_{\overline{B}} = 1 - (1 - \mathbf{1}_A)(1 - \mathbf{1}_B) = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B. $$
Différence. $A \setminus B = A \cap \overline{B}$, donc $\mathbf{1}_{A \setminus B} = \mathbf{1}_A \cdot (1 - \mathbf{1}_B)$.
Idempotence. $\mathbf{1}_A^2 = \mathbf{1}_{A \cap A} = \mathbf{1}_A$ --- de manière équivalente, $0^2 = 0$ et $1^2 = 1$.
Inclusion. $A \subset B \iff \forall x, \ (x \in A \Rightarrow x \in B) \iff \forall x, \ \mathbf{1}_A(x) \leq \mathbf{1}_B(x)$ (le seul cas interdit est $\mathbf{1}_A(x) = 1$ et $\mathbf{1}_B(x) = 0$).
Égalité. Appliquer le point précédent deux fois, ou remarquer que $A = B \iff \forall x, \ (x \in A \iff x \in B) \iff \forall x, \ \mathbf{1}_A(x) = \mathbf{1}_B(x)$.

Exemple

De Morgan via les indicatrices. L'identité $\mathbf{1}_{\overline{A \cup B}} = \mathbf{1}_{\overline{A} \cap \overline{B}}$ devient une vérification algébrique en une ligne : $$ 1 - (\mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B) = (1 - \mathbf{1}_A)(1 - \mathbf{1}_B), $$ ce qui n'est que le développement du membre de droite. À comparer avec la preuve par chaîne d'appartenance de De Morgan donnée plus haut --- l'approche par indicatrices remplace la logique par l'algèbre.

Exemple

Différence symétrique. L'ensemble $A \triangle B = (A \setminus B) \cup (B \setminus A)$ (dans $A$ ou dans $B$ mais pas dans les deux) a pour indicatrice $$ \mathbf{1}_{A \triangle B} = \mathbf{1}_A + \mathbf{1}_B - 2 \mathbf{1}_A \mathbf{1}_B = \mathbf{1}_A + \mathbf{1}_B \pmod{2}. $$ Le lien « $\pmod{2}$ » est la raison pour laquelle théorie des ensembles et algèbre de Boole sur $\mathbb{F}_2 = \{0, 1\}$ coïncident.

Compétences à pratiquer

Calculer $\mathbf{1}_A$
Démontrer des identités ensemblistes via les indicatrices
Démontrer la formule du crible par les indicatrices

Aller à la section

Notation	Signification	Diagramme de Venn
\(\overline{A}\)	Complémentaire de \(A\) dans \(E\)
\(A \subset B\)	\(A\) est inclus dans \(B\)
\(A \cup B\)	Réunion : dans \(A\) ou dans \(B\)
\(A \cap B\)	Intersection : dans \(A\) et dans \(B\)
\(A \setminus B\)	Différence : dans \(A\) mais pas dans \(B\)
\(A \cap B = \emptyset\)	\(A\) et \(B\) sont disjoints