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:不交并]]