Disjoint sets

(Redirected from Disjoint)

In mathematics, two sets are said to be disjoint if they have no element in common. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets.

Formally, two sets A and B are disjoint if their intersection is empty, i.e. if

<math>A\cap B = \empty<math>

This definition extends to any collection of sets. A collection of sets is pairwise disjoint or mutually disjoint if any two distinct sets in the collection are disjoint.

Formally, let I be an index set, and for each i in I, let A_i be a set. Then the collection of sets {A_i : i in I} is pairwise disjoint if for any i and j in I,

<math>A_i \ne A_j \quad \Rightarrow \quad A_i \cap A_j = \empty<math>

For example, the collection of sets { {1}, {2}, {3}, ... } is pairwise disjoint. If {A_i} is a pairwise disjoint collection, then clearly its intersection is empty:

<math>\bigcap_{i\in I} A_i = \empty<math>

However, the converse is not true — the intersection of the collection {{1, 2, 3}, {4, 5, 6}, {3, 4}} is empty, but the collection is not pairwise disjoint.

A collection of sets {A_i : i in I} is a partition of the set X if {A_i} is a pairwise disjoint collection not containing the empty set, and if

<math>\bigcup_{i\in I} A_i = X<math>