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:

$\ds \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$:

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

$2$ Sets

Let $I$ be a doubleton, say $I := \set {0, 1}$.

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

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

\(\ds \bigsqcup_{i \mathop \in I} S_i\) \(=\) \(\ds \bigcup_{i \mathop \in I} \set {\tuple {x, 0}, \tuple {y, 1} : x \in S_0, y \in S_1}\)
\(\ds \) \(=\) \(\ds \bigcup \set {S_0 \times \set 0, S_1 \times \set 1}\)
\(\ds \) \(=\) \(\ds \paren {S_0 \times \set 0} \cup \paren {S_1 \times \set 1}\)
\(\ds \) \(=\) \(\ds S_0 \sqcup S_1\)

Disjoint Sets

Let $A$ and $B$ be disjoint sets, that is:

$A \cap B = \O$

Then the disjoint union of $A$ and $B$ can be defined as:

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

where $A \cup B$ is the (usual) set union of $A$ and $B$.

Also known as

A disjoint union in the context of set theory 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.


The notations:

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

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

When two sets are under consideration, the notation:

$A \sqcup B$


$A \coprod B$

are usually used.

Some sources use:

$A \vee B$

The notations:

$A + B$


$A \oplus B$

are 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.