Disjoint union 188946 210684082 2008-05-06T23:17:59Z Mikkalai 28438 /* See also */ In [[set theory]], a '''disjoint union''' (or '''discriminated union''') is a modified [[union (set theory)|union]] operation which indexes the elements according to which set they originated in. Formally, let {''A''<sub>''i''</sub> : ''i'' ∈ ''I''} be a [[family (set theory)|family]] of sets indexed by ''I''. The '''disjoint union''' of this family is the set :<math>\coprod_{i\in I}A_i = \bigcup_{i\in I}\{(x,i) : x \in A_i\}.</math> The elements of the disjoint union are [[ordered pairs]] (''x'', ''i''). Here ''i'' serves as an auxiliary index that indicates which ''A''<sub>''i''</sub> the element ''x'' came from. Each of the sets ''A''<sub>''i''</sub> is canonically embedded in the disjoint union as the set :<math>A_i^* = \{(x,i) : x \in A_i\}.</math> For ''i'' ≠ ''j'', the sets ''A''<sub>''i''</sub>* and ''A''<sub>''j''</sub>* are disjoint even if the sets ''A''<sub>''i''</sub> and ''A''<sub>''j''</sub> are not. In the extreme case where each of the ''A''<sub>''i''</sub> are equal to some fixed set ''A'' for each ''i'' ∈ ''I'', the disjoint union is the [[Cartesian product]] of ''A'' and ''I'': :<math>\coprod_{i\in I}A = A \times I.</math> One may occasionally see the notation :<math>\sum_{i\in I}A_i</math> for the disjoint union of a family of sets, or the notation ''A'' + ''B'' for the disjoint union of two sets. This notation is meant to be suggestive of the fact that the [[cardinality]] of the disjoint union is the [[sum]] of the cardinalities of the terms in the family. Compare this to the notation for the [[Cartesian product]] of a family of sets. In the language of [[category theory]], the disjoint union is the [[coproduct]] in the [[category of sets]]. It therefore satisfies the associated [[universal property]]. This also means that the disjoint union is the [[categorical dual]] of the [[Cartesian product]] construction. See [[coproduct]] for more details. For many purposes, the particular choice of auxiliary index is unimportant, and in a simplifying [[abuse of notation |abuse of notation]], the indexed family can be treated simply as a collection of sets. In this case <math>A_i^*</math> is referred to as a ''copy'' of <math>A_i</math> and the notation <math>\bigcup_{A \in C}{^*} A</math> is sometimes used. The term ''disjoint union'' (but not ''discriminated union'') is also used to refer to a union of a collection of [[set]]s whose members are [[pairwise disjoint]]. In this case the disjoint union may be identified with the simple union, and the same notation is used. This usage is more common in computer science. Formally, if <math>C</math> is a collection of sets, then :<math>\bigcup_{A \in C} A</math> is a disjoint union in this sense [[if and only if]] for all ''A'' and ''B'' in ''C'' :<math>A \neq B \implies A \cap B = \varnothing.</math> == See also == *[[Coproduct]] *[[Disjoint union (topology)]] *[[Disjoint union of graphs]] *[[Tagged union]] *[[Union (computer science)]] [[Category:Basic concepts in set theory]] [[pl:Suma rozłączna]] [[ru:Дизъюнктное объединение]] [[de:Disjunkte Vereinigung]] [[ko:서로소 합집합]] [[it:Somma disgiunta]] [[zh:不交并]]