Disjoint union
In mathematics, the disjoint union of two sets A and B is a set-theoretic construction defined as the set of ordered pairs \{(a, 1) \mid a \in A\} \cup \{(b, 2) \mid b \in B\}, which combines all elements from A and B while tagging each with an identifier to ensure they remain distinguishable regardless of any potential overlap in the original sets.[1] This operation preserves the cardinality additivity for finite sets, such that if A and B are finite, then the cardinality of their disjoint union equals |A| + |B|.[2] For example, if A = \{1, 2\} and B = \{2, 3\}, the disjoint union includes (1,1), (2,1), (2,2), and (3,2), avoiding duplication of the shared element 2.[1]
The concept generalizes to a family of sets \{A_i\}_{i \in I} indexed by a set I, forming \bigsqcup_{i \in I} A_i = \bigcup_{i \in I} (A_i \times \{i\}), where elements are pairs (a, i) with a \in A_i.[1] This ensures the images of the canonical injections A_i \hookrightarrow \bigsqcup_{i \in I} A_i are pairwise disjoint, making the disjoint union the unique (up to isomorphism) set satisfying the universal property that for any set X and family of functions f_i: A_i \to X, there exists a unique function \overline{f}: \bigsqcup_{i \in I} A_i \to X such that \overline{f} \circ \iota_i = f_i for each i.[3] In the category of sets, the disjoint union is precisely the coproduct, serving as the categorical dual to the product.[3]
Beyond set theory, the disjoint union extends to other mathematical structures, such as topological spaces, where the disjoint union topology on \bigsqcup_{\alpha} X_{\alpha} equips the underlying set with the finest topology making each inclusion X_{\alpha} \hookrightarrow \bigsqcup_{\alpha} X_{\alpha} continuous; a subset is open if its intersection with each X_{\alpha} is open in X_{\alpha}.[3] This construction is fundamental in algebraic topology for building spaces like wedges or suspensions[3] and in measure theory for additivity over disjoint decompositions.[4] In category theory more broadly, while the coproduct in the category of sets is disjoint, coproducts in other categories (e.g., pointed sets or groups) may involve additional identifications, such as the direct sum for abelian groups.[5]
Introduction and Examples
The disjoint union provides a standard way to combine two or more sets, such as A and B, into a single set in which elements originating from A remain distinguishable from those originating from B, even if the sets share identical underlying elements.[1] This approach ensures that the structure and provenance of each element are preserved during the merger, allowing for clear separation based on their source sets.[1]
In contrast to the ordinary union of sets, which simply collects all unique elements and may inadvertently identify overlapping items without regard to their origins, the disjoint union addresses this issue by enforcing distinguishability, thereby maintaining the integrity of the individual sets' identities.[6] This is particularly useful in scenarios where tracking element membership is essential to avoid unintended equivalences.
The concept originated in set theory with Georg Cantor's 1878 work, where he employed it to define operations on collections without presupposing that the sets were already disjoint.[7]
Basic Example
Consider the sets A = \{1, 2\} and B = \{2, 3\}. Their ordinary union is A \cup B = \{1, 2, 3\}, which contains only three elements because the shared value 2 is identified regardless of its origin.[1] In contrast, the disjoint union A \sqcup B treats elements from A and B as distinct, even when they share the same value, resulting in a set with four elements that preserves information about each element's source set.[1][5]
To compute A \sqcup B, tag each element with an indicator of its originating set, such as "L" for elements from A and "R" for elements from B: the tagged version of A becomes \{(1, \text{L}), (2, \text{L})\}, and the tagged version of B becomes \{(2, \text{R}), (3, \text{R})\}.[1] The disjoint union is then the ordinary union of these tagged sets: A \sqcup B = \{(1, \text{L}), (2, \text{L})\} \cup \{(2, \text{R}), (3, \text{R})\} = \{(1, \text{L}), (2, \text{L}), (2, \text{R}), (3, \text{R})\}.[1] Here, the two instances of 2 are now distinct—(2, \text{L}) represents the 2 from A, while (2, \text{R}) represents the 2 from B—ensuring no overlap or loss of provenance.[5]
This tagging approach builds on the basic intuition of distinguishability by explicitly marking origins to avoid conflating identical values from different sets.[1]
The following table illustrates the sets before and after the disjoint union:
| Original Sets | Elements |
|---|
| A | 1, 2 |
| B | 2, 3 |
| A \cup B | 1, 2, 3 (3 elements) |
| A \sqcup B | (1, L), (2, L), (2, R), (3, R) (4 elements) |
Tagged Union Construction
In set theory, the tagged union construction defines the disjoint union of two sets A and B, denoted A \sqcup B, as the set (A \times \{0\}) \cup (B \times \{1\}), consisting of all ordered pairs (a, 0) for a \in A and (b, 1) for b \in B.[8]
The original sets are embedded into this union via injections i_A: A \to A \sqcup B defined by a \mapsto (a, 0) and i_B: B \to A \sqcup B defined by b \mapsto (b, 1); these mappings are injective because distinct elements in A (or B) produce distinct pairs due to the uniqueness of ordered pairs in set theory.[8]
Disjointness follows directly from the construction: the sets A \times \{0\} and B \times \{1\} have no elements in common, as any supposed shared element (x, 0) = (y, 1) would require $0 = 1, which is impossible.[8] As a result, the cardinality of the disjoint union is the sum of the individual cardinalities, |A \sqcup B| = [|A|](/page/Cardinality) + [|B|](/page/Cardinality).[8] For the basic example of sets \{1,2\} and \{2,3\}, this tags the shared element 2 as (2, 0) and (2, 1) to ensure distinguishability.[8]
Algebraic Properties
The disjoint union operation on sets, denoted A \sqcup B, is associative up to canonical isomorphism. Specifically, for sets A, B, and C, the disjoint union (A \sqcup B) \sqcup C is isomorphic to A \sqcup (B \sqcup C) via a bijection that recursively adjusts tags: elements tagged from the left-associative structure are remapped by incrementing the tag index appropriately to match the right-associative tagging.[9] This isomorphism preserves the set structure and follows from the tagged construction of the disjoint union.[10]
The operation is also commutative up to isomorphism: A \sqcup B \cong B \sqcup A, achieved by a bijection that swaps the tags assigned to elements of A and B.[9] This property ensures that the order of combining sets does not affect the resulting structure, up to relabeling of the distinguishing tags.
The empty set \emptyset serves as a neutral element for the disjoint union: A \sqcup \emptyset \cong A via the identity map on A, as the empty set contributes no elements or tags.[9] This extends to iterated finite or infinite disjoint unions, where adjoining empty sets leaves the union unchanged up to isomorphism. In the context of cardinal arithmetic, where the cardinality of the disjoint union corresponds to cardinal addition, the zero cardinal acts analogously as an identity.[11]
The disjoint union is compatible with set functions in a bifunctorial manner. Given functions f: A \to C and g: B \to D, there exists a unique induced function \overline{(f,g)}: A \sqcup B \to C \sqcup D defined by \overline{(f,g)}(a,0) = (f(a),0) for a \in A and \overline{(f,g)}(b,1) = (g(b),1) for b \in B, where 0 and 1 are the distinguishing tags.[9] This construction ensures that the disjoint union respects the categorical structure of the category of sets.[10]
Categorical Framework
Coproduct Interpretation
In category theory, the disjoint union provides a fundamental example of a coproduct within the category of sets, Set, where objects are sets and morphisms are functions between them. The coproduct of two sets A and B, denoted A \sqcup B, is their disjoint union, equipped with canonical injection morphisms i_A: A \to A \sqcup B and i_B: B \to A \sqcup B. These injections embed A and B into A \sqcup B such that their images are disjoint, ensuring no overlap between elements originating from A and those from B.[12][13]
This coproduct structure is characterized by a commutative diagram illustrating the injections i_A and i_B. For any set Z and any pair of functions f: A \to Z, g: B \to Z, there exists a unique function h: A \sqcup B \to Z such that the following diagram commutes:
\begin{CD}
A @>f>> Z \\
@V i_A VV @VV id_Z V \\
A \sqcup B @>h>> Z \\
@A i_B AA @AA id_Z A \\
B @>g>> Z
\end{CD}
Here, h \circ i_A = f and h \circ i_B = g, with h factoring the pair (f, g) uniquely through the coproduct.[9][14]
The set-theoretic formalism of the tagged union construction realizes this coproduct concretely in Set, where elements of A \sqcup B are pairs (a, \text{tag}_A) or (b, \text{tag}_B) with distinct tags ensuring disjointness, thereby confirming the disjoint union as the categorical coproduct in this context.[12]
Universal Property
The universal property of the disjoint union characterizes it as the coproduct in a category. Specifically, for objects A and B in a category \mathcal{C}, their coproduct A \sqcup B is equipped with morphisms (injections) i_A: A \to A \sqcup B and i_B: B \to A \sqcup B such that for any object Z in \mathcal{C} and any morphisms f: A \to Z, g: B \to Z, there exists a unique morphism h: A \sqcup B \to Z satisfying h \circ i_A = f and h \circ i_B = g.[15]
In the category of sets \mathbf{Set}, where the coproduct is realized as the disjoint union, the proof proceeds by explicit construction. The injections embed A and B into disjoint subsets of A \sqcup B, typically via tagging elements as pairs (a, 0) for a \in A and (b, 1) for b \in B. The unique morphism h is then defined piecewise: h((a, 0)) = f(a) and h((b, 1)) = g(b). This satisfies the required commutativity, and uniqueness follows because every element of A \sqcup B lies in exactly one tagged component, ensuring h is fully determined by its action on the images of i_A and i_B.[12][15]
This property generalizes to any category admitting coproducts, where the disjoint union (or its categorical analogue) satisfies the same mediating morphism condition without reference to underlying set structures.[9][15]
Extensions and Variants
Disjoint Union in Topology
In topology, the disjoint union of two topological spaces (X, \tau_X) and (Y, \tau_Y) is constructed as the set-theoretic disjoint union X \sqcup Y = (X \times \{0\}) \cup (Y \times \{1\}), equipped with the disjoint union topology. This topology consists of all subsets of the form \bigcup (U_i \times \{i\}), where i \in \{0,1\} and each U_i is open in the corresponding space (i.e., U_0 \in \tau_X or U_1 \in \tau_Y); more precisely, the open sets are those that intersect X \times \{0\} in an open subset of X and Y \times \{1\} in an open subset of Y.[16] This ensures that the topology on each component remains unchanged, with no "interaction" between the spaces—open sets cannot mix points from X and Y in a way that would require continuity across components.[16]
A key property of the disjoint union topology is that it makes X \sqcup Y the categorical coproduct of X and Y in the category \mathbf{Top} of topological spaces and continuous maps. Specifically, for any topological space Z and continuous maps f: X \to Z, g: Y \to Z, there exists a unique continuous map h: X \sqcup Y \to Z such that h|_X = f and h|_Y = g, induced by the inclusions of X and Y into the disjoint union.[17] This coproduct structure aligns with the general categorical interpretation but specializes to continuous functions, preserving the openness of sets within each disjoint component without additional topological glue.[17]
For a concrete example, consider the disjoint union of two copies of the real line \mathbb{R}, denoted \mathbb{R}_1 \sqcup \mathbb{R}_2, where \mathbb{R}_1 = \mathbb{R} \times \{1\} and \mathbb{R}_2 = \mathbb{R} \times \{2\} with the subspace topologies inherited from the standard topology on \mathbb{R}. Open sets in this space are unions of open intervals from each copy, such as (a,b) \times \{1\} \cup (c,d) \times \{2\}, resulting in two parallel, separate "axes" that are topologically disconnected from one another—points from different copies cannot be connected by continuous paths within the space.[18]
Disjoint Union Types in Computing
In typed programming languages such as Haskell and Rust, a disjoint union type, often termed a sum type or variant, enables the representation of values that belong to one of several mutually exclusive types, with explicit tags to distinguish constructors and enforce type safety at compile time.[19] This construction mirrors the tagged union from set theory, where elements from different sets are paired with identifiers to avoid overlap.[20] For instance, a disjoint union of types A and B, denoted A + B, permits values constructed as either a tagged element from A or from B, preventing unsafe unions that could lead to runtime errors in less strict languages.[21]
Key properties of disjoint union types include support for exhaustive pattern matching, which requires handling all possible variants to ensure completeness, and their interpretation as coproducts in the category of types, where morphisms respect the disjoint structure.[19] In practice, this exhaustiveness is checked by the compiler: unhandled cases trigger errors, promoting robust error handling and reducing bugs.[22] The coproduct property ensures that functions on the union type can be defined by specifying behavior for each tagged component separately, facilitating modular code.[20]
A representative example is the Either type in Haskell, which defines a binary disjoint union. The type is declared as:
haskell
data Either a b = Left a | Right b
data Either a b = Left a | Right b
Construction involves applying Left to a value of type a or Right to a value of type b; for deconstruction, pattern matching via the either function or case expressions exhausts the possibilities:
haskell
either :: (a -> c) -> (b -> c) -> Either a b -> c
either leftCase rightCase (Left a) = leftCase a
either leftCase rightCase (Right b) = rightCase b
either :: (a -> c) -> (b -> c) -> Either a b -> c
either leftCase rightCase (Left a) = leftCase a
either leftCase rightCase (Right b) = rightCase b
This usage is conventional for error handling, with Left signaling failure and Right success, ensuring type-safe propagation of results.[23]
In Rust, enums serve as disjoint unions, allowing variants with associated data. Consider an enum for network messages:
rust
enum IpAddrKind {
V4,
V6,
}
enum IpAddrKind {
V4,
V6,
}
Or a more expressive variant with payloads:
rust
enum [Message](/page/Message) {
Quit,
Move { x: i32, y: i32 },
Write([String](/page/String)),
}
enum [Message](/page/Message) {
Quit,
Move { x: i32, y: i32 },
Write([String](/page/String)),
}
Deconstruction occurs through match expressions, which the compiler verifies for exhaustiveness:
rust
let msg = Message::Write(String::from("hello"));
match msg {
Message::Quit => println!("Quit"),
Message::Move { x, y } => println!("Move to x: {}, y: {}", x, y),
Message::Write(text) => println!("Write: {}", text),
}
let msg = Message::Write(String::from("hello"));
match msg {
Message::Quit => println!("Quit"),
Message::Move { x, y } => println!("Move to x: {}, y: {}", x, y),
Message::Write(text) => println!("Write: {}", text),
}
This pattern matching guarantees all cases are covered, aligning with the type's disjoint nature and enabling safe handling of variant-specific logic.[24][22]