Ensembles et opérations

Au chapitre 2, on a passé tout le chapitre à parler du « domaine de discours », cet ensemble sur lequel varient les variables, en se contentant d’une idée intuitive : une collection d’objets. Le chapitre s’est même fermé sur une promesse : « $A \subseteq B$ » se dira « $\forall x,\ x \in A \Rightarrow x \in B$ ». Il est temps de la tenir. Mais qu’est-ce qu’un ensemble, au juste ? Comment le décrit-on, comment teste-t-on qu’un objet lui appartient, comment en fabrique-t-on de nouveaux à partir d’anciens ?

La réponse est plus belle qu’un simple catalogue de symboles. Tu vas découvrir que la théorie des ensembles n’est pas un nouveau territoire à apprendre par coeur : c’est la logique du chapitre 1, mais coulée dans des objets. Le « ou » devient l’union, le « et » devient l’intersection, le « non » devient le complémentaire, et les lois de De Morgan que tu connais déjà vont réapparaître, identiques, sur des ensembles.

Décrire un ensemble

Un ensemble Ensemble Collection d'objets, appelés ses éléments, considérée comme un tout. Un ensemble est entièrement déterminé par ses éléments : deux ensembles ayant exactement les mêmes éléments sont égaux. On le décrit en extension, en listant ses éléments entre accolades comme {1, 2, 3}, ou en compréhension, en donnant la propriété que ses éléments vérifient, comme {x | x > 3}. est une collection d’objets, ses éléments, considérée comme un tout.

Le geste de base, celui dont tout le reste découle, est de demander si un objet est dedans ou dehors. Cette relation s’appelle l’ appartenance Appartenance Relation fondamentale entre un objet et un ensemble, notée ∈. « x ∈ A » se lit « x appartient à A » et signifie que x est l'un des éléments de A. Sa négation se note ∉. L'appartenance est le prédicat de base de la théorie des ensembles : tout le reste, inclusion et opérations, se définit à partir d'elle. et se note $\in$ :

se lit « $x$ appartient à $A$ », c’est-à-dire « $x$ est l’un des éléments de $A$ ». Sa négation se note $x \notin A$. Remarque que « $x \in A$ » est exactement un prédicat au sens du chapitre 2 : selon ce qu’on met à la place de $x$, c’est vrai ou faux. Toute la théorie des ensembles est bâtie sur ce seul prédicat.

Il y a deux façons de décrire quels objets sont dans un ensemble :

• En extension : on liste les éléments entre accolades. $A = \{1, 2, 3\}$. Pratique pour les petits ensembles.
• En compréhension : on donne la propriété que les éléments vérifient. $A = \{x \mid x > 0 \text{ et } x < 4 \text{ et } x \text{ entier}\}$. Ici la barre $\mid$ se lit « tel que ».

La description en compréhension dévoile le lien profond avec le chapitre 2 : un ensemble en compréhension, $\{x \mid P(x)\}$, n’est rien d’autre qu’un prédicat $P$ transformé en objet. L’ensemble, c’est la collection de tous les témoins qui rendent $P$ vrai.

Un dernier principe, discret mais fondateur : un ensemble est entièrement déterminé par ses éléments. Deux ensembles qui ont exactement les mêmes éléments sont le même ensemble, peu importe comment on les a décrits. Ainsi $\{1, 2, 3\}$, $\{3, 2, 1\}$ et $\{1, 1, 2, 3\}$ sont un seul et même ensemble : l’ordre et les répétitions ne comptent pas. Ce principe s’appelle l’extensionnalité, et c’est lui qui rend la suite possible.

Comparer : l’inclusion et l’égalité

Maintenant qu’on sait tester l’appartenance, on peut comparer deux ensembles. La promesse du chapitre 2 arrive ici. L’ inclusion Inclusion Relation entre deux ensembles, notée ⊆. « A ⊆ B » se lit « A est inclus dans B » ou « A est un sous-ensemble de B », et signifie que tout élément de A est aussi élément de B. Sa définition est un énoncé quantifié : A ⊆ B équivaut à « pour tout x, x ∈ A implique x ∈ B ». Deux ensembles sont égaux exactement quand chacun est inclus dans l'autre (double inclusion). , notée $\subseteq$, dit que tout élément du premier ensemble est aussi dans le second :

Cette équation se lit : « $A$ est inclus dans $B$ » exactement quand « pour tout $x$, si $x$ appartient à $A$, alors $x$ appartient à $B$ ». L’inclusion n’est donc pas un symbole de plus à mémoriser : c’est une implication universelle, le « pour tout » du chapitre 2 appliqué au prédicat d’appartenance. On dit que $A$ est un sous-ensemble de $B$.

Comment dit-on alors que deux ensembles sont égaux ? Par l’extensionnalité, $A = B$ veut dire qu’ils ont les mêmes éléments, c’est-à-dire que chacun est inclus dans l’autre :

