Disjoint Unions

Motivation: The Problem with Union

Given sets $A$ and $B$, the ordinary union $A \cup B$ loses information:

• If $x \in A \cap B$, we cannot tell if $x$ came from $A$, from $B$, or from both
• The size is $|A \cup B| = |A| + |B| - |A \cap B|$, not simply $|A| + |B|$

Definition of Disjoint Union

The disjoint union (also called coproduct or sum) of $A$ and $B$ is:

$A + B = (\{0\} \times A) \cup (\{1\} \times B)$

Each element is “tagged” with its origin: $0$ for elements from $A$, $1$ for elements from $B$.

Alternative Notations

• $A \amalg B$ (amalgamation symbol)
• $A \sqcup B$
• $A \oplus B$

Examples

Example 1

$A = \{a, b\}$, $B = \{b, c\}$.

• $A \cup B = \{a, b, c\}$ (ordinary union, $b$ appears once)
• $A + B = \{(0, a), (0, b), (1, b), (1, c)\}$ (disjoint union, $b$ appears twice with different tags)

Example 2

$A = \{1, 2, 3\}$, $B = \{x, y\}$.

$A + B = \{(0, 1), (0, 2), (0, 3), (1, x), (1, y)\}$

Properties

Cardinality

$|A + B| = |A| + |B|$

This is the key advantage: the size adds without any correction.

Injective Maps

There are natural injection maps:

• $\iota_A : A \to A + B$ given by $\iota_A(a) = (0, a)$
• $\iota_B : B \to A + B$ given by $\iota_B(b) = (1, b)$

Universal Property

Given any set $C$ and functions $f : A \to C$, $g : B \to C$, there is a unique function $[f, g] : A + B \to C$ such that:

$[f, g] \circ \iota_A = f \quad \text{and} \quad [f, g] \circ \iota_B = g$

Explicitly: $[f, g](0, a) = f(a)$ and $[f, g](1, b) = g(b)$.

Case Analysis

The disjoint union enables case analysis in proofs:

To define a function $h : A + B \to C$, define:

1. A function $h_A : A \to C$ for the “left” case
2. A function $h_B : B \to C$ for the “right” case

Then $h = [h_A, h_B]$.

n-ary Disjoint Union

For sets $A_1, \ldots, A_n$:

$A_1 + A_2 + \cdots + A_n = \{(i, a) : i \in \{1, \ldots, n\}, a \in A_i\}$

Cardinality

$\left|\sum_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i|$

Product vs Sum

Product $\times$	Sum $+$
Pair $(a, b)$ with both	Tagged $(i, a)$ with one
$	A \times B
Projection maps	Injection maps
Universal: maps out	Universal: maps in

These are dual constructions in category theory.

---

Summary

• Disjoint union $A + B$ tags elements to preserve origin
• $|A + B| = |A| + |B|$ without intersection correction
• Natural injections $\iota_A$, $\iota_B$ embed $A$, $B$ into the sum
• Universal property: maps $A + B \to C$ correspond to pairs of maps $A \to C$, $B \to C$