Langage ensembliste : inclusion, intersection, réunion

Un ensemble est une collection d'objets distincts, appelés ses éléments. Le langage ensembliste donne les mots et les symboles pour en parler : appartenance (∈), inclusion (⊂), ensemble vide (∅), ensemble des parties P(E), complémentaire, intersection (∩) et réunion (∪). Ce chapitre les présente et montre qu'ils fonctionnent exactement comme les connecteurs logiques, ce qui prépare l'algèbre de Boole. Le produit cartésien, les relations et les applications ont leur propre cours : la théorie des ensembles.

Ensemble, élément et appartenance

On décrit un ensemble de deux façons :

• en extension, en donnant la liste de ses éléments entre accolades : E = {lundi, mardi, mercredi, jeudi, vendredi} ;
• en compréhension, par une propriété qui caractérise ses éléments : A = {x ∈ ℕ | x est pair et x < 10}, qui se lit « l'ensemble des entiers naturels x tels que x est pair et x < 10 ». En extension, A = {0, 2, 4, 6, 8}.

Dans un ensemble, l'ordre ne compte pas et chaque élément n'apparaît qu'une fois : {1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}.

On note x ∈ A (« x appartient à A ») quand x est un élément de A, et x ∉ A sinon : 4 ∈ A, 5 ∉ A.

Le cardinal d'un ensemble fini A, noté card(A) ou |A|, est son nombre d'éléments : card(A) = 5.

L'ensemble vide, noté ∅, ne contient aucun élément : card(∅) = 0. Par exemple, {x ∈ ℕ | x + 3 = 1} = ∅.

Les ensembles de nombres usuels ont des noms réservés : ℕ (entiers naturels), ℤ (entiers relatifs), ℚ (rationnels), ℝ (réels).

Inclusion et ensemble des parties P(E)

A est inclus dans B, noté A ⊂ B (ou A ⊆ B), quand tout élément de A est aussi un élément de B :

A ⊂ B ⇔ (∀x, x ∈ A ⇒ x ∈ B)

On dit aussi que A est une partie ou un sous-ensemble de B. Par exemple, {2, 4} ⊂ {0, 2, 4, 6, 8}. Pour tout ensemble E, ∅ ⊂ E et E ⊂ E.

Deux ensembles sont égaux quand chacun est inclus dans l'autre : A = B ⇔ (A ⊂ B et B ⊂ A). C'est la méthode habituelle pour démontrer une égalité d'ensembles, par double inclusion.

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

Pour E = {a, b, c} :

P(E) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

Ici, {a} ∈ P(E) et {a, b} ∈ P(E) : une partie de E est un élément de P(E).

Ce « dedans ou pas » est un bit. Une partie de E = {a, b, c} se code par un mot de 3 bits : 101 code {a, c}, 000 code ∅, 111 code E. Les 2³ = 8 mots de 000 à 111 codent les 8 parties, exactement comme les 8 lignes d'une table de vérité à 3 variables. C'est aussi le principe des droits Unix : rwx est une partie de l'ensemble {lecture, écriture, exécution}, codée sur 3 bits (cours Linux).

Complémentaire, intersection, réunion et différence

Dans toute la suite, A et B sont deux parties d'un même ensemble E, appelé ensemble de référence (ou univers).

Deux ensembles sont disjoints quand leur intersection est vide : A ∩ B = ∅.

Exemple. E = {1, 2, 3, 4, 5, 6, 7, 8}, A = {1, 2, 3, 4} et B = {3, 4, 5, 6}.

• A ∩ B = {3, 4}
• A ∪ B = {1, 2, 3, 4, 5, 6}
• A̅ = {5, 6, 7, 8} et B̅ = {1, 2, 7, 8}
• A \ B = {1, 2} et B \ A = {5, 6}

Un diagramme de Venn représente E par un rectangle et chaque partie par une zone fermée. Il ne démontre rien, mais il aide à voir et à vérifier.

Propriétés des opérations et lois de De Morgan

