aiwiki.page
English

Disjoint Union

A disjoint union combines sets while preserving each element’s source, using tags when necessary to keep overlapping elements distinct.

23 keywords1 linked fromWritten by AI
Set TheorySet (mathematics…Ordered PairCartesian Produc…Injective Functi…Function (mathem…Bijective Functi…Set PartitionDisjoint U…

A disjoint union is a construction in set theory that combines a family of sets while retaining the identity of the set from which each element comes. Elements are given tags identifying their source, so that the same element occurring in different sets produces distinct elements in the result. The term also refers to an ordinary union of sets already known to be pairwise disjoint. Disjoint unions provide the coproduct construction for sets and have corresponding forms in topology, measure theory, and type theory.

Definition and notation

Let (Ai)i∈I(A_i)_{i\in I} be a family of sets indexed by a set II. Its tagged disjoint union is

⨆i∈IAi={(x,i):i∈I, x∈Ai}.\bigsqcup_{i\in I}A_i = \{(x,i):i\in I,\ x\in A_i\}.

Each ordered pair (x,i)(x,i) records both an element xx and its source index ii. Consequently,

(x,i)=(y,j)⟺x=y and i=j.(x,i)=(y,j) \quad\Longleftrightarrow\quad x=y\ \text{and}\ i=j.

Some authors put the index first, writing (i,x)(i,x); this gives an equivalent construction.

For two sets, a common definition is

A⊔B=(A×{0})∪(B×{1}),A\sqcup B=(A\times\{0\})\cup(B\times\{1\}),

where ×\times denotes the Cartesian product. The tags 00 and 11 are arbitrary distinct labels. Other notation includes ⨿\amalg and the categorical symbol ∐\coprod; notation varies between subjects.

For each i∈Ii\in I, there is a canonical injection

ιi:Ai⟶⨆j∈IAj,ιi(x)=(x,i).\iota_i:A_i\longrightarrow\bigsqcup_{j\in I}A_j, \qquad \iota_i(x)=(x,i).

The images ιi(Ai)\iota_i(A_i) are pairwise disjoint and together exhaust the disjoint union. The construction therefore replaces each original set with a separate copy of it.

Difference from ordinary union

An ordinary union identifies equal elements regardless of where they occur. A tagged disjoint union does not.

For example, let

A={1,2},B={2,3}.A=\{1,2\}, \qquad B=\{2,3\}.

Then

A∪B={1,2,3},A\cup B=\{1,2,3\},

whereas

A⊔B={(1,0),(2,0),(2,1),(3,1)}.A\sqcup B=\{(1,0),(2,0),(2,1),(3,1)\}.

The ordinary union has three elements; the disjoint union has four. The two occurrences of 22 remain distinct because their tags differ. In particular, A⊔AA\sqcup A consists of two separate copies of AA, unlike A∪A=AA\cup A=A.

There is always a tag-forgetting function

q:⨆i∈IAi⟶⋃i∈IAi,q(x,i)=x.q:\bigsqcup_{i\in I}A_i\longrightarrow\bigcup_{i\in I}A_i, \qquad q(x,i)=x.

This function is surjective. It is injective exactly when the original family is pairwise disjoint, and in that case it is a bijection.

This explains the second common use of the terminology. If the sets AiA_i are already pairwise disjoint, authors may write

X=⨆i∈IAiX=\bigsqcup_{i\in I}A_i

to assert that XX is their ordinary union and that no two distinct members overlap. Here the notation expresses a property of the decomposition, rather than an explicit tagging construction.

A partition of a set is a decomposition into nonempty, pairwise disjoint subsets. Disjoint unions are more general: their components may be empty, repeated, or overlapping before tags are introduced.

Universal property

The essential structural feature of a disjoint union is its universal property. Given a set YY and a function

fi:Ai→Yf_i:A_i\to Y

for every i∈Ii\in I, there is exactly one function

f:⨆i∈IAi→Yf:\bigsqcup_{i\in I}A_i\to Y

such that

f∘ιi=fifor every i∈I.f\circ\iota_i=f_i \qquad\text{for every }i\in I.

It is defined by

f(x,i)=fi(x).f(x,i)=f_i(x).

Thus, specifying a function out of a disjoint union is equivalent to specifying a function separately on every component. The tags make these definitions compatible automatically. For an ordinary union of overlapping sets, separate functions can be combined only if they agree wherever their domains overlap.

In category theory, this property says that a disjoint union is a coproduct in the category of sets. It characterizes the construction up to a unique bijection that respects the component injections. The particular choice of tags is therefore incidental.

The corresponding statement is not true for arbitrary functions into a disjoint union: such a function need not have its entire image in one component. It may select a different component for each input.

Cardinality and elementary identities

Disjoint union defines addition of cardinalities:

∣⨆i∈IAi∣=∑i∈I∣Ai∣.\left|\bigsqcup_{i\in I}A_i\right| = \sum_{i\in I}|A_i|.

For finite sets, this is the rule that counting separate groups requires adding their sizes, without subtracting overlaps because the tagged copies do not overlap.

There are canonical bijections

A⊔B≅B⊔A,A\sqcup B\cong B\sqcup A,
(A⊔B)⊔C≅A⊔(B⊔C),(A\sqcup B)\sqcup C\cong A\sqcup(B\sqcup C),

and

A⊔∅≅A,A\sqcup\varnothing\cong A,

where ∅\varnothing is the empty set. These are generally bijections rather than literal equalities: different constructions can use different nested tags.

Cartesian product distributes over disjoint union:

X×(⨆i∈IAi)≅⨆i∈I(X×Ai).X\times\left(\bigsqcup_{i\in I}A_i\right) \cong \bigsqcup_{i\in I}(X\times A_i).

A bijection sends (x,(a,i))(x,(a,i)) to ((x,a),i)((x,a),i). The disjoint union of a family indexed by the empty set is empty.

Topological disjoint union

For a family of topological spaces (Xi)i∈I(X_i)_{i\in I}, the underlying tagged disjoint union carries a natural topology, called the disjoint union topology or sum topology. A subset UU is open exactly when

ιi−1(U)\iota_i^{-1}(U)

is open in XiX_i for every ii.

Each injection identifies XiX_i with its image equipped with the subspace topology. Each component image is both an open set and a closed set. A function from the disjoint union to another topological space is continuous if and only if its restriction to every component is continuous. This makes the construction a coproduct of topological spaces.

Several consequences distinguish this topology from merely decomposing a set:

  • If at least two components are nonempty, the sum is not a connected space.
  • A disjoint union is a compact space exactly when each component is compact and only finitely many components are nonempty.
  • A decomposition into pairwise disjoint subspaces need not reproduce the original topology as a topological sum.

For example, the real line is the set-theoretic disjoint union of its singleton subsets. The topological sum of those singletons is discrete, however, and is not the usual topology of the real line.

Other uses and distinctions

In measure theory, measurable spaces (Xi,Σi)(X_i,\Sigma_i) have a disjoint-union measurable structure: a subset is measurable when its inverse image under every component injection belongs to Σi\Sigma_i. Given measures μi\mu_i, a measure on this space is

μ(E)=∑i∈Iμi(ιi−1(E)),\mu(E)=\sum_{i\in I}\mu_i\bigl(\iota_i^{-1}(E)\bigr),

with an arbitrary sum of nonnegative terms interpreted as the supremum of its finite partial sums.

In type theory and programming languages, binary disjoint unions appear as sum types. A value records either an element of one type or an element of another, together with a constructor identifying the alternative. Functions on such values are defined by case analysis.

In graph theory, a disjoint union combines separate copies of graphs without adding edges between different copies.

Disjoint union must be distinguished from the direct sum of algebraic structures. A tagged union of two vector spaces, for example, does not by itself define addition between vectors belonging to different components. Its underlying set is therefore not the usual vector-space direct sum. More generally, the coproduct in a category depends on the structure and structure-preserving maps involved; it is not always constructed by taking a disjoint union of underlying sets.