Algèbre des parties d'un ensemble

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 :

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

c'est-à-dire que :

x ∈ A ∪ B si et seulement si x ∈ A ou x ∈ B.

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

A ∪ B ∪ C.

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

${\displaystyle (A\cup B)\cup C=A\cup (B\cup C)}$

et on note 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 :

${\displaystyle A\cup B=B\cup A}$ ;

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

${\displaystyle A\cup A=A}$ ;

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

${\displaystyle A\cup \varnothing =A}$ ;

• U est absorbant : U ∪ A = U.

L'ensemble A ∪ B est la borne supérieure pour l'inclusion des deux ensembles A et B, c'est-à-dire qu'il contient A et B, et qu'il est contenu dans tout ensemble contenant A et B :

• 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.

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 :

${\displaystyle A\cap B=\{x\in \mathrm {U} \mid (x\in A)\land (x\in B)\}}$

c'est-à-dire que :

x ∈ A ∩ B si et seulement si x ∈ A et x ∈ B.

Deux ensembles qui n'ont aucun élément en commun, c'est-à-dire que leur intersection est vide, sont dits disjoints.

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 :

A ∩ B ∩ C.

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

${\displaystyle (A\cap B)\cap C=A\cap (B\cap C)}$

et on 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

${\displaystyle A\cap B=B\cap A}$ ;

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

${\displaystyle A\cap A=A}$

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

${\displaystyle 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 qu'il est inclus dans A et dans B, et qu'il contient tout ensemble inclus à la fois dans A et dans B :

• 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.

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 :

${\displaystyle 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 :

${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$.

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 ${\displaystyle (E_{i})_{i\in I}}$ est définie par :

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

Cette définition ne dépend pas de U. La réunion d'une famille vide est l'ensemble vide.

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

${\displaystyle \bigcap _{i\in I}E_{i}=\left\{x\in \mathrm {U} \mid \forall i\in I\quad 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.

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

• l'intersection et la réunion d'une famille ${\displaystyle (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 :

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

• plus généralement, on a l'égalité ${\displaystyle \bigcap _{i\in I}{\bigcup _{j\in J_{i}}{A_{i,j}}}=\bigcup _{f\in \left(\prod _{i\in I}{J_{i}}\right)}{\bigcap _{i\in I}{A_{i,f(i)}}}}$ (dans laquelle l'inclusion ${\displaystyle \supset }$ est immédiate mais l'inclusion ${\displaystyle \subset }$ utilise l'axiome du choix si ${\displaystyle I}$ est infini) ainsi que l'égalité duale[1].

(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ée algèbre de Boole.

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

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 :

${\displaystyle A\setminus B=\{x\in A\mid 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 »[2] (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 :

${\displaystyle A\setminus B=A-B=\complement _{A}B=\{x\in A\mid x\notin B\}}$.

On a :

x ∈ A \ B si et seulement si x ∈ A et x ∉ B

x ∉ A \ B si et seulement si x ∉ A ou x ∈ B

et donc :

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

Les propriétés de la différence s'obtiennent à partir de sa définition et de celles de la réunion de l'intersection et du complémentaire. Par exemple la première qui suit est une suite d'intersections, alors que la seconde utilise une loi de De Morgan et la distributivité de l'intersection sur la réunion.

${\displaystyle (A\cap B)\setminus C=A\cap (B\setminus C)=(A\setminus C)\cap (B\setminus C)}$

${\displaystyle A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)}$.

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

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

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

On a :

x ∈ A Δ B si et seulement si ou bien x ∈ A ou bien x ∈ B (ou exclusif)

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

ainsi 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.

(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 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, le parenthésage n'est pas nécessaire :

${\displaystyle (A\,\Delta \,B)\,\Delta \,C=A\,\Delta \,(B\,\Delta \,C)}$

et on peut écrire A Δ B Δ C.

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

${\displaystyle A\,\Delta \,B=B\,\Delta \,A}$

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

${\displaystyle A\,\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 :

${\displaystyle A\,\Delta \,A=\varnothing }$

Une conséquence est la régularité : si A Δ B = A Δ C, alors 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 :

${\displaystyle A\cap (B\,\Delta \,C)=(A\cap B)\,\Delta \,(A\cap C)}$.

La différence symétrique, contrairement à la réunion, n'est pas distributive par rapport à l'intersection.

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.