Disjoint union

(Redirected from Discriminated 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$ in $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 \}$ .

The disjoint union of a collection of sets $C$ is often denoted

$\mathcal{A} = \coprod_{A \in C} A$

to distinguish it from an ordinary union.

In the language of category theory, the disjoint union is the coproduct in the category of sets. This means that it is the categorical dual of the cartesian product construction. It satisfies the associated universal property. See coproduct for more details.

Disjoint union

See also