Éléments de la théorie des ensembles

Sommaire

1. Vocabulaire de base
2. Opérations sur les ensembles
3. Propriétés
4. Produit cartésien
5. Cardinal et dénombrement
6. Applications

Module 5 de l'unité U21. Le langage ensembliste structure les bases de données, les types de données et les raisonnements de dénombrement.

1. Vocabulaire de base

Ensemble = collection d'objets appelés éléments. Deux descriptions possibles :

En extension, en listant les éléments : A = {1, 2, 3, 4}.
En compréhension, par une propriété : A = {x ∈ ℕ | 1 ≤ x ≤ 4}.

Notation	Signification
x ∈ A	x appartient à A
x ∉ A	x n'appartient pas à A
A ⊂ B	A est inclus dans B : tout élément de A est dans B
∅	Ensemble vide, sans aucun élément
℘(A)	Ensemble des parties de A

Ne pas confondre appartenance et inclusion : 1 ∈ {1, 2} mais {1} ⊂ {1, 2}. L'ensemble vide est inclus dans tout ensemble.

Ensembles de nombres usuels : ℕ (entiers naturels) ⊂ ℤ (entiers relatifs) ⊂ ℚ (rationnels) ⊂ ℝ (réels).

2. Opérations sur les ensembles

Opération	Notation	Définition
Union	A ∪ B	éléments de A ou de B
Intersection	A ∩ B	éléments de A et de B
Différence	A \ B	éléments de A qui ne sont pas dans B
Complémentaire	Ā ou E \ A	éléments de l'ensemble de référence E hors de A
Différence symétrique	A Δ B	éléments de A ou de B mais pas des deux

Avec A = {1, 2, 3, 4} et B = {3, 4, 5} :

Opération	Résultat
A ∪ B	{1, 2, 3, 4, 5}
A ∩ B	{3, 4}
A \ B	{1, 2}
A Δ B	{1, 2, 5}

Deux ensembles sont disjoints si A ∩ B = ∅.

3. Propriétés

Les opérations ensemblistes reflètent exactement les connecteurs logiques : ∪ correspond au ∨, ∩ au ∧, le complémentaire à la négation. Toutes les lois de la logique se transposent.

Propriété	Énoncé
Commutativité	A ∪ B = B ∪ A
Associativité	(A ∪ B) ∪ C = A ∪ (B ∪ C)
Distributivité	A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morgan	A ∪ B = A ∩ B

4. Produit cartésien

A × B est l'ensemble des couples ordonnés (a, b) avec a ∈ A et b ∈ B.

A = {1, 2}   B = {x, y}

A × B = { (1,x), (1,y), (2,x), (2,y) }        card = 2 × 2 = 4

L'ordre compte : (1, x) ≠ (x, 1), donc A × B ≠ B × A en général.

C'est la notion qui fonde le modèle relationnel : une relation (une table) est un sous-ensemble d'un produit cartésien de domaines. Et la jointure croisée CROSS JOIN en SQL calcule littéralement le produit cartésien de deux tables — d'où l'explosion du nombre de lignes quand on oublie la condition de jointure.

5. Cardinal et dénombrement

Le cardinal card(A) est le nombre d'éléments d'un ensemble fini.

Principe d'inclusion-exclusion

card(A ∪ B) = card(A) + card(B) − card(A ∩ B)

On retranche l'intersection parce qu'elle a été comptée deux fois. Exemple : sur 30 étudiants, 18 suivent l'option réseau, 15 l'option développement et 8 les deux. Combien en suivent au moins une ? 18 + 15 − 8 = 25. Donc 5 n'en suivent aucune.

Formules de dénombrement

Situation	Formule	Exemple
Parties d'un ensemble à n éléments	2ⁿ	3 éléments → 8 parties
p-listes (avec répétition, ordonnées)	n^p	Mot de passe de 4 chiffres : 10⁴ = 10 000
Arrangements (sans répétition, ordonnés)	n! / (n − p)!	Podium de 3 parmi 8 : 336
Permutations	n!	Ordonner 5 fichiers : 120
Combinaisons (sans répétition, non ordonnées)	C(n, p) = n! / (p! (n − p)!)	Choisir 3 serveurs parmi 8 : 56

La question à se poser pour choisir la formule : l'ordre compte-t-il ? et peut-on répéter ? Un code PIN est une liste (ordre + répétition), une équipe est une combinaison (ni l'un ni l'autre).

Application sécurité : un mot de passe de 8 caractères pris parmi 26 minuscules offre 26⁸ ≈ 2 × 10¹¹ possibilités ; en ajoutant majuscules, chiffres et symboles (94 caractères), on passe à 94⁸ ≈ 6 × 10¹⁵. C'est ce calcul qui justifie les politiques de complexité.

6. Applications

SQL : UNION, INTERSECT, EXCEPT sont exactement ∪, ∩ et la différence. DISTINCT traduit le fait qu'un ensemble n'a pas de doublons.
Types de données : un type est un ensemble de valeurs possibles ; int ⊂ ℤ, et le débordement vient du fait que cet ensemble est fini.
Structures de données : les set de Python et les Set de Java implémentent directement ces opérations, avec un test d'appartenance en temps constant.
Droits d'accès : les permissions effectives d'un utilisateur sont l'intersection ou l'union de celles de ses groupes, selon le modèle retenu.

À retenir

Appartenance : 1 ∈ {1,2} | inclusion : {1} ⊂ {1,2} — ne pas confondre
∅ est inclus dans tout ensemble
∪ = ou | ∩ = et | complémentaire = négation → mêmes lois que la logique
Produit cartésien A × B = couples ordonnés → A×B ≠ B×A
Le produit cartésien fonde le modèle relationnel → CROSS JOIN
card(A ∪ B) = card(A) + card(B) − card(A ∩ B)
Parties d'un ensemble à n éléments : 2ⁿ
Ordre compte + répétition → n^p | ordre compte sans répétition → arrangement | ni l'un ni l'autre → combinaison
SQL : UNION, INTERSECT, EXCEPT