nLab
disjoint union

Context

Category theory

Limits and colimits

Disjoint unions

Idea

The disjoint union is a coproduct in Set, the category of sets.

In a general category coproducts need not have the expected disjointness property of those in Set. If they do they are called disjoint coproducts.

Definition

Given any family (A i) i:I(A_i)_{i:I} of sets, the (external) disjoint union iA i\biguplus_i A_i (also written iA i\sum_i A_i, iA i\coprod_i A_i, etc) of the family is the set of all (ordered) pairs (i,a)(i,a) with ii in the index set II and aa in A iA_i.

As stated, the second element of such a pair depends on the first element, which is natural in dependent type theory and certainly feasible in material set theory; but if you don’t like this, then define iA i\biguplus_i A_i to be the set of those elements xx of the cartesian product i𝒫A i\prod_i \mathcal{P}A_i of the power sets such that there is exactly one index jj such that x jx_j is inhabited and that x jx_j is a singleton. If you're trying to be predicative too, consider adopting the existence of disjoint unions as an axiom (the axiom of disjoint unions) in your foundations.

There is a natural injection A j iA iA_j \to \biguplus_i A_i (mapping aa to (j,a)(j,a)) for each index jj, and its common to treat A jA_j as a subset of iA i\biguplus_i A_i. So if no confusion can result (in particular, when the notation for an elements of A jA_j always makes the ambient set clear), one often suppresses the index in the notation for an element of the disjoint union.

Special cases

Given sets AA and BB, the disjoint union of the binary family (A,B)(A,B) is written ABA \uplus B (also A+BA + B, A⨿BA \amalg B, etc); its elements may be written (if care is needed) as (0,a)(0,a) and (1,b)(1,b), (1,a)(1,a) and (2,b)(2,b), ιa\iota{a} and κb\kappa{b}, and in many other styles.

Given sets A 1A_1 through A nA_n, the disjoint union of the nn-ary family (A 1,,A n)(A_1,\ldots,A_n) is written i=1 nA i\biguplus_{i=1}^n A_i (or similarly); its elements may be written (if care is needed) as (i,a)(i,a) for 1in1 \leq i \leq n and aA ia \in A_i.

Given sets A 1A_1, A 2A_2, etc, the disjoint union of the countably infinitary family (A 1,A 2,)(A_1,A_2,\ldots) is written i=1 A i\biguplus_{i=1}^\infty A_i (or similarly); its elements may be written (if care is needed) as (i,a)(i,a) for ii a natural number and aA ia \in A_i.

Given a set AA, the disjoint union of the unary family (A)(A) may be identified with AA itself; that is, we identify (i,a)(i,a) for the unique index ii with aa.

The disjoint union of the empty family ()() is empty; it has no elements.

Internal version

(This is internal in the sense of ‘internal direct sum’, not internalization. For that, just see coproduct.)

If a family (A i) i:I(A_i)_{i: I} of subsets of a given set XX are all pairwise disjoint (that is, A iA jA_i \cap A_j has an element only if i=ji = j, for any indices ii and jj), then the union iA i\bigcup_i A_i is naturally bijective with the (external) disjoint union defined above. Conversely, given an external disjoint union iA i\biguplus_i A_i, each A jA_j may be identified with a subset of iA i\biguplus_i A_i (as explained above); these subsets are all pairwise disjoint, and their union is the entire disjoint union.

Accordingly, a union of pairwise disjoint subsets may be called an internal disjoint union. (Compare the internal vs external notions of direct sum.)

Revised on November 8, 2012 12:59:39 by Urs Schreiber (82.169.65.155)