disjoint union

In set theory, a disjoint union or discriminated union is a set union in which each element of the resulting union is disjoint from each of the others; the intersection over a disjoint union is the empty set. The term is also used to refer to a modified union operation which indexes the elements according to which set they originated in, ensuring that the result is a disjoint union. In computer science, this concept is important to construction of many data structures and is implemented directly by tagged unions and algebraic data types. Formally, if

C

is a collection of sets, then

\mathcal{A} = \bigcup_{A \in C} A is a disjoint union if and only if for all sets

A

and

B

C

A\ne B \implies A \cap B = \empty

As mentioned, one can take the disjoint union of sets that are not in fact disjoint by using an indexing device. For example given

A_1

and

A_2

, which may have common elements, with union

B

, the disjoint union as a subset of

B \times \{ 1, 2 \}

is the union of

A_1 \times \{ 1 \}

and

A_2 \times \{ 2 \}

Disjoint Union

See also