Algèbre des parties d'un ensemble

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

Cet article est consacré à une première approche des opérations sur les ensembles et de leurs propriétés : réunion, intersection, différence, complémentation, différence symétrique...

Réunion

Définition

Pour tout ensemble A et tout ensemble B, il existe un ensemble U dont les éléments sont ceux de A et de B (cette proposition, qui est un axiome implicite de la théorie naïve des ensembles, découle, dans la théorie des ensembles de l'axiome de la paire et de l'axiome de la réunion). En notation symbolique :

\exists U, \forall x, (x \in U) \Leftrightarrow [(x \in A) \lor (x \in B)] .

L'unicité de l'ensemble U est garantie par l'axiome d'extensionnalité. On le note « A U B » ( lire « A union B » ), et on l'appelle réunion de A et de B.

A \cup B = {x ∣ (x \in A) \lor (x \in B)} .

Propriétés

Pour tous ensembles A, B, C, D, on a les propriétés suivantes :

U1 (commutativité) : la réunion de deux ensembles ne dépend pas de l'ordre dans lequel ces deux ensembles sont pris :

A \cup B = B \cup A,

U2 (Ø neutre) : la réunion de l'ensemble vide avec un ensemble quelconque redonne cet ensemble :

A \cup \emptyset = A,

U3 (idempotence) : la réunion d'un ensemble quelconque avec lui-même redonne cet ensemble :

A \cup A = A,

U4 : tout ensemble est inclus dans sa réunion avec n'importe quel autre ensemble :

A \subseteq A \cup B,

U5 : un ensemble A est inclus dans un ensemble B si et seulement si leur réunion est égale à B :

(A \subseteq B) \Leftrightarrow (A \cup B = B),

U6 : si la réunion de deux ensembles est vide, alors ils sont vides tous les deux :

[A \cup B = \emptyset] \Rightarrow [(A = \emptyset) \land (B = \emptyset)],

U7 (compatibilité avec l'inclusion) : la réunion de deux sous-ensembles est incluse dans la réunion des deux ensembles dont ils sont sous-ensembles :

[(A \subseteq B) \land (C \subseteq D)] \Rightarrow [(A \cup C) \subseteq (B \cup D)],

U8 (associativité) : le résultat de la réunion de plusieurs ensembles ne dépend pas de l'ordre dans lequel les opérations de réunion sont faites :

(A \cup B) \cup C = A \cup (B \cup C) = A \cup B \cup C .

Intersection

Définition

Pour tout ensemble A et tout ensemble B, il existe un ensemble S dont les éléments sont ceux qui sont communs à A et à B. Cette proposition, qui est un axiome implicite de la théorie naïve des ensembles, découle, dans la théorie des ensembles, du schéma d'axiomes de compréhension. En notation symbolique :

\exists S, \forall x, (x \in S) \Leftrightarrow [(x \in A) \land (x \in B)] .

L'unicité de l'ensemble S est garantie par l'axiome d'extensionnalité. On le note « A ∩ B » ( lire « A inter B » ), et on l'appelle intersection de A et de B.

A \cap B = {x ∣ (x \in A) \land (x \in B)} .

Propriétés

Pour tous ensembles A, B, C, D, on a les propriétés suivantes :

N1 (commutativité) : l'intersection de deux ensembles ne dépend pas de l'ordre dans lequel ces deux ensembles sont pris :

A \cap B = B \cap A,

N2 (Ø absorbant) : l'intersection de l'ensemble vide et d'un ensemble quelconque est vide :

A \cap \emptyset = \emptyset,

N3 (idempotence) : l'intersection d'un ensemble quelconque avec lui-même redonne cet ensemble :

A \cap A = A,

N4 : l'intersection de deux ensembles est incluse dans chacun de ces deux ensembles :

A \cap B \subseteq A,

N5 : un ensemble A est inclus dans un ensemble B si et seulement si leur intersection est égale à A :

(A \subseteq B) \Leftrightarrow (A \cap B = A),

N6 : l'équivalent de U6 se traduit par une définition, celle des ensembles disjoints (voir ci-dessous).
N7 (compatibilité avec l'inclusion) : l'intersection de deux sous-ensembles est incluse dans l'intersection des deux ensembles dont ils sont sous-ensembles :

[(A \subseteq B) \land (C \subseteq D)] \Rightarrow [(A \cap C) \subseteq (B \cap D)],

N8 (associativité) : le résultat de l'intersection de plusieurs ensembles ne dépend pas de l'ordre dans lequel les opérations sont faites :

(A \cap B) \cap C = A \cap (B \cap C) = A \cap B \cap C .

Cas des familles d'ensembles

Il est possible de définir l'intersection d'une famille quelconque d'ensembles $(E_{i}) i \in I$ comme l'intersection des ensembles composant cette famille :

$⋂_{i \in I} E_{i} = {x ∣ \forall i \in I, x \in E_{i}}$ .

En particulier, pour une famille vide d'ensembles, $⋂_{i \in \emptyset}_{E_{i}}$ est la « classe » de tous les ensembles et n'est donc pas un ensemble.

Ensembles disjoints

Deux ensembles sont disjoints si et seulement si leur intersection est vide, c'est-à-dire s'ils n'ont pas d'éléments en commun. Par exemple, si A = { 1, 2 } et B = { 3, 4 }, alors A ∩B = Ø, et A et B sont donc disjoints.

Il existe deux manières de généraliser cette définition à plus de deux ensembles : E désignant un ensemble d'ensembles,

les éléments de E sont dits (globalement) disjoints si « l'ensemble noyau de E » (noté ∩E et désignant l'intersection de tous les ensembles appartenant à E) est vide : $\cap E = \emptyset$ ;
les éléments de E sont dits mutuellement disjoints ou disjoints deux à deux si et seulement si l'ensemble noyau de toute paire de ces éléments est vide, c'est-à-dire si : $\forall X \in E, \forall Y \in E, X \neq = Y \Rightarrow X \cap Y = \emptyset .$

Ces deux notions sont différentes : des ensembles disjoints deux à deux sont globalement disjoints (dès qu'il y en a au moins deux), tandis que des ensembles globalement disjoints ne le sont pas nécessairement deux à deux.

Liens avec la réunion

Pour tous ensembles A, B, C, on a les deux propriétés suivantes :

UN1 (distributivité de l'intersection par rapport à la réunion : l'intersection de la réunion de deux ensembles avec un troisième ensemble est égale à la réunion de l'intersection de chacun des deux premiers ensembles avec le troisième :

A \cap (B \cup C) = (A \cap B) \cup (A \cap C),

UN2 (distributivité de la réunion par rapport à l'intersection) : la réunion de l'intersection de deux ensembles avec un troisième ensemble est égale à l'intersection de la réunion de chacun des deux premiers ensembles avec le troisième :

A \cup (B \cap C) = (A \cup B) \cap (A \cup C) .

Différence

Définition

Pour tout ensemble A et tout ensemble B, il existe un ensemble D dont les éléments sont ceux de A qui n'appartiennent pas à B (cette proposition, qui est un axiome implicite de la théorie naïve des ensembles, découle, dans la théorie des ensembles du schéma d'axiomes de compréhension). En notation symbolique :

\exists D, \forall x, (x \in D) \Leftrightarrow [(x \in A) \land (x \in / B)] .

L'unicité de l'ensemble D est garantie par l'axiome d'extensionnalité. On le note « A \ B » ( lire « A moins B » ), et on l'appelle différence de A et de B.

A ∖ B = {x ∣ (x \in A) \land (x \in / B)} .

« Faire la différence » de deux ensembles A et B se dit aussi « soustraire » B de A.

Propriétés

Pour tous ensembles A, B, C, on a les propriétés suivantes :

D1 (Ø neutre à droite) : soustraire l'ensemble vide d'un ensemble redonne cet ensemble :

A ∖ \emptyset = A,

D2 (Ø absorbant à gauche) : soustraire un ensemble de l'ensemble vide donne l'ensemble vide :

\emptyset ∖ B = \emptyset,

D3 (involutivité) : soustraire un ensemble de lui-même donne l'ensemble vide :

A ∖ A = \emptyset,

D4 (généralisation de D2 et D3) : soustraire un sur-ensemble d'un ensemble donne l'ensemble vide, ou, en d'autres termes, pour tout A et tout B, la différence de A et de B est vide si et seulement si A est inclus dans B :

(A ∖ B = \emptyset) \Leftrightarrow (A \subseteq B),

D5 : soustraire un ensemble d'un autre redonne cet ensemble si et seulement si les deux ensembles sont vides :

[A ∖ B = B] \Leftrightarrow [(A = \emptyset) \land (B = \emptyset)],

D6 : les deux ensembles intervenant dans une différence ne sont interchangeables sans modification du résultat que s'ils sont égaux :

(A ∖ B = B ∖ A) \Leftrightarrow (A = B),

D7 (généralisation de D1 et D2) : soustraire un ensemble B d'un ensemble A redonne A si et seulement si les deux ensembles sont disjoints :

(A ∖ B = A) \Leftrightarrow (A \cap B = \emptyset),

D8 (réciproque de D2) : soustraire un ensemble B d'un ensemble A donne leur intersection si et seulement si A est vide :

(A ∖ B = A \cap B) \Leftrightarrow (A = \emptyset),

D9 (réciproque de D1) : soustraire un ensemble B d'un ensemble A donne leur réunion si et seulement si B est vide :

(A ∖ B = A \cup B) \Leftrightarrow (B = \emptyset),

D10 : si on soustrait un ensemble B d'un ensemble A, le résultat est un sous-ensemble de A :

A ∖ B \subseteq A,

D11 (pseudo-distributivité à droite en intersection de la différence par rapport à elle-même) : soustraire successivement deux ensembles B et C d'un ensemble A revient à prendre l'intersection des différences de A et de B, et de A et de C :

(A ∖ B) ∖ C = (A ∖ B) \cap (A ∖ C),

D12 : soustraire d'un ensemble A la différence de deux ensembles B et C revient à prendre la réunion de la différence de A et de B, et de l'intersection de A et de C :

A ∖ (B ∖ C) = (A ∖ B) \cup (A \cap C),

D13 : réunir un ensemble C avec la différence de deux ensembles A et B revient à soustraire la différence de B et de C de la réunion de A et de C :

(A ∖ B) \cup C = (A \cup C) ∖ (B ∖ C),

D14 : soustraire un ensemble C de l'intersection de deux ensembles A et B revient à prendre l'intersection de A avec la différence de B et de C :

(A \cap B) ∖ C = A \cap (B ∖ C),

D15 (distributivité à droite de la différence par rapport à l'intersection) : soustraire un ensemble C de l'intersection de deux ensembles A et B revient à prendre l'intersection de la différence de chacun de ces ensembles avec C :

(A \cap B) ∖ C = (A ∖ C) \cap (B ∖ C),

D16 (distributivité à droite de la différence par rapport à la réunion) : soustraire un ensemble C de la réunion de deux ensembles A et B revient à prendre la réunion de la différence de chacun de ces ensembles avec C :

(A \cup B) ∖ C = (A ∖ C) \cup (B ∖ C),

D17 (pseudo-distributivité à gauche en réunion de la différence par rapport à l'intersection) : soustraire l'intersection de deux ensembles B et C d'un ensemble A revient à prendre la réunion de la différence de A avec chacun des ensembles B et C :

A ∖ (B \cap C) = (A ∖ B) \cup (A ∖ C),

D18 (pseudo-distributivité à gauche en intersection de la différence par rapport à la réunion) : soustraire la réunion de deux ensembles B et C d'un ensemble A revient à prendre l'intersection de la différence de A avec chacun des ensembles B et C :

A ∖ (B \cup C) = (A ∖ B) \cap (A ∖ C) .

Cette dernière propriété peut en fait se déduire des précédentes. D14 et D15 peuvent être rapprochées, de même que D12 et D17.

Complémentaires

Définitions

Pour tout ensemble A et tout ensemble B, si B est inclus dans A, alors A \ B se note aussi « A - B » (lire encore « A moins B »), et s'appelle complémentaire relatif de B dans A.

A ∖ B = A - B = ∁_{A} B = {x \in A ∣ x \in / B} .

L'ensemble C = A - B est alors caractérisé par

(B \cup C = A) \land (B \cap C = \emptyset),

et les deux ensembles B et C sont dits complémentaires l'un de l'autre dans A.

Si Ω désigne un ensemble de référence fixé et A un ensemble inclus Ω alors Ω - A désigne le complémentaire absolu de A. Il est noté habituellement $\overline{A}$ (lire « A barre » ou « non A »).

\overline{A} = Ω - A = {x \in Ω ∣ x \in / A} .

Propriétés

Pour tout ensemble Ω et tous sous-ensembles A et B de Ω, on a les quatre propriétés suivantes :

\overline{\overline{A}} = A,

A ∖ B = A \cap \overline{B},

\overline{A ∖ B} = \overline{A} \cup B,

(A \subseteq B) \Leftrightarrow (\overline{B} \subseteq \overline{A}) .

Différence symétrique

Définition

Pour tout ensemble A et tout ensemble B, il existe un ensemble dont les éléments sont ceux qui appartiennent soit à A, soit à B, mais pas aux deux à la fois : la différence de A U B et de A ∩ B. On l'appelle la différence symétrique de A et de B et on le note « A Δ B » (lire « A delta B »). On peut l'écrire sous diverses formes :

A Δ B = {x ∣ (x \in A) \oplus (x \in B)} = {x ∣ (x \in A) \Leftrightarrow (x \in / B)} = (A \cup B) ∖ (A \cap B) = (A ∖ B) \cup (B ∖ A) .

Cette dernière expression justifie l'appellation de différence symétrique donnée à cette opération.

Propriétés

Pour tout ensemble Ω et tous sous-ensembles A, B, C de Ω, on a les propriétés suivantes :

DS1 (commutativité) : la différence symétrique de deux ensembles ne dépend pas de l'ordre dans lequel ces ensembles sont pris :

A Δ B = B Δ A,

DS2 (Ø neutre) : la différence symétrique de l'ensemble vide et d'un autre ensemble redonne cet ensemble :

A Δ \emptyset = A,

DS3 (involutivité) : la différence symétrique de tout ensemble avec lui-même donne l'ensemble vide :

A Δ A = \emptyset,

DS4 (inversibilité) : A est inversible pour Δ (car son inverse est lui-même, d'après l'involutivité),
DS5 (régularité, conséquence de l'inversibilité) : si les différences symétriques d'un ensemble avec deux autres ensembles sont égales entre elles, alors ces deux autres ensembles sont égaux entre eux :

(A Δ B = A Δ C) \Rightarrow (B = C);

DS6 (Ω élément inverseur) : la différence symétrique d'un ensemble et du référentiel donne le complément absolu de cet ensemble :

A ΔΩ = \overline{A},

DS7 : la différence symétrique d'un ensemble et de son complément absolu redonne le référentiel :

A Δ \overline{A} = Ω,

DS8 : le complément absolu de la différence symétrique de deux ensembles est égal à la différence symétrique de l'un des deux ensembles avec le complément absolu de l'autre ensemble :

\overline{A Δ B} = A Δ \overline{B};

DS9 : A \ B et B \ A sont complémentaires l'un de l'autre dans A Δ B :

[A Δ B = (A ∖ B) \cup (B ∖ A)] \land [(A ∖ B) \cap (B ∖ A) = \emptyset],

DS10 : A Δ B et A ∩ B sont complémentaires l'un de l'autre dans A U B :

[A \cup B = (A Δ B) \cup (A \cap B)] \land [(A Δ B) \cap (A \cap B) = \emptyset];

DS11 : la différence symétrique de deux ensembles est vide si et seulement si les deux ensembles sont égaux :

(A Δ B = \emptyset) \Leftrightarrow (B = A),

DS12 : la différence symétrique de deux ensembles est égale à l'un des deux ensembles si et seulement si l'autre ensemble est vide :

(A Δ B = A) \Leftrightarrow (B = \emptyset),

DS13 : la différence symétrique de deux ensembles est égale au référentiel si et seulement si les deux ensembles sont complémentaires absolus :

(A Δ B = Ω) \Leftrightarrow (B = \overline{A}),

DS14 : la différence symétrique de deux ensembles est égale au complément absolu de l'un d'entre eux si et seulement si l'autre ensemble est le référentiel :

(A Δ B = \overline{A}) \Leftrightarrow (B = Ω),

DS15 : la différence symétrique de deux ensembles est égale à leur intersection si et seulement si les deux ensembles sont vides :

(A Δ B = A \cap B) \Leftrightarrow (A = B = \emptyset),

DS16 : la différence symétrique de deux ensembles est égale à leur réunion si et seulement s’ils sont disjoints :

(A Δ B = A \cup B) \Leftrightarrow (A \cap B = \emptyset),

DS17 : la différence symétrique de deux ensembles est égale à la différence de l'un avec l'autre si et seulement si l'un est inclus dans l'autre :

(A Δ B = A ∖ B) \Leftrightarrow (B \subseteq A);

DS18 (associativité) : la différence symétrique de trois ensembles ne dépend pas de l'ordre dans lequel les opérations sont effectuées :

(A Δ B) Δ C = A Δ (B Δ C),

DS19 (distributivité de ∩ par rapport à Δ) : l'intersection d'un ensemble avec la différence symétrique de deux autres ensembles est égale à la différence symétrique des intersections du premier ensemble avec chacun des deux autres :

A \cap (B Δ C) = (A \cap B) Δ (A \cap C) .

Exemples

Pour illustrer ces notions, soient A l'ensemble des hommes gauchers, et B l'ensemble des hommes blonds

Alors A ∩ B est l'ensemble de tous les gauchers blonds, alors que A ∪ B est l'ensemble de tous les hommes qui sont ou gauchers ou blonds, ou les deux. A \ B, en revanche, est l'ensemble de toutes les gauchers qui ne sont pas blonds, alors que B \ A est l'ensemble de tous les blonds qui ne sont pas gauchers. Enfin, A Δ B désigne l'ensemble de tous les hommes qui sont soit blonds, soit gauchers, mais pas les deux à la fois.

Maintenant supposons que C soit l'ensemble de tous les hommes âgés de plus de 1000 ans. Dans ce cas, A ∩ C est l'ensemble de tous les gauchers de plus de 1000 ans. Mais aucun homme n'a plus de 1000 ans (C est l'ensemble vide : Ø), donc A ∩ C doit être vide aussi.

Nous avons énuméré sans démonstration plusieurs propriétés simples des opérations sur les ensembles. Ces propriétés peuvent être visualisées avec les diagrammes de Venn.