Algèbre des parties d'un ensemble

L'ensemble des parties d'un ensemble muni des opérations d'intersection, de réunion, et de passage au complémentaire possède une structure d'algèbre de Boole. D'autres opérations s'en déduisent, comme la différence ensembliste et la différence symétrique ... L'algèbre de Boole des parties d'un ensemble étudie l'arithmétique de ces opérations (voir l'article opération ensembliste pour des opérations qui ne sont pas stables sur l'ensemble des parties d'un ensemble).

Inclusion et égalité

A ⊂ B (ou A ⊆ B)

Dans tout l'article les ensembles considérés sont tous supposés inclus dans un ensemble donné U. L'inclusion est une relation d'ordre (partielle) notée « ⊂ » ou « ⊆ », et définie sur P(U) par :

A ⊂ B si et seulement ∀ x ∈ U (x ∈ A ⇒ x ∈ B).

L'égalité est définie par extensionnalité, deux ensembles sont égaux quand ils ont les mêmes éléments, c'est-à-dire que :

A = B si et seulement ∀ x ∈ U (x ∈ A ⇔ x ∈ B).

ou encore

A = B si et seulement A ⊂ B et B ⊂ A.

Les propriétés qui suivent correspondent donc, pour les égalités, à des équivalences en calcul propositionnel dont elles se déduisent. Elles peuvent être visualisées avec les diagrammes de Venn, une façon schématique de décrire toutes les cas possibles pour l'appartenance d'un élément à un nombre fini (et suffisamment réduit) d'ensembles, et qui peut donc permettre également de décrire des démonstrations d'égalité ou d'inclusion.

De façon similaire, les inclusions se ramènent à des implications.

Réunion et intersection

Réunion de deux ensembles

La réunion de deux ensembles : A ∪ B

L'ensemble réunion de A et de B, noté « A U B » ( lire « A union B » ), est l'ensemble des éléments appartenant à A ou à B  :

$A\cup B=\{x\in \mathrm {U} |(x\in A)\lor (x\in B)\}$

Propriétés

L'ensemble U muni de la réunion a les propriétés suivantes (pour tous sous-ensembles A, B, C de U) :

• (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)$

et on note également A ∪ B ∪ C cet ensemble ;

