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
- <math>
\mathcal{A} = \bigcup_{A \in C} A
<math>
is a disjoint union if and only if
- <math>
\forall A,B \in C \quad
st. \ A \ne B: A \cap B = \empty
<math>
As mentioned, one can take the disjoint union of sets that are not in fact disjoint by using an indexing device. For example given A1 and A2, which may have common elements, with union B, the disjoint union as a subset of B x {1,2} is the union of A1 x {1} and A2x{2}.
See also: Basic Set Theory
