Théorie naïve des ensembles#
Introduction#
La théorie des ensembles est l’étude mathématique des collections d’objets. Branche relativement récente des mathématiques, elle est née à la fin de l’année 1873 dans les travaux de Georg Cantor qui étudiait les propriétés des nombres réels. Malgré l’apparente simplicité des objets de base qu’elle traite, les ensembles et leurs éléments, la théorie des ensembles est une branche riche et fondamentale des mathématiques modernes. Sa naissance a marqué un tournant, jouant un rôle central dans la quête pour une fondation formelle des mathématiques qui s’est déroulée à la fin du 19e et au début du 20e siècle. À cette époque, il est devenu évident que des concepts tels que les ensembles infinis n’étaient pas traités correctement par les mathématiciens : de célèbres paradoxes étaient apparus, nécessitant une résolution immédiate - au risque de montrer que les mathématiques ne sont pas logiquement cohérentes ! La solution à cette crise a été apportée par une théorie formelle des ensembles introduite par Zermelo et Fraenkel, qui a finalement réussi à formaliser la notion d’ensembles infinis, donnant ainsi aux mathématiques un fondement adéquat. Depuis lors, la théorie des ensembles a été un sujet actif de recherche pour les mathématiciens, les logiciens et les philosophes. Dans ce cours, nos investigations porteront principalement sur les ensembles finis. Par conséquent, une théorie naïve des ensembles (beaucoup plus simple que la théorie de Zermelo et Fraenkel mentionnée plus haut) suffira. Cela nous donne le privilège de travailler dans un langage informel (au lieu de la logique formelle) et de prendre pour acquis diverses notions de base. Cependant, nous devons toujours être conscients de la faiblesse suivante de notre approche informelle : nos résultats ne seront pas toujours directement transférables des ensembles finis aux ensembles infinis. L’infini est aussi merveilleux que peu intuitif !
Langage mathématique#
Avant de poursuivre notre étude des ensembles, fixons d’abord quelques notions de base du langage mathématique informel que nous développerons au cours de notre étude. Nous commençons par les notions de base de constantes et de connecteurs. Les constantes sont des symboles correspondant à des objets nommés dont nous supposons l’existence. Voici quelques exemples de constantes :
Les symboles \(\top\) et \(\bot\) qui sont lus respectivement comme « vrai » et « faux »,
tout autre symbole tel que \(\bullet, \circ, \triangle\). Bien entendu, un langage qui ne peut se référer qu’à un seul objet à la fois n’est pas très intéressant. Les connecteurs servent à coller les formules pour en former de plus grandes. Dans le cas le plus simple, ils peuvent être soit unaires, auquel cas ils modifient une seule formule, soit binaires, auquel cas ils sont utilisés pour coller deux formules. Les connecteurs de base que nous utiliserons sont :
\(\lnot\) qui est un connecteur unaire lu comme « pas ».
\(\land\) qui est une conjonctive binaire lue comme « et ».
\(\lor\), qui est une conjonction binaire lue comme « ou ».
\(\rightarrow\) qui est une conjonction binaire lue comme « implique ». Voici quelques exemples d’utilisation de ces connecteurs : \(\not \triangle\), \(\top \land \bot\), \(\bullet \implies \top\). Pour les formules plus compliquées, nous pouvons utiliser des parenthèses pour les rendre non ambiguës : \((\not \top) \implies \bot\).
Jusqu’à présent, nous n’avons fait que définir la syntaxe de notre langue : des symboles sans signification intrinsèque et des moyens de les combiner pour former des formules plus grandes. Leur attribuer une signification est le sujet de la sémantique que nous traiterons de manière très informelle :
Aux symboles \(\top\) et \(\bot\), nous attribuerons les deux valeurs booléennes classiques de \(vrai\) et \(faux\).
Aux symboles \(\bullet, \circ, \triangle\) nous pouvons assigner des « objets abstraits » dont nous supposons qu’ils existent déjà et dont la nature précise n’est pas pertinente. Nous attribuons des fonctions booléennes unaires ou binaires aux connecteurs :
A \(\lnot\) nous assignerons la fonction qui associe \(vrai\) à \(faux\) et \(faux\) à \(vrai\).
A \(\land\) nous assignerons la fonction qui s’évalue à \(vrai\) si et seulement si ses deux arguments sont \(vrai\). Autrement dit, à \(P \land Q\) nous assignons la valeur \(vrai\) si et seulement si \(P\) et \(Q\) ont tous les deux la valeur \(vrai\).
A \(\lor\) nous assignerons la fonction qui s’évalue à \(vrai\) si l’une ou l’autre de ses entrées est \(vrai\). C’est-à-dire que \(P \lor Q\) est \(vrai\) si \(P\) ou \(Q\) le sont.
A \(\rightarrow\) nous assignons la fonction qui évalue à \(faux\) si et seulement si son premier argument est \(vrai\) et le second \(faux\) sinon elle est évaluée à \(vrai\). C’est-à-dire que \(P \rightarrow Q\) est toujours \(vrai\) sauf si \(P\) est \(vrai\) et \(Q\) est \(faux\), auquel cas la formule entière a la valeur \(faux\). Nous enrichirons ce langage de nouveaux concepts lorsque cela s’avérera utile. Nous passerons également librement de cette notation plus abstraite à son équivalent en langage naturel, en utilisant celle qui nous permet d’énoncer le plus succinctement et le plus clairement les formules souhaitées.
Les ensembles et leurs éléments#
Nous sommes enfin prêts à présenter nos principaux objets d’étude.
Definition (Ensembles et éléments).
Un ensemble est une collection non ordonnée d’objets, appelés éléments de l’ensemble. Ces éléments sont considérés comme étant tous distincts (aucune répétition n’est autorisée).
Bien que très informelle d’un point de vue mathématique moderne, cette « définition » est assez proche de celle que Cantor lui-même donne dans [Can95] :
Un ensemble est une réunion en une totalité d’objets définis et distincts de notre perception ou de notre pensée, que l’on appelle éléments de l’ensemble. – Georg Cantor
Ayant introduit un nouvel objet mathématique, enrichissons maintenant notre langage avec de nouvelles constantes appropriées pour parler d’ensembles. Tout d’abord, nous introduisons le symbole \(\emptyset\) qui représente l’ensemble vide : l’ensemble qui ne contient aucun élément, que nous supposons existe. Nous supposerons également l’existence de l’ensemble des nombres naturels pour lequel nous introduisons les constantes \(\mathbb{N}\) pour l’ensemble lui-même et les chiffres indo-arabes habituels \(0, 1, 2, 3, \dots\) pour ses éléments. Nous pouvons également admettre quelques fonctions et relations de base et des relations sur les nombres naturels tels que \(+, -, *, /, \geq, \leq\). Enfin, nous adoptons la notation extensionnelle, qui est une façon très répandue de représenter les ensembles en énumérant ses éléments séparés par des virgules et placés entre accolades \(\{, \}\).Par exemple :
Un ensemble contenant les 3 premiers nombres naturels non nuls peut être écrit comme suit : \(\{1, 2, 3\}\).
Un ensemble contenant deux éléments abstraits est \(\{\bullet, \circ \}\).
L’ensemble vide, qui ne contient rien, s’écrit \(\{\}\) ou en abrégé \(\emptyset\). Un ensemble étant un objet en soi peut donc être un élément d’un autre ensemble : \(\{1,2,\{1,5\}\}\) est un ensemble parfaitement valide contenant les éléments \(1, 2, \{1, 5\}\)[1].
Variables et quantificateurs#
Pour faciliter la manipulation des ensembles et de leurs objets, nous enrichissons notre langage en autorisant l’utilisation de variables : celles-ci serviront d’arguments aux aux fonctions ensemblistes. Nous désignerons les variables par des lettres latines minuscules \(x, y, z, \dots\) désignant des éléments et des lettres majuscules telles que \(A, B, S, U \dots\) désignant des ensembles. Les variables elles-mêmes n’ont pas beaucoup d’utilité à moins d’être combinées avec l’utilisation de quantificateurs : le quantificateur universel et le quantificateur existentiel \(\exists\) qui se lisent comme « pour tous » et « il existe ». et « il existe ». Les quantificateurs lient les variables dans une formule : \(\forall\) et \(\exists\) sont tous deux accompagnés accompagnés d’une variable et d’une formule. La syntaxe de base est celle de \(\forall x P\) et \(\exists x P\), où \(P\) est une formule dans laquelle la variable variable \(x\) apparaît libre, c’est-à-dire qu’elle n’est liée à aucun quantificateur. En termes de sémantique, les variables reçoivent des valeurs d’un ensemble qui contient tous les objets qui nous intéressent. Cet ensemble universel est également appelé domaine (ou univers) du discours. La formule \(\forall x~P\) aura la valeur \(vrai\) si et seulement si la formule \(P\) est vraie pour toute affectation possible de \(x\). La formule \(\exists x~P\) prendra la valeur \(vrai\) si et seulement s’il existe au moins une affectation de \(x\) qui rend \(P\) vrai. Par exemple,
La formule \(\exists x~(x \in {1,2,3}) \land (x \in \{2,4,6\})\) est vraie,
tandis que \(\forall x ~ (x \in \{1,2,3\}) \rightarrow (x \{2,4,6\})\) est fausse.
Nous utiliserons souvent l’abréviation \(\exists x \in S~P\) pour signifier \(\exists x ~ (x \in S) \land P\) et \(\forall x \in S~P\) to stand for \(\forall x ~ (x \in S \rightarrow P)\). Prenons \(A = \{1,2,3\}\) et \(B =\{2,5\}\), nous pouvons utiliser cette notation abrégée pour réécrire les deux exemples ci-dessus comme suit :
\(\exists x \in A ~ x \in B\) and
\(\forall x \in A ~ x \in B\).
La relation de sous-ensemble#
Compte tenu de ce qui précède, nous pouvons maintenant définir une relation entre les ensembles qui capture la notion d’un ensemble à l’intérieur d’un autre.
Definition (Sous-ensemble).
Nous disons qu’un ensemble \(A\) est un sous-ensemble d’un ensemble \(B\), noté \(A \subseteq B\), si tous les éléments de \(A\) appartiennent à \(B\). Autrement dit, \(A \subseteq B\) si et seulement si \(\forall x \in A ~ x \in B\).
Deux faits importants en découlent :
Tout ensemble est un sous-ensemble de lui-même : \(A \subseteq A\) est vrai.
L’ensemble vide est un sous-ensemble de tous les ensembles : \(\forall S~\emptyset \subseteq S\) est vrai. Par exemple, \(\{2,4,6\} \subseteq \{1,2,3,4,5,6\}\), tandis que \(\{1,2,3\} \not\subseteq \{1,2,\{3,4,5\}\}\), où \(A \not\subseteq B\) signifie \(\lnot(A \subseteq B)\). Une façon pratique de décrire les sous-ensembles, qui complète la notation extensionnelle introduite ci-dessus, est la façon intensionnelle : nous spécifions qu’un ensemble \(A\) est un sous-ensemble d’un ensemble \(B\) dont les éléments satisfont une propriété supplémentaire. Par exemple,: \(\{ x \in \{1,2,3\} \lvert x >= 2\}\) définit l’ensemble \(\{2,3\}\).
Opérations sur les ensembles#
Au-delà des constructions extensionnelles et intensionnelles d’ensembles, nous pouvons construire de nouveaux ensembles en combinant des ensembles existants, via des opérations :
Definition (Union).
L’union de deux ensembles \(A\) et \(B\), notée \(A \cup B\), est l’ensemble constitué de tous les éléments de \(A\) et de tous ceux de \(B\).
Definition (Intersection).
L’intersection de deux ensembles \(A\) et \(B\), notée \(A \cap B\), est l’ensemble constitué de tous les éléments de \(A\) qui appartiennent aussi à \(B\).
Definition (Différence).
La différence de deux ensembles \(A\) et \(B\), notée \(A \setminus B\), est l’ensemble constitué de tous les éléments de \(A\) qui n’appartiennent pas à \(B\).
(def-complement)
Definition (Complément).
Le complément d’un ensemble \(A\) par rapport au domaine de discours \(U\) est \(U \setminus A\).
Voici quelques identités importantes impliquant ces opérations :
\(A \cap B = B \cap A\)
\(A \cup B = B \cup A\)
\(A \cap (B \cap C) = (A \cap B) \cap C\)
\(A \cup (B \cup C) = (A \cup B) \cup C\)
\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
\(E \setminus (E \setminus A) = A\)
\(E \setminus (A \cup B) = (E \setminus A) \cap (E \setminus B)\)
\(E \setminus (A \cap B) = (E \setminus A) \cup (E \setminus B)\) Une manière simple de se convaincre que ces propriétés sont valables est de dessiner des diagrammes de Venn, dans lesquels l’univers du discours est
dessiné comme une boîte et ses sous-ensembles sont dessinés comme des formes «
ovaloïdes », de sorte que les formes correspondant à deux ensembles \(A,B\) se
chevauchent si \(A \cap B \neq \emptyset\) et ne se chevauchent pas dans le cas
contraire.
Par exemple, pour trois ensembles \(A,B,C\) avec \(A \cap B \neq \emptyset, (A
\cup B) \cap C \neq \emptyset\) nous dessinons ce qui suit :
Cardinalité#
Une notion importante pour les ensembles est celle de cardinalité :
Définition (cardinalité)
La cardinalité d’un ensemble fini est son nombre d’éléments.
On utilise souvent la notation \(\lvert A \rvert\) pour désigner la cardinalité d’un ensemble \(A\). Par exemple, l’ensemble \(\{1,2,3\}\) est de cardinalité \(\lvert\{1,2,3\}\rvert = 3\) tandis que \(\lvert\{1,2,\{1,5\},\emptyset,\{2,3,\{4\}\}\}\rvert = 5\).
Warning
Un avertissement s’impose : la définition ci-dessus est très, très informelle et assez circulaire. La définition formelle de la cardinalité utilisée dans les mathématiques contemporaines est en fait fondée sur la notion de bijections, qui traite de manière uniforme le cas des ensembles finis et infinis.
Tuples et produits cartésiens#
Introduisons maintenant une autre notion de collection d’éléments.
Définition (\(n\)-tuple)
Étant donné un entier naturel \(n \in \mathbb{N}\), un \(n\)-tuple est une collection ordonnée de \(n\) éléments.
Contrairement aux ensembles, les \(n\)-tuples prennent en compte l’ordre dans lequel les éléments sont énuméréset permettent également les répétitions. Nous dénoterons les \(n\)-tuples en utilisant une syntaxe similaire à celle des ensembles, en remplaçant les accolades \(\{,\}\) par des parenthèses \((,)\). Deux \(n\)-tuples seront considérés comme égaux s’ils contiennent les mêmes éléments dans le même ordre. Des exemples de \(n\)-tuples sont :
\((1,2)\), un \(2\)-tuple également appelé une paire.
\((2,1)\), un autre \(2\)-tuple différent du précédent.
\((1,2,3,4,5)\), \((1,8,10,3,0)\), deux \(5\)-tuples. La construction suivante permet de construire \(n\)-tuples à partir d’ensembles.
Definition (Produit cartésien)
Etant donné un entier naturel \(n dans \mathbb{N}\) et \(n\) ensembles \(S_1, S_2, \dots, S_n\), le produit cartésien de \(n\) ensembles \(S_1 \times S_2 \times \dots \times S_n\) est l’ensemble de tous les \(n\)-tuples possibles pour lesquels le premier élément est tiré de \(S_1\), le second est tiré de \(S_2\), et ainsi de suite :
Ensemble des parties#
La construction suivante nous permet de rassembler tous les sous-groupes d’un ensemble donné \(S\) :
Definition (Ensemble des parties)
Étant donné un ensemble \(S\), l’ensemble des parties \(\mathcal{P}(S)\) est l’ensemble constitué de tous les sous-ensembles de \(S\) :
Par exemple \(\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\). Pour les ensembles finis, la cardinalité de leur ensemble des parties est donnée par le lemme suivant.
Lemme (Cardinalité de l’ensemble des parties)
Étant donné un ensemble fini \(S\), l’ensemble des parties \(\mathcal{P}(S)\) a pour cardinalité :
Exercises#
Exercice 1#
Évaluez les formules suivantes :
\(\emptyset \subseteq \emptyset\),
\(\emptyset \subset \emptyset\),
\(\emptyset \in \emptyset\),
\(\forall X~\emptyset \subseteq X\),
\(\forall X~\emptyset \in X\),
\(\exists X~\emptyset \in X\),
\(\exists X~\emptyset \notin X\).
\(\emptyset \in \mathcal{P}(S)\) pour tout ensemble \(S\).
\(S \in \mathcal{P}(S)\) pour tout ensemble \(S\).
Exercice 2#
Décrire un moyen de passer de formules impliquant des occurrences du quantificateur \(\forall\) à des formules impliquant uniquement le quantificateur \(\exists\), d’une manière qui préserve la valeur de vérité de ces formules.
Exercice 3#
Décrire un moyen de passer de formules impliquant des occurrences du quantificateur \(\exists\) à des formules impliquant uniquement le quantificateur \(\forall\), d’une manière qui préserve la valeur de vérité de ces formules.
Exercice 4#
Donnez une définition équivalente de la relation d’appartenance utilisant le quantificateur \(\exists\).
Exercice 5#
En supposant que le domaine du discours est un ensemble fini \(U\), décrivez une façon de traduire les formules impliquant \(\forall\) et \(\exists\) en formules n’impliquant pas de quantificateurs, d’une manière qui préserve la valeur de vérité de ces formules.
Exercice 6#
Dessinez des diagrammes de Venn pour vous convaincre des propriétés énumérées dans la section Opérations sur les ensembles.
Exercice 7#
Écrire en extension les ensembles suivants :
\(\{1,2,3\} \cup \{4,5,6\}\)
\(\{1,2,3\} \cup \{3,4,5\}\)
\(\{1,2,3\} \cup \{1,3,4\}\)
\(\{1,2,3\} \cap \{4,5,6\}\)
\(\{1,2,3\} \cap \{2,3,4\}\)
\((\{1,2,3\} \cap \{2,3,4\}) \cup \{5,6\}\)
\((\{1,2\} \cup \{3,4\}) \cap \{2,4\}\)
Exercice 8#
On note \(A\) l’ensemble \(\{1,2,3\}\) et \(B\) l’ensemble \(\{-1,0.1\}\). Écrire en extension les ensembles suivants:
\(A \cap B\)
\(A \cup B\)
\(A \setminus B\)
\(B \setminus A\)
\(\{x + 2 \lvert x \in A\}\)
\(\{2x \lvert x \in B \}\)
\(\{x + y \lvert x \in A, y \in B \}\)
\(\{x+y \lvert x \in A, y \in A\}\)
\(\{x + x \lvert x \in A\}\)
\(A \times B\)
\(\mathcal{P}(A)\)
\(\mathcal{P}(B)\)
Exercice 9#
En sachant que \(A \cup B = \{1,2,3,4\}, A \cap B = \{3\}, A \setminus B = \{1,2\}, \overline\{A\} = \{4,5,6\}\), pouvez-vous dessiner un diagramme de Venn pour les ensembles \(A, B\) dans l’univers \(U = \{1,2,3,4,5,6\}\).