Ensembles disjoints

En mathématiques, deux ensembles sont dits disjoints s'ils n'ont pas d'éléments en commun. Par exemple, {1,2,3} et {4,5,6} sont deux ensembles disjoints.

Explication

De manière formelle, deux ensembles A et B sont disjoints si leur intersection est l'ensemble vide, c'est-à-dire si

$A\cap B = \varnothing~.$

Cette définition s'étend à une famille d'ensembles. Les ensembles d'une famille sont dits disjoints deux à deux ou mutuellement disjoints si deux ensembles quelconques de cette famille sont disjoints.

Plus précisément, soient $I~$ un ensemble d'indices, et pour chaque $i \in I$, un ensemble A_i. Alors les ensembles de la famille $(A_i)_{i\in I}$ sont mutuellement disjoints si

$\forall (i,j)\in I^2\qquad(\ i \neq j\Rightarrow \ A_i \cap A_j = \varnothing)~.$

Par exemple, les singletons de la famille ({1},{2},{3}) sont mutuellement disjoints.

Si $(A_i)_{i\in I}$ est une famille d'ensembles mutuellement disjoints, et s'il y a au moins deux indices dans I, alors l'intersection de la famille est vide :

$\cap_{i\in I}A_i=\varnothing~.$

Cependant, la réciproque est fausse : l'intersection de la famille ({1,2},{2,3},{3,4}) est vide, mais ces trois ensembles ne sont pas mutuellement disjoints.

Une partition d'un ensemble X est une famille $(A_i)_{i\in I}$ de sous-ensembles de X non vides, mutuellement disjoints et tels que :

$\bigcup_{i\in I} A_i = X~.$

Voir aussi

• Ensembles presque disjoints (en)
• Connectivité
• Union disjointe
• Union-Find

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Disjoint sets » (voir la liste des auteurs)