Definition:Disjoint Union (Set Theory)

From ProofWiki
Jump to navigation Jump to search


Let $\family {S_i}_{i \mathop \in I}$ be an $I$-indexed family of sets.

The disjoint union of $\family {S_i}_{i \mathop \in I}$ is defined as the set:

$\displaystyle \bigsqcup_{i \mathop \in I} S_i = \bigcup_{i \mathop \in I} \set {\tuple {x, i}: x \in S_i}$

where $\bigcup$ denotes union.

Each of the sets $S_i$ is canonically embedded in the disjoint union as the set:

$S_i^* = \set {\tuple {x, i}: x \in S_i}$

For distinct $i, j \in I$, the sets $S_i^*$ and $S_j^*$ are disjoint even if $S_i$ and $S_j$ are not.

If $S$ is a set such that $\forall i \in I: S_i = S$, then the disjoint union (as defined above) is equal to the cartesian product of $S$ and $I$:

$\displaystyle \bigsqcup_{i \mathop \in I} S = S \times I$

Where $A \cap B = \O$, we can define:

$A \sqcup B := A \cup B$

where $A \cup B$ is the union of $A$ and $B$.

Also known as

This is also called a discriminated union.

In Georg Cantor's original words:

We denote the uniting of many aggregates $M, N, P, \ldots$, which have no common elements, into a single aggregate by
$\tuple {M, N, P, \ldots}$.
The elements in this aggregate are, therefore, the elements of $M$, of $N$, of $P$, $\ldots$, taken together.

Occasionally the notations:

$\displaystyle \sum_{i \mathop \in I} S_i$ and $\displaystyle \coprod_{i \mathop \in I} S_i$

can be seen for the disjoint union of a family of sets.

When two sets are under consideration, the notation:

$A \sqcup B$

is usually used.

Some sources use:

$A \vee B$

The notation:

$A + B$

is also encountered sometimes.

This notation reflects the fact that, from the corollary to Cardinality of Set Union, the cardinality of the disjoint union is the sum of the cardinalities of the terms in the family.

It is motivated by the notation for a coproduct in category theory, combined with Disjoint Union is Coproduct in Category of Sets.

Compare this to the notation for the cartesian product of a family of sets.

Also see

  • Results about disjoint unions can be found here.