Disjoint union: union of disjoint sets vs. tagged union
“Disjoint union” can mean an ordinary union of sets that happen to be disjoint, or a construction that tags each element with the set it came from, so that copies of overlapping sets are kept apart.
Definitions
Consider two sets $A$ and $B$ that have no elements in common. The union $A \cup B$ is a union of disjoint sets.
Consider sets $A$ and $B$ such that $A \cap B = \emptyset$. A union of disjoint sets is the ordinary union $A \cup B$ in this case. Writing $A \sqcup B$ (or $A \mathbin{\dot{\cup}} B$) for it asserts that $A$ and $B$ are disjoint.
Examples
- $A = \setdef{1, 2}$ and $B = \setdef{3, 4}$ : $A \cup B = \setdef{1, 2, 3, 4}$
-
$A = \setdef{\text{apple}}$ and $B = \setdef{\text{banana}}$
: $A \cup B = \setdef{\text{apple}, \text{banana}}$
$A$ and $B$ are disjoint, so their union is a union of disjoint sets. The tagged disjoint union is usually identified with it.
-
$A = \setdef{\text{apple}, \text{orange}}$ and $B = \setdef{\text{orange}, \text{banana}}$
: None
The union of $A = \setdef{\text{apple}, \text{orange}}$ and $B = \setdef{\text{orange}, \text{banana}}$ is not a union of disjoint sets, because $A$ and $B$ overlap.
Consider two sets $A$ and $B$, which may overlap. The disjoint union of $A$ and $B$ is a set that combines $A$ and $B$ while keeping the elements of $A$ apart from the elements of $B$:
\[A \sqcup B = (\setdef{1} \times A) \cup (\setdef{2} \times B),\]so each element is tagged with the set it came from.
Examples
-
$A = \setdef{\text{apple}}$ and $B = \setdef{\text{banana}}$
: $A \sqcup B = \setdef{(1, \text{apple}), (2, \text{banana})}$
Each element is tagged with $1$ (from $A$) or $2$ (from $B$). The result is usually identified with $\setdef{\text{apple}, \text{banana}}$.
-
$A = \setdef{\text{apple}, \text{orange}}$ and $B = \setdef{\text{orange}, \text{banana}}$
: $A \sqcup B = \setdef{(1, \text{apple}), (1, \text{orange}), (2, \text{orange}), (2, \text{banana})}$
The tagged disjoint union keeps both copies of orange, so it has $4$ elements.
Examples
Each cell is the disjoint union of $A$ and $B$, in the ___ sense. In the tagged sense, each element is paired with a tag, $1$ for $A$ or $2$ for $B$.
| Example | disjoint union (of disjoint sets) | disjoint union (tagged) | Why |
|---|---|---|---|
| $A = \setdef{\text{apple}}$ and $B = \setdef{\text{banana}}$ | $A \cup B = \setdef{\text{apple}, \text{banana}}$ | $A \sqcup B = \setdef{(1, \text{apple}), (2, \text{banana})}$ | |
| $A = \setdef{\text{apple}, \text{orange}}$ and $B = \setdef{\text{orange}, \text{banana}}$ | None | $A \sqcup B = \setdef{(1, \text{apple}), (1, \text{orange}), (2, \text{orange}), (2, \text{banana})}$ | $A$ and $B$ overlap, so their ordinary union $\setdef{\text{apple}, \text{orange}, \text{banana}}$ is not a disjoint union in either sense. The tagged disjoint union keeps both copies of orange, so it has $4$ elements. |
Notes
- When $A$ and $B$ are disjoint, the two meanings agree up to a natural bijection, so many authors use them interchangeably.
- The tagged disjoint union has $\abs{A} + \abs{B}$ elements, even when $A$ and $B$ overlap. For example, $\reals \sqcup \reals$ is two separate copies of the real line.