Ensembles, inclusion et parties P(E)

Un ensemble est une collection d'objets distincts, appelés ses éléments, définie de façon qu'on puisse toujours dire si un objet en fait partie ou non. Ce chapitre pose le vocabulaire et les notations de tout le cours : appartenance, cardinal, inclusion et ensemble des parties. Ce sont aussi les notions les plus souvent mélangées en copie.

C'est quoi un ensemble en maths ?

Les ports TCP d'un serveur web, les comptes d'un domaine Active Directory, les chiffres de la base 2 : chacun de ces objets est un ensemble. Deux règles le définissent.

Chaque élément compte une seule fois. {1 ; 2 ; 2 ; 3} et {1 ; 2 ; 3} désignent le même ensemble.
L'ordre ne compte pas. {1 ; 2 ; 3} = {3 ; 1 ; 2}.

On nomme un ensemble par une lettre majuscule (E, A, B) et ses éléments par des minuscules (x, a). Un élément peut être un nombre, un mot, un couple, ou même un autre ensemble : {{1 ; 2} ; 3} est un ensemble de deux éléments, l'ensemble {1 ; 2} et le nombre 3.

Écrire un ensemble : en extension ou en compréhension

Il y a deux façons de décrire un ensemble.

En extension, tu donnes la liste de tous ses éléments :

B = {0 ; 1}

W = {22 ; 80 ; 443}, les ports ouverts sur un serveur web administré en SSH.

En compréhension, tu donnes une propriété que vérifient exactement ses éléments, sous la forme {x ∈ E | propriété de x}, qui se lit « l'ensemble des x de E tels que… ». Le symbole | (on trouve aussi « ; » ou « : ») se lit « tel que ».

A = {n ∈ ℕ | n < 5} = {0 ; 1 ; 2 ; 3 ; 4}

D = {n ∈ ℕ | n divise 12} = {1 ; 2 ; 3 ; 4 ; 6 ; 12}

C = {x ∈ ℤ | x² = 4} = {−2 ; 2}

L'écriture en compréhension est la seule possible pour un ensemble infini, comme l'ensemble des nombres pairs P = {n ∈ ℕ | n = 2k avec k ∈ ℕ}. C'est aussi celle d'une requête : SELECT * FROM poste WHERE ram_go >= 16 décrit, en compréhension, l'ensemble des postes qui ont au moins 16 Go de mémoire.

Les ensembles de nombres à connaître :

Notation	Nom	Exemples d'éléments
ℕ	Entiers naturels	0, 1, 2, 255
ℤ	Entiers relatifs	−3, 0, 42
ℚ	Nombres rationnels (fractions)	1/3, −0,25
ℝ	Nombres réels	√2, π, 0,1

On a ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ. Une étoile retire le zéro : ℕ* = {1 ; 2 ; 3 ; …}. En informatique, on travaille surtout avec des ensembles finis : les entiers codés sur 8 bits, {0 ; 1 ; … ; 255}, les 26 lettres de l'alphabet, les adresses d'un réseau.

L'ensemble vide, noté ∅, ne contient aucun élément. C'est par exemple {x ∈ ℝ | x² = −1}, ou le résultat d'une requête qui ne renvoie aucune ligne. Un ensemble qui contient un seul élément, comme {5}, s'appelle un singleton.

Appartenance : le symbole ∈

On écrit x ∈ E pour dire que x est un élément de E (« x appartient à E »), et x ∉ E sinon.

Avec W = {22 ; 80 ; 443} : 80 ∈ W, 21 ∉ W.

L'appartenance relie un élément à un ensemble. C'est la seule question qu'on puisse poser à un ensemble : « cet objet en fait-il partie ? ». C'est aussi ce que teste l'opérateur IN de SQL (WHERE port IN (22, 80, 443)) ou x in s en Python.

Le cardinal d'un ensemble fini

