L’objet fondamental à la base des mathématiques discrètes (voire même des mathématiques en général) est une structure appelée ensemble. Un ensemble est une structure qui regroupe des objets. On peut parler de l’ensemble des étudiants du programme Sciences, informatique et mathématique, de l’ensemble des arbres sur le terrain du cégep ou encore l’ensemble des nombres naturels compris entre \(4\) et \(42\text{.}\)
Le terme objet est pris dans son sens intuitif et large. Au début de la théorie des ensembles, plusieurs paradoxes furent relevés, le plus célèbre par Bertrand Russel. On peut pallier à ces paradoxes en donnant une définition axiomatique de la théorie des ensembles. Pour ce qui suit, ce n’est pas nécessaire. On utilisera plutôt l’approche naïve de la théorie des ensembles. Un ensemble sera donc bien défini si, étant donné tout objet, on peut déterminer sans aucun doute son appartenance ou non à l’ensemble.
Dans cette section, on définit la notion d’ensemble, la description en extension et en compréhension d’un ensemble, la relation d’appartenance d’un objet à un ensemble, la relation entre deux ensembles et la cardinalité d’un ensemble. On donne aussi des exemples importants d’ensembles, dont l’ensemble vide.
On commence avec la définition d’un ensemble. Un ensemble sera bien défini si on peut toujours déterminer l’appartenance ou non appartenance d’un objet à cet ensemble sans aucun doute. Pour voir un exemple d’ensemble qui n’est pas bien défini, on pourra consulter l’exercice 1.1.5.8.
Un ensemble est une collection non ordonnée d’objets. On appelle aussi les objets des éléments ou des membres. Typiquement, on dénote un ensemble par une lettre majuscule du début de l’alphabet.
Bien que les ensembles soient normalement utilisés pour regrouper des objets avec des propriétés similaires, rien n’oblige que ce soit le cas. On peut même avoir un ensemble dont les éléments sont eux-mêmes des ensembles.
On peut décrire un ensemble de plusieurs manières. La plus simple, mais pas toujours pratique ou même possible, est d’énumérer ses éléments. On dit alors que l’ensemble est décrit en extension. On utilisera les accolades \(\{, \}\) pour encadrer les éléments d’un ensemble. Ceci est cohérent avec la notion d’ensemble de plusieurs langages de programmation, dont Python/Sage, qui sera utilisé à plusieurs reprises dans ces notes.
Tel que mentionné dans la définition, un ensemble est une collection non ordonnée d’objets. Cela signifie que l’ordre n’est pas important dans la description de l’ensemble. Ainsi, l’ensemble \(A^{'}=\{4,5,3,7,9,8,6\}\) est en fait le même ensemble que l’ensemble \(A\) de l’exemple 1.1.2. De plus, comme c’est l’appartenance d’un objet à l’ensemble qui est important, la répétition n’est pas nécessaire. L’ensemble \(B^{'}=\{t,u,r,c,o,t,t,e\}\) est le même ensemble que l’ensemble \(B\) de l’exemple 1.1.2.
Dans la description en extension de l’ensemble des carrés parfaits inférieurs à \(100\text{,}\) on a utilisé les « … » afin de limiter l’écriture. On comprend que la suite définie par les premiers termes de la description continue de manière naturelle dans cette omission. Souvent, pour décrire un ensemble contenant beaucoup d’éléments, même une infinité, on utilisera la description en compréhension de l’ensemble. On énonce alors la (ou les) propriété que possèdent les éléments de l’ensemble à l’intérieur même de la description. Dans ce cas, on utilisera souvent une lettre minuscule pour dénoter un élément arbitraire de l’ensemble analogue à celle utilisée pour le nom de l’ensemble ou encore ayant un sens particulier dans le contexte.
Dans la description en compréhension, on sépare la variable utilisée de la condition avec une barre verticale. Cette barre devrait se lire comme l’expression « tel que ». On voit souvent le « deux points (:) » comme autre possibilité de notation.
Il peut exister plusieurs manières valides de décrire un objet en compréhension. Toutefois, on veut respecter une certaine structure syntaxique. On peut avoir :
un ensemble domaine, suivie d’une condition pour filtrer les éléments du domaine, par exemple \(A=\{x\in \Z ~|~ x^2< 25\}\text{;}\)
Étant donné un objet quelconque \(a\) et un ensemble \(A\text{,}\) on écrit \(a\in A\) (se lit \(a\) est dans \(A\) ou encore \(a\) appartient à \(A\)) si \(a\) est un élément de l’ensemble \(A\) et \(a\notin A\) (\(a\) n’appartient pas à \(A\)) sinon. Puisque plusieurs descriptions sont possibles pour un même ensemble, il peut être pratique de déterminer si deux ensembles sont égaux. On définit ci-dessous deux relations possibles entre deux ensembles, celle d’inclusion et celle d’égalité.
Soit \(A\) et \(B\) deux ensembles avec la propriété que, pour tout élément \(a\in A\text{,}\) on a aussi \(a\in B\text{.}\) On dit alors que \(A\) est un sous-ensemble de \(B\) et on écrit \(A\subseteq B\text{.}\) Si on est certain que les ensembles sont différents, on pourra utiliser le symbole d’inclusion stricte, \(\subset\text{.}\) Ces symboles font penser aux symboles pour les inégalités. Ainsi, bien que d’usage beaucoup moins répandu, on peut aussi écrire \(B\supseteq A\text{.}\)
Ces symboles existent aussi dans leur version «négative» (\(\not\subseteq,\not\subset,\not\supseteq,\not\supset\)), utilisés pour la non inclusion d’un ensemble dans un autre. De plus, une variante souvent utilisée pour mettre l’emphase sur un sous-ensemble strict est le symbole \(\subsetneq\text{.}\)
L’ensemble \(A\) contient trois éléments. Un sous-ensemble pourrait donc potentiellement contenir un, deux ou même trois éléments. On énumère les possibilités ci-dessous.
\(A_1=\{a\},A_2=\{b\}\) et \(A_{3}=\{c\}\text{,}\) qui ne contiennent qu’un élément.
Plus tard, on verra comment compter tous les sous-ensembles possibles à partir d’un ensemble ayant \(n\) éléments. Avec une petite précision, on reparlera de l’ensemble de tous les sous-ensembles possibles à la définition 1.1.13.
Soit \(A\) et \(B\) deux ensembles. On dit que les ensembles sont égaux, et on écrit \(A=B\ \text{,}\) si et seulement s’ils sont formés des mêmes éléments.
\begin{align*}
A&=\{2,4,6\}\\
B&=\{n~|~ n \text{ est un nombre entier compris entre }0\text{ et }9\text{ inclusivement}\}\\
C&=\{4,6,2\}\\
D&=\{n~|~ n \text{ est un nombre entier et } -1\leq n\leq 9\}
\end{align*}
On peut remarquer les relations suivantes: \(C\subseteq A\text{,}\)\(A\subseteq C\text{,}\)\(A\subseteq B\text{,}\)\(B\subset D\text{,}\)\(A=C\text{.}\) On aurait pu noter sans problème que \(B\subsetneq D\) (équivalent à \(\subset\text{,}\) ou même \(B\subseteq D\) (moins strict, mais quand même vrai), mais pas que \(A\subset C\text{.}\)
Le nombre d’éléments dans un ensemble est appelé la cardinalité de l’ensemble. Pour un ensemble \(A\text{,}\) on la note \(\text{card}(A)=|A|\text{.}\)
La cardinalité d’un ensemble peut être n’importe quel nombre naturel ou même infini. Un ensemble est dit fini si sa cardinalité est un nombre naturel et infini sinon.
Il peut être utile d’avoir une représentation graphique de la notion d’ensemble et des concepts associés. Pour cela on peut utiliser un diagramme de Venn. Dans un tel diagramme, on identifie l’ensemble des tous les objets étudiés par un rectangle. On le notera \(\Omega\) (la lettre grecque omega, majuscule). On l’appelle souvent le référentiel ou encore l’ensemble univers. Dans ce rectangle, un certain nombre d’ensembles peuvent être illustrés, souvent par des cercles.
À titre d’exemple, on prend comme ensemble univers les chiffres arabes \(\Omega=\{0,1,\ldots ,9\}\) et on considère les deux sous-ensembles suivants: \(A=\{1,2,3,4\},B=\{3,4,5,6\}\text{.}\) La figure suivante illustre un diagramme de Venn de ces ensembles.
Un rectangle avec la lettre Omega majuscule est illustré. À l’intérieur, on peut y voir deux cercles qui s’intersectent. Les chiffres de 0 à 9 sont aussi présent. Dans le cercle de gauche, on peut voir que les chiffres 1 et 2 sont présents. Le cercle de droite contient les chiffres 5 et 6. Au centre, à la fois dans le cercle de gauche et dans celui de droite, on peut voir les chiffres 3 et 4. Finalement, à l’extérieur des deux cercles, mais à l’intérieur du rectangle, on voit les chiffres 0,7,8 et 9.
On peut remarquer dans la figure 1.1.10 que les éléments \(3,4\) sont à la fois dans \(A\) et dans \(B\text{.}\) C’est un cas particulier de l’intersection de deux ensembles, qui sera défini dans la section 1.2.
On donne maintenant la définition de certains ensembles importants. L’un deux, l’ensemble univers a déjà été mentionné. Un autre ensemble d’une grande importance est l’ensemble vide. On le note par \(\emptyset\) ou encore \(\{\}\text{.}\) Sa cardinalité est de \(0\text{.}\)C’est le seul ensemble qui possède cette propriété. Il possède aussi la propriété d’être un sous-ensemble de tous les ensembles, incluant lui-même.
Étant donné un ensemble \(A\text{,}\) l’ensemble de tous les ensembles formés des éléments de \(A\text{,}\) c’est-à-dire tous les sous-ensembles de \(A\text{,}\) est appelé l’ensemble des puissances (ou des parties) de \(A\text{.}\) On le note par \(\mathscr{P}(A)\text{.}\)
L’ensemble des nombres réels, noté \(\R\text{.}\) Pour cet ensemble, on se fie à l’intuition de ce que sont les nombres réels, par exemple les nombres situés sur une droite infinie, car donner une définition précise est difficile. Cet ensemble sera peu utilisé, sa nature étant davantage du côté continu que discret.
Dans la description d’un ensemble en compréhension, lorsque les éléments sont des nombres, il est de bon usage de spécifier dans quel ensemble ces nombres se trouvent. La précision de l’ensemble permet de déterminer avec certitude les éléments de l’ensemble. Par exemple, l’ensemble \(A=\{k ~|~ k^2\leq 16\}\) est égal à \(\{-4,-3,-2,-1,0,1,2,3,4\}\) si l’on considère le domaine comme \(\Z\text{,}\) mais vaut \(\{0,1,2,3,4\}\) si l’on prend comme domaine \(\N\text{.}\)
On délimite les ensembles par les paires d’accolades, soit en énumérant les éléments ou en donnant une description des membres. Pour les ensembles dont la cardinalité est infinie, il peut être difficile ou impossible d’énumérer les éléments. En particulier, certains sous-ensembles des nombres réels sont assez importants pour qu’on leur donne une notation propre à eux. Ce sont les intervalles. Voici quatre exemples de cette notation:
Soit \(A,B\subseteq\Omega\) deux ensembles quelconques. Dessiner toutes les configurations relatives possibles que peuvent avoir \(A\) et \(B\) dans un diagramme de Venn (en supposant que si un sous-ensemble est vide, il est absent).
On définit \(X\) comme l’ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes. Ainsi, pour un ensemble \(A\text{,}\) on a \(A \in X\) si et seulement si \(A\notin A\text{.}\) Déterminer si \(X\) est un ensemble bien défini.
Non, \(X\) n’est pas bien défini. Il n’est pas évident de déterminer si l’élément \(X\) appartient à l’ensemble \(X\text{.}\) D’une part, si \(X\notin X\text{,}\) alors \(X\) fait partie de l’ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes. Or dans ce cas, cela signifie que \(X\in X\text{,}\) ce qui contredit la dernière phrase.
Les deux ensembles ont une cardinalité de deux. L’un de leurs éléments, l’élément \(\{a,b\}\text{,}\) est un élément commun aux deux ensembles. Par contre, le deuxième élément est différent. En effet, l’ensemble \(\Bigl\{\{a,b\},a\Bigr\}\) contient l’élément \(a\text{,}\) alors que l’ensemble \(\Bigl\{\{a,b\},\{a\}\Bigr\}\) contient l’élément \(\{a\}\text{,}\) c’est-à-dire l’ensemble contenant \(a\text{.}\)
Car l’ensemble \(\Bigl\{\{\emptyset,\emptyset\}\Bigr\}\) ne contient qu’un seul élément, c’est-à-dire \(\{\emptyset,\emptyset\}\text{.}\) De l’autre côté, l’ensemble \(\Bigl\{\emptyset,\{\emptyset\}\Bigr\}\) contient deux éléments, l’élément \(\emptyset\) ainsi que l’élément \(\{\emptyset\}\text{.}\)