Ce découpage s’appelle la double inclusion. Il a l’air anodin, mais c’est l’outil de démonstration le plus utilisé dès qu’on veut prouver que deux ensembles sont égaux : on prouve une inclusion, puis l’autre. Garde-le en tête, le chapitre 4 en fera son pain quotidien.

On peut aussi rassembler tous les sous-ensembles d’un ensemble $E$ dans un nouvel ensemble : l’ ensemble des parties Ensemble des parties Ensemble de tous les sous-ensembles d'un ensemble E, noté P(E). Ses éléments sont eux-mêmes des ensembles : l'ensemble vide et E lui-même en font toujours partie. Si E a n éléments, alors P(E) en a 2 puissance n, car chaque élément de E est soit pris, soit laissé dans un sous-ensemble. Par exemple P({a, b}) = {∅, {a}, {b}, {a, b}}. , noté $\mathcal{P}(E)$. Ses éléments sont eux-mêmes des ensembles. Par exemple :

On y retrouve toujours $\varnothing$ et $E$ lui-même. Et un comptage simple : si $E$ a $n$ éléments, $\mathcal{P}(E)$ en a $2^n$, car pour fabriquer un sous-ensemble, chaque élément de $E$ est soit pris, soit laissé, deux choix indépendants répétés $n$ fois.

Combiner : les opérations sont les connecteurs

Voici le coeur du chapitre. À partir de deux ensembles, on en fabrique de nouveaux avec trois opérations. Chacune se définit par sa condition d’appartenance, et cette condition est un connecteur du chapitre 1.

L’ union Union Opération qui réunit deux ensembles, notée ∪. A ∪ B est l'ensemble des objets qui appartiennent à A ou à B (ou aux deux). Sa condition d'appartenance est une disjonction : x ∈ A ∪ B équivaut à « x ∈ A ou x ∈ B ». L'union est au « ou » logique ce que l'objet est au connecteur. , notée $\cup$, rassemble :

Un objet est dans $A \cup B$ s’il est dans $A$ ou dans $B$ (ou dans les deux). L’union, c’est le « ou » logique devenu objet.

L’ intersection Intersection Opération qui ne garde que ce que deux ensembles ont en commun, notée ∩. A ∩ B est l'ensemble des objets qui appartiennent à la fois à A et à B. Sa condition d'appartenance est une conjonction : x ∈ A ∩ B équivaut à « x ∈ A et x ∈ B ». Quand A ∩ B est vide, on dit que A et B sont disjoints. , notée $\cap$, ne garde que le commun :

Un objet est dans $A \cap B$ s’il est dans $A$ et dans $B$. L’intersection, c’est le « et ». Quand $A \cap B = \varnothing$, on dit que $A$ et $B$ sont disjoints.

Le complémentaire Complémentaire Opération qui retourne ce qui n'est pas dans un ensemble, relativement à un univers de référence. Le complémentaire de A, noté Aᶜ (ou A barre), est l'ensemble des objets de l'univers qui n'appartiennent pas à A. Sa condition d'appartenance est une négation : x ∈ Aᶜ équivaut à « non (x ∈ A) ». Le complémentaire dépend de l'univers choisi : sans univers fixé, il n'a pas de sens. , noté $A^c$, retourne ce qui n’est pas dans $A$, par rapport à un univers de référence $U$ :

C’est le « non ». Attention : le complémentaire n’a de sens que si l’univers est fixé. Sans dire « non par rapport à quoi », $A^c$ ne veut rien dire. C’est le même rôle que le domaine de discours du chapitre 2.

Le tableau se complète tout seul : à chaque connecteur logique correspond une opération ensembliste, parce que les deux sont la même idée vue de deux côtés.

Et puisque les opérations sont des connecteurs, les lois qui régissent les connecteurs deviennent des lois sur les ensembles. Les lois de De Morgan du chapitre 1, $\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$, se transposent mot pour mot :

Lis la première à voix haute : « le complémentaire d’une union est l’intersection des complémentaires ». Pour ne pas être dans $A$ ou $B$, il faut n’être ni dans $A$, ni dans $B$. C’est exactement le « non (P ou Q) revient à (non P) et (non Q) » du chapitre 1. Tu ne démontres pas une nouvelle vérité : tu reconnais une ancienne sous un nouveau costume.

Manipuler De Morgan sur des objets

Le composant ci-dessous rend tout cela tangible. L’univers est $U = \{1, 2, 3, 4, 5, 6\}$, avec au départ $A = \{1, 2, 3\}$ et $B = \{3, 4, 5\}$. Tu places chaque élément dans l’une des quatre régions en cliquant dessus, et tu choisis l’opération à afficher : le composant te montre la condition d’appartenance correspondante et surligne les éléments retenus.