Le cardinal d'un ensemble fini E est son nombre d'éléments. Il se note card(E), et parfois |E| ou #E.

Ensemble	Cardinal
W = {22 ; 80 ; 443}	card(W) = 3
D = {1 ; 2 ; 3 ; 4 ; 6 ; 12}	card(D) = 6
∅	card(∅) = 0
{∅}	card({∅}) = 1
{{1 ; 2} ; 3}	2 (l'ensemble {1 ; 2} compte pour un élément)
L'ensemble des octets	256

En SQL, le cardinal d'un résultat, c'est COUNT(*), et le cardinal d'un ensemble de valeurs sans doublon, COUNT(DISTINCT colonne).

Inclusion : le symbole ⊂

A est inclus dans B, ce qu'on note A ⊂ B, quand tout élément de A est aussi un élément de B. On dit aussi que A est une partie (ou un sous-ensemble) de B.

A ⊂ B signifie : pour tout x, si x ∈ A, alors x ∈ B.

Exemples :

{22 ; 80} ⊂ {22 ; 80 ; 443}.
{21 ; 80} ⊄ {22 ; 80 ; 443}, car 21 n'est pas dans le second ensemble. Un seul élément qui manque suffit à refuser l'inclusion.
ℕ ⊂ ℤ.
L'ensemble des administrateurs du domaine est inclus dans l'ensemble des comptes du domaine.

Trois propriétés sont toujours vraies, pour n'importe quel ensemble E :

∅ ⊂ E : l'ensemble vide est inclus dans tout ensemble (il n'a aucun élément qui pourrait manquer à E) ;
E ⊂ E : tout ensemble est inclus dans lui-même ;
si A ⊂ B et B ⊂ C, alors A ⊂ C.

Égalité. Deux ensembles sont égaux quand ils ont exactement les mêmes éléments, c'est-à-dire quand A ⊂ B et B ⊂ A. C'est ainsi qu'on démontre une égalité d'ensembles : on prouve les deux inclusions, ce qu'on appelle une double inclusion.

Une inclusion en réseau

Le réseau 192.168.10.0/24 est l'ensemble des 256 adresses de 192.168.10.0 à 192.168.10.255. Le sous-réseau 192.168.10.64/26 contient les 64 adresses de 192.168.10.64 à 192.168.10.127. Toutes sont dans le /24 : le sous-réseau est inclus dans le réseau. Découper un réseau en sous-réseaux, c'est le partager en parties qui ne se chevauchent pas ; tu retrouveras cette idée de partition au chapitre 5 et dans le cours Réseaux.

Appartenance ou inclusion : ne plus les confondre

C'est l'erreur la plus fréquente en début d'année. Pose-toi une seule question : ce qui est à gauche est-il un élément ou un ensemble ?

Un élément appartient : 3 ∈ {1 ; 2 ; 3}.
Un ensemble est inclus : {3} ⊂ {1 ; 2 ; 3}.

Écriture	Vrai ou faux ?	Pourquoi
3 ∈ {1 ; 2 ; 3}	Vrai	3 est un des éléments
{3} ∈ {1 ; 2 ; 3}	Faux	Les éléments sont 1, 2 et 3, pas l'ensemble {3}
{3} ⊂ {1 ; 2 ; 3}	Vrai	Le seul élément de {3} est dans l'ensemble
3 ⊂ {1 ; 2 ; 3}	Faux, et mal écrit	3 n'est pas un ensemble
∅ ⊂ {1 ; 2 ; 3}	Vrai	Toujours vrai
∅ ∈ {1 ; 2 ; 3}	Faux	∅ n'est pas un des éléments
{1 ; 2} ∈ {{1 ; 2} ; 3}	Vrai	{1 ; 2} est un élément de cet ensemble
{1 ; 2} ⊂ {{1 ; 2} ; 3}	Faux	1 n'est pas un élément de {{1 ; 2} ; 3}

