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 type of the second element of such a pair depends on the first element, which is natural in dependent type theory (see at dependent sum type) and no problem for material set theory, but it may be ill formed in a structural set theory or in some forms of type theory, especially those based on the internal language of topos theory. Alternatively, one may 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, then you may need to simply adopt the existence of disjoint unions as an axiom (the axiom of disjoint unions) in your foundations, stating the following facts about it.

There is a natural injection A j iA iA_j \to \biguplus_i A_i (mapping aa to (j,a)(j,a), or mapping aa to (i{a|i=j})(i \mapsto \{a \;|\; i = j\})) for each index jj. Conversely, for each element xx of iA i\biguplus_i A_i, there is a unique index jj and such that xx is in the image of the injection from A jA_j. It is 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 element 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 April 20, 2017 00:22:10 by Toby Bartels (108.167.41.14)