Les opérations sur les ensembles ont exactement les mêmes propriétés que les connecteurs logiques du chapitre 2 :

S'y ajoute : le complémentaire de A̅ est A.

Vérification sur l'exemple : A ∩ B = {3, 4}, donc son complémentaire est {1, 2, 5, 6, 7, 8}. Et A̅ ∪ B̅ = {5, 6, 7, 8} ∪ {1, 2, 7, 8} = {1, 2, 5, 6, 7, 8}. Même résultat.

Pour démontrer une telle égalité, on raisonne sur un élément x quelconque de E et on utilise la logique : x appartient au complémentaire de A ∩ B ⇔ ¬(x ∈ A ∧ x ∈ B) ⇔ ¬(x ∈ A) ∨ ¬(x ∈ B) ⇔ x ∈ A̅ ∨ x ∈ B̅ ⇔ x ∈ A̅ ∪ B̅. La loi de De Morgan des ensembles est la loi de De Morgan de la logique, appliquée à « x ∈ A » et « x ∈ B ».

Cardinal d'une réunion

Pour compter les éléments de A ∪ B, on ne peut pas simplement ajouter card(A) et card(B) : les éléments de A ∩ B seraient comptés deux fois. D'où la formule :

Sur l'exemple : card(A ∪ B) = 4 + 4 − 2 = 6. C'est bien le nombre d'éléments de {1, 2, 3, 4, 5, 6}.

Exemple d'énoncé. Sur les 120 postes d'une entreprise, 70 ont l'antivirus à jour, 85 ont le système à jour, et 50 ont les deux. Combien de postes n'ont ni l'un ni l'autre à jour ?

• Avec A : « antivirus à jour » et S : « système à jour », card(A ∪ S) = 70 + 85 − 50 = 105.
• Les postes sans aucune des deux mises à jour forment le complémentaire de A ∪ S, qui est A̅ ∩ S̅ (De Morgan) : 120 − 105 = 15 postes.

Des propositions aux ensembles

Si p(x) est un prédicat sur E, l'ensemble des éléments qui le vérifient est {x ∈ E | p(x)}, souvent noté par la majuscule correspondante : P = {x ∈ E | p(x)}. Chaque connecteur logique correspond alors à une opération sur les ensembles. C'est ce que le programme appelle « interpréter en termes ensemblistes » la négation, la conjonction, la disjonction et l'implication.

La dernière correspondance éclaire l'implication : dire que « tout salarié en télétravail est cadre », c'est dire que l'ensemble des télétravailleurs est inclus dans l'ensemble des cadres. Un cadre qui n'est pas en télétravail ne contredit rien : il est dans Q, hors de P. C'est la ligne « F ⇒ V est vraie » de la table de l'implication.

En informatique : ensembles, SQL et Python

• Les requêtes SQL manipulent des ensembles de lignes. UNION calcule une réunion, INTERSECT une intersection et EXCEPT une différence (MySQL les accepte depuis la version 8.0.31). Une clause WHERE p AND q sélectionne l'intersection des lignes qui vérifient p et de celles qui vérifient q. Voir le chapitre UNION, CTE et fonctions de fenêtrage du cours SQL.
• Python a un type set, avec les opérateurs & (intersection), | (réunion), - (différence), ^ (différence symétrique) et <= (inclusion).
• Les groupes d'un annuaire (Active Directory, LDAP) sont des ensembles d'utilisateurs ; les droits effectifs d'un utilisateur se calculent souvent comme la réunion des droits de ses groupes.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
E = set(range(1, 9))        # {1, ..., 8}

print(A & B)                # {3, 4}
print(A | B)                # {1, 2, 3, 4, 5, 6}
print(E - A)                # complémentaire de A : {8, 5, 6, 7}, dans un ordre quelconque
print(E - (A & B) == (E - A) | (E - B))   # De Morgan : True
print(len(A | B) == len(A) + len(B) - len(A & B))   # True

Un ensemble Python n'a pas d'ordre : l'affichage peut lister les éléments dans un ordre inattendu, ce qui ne change rien à l'ensemble.

Exercices