Definition:Disjoint Union (Set Theory)

From ProofWiki
Jump to navigation Jump to search

Definition

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.


Notation

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$

or:

$A \coprod B$

are usually used.


Some sources use:

$A \vee B$


The notations:

$A + B$

or

$A \oplus B$

are also encountered sometimes.


This notation reflects the fact that, from the Cardinality of Set Union: Corollary, 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.


Sources