• (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$ ;

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

$A\cup A=A$ ;

• Ø est neutre : la réunion de l'ensemble vide avec un ensemble quelconque redonne cet ensemble :

$A\cup \varnothing =A$ ;

• U est absorbant : U ∪ A = A.

L'ensemble A ∪ B est la borne supérieure pour l'inclusion des deux ensembles A et B, c'est-à-dire que :

• A ⊂ A ∪ B,   B ⊂ A ∪ B et   ∀ C [(A ⊂ C et B ⊂ C) ⇒ A ∪ B ⊂ C].

Par conséquent l'inclusion se définit à partir de la réunion :

A ⊂ B   si et seulement si   A ∪ B = B.

Intersection de deux ensembles

L'intersection de deux ensembles : A ∩ B

L'ensemble intersection de A et de B, noté « A ∩ B » ( lire « A inter B » ) est l'ensemble des éléments de A qui sont également éléments de B, soit :

$A\cap B=\{x\in \mathrm {U} |(x\in A)\land (x\in B)\}$.

Propriétés

Les propriétés de l'intersection sont similaires à celles de la réunion. On dit qu'elles sont duales de celles--ci, car on les obtient en remplaçant le signe de réunion par celui d'intersection, et si nécessaire en échangeant ∅ et U, l'inclusion et sa réciproque. Pour tous sous-ensembles A, B, C de U on a les propriétés suivantes :

• (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$

et non note A ∩ B ∩ C cet ensemble ;

• (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$ ;

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

$A\cap A=A$

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

$A\cap \varnothing =\varnothing$ ;

• U est neutre : U ∩ A = A.

L'ensemble A ∩ B est la borne inférieure pour l'inclusion des deux ensembles A et B, c'est-à-dire que :

• A ∩ B ⊂ A,   A ∩ B ⊂ B   et   ∀ C [(C ⊂ A et C ⊂ B) ⇒ C ⊂ A ∩ B].

Ceci permet de définir l'inclusion à partir de l'intersection cette fois :

A ⊂ B   si et seulement si A ∩ B = A.

Distributivité

A ∩ (B ∪ C) =
(A ∩ B) ∪ (A ∩ C)

A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C)

Les deux opérations de réunion et d'intersection sont distributives l'une par rapport à l'autre, c'est-à-dire que l'on a les deux propriétés suivantes, pour tous ensembles A, B, C :

• (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)$ ;

• (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)$.

Démonstration

De chaque côté de la première égalité figure un ensemble et nous voulons démontrer que ces ensembles sont égaux, c'est-à-dire montrer qu'un élément quelconque $x$ appartient au premier si et seulement s'il appartient au second. Notons respectivement a, b, c les propositions $x\in A$, $x\in B$, $x\in C$. D'après la distributivité de $\land$ par rapport à $\lor$ (que l'on peut vérifier sur une table de vérité) on a

$a\land (b\lor c)\Leftrightarrow (a\land b)\lor (a\land c)~,$

ce qui traduit exactement l'équivalence souhaitée :

$x\in [A\cap (B\cup C)]\Leftrightarrow x\in [(A\cap B)\cup (A\cap C)]~.$

La démonstration de la seconde égalité est identique, en échangeant $\land$ et $\lor$.

Réunion et intersection : cas général

Il est possible de généraliser la réunion à un nombre fini d'ensembles : on se ramène au cas de deux ensembles par réunion binaires successives et l'associativité de la réunion assure que l'ordre n'a pas d'importance. De même pour l'intersection.

Mais il est possible également de généraliser ces opérations à une famille non nécessairement finie d'ensembles.

La réunion d'une famille d'ensembles $\ _{(E_{i})_{i\in I}}$ est définie par :

$\bigcup _{i\in I}E_{i}=\left\{x\in \mathrm {U} |\exists \ i\in I,\ x\in E_{i}\,\right\}$.

Cette définition ne dépend pas de U. L'intersection d'une famille vide est l'ensemble vide.

L'intersection d'une famille d'ensembles $\ _{(E_{i})_{i\in I}}$ est définie par :

$\bigcap _{i\in I}E_{i}=\left\{x\in \mathrm {U} |\forall \ i\in I,\ x\in E_{i}\,\right\}$.

La définition ci-dessus ne dépend pas de l'ensemble U sauf quand la famille est vide. dans ce dernier cas l'intersection de la famille vide est par définition l'ensemble de référence U, ce qui reste compatible avec les propriétés de l'intersection. On ne peut pas définir « dans l'absolu » (sans ensemble de référence) l'intersection d'une famille vide.

Certains de propriétés de la réunion et de l'intersection binaire se généralise au cas infini. ce ne sont maintenant des propriétés du calcul des prédicats (et plus seulement du calcul proprositionnel) qui sont en jeu. En particulier :

• l'intersection et la réunion d'une famille $\ _{(E_{i})_{i\in I}}$ ne dépendent que de l'ensemble image de la famille, ce qui généralise l'associativité, la commutativité et l'idempotence, et découle directement de la définition ;
• l'intersection d'une famille d'ensemble (E_i)_{i ∈ I} est la borne inférieure de l'ensemble { {E_i | i ∈ I} ;
• la réunion d'une famille d'ensemble (E_i)_{i ∈ I} est la borne supérieure de l'ensemble { {E_i | i ∈ I} ;
• l'intersection binaire se distribue sur une réunion quelconque, de même que la réunion binaire sur une intersection quelconque :

$A\cap \bigcup _{i\in I}B_{i}=\bigcup _{i\in I}(A\cap B_{i})$   ;   $A\cup \bigcap _{i\in I}B_{i}=\bigcap _{i\in I}(A\cup B_{i})$.

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=\varnothing$;
• 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=\varnothing ~.$

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.

Complémentaire

L'ensemble A

son complémentaire A^c

Un ensemble de référence U étant donné, le complémentaire du sous-ensemble A de U (sous-entendu relativement à U) est l'ensemble des élements de U qui n'appartiennenent pas à A; Il est noté U - A A, A^c, ou encore $\complement A$ :

$A^{\mathrm {c} }=\{x\in \mathrm {U} |x\notin A\}$.

Il est caractérisé par les deux égalités :

A ∩ A^c = ∅   et   A ∪ A^c = U,

et l'opération de passage au complémentaire est involutive :

(A^c)^c = A.

Lois de de Morgan

(A ∩ B)^c = A^c ∪ B ^c

(A ∪ B)^c = A^c ∩ B ^c

Le passage au complémentaire inverse la relation d'inclusion :

A ⊂ B   si et seulement si   B ^c ⊂ A^c

et par conséquent il échange la réunion et l'intersection, qui sont la borne supérieure et la borne inférieure, ce sont les lois de de Morgan :

(A ∩ B)^c = A^c ∪ B ^c

(A ∪ B)^c = A^c ∩ B ^c

Une structure ordonnée qui, comme l'ensemble des parties de U muni des opérations binaires de réunion et d'intersection, de l'opération de passage au complémentaire, et des deux éléments distingués ∅ et U, vérifie les propriétés de ces opérations énumérées jusqu'à présent est appelé algèbre de Boole.

Différence et différence symétrique

La différence
A \ B = A ∩ B ^c

La différence symétrique
A Δ B)^c = (A ∩ B ^c) ∪ (A^c ∩ B)

La différence ensembliste de A et B notée « A \ B » ( lire « A moins B » ) est l'ensemble des éléments de A qui n'appartiennent pas à B, soit :

$A\setminus B=\{x\in U|(x\in A)\land (x\notin B)\}$.

LA différence de A et B dans U se définit à partir du complémentaire par A ∩ B ^c, et alors (A ∩ B ^c)^c = A^c ∪ 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 de B dans A (ou relativement à A). On retrouve la notion de complémentaire ci-dessus, qui est le complémentaire relativement à U :

$A\setminus B=A-B=\complement _{A}B=\{x\in A|x\notin B\}$

La différence symétrique de A et de B, notée « A Δ B » (lire « A delta B ») et l'ensemble des éléments qui appartiennent soit à A, soit à B, mais pas aux deux à la fois. C'est la la différence de A ∪ B et de A ∩ B. . On peut l'écrire sous diverses formes :

$A\Delta B=(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A)=(A^{\mathrm {c} }\cap B)\cup (A\cap B^{\mathrm {c} })$.

On remarque que :

x ∉ A Δ B   si et seulement si   x ∈ A ⇔ x ∈ B

c'est-à-dire que la différence symétrique de deux ensembles est vide si et seulement si les deux ensembles sont égaux :

A Δ B = ∅   si et seulement si   A = B.

Propriétés de la différence symétrique

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

L'ensemble des parties de U muni de l'opération de différence symétrique est un groupe commutatif, avec ∅ pour élément neutre, et où chaque sous-ensemble de U est son propre opposé, c(est-à-dire que pour et tous sous-ensembles A, B, C de U, on a  :

• (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{\mathrel {\Delta }}B){\mathrel {\Delta }}C=A{\mathrel {\Delta }}(B{\mathrel {\Delta }}C)$

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

$A{\mathrel {\Delta }}B=B{\mathrel {\Delta }}A$

• Ø est élément neutre : la différence symétrique de l'ensemble vide et d'un autre ensemble redonne cet ensemble :

$A{\mathrel {\Delta }}\varnothing =A$

• Chaque sous-ensemble est son propre opposé : la différence symétrique de tout ensemble avec lui-même donne l'ensemble vide :

$A{\mathrel {\Delta }}A=\varnothing$

Une conséquence est la régularité :

$(A{\mathrel {\Delta }}B=A\Delta C)\Rightarrow (B=C)$.

A ∩ (B Δ C) =
(A ∩ B) Δ (A ∩ C)

L'ensemble des parties de U muni, en plus de la différence symétrique, de l'intersection, est un anneau commutatif unitaire, c'est-à-dire qu'en plus des propriétés d'associativité et de commutativité de l'intersection, et de ce que U est élément neutre

• 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{\mathrel {\Delta }}C)=(A\cap B){\mathrel {\Delta }}(A\cap C)$.

C'est une propriété générale des algèbres de Boole qu'une opération définie comme la différence symétrique (avec la réunion l'intersection et le passage au complémentaire) permet de définir une structure d'anneau, appelé parfois anneau de Boole. D'autres propriétés, communes à toutes les algèbres de Boole, sont vérifiées comme :

A^c = U Δ A   et donc   A^c Δ A = U.

ou encore   (A Δ B)^c = A^c Δ B = A Δ B ^c.

Propriétés de la différence

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\setminus \varnothing =A~,$

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

$\varnothing \setminus B=\varnothing ~,$

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

$A\setminus A=\varnothing ~,$

• 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\setminus B=\varnothing )\Leftrightarrow (A\subseteq B)~,$

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

$[A\setminus B=B]\Leftrightarrow [(A=\varnothing )\land (B=\varnothing )]~,$

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

$(A\setminus B=B\setminus 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\setminus B=A)\Leftrightarrow (A\cap B=\varnothing )~,$

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

$(A\setminus B=A\cap B)\Leftrightarrow (A=\varnothing )~,$

• 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\setminus B=A\cup B)\Leftrightarrow (B=\varnothing )~,$

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

$A\setminus 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\setminus B)\setminus C=(A\setminus B)\cap (A\setminus 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\setminus (B\setminus C)=(A\setminus 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\setminus B)\cup C=(A\cup C)\setminus (B\setminus 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)\setminus C=A\cap (B\setminus 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)\setminus C=(A\setminus C)\cap (B\setminus 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)\setminus C=(A\setminus C)\cup (B\setminus 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\setminus (B\cap C)=(A\setminus B)\cup (A\setminus 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\setminus (B\cup C)=(A\setminus B)\cap (A\setminus 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.

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.

Aspects axiomatiques

D'un point de vue axiomatique, en théorie des ensembles tout ce qui précède se développe à partir de l'axiome d'extensionnalité (égalité de deux ensembles), qui garantit en particulier l'unicité des constructions introduites, et du schéma d'axiomes de compréhension, qui garantit leur existence, tous les ensembles introduits étant définis comme sous-ensemble d'un ensemble U donné.

Voir aussi

• Opération ensembliste
• Théorie naïve des ensembles
• Ensemble
• Sous-ensemble
• Produit cartésien
• Correspondance et relation