Ta mission : active le mode De Morgan. À gauche, le composant calcule $(A \cup B)^c$ ; à droite, $A^c \cap B^c$. Les deux listes sont identiques, ici $\{6\}$, le seul élément hors des deux cercles. Maintenant déplace des éléments d’une région à l’autre, autant que tu veux : les deux côtés restent toujours égaux. Tu n’as rien démontré encore, mais tu as vu la loi résister à chaque essai.

Trois questions à te poser en jouant :

• Mets tous les éléments dans la région « hors de A et B ». Que vaut $A \cup B$ ? Et $(A \cup B)^c$ ? L’égalité De Morgan tient-elle encore sur des ensembles vides ?
• Choisis l’opération « différence $A \setminus B$ ». Devine sa condition d’appartenance avant de la lire : à quel connecteur correspond « dans $A$ mais pas dans $B$ » ?
• Place un seul élément dans l’intersection. Combien de régions le complémentaire de $A$ recouvre-t-il ?

Fabriquer du neuf : le produit cartésien

Les trois opérations précédentes restent à l’intérieur de l’univers de départ. Une dernière construction sort vraiment du lot, au sens propre : le produit cartésien Produit cartésien Opération qui fabrique un ensemble de couples à partir de deux ensembles, notée ×. A × B est l'ensemble de tous les couples ordonnés (a, b) où a ∈ A et b ∈ B. L'ordre compte : (a, b) n'est pas (b, a). Si A a m éléments et B en a n, alors A × B en a m × n. C'est la brique de départ des relations et des fonctions. , noté $\times$. Il fabrique des couples :

$A \times B$ est l’ensemble de tous les couples ordonnés dont la première coordonnée vient de $A$ et la seconde de $B$. L’ordre compte : $(a, b)$ n’est pas $(b, a)$. Et le comptage est limpide : si $A$ a $m$ éléments et $B$ en a $n$, alors $A \times B$ en a $m \times n$, d’où le nom. Avec $A = \{1, 2\}$ et $B = \{x, y\}$ :

On n’ira pas plus loin ici, mais retiens où mène cette brique : un couple, c’est le germe d’une relation, et une relation bien choisie, c’est une fonction. Tout le langage des fonctions, que les cours suivants déploieront, se construit sur ce simple $\times$.

En une phrase

Un ensemble est déterminé par ses éléments via l’appartenance ; l’inclusion est une implication universelle, l’union un « ou », l’intersection un « et », le complémentaire un « non », si bien que les lois de De Morgan du chapitre 1 régissent encore les ensembles, mot pour mot.

Vers le chapitre 4

Tu as vu, sur le composant et sur des exemples, que $(A \cup B)^c = A^c \cap B^c$. Tu l’as testé, encore et encore, sans jamais le prendre en défaut. Mais teste n’est pas démontre : vérifier une identité sur un univers de six éléments ne prouve pas qu’elle vaut pour tous les ensembles, exactement comme essayer cent nombres ne prouve pas une propriété universelle (souviens-toi du contre-exemple de Fermat au chapitre 2). Comment passe-t-on de « ça marche à chaque essai » à « c’est vrai, toujours, sans exception » ?

La clé est déjà dans ce chapitre : pour prouver $A = B$, on prouve $A \subseteq B$ et $B \subseteq A$ ; et chaque inclusion est un « $\forall x,\ x \in A \Rightarrow x \in B$ », donc une implication universelle à démontrer. Le chapitre 4 donne précisément les techniques pour démontrer de tels énoncés, sans exemple ni dessin : preuve directe, contraposée, raisonnement par l’absurde. La double inclusion de ce chapitre est l’obligation de preuve que le suivant t’apprendra à honorer.

Exercices

Prends une feuille et un crayon. Les corrigés sont juste en dessous, regarde-les seulement après avoir essayé.

Exercice 1 : prouver une inclusion par l’appartenance

Montrer que $A \subseteq A \cup B$ pour tous ensembles $A$ et $B$. Indication : traduire l’inclusion en énoncé quantifié, puis raisonner sur un élément quelconque.

Exercice 2 : vérifier De Morgan sur un univers fini

L’univers est $U = \{1, 2, 3, 4, 5, 6\}$, avec $A = \{1, 2, 3\}$ et $B = \{3, 4, 5\}$. Calculer $(A \cup B)^c$ d’un côté, puis $A^c \cap B^c$ de l’autre, et comparer.

Sources

• Halmos, P. (1960). Naive Set Theory. Van Nostrand. La référence classique, courte et lumineuse, sur la théorie intuitive des ensembles.
• Cantor, G. (1895). « Beiträge zur Begründung der transfiniten Mengenlehre. » Mathematische Annalen 46. L’acte fondateur de la théorie des ensembles.

Pour aller plus loin

• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Chapitre 1 sur les ensembles et leurs opérations, dans l’esprit exact de ce cours.
• Enderton, H. (1977). Elements of Set Theory. Academic Press. Pour la version axiomatique, une fois le chapitre 4 digéré.