L'ensemble des parties P(E)

L'ensemble des parties de E, noté P(E) (souvent avec un P calligraphique), est l'ensemble de tous les sous-ensembles de E, y compris ∅ et E lui-même.

Ses éléments sont des ensembles. On a donc : A ∈ P(E) si et seulement si A ⊂ E.

Exemple. Avec E = {1 ; 2 ; 3}, range les parties par nombre d'éléments pour n'en oublier aucune :

Nombre d'éléments	Parties	Combien
0	∅	1
1	{1}, {2}, {3}	3
2	{1 ; 2}, {1 ; 3}, {2 ; 3}	3
3	{1 ; 2 ; 3}	1

P(E) = {∅ ; {1} ; {2} ; {3} ; {1 ; 2} ; {1 ; 3} ; {2 ; 3} ; {1 ; 2 ; 3}}, et card(P(E)) = 8.

Pourquoi un ensemble de n éléments a 2ⁿ parties

Pour fabriquer une partie de E, tu passes chaque élément en revue et tu décides : je le prends, ou je ne le prends pas. Deux choix pour le premier élément, deux pour le deuxième, et ainsi de suite : 2 × 2 × … × 2 = 2ⁿ façons de choisir.

Ce « je le prends ou pas » se code par un bit : 1 si l'élément est dans la partie, 0 sinon. Une fois les éléments de E rangés dans un ordre fixé, chaque partie correspond à un mot binaire de n bits, et chaque mot de n bits à une partie. C'est ce qu'on appelle la fonction caractéristique de la partie, et c'est ainsi que les programmes stockent des ensembles dans un entier : un masque de bits.

Les droits Unix sont des parties de {r ; w ; x}

Sous Linux, les droits d'un fichier pour son propriétaire forment une partie de E = {r ; w ; x} (lecture, écriture, exécution). Il y en a 2³ = 8. Chaque partie s'écrit sur 3 bits, dans l'ordre r, w, x, ce qui donne un chiffre de 0 à 7 : c'est la notation octale de chmod.

Partie de {r ; w ; x}	Bits r w x	Chiffre octal	Affichage `ls -l`
∅	0 0 0	0	`---`
{x}	0 0 1	1	`--x`
{w}	0 1 0	2	`-w-`
{w ; x}	0 1 1	3	`-wx`
{r}	1 0 0	4	`r--`
{r ; x}	1 0 1	5	`r-x`
{r ; w}	1 1 0	6	`rw-`
{r ; w ; x}	1 1 1	7	`rwx`

chmod 750 script.sh donne {r ; w ; x} au propriétaire, {r ; x} au groupe et ∅ aux autres.

Les 2³ = 8 parties de {r ; w ; x} et leur code chmod : chaque trait monte d'une partie à une partie qui la contient, avec un droit de plus.

Combien de parties ont k éléments ?

Dans le tableau de E = {1 ; 2 ; 3}, les effectifs 1, 3, 3, 1 ne sont pas un hasard : ce sont les nombres de façons de choisir k éléments parmi n, notés C(n, k) et lus « k parmi n ». Pour n = 4, on trouve 1, 4, 6, 4, 1, dont la somme fait bien 16 = 2⁴. Le calcul de ces coefficients relève du dénombrement, vu avec les probabilités dans l'épreuve facultative EF2 (cours de probabilités) : à l'E3, il suffit de savoir lister les parties d'un petit ensemble et d'en connaître le nombre total.

Exercices

Exercice 1 sur 5 Extension et compréhension Réussi À revoir

Écris en extension :

A = {n ∈ ℕ | n ≤ 6 et n est impair}
B = {n ∈ ℕ | n divise 18}
C = {x ∈ ℤ | −2 ≤ x < 3}
D = {x ∈ ℝ | x² = 9}
F = {n ∈ ℕ | 2ⁿ ≤ 100}

Donne ensuite le cardinal de chacun.