Disjunktní sjednocení

Disjunktní sjednocení je množinová operace podobná sjednocení. Tak jako lze sjednocení množin A a B chápat jako nejmenší množinu, v níž jsou všechny prvky z A i B, lze disjunktní sjednocení chápat jako nejmenší množinu, v níž jsou všechny prvky z A i B, ovšem každý objekt nese informaci, z které množiny byl převzat a objekty, které jsou v A i B, se vyskytují ve výsledku zvlášť za A a zvlášť za B.

Zatímco sjednocení množin ${\displaystyle \{1,2,3\}\,\!}$ a ${\displaystyle \{2,10\}\,\!}$ je čtyřprvková množina ${\displaystyle \{1,2,3,10\}\,\!}$, jejich disjunktní sjednocení je pětiprvková množina, jejíž prvky lze intuitivně chápat takto:

• 1 z množiny A
• 2 z množiny A
• 2 z množiny B
• 3 z množiny A
• 10 z množiny B

Název disjunktní sjednocení pochází ze skutečnosti, že tato operace chová jako sjednocení na disjunktních množinách, tj. množinách, které nemají žádné společné prvky (mají prázdný průnik). V takovém případě totiž platí, že u každého prvku ${\displaystyle A\bigcup B\,\!}$ lze určit, zda pochází z A nebo B, a proto pro mohutnost množin platí ${\displaystyle \left\vert A\bigcup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert \,\!}$ (a to i u nekonečných množin).

Názvosloví

Tento článek pojednává o konstrukci, kterou lze provést nad libovolnými množinami, i když nejsou disjunktní. Formulace „C je disjunktním sjednocením množin A a B“ se však často používá ve smyslu „C je sjednocením množin A a B, které jsou disjunktní“. Jelikož u disjunktním množin má jejich obyčejné a disjunktní sjednocení velmi podobné vlastnosti (byť formálně nejde o týž objekt), rozdíl mezi těmito dvěma významy je často bezvýznamný.

Konstrukce

Pokud nějaký prvek x je v A i B, je nutné jeho jednotlivé kopie v disjunktním sjednocení odlišit pomocí uspořádaných dvojic; prvek pocházející z A je zvykem reprezentovat jako ${\displaystyle (x,0)}$ a prvek pocházející z B jako (x,1). Ovšem bylo by nepraktické toto použít pouze u těch prvků, které se skutečně vyskytují v obou množinách; proto se toto použije u všech prvků. Za každý prvek se tedy formou uspořádané dvojice "přidá" informace o tom, ze které množiny byl převzat. Disjunktní sjednocení dvou množin se tedy definuje jako

${\displaystyle C\{(a,0)|a\in A\}\;\bigcup \;\{(b,1)|b\in B\}\,\!}$

Konstrukce pro větší kolekce množin

Sjednocení i disjunktní sjednocení lze však definovat pro libovolně velké kolekce množin. Abychom s nimi mohli přehledně pracovat, používáme konvenci, že máme nějakou indexovou množinu I a jednotlivé množiny značíme M_i pro ${\displaystyle i\in I\,\!}$. M je tedy formálně chápáno jako zobrazení, jehož definičním oborem je I a M_i je jen přehlednější zápis pro M(i).

Tato konvence není nikterak omezující, neboť přejeme-li si pracovat s libovolným systémem množin S, můžeme (pokud se nenabízí přehlednější způsob indexování) položit I = S a M(i) = i. Tedy index množiny M_i bude matematický objekt totožný s množinou M_i. Často je však přehlednější indexovat např. přirozenými čísly. Pokud chceme disjunktní sjednocení z kolekce, v níž jsou některé množiny vícekrát (například disjunktní sjednocení z tří kopií množiny celých čísel plus dvou kopií množiny záporných celých čísel), pak zobrazení M nebude prosté, ale různým indexům i přiřadí tutéž množinu M_i.

V uvedeném případě můžeme zvolit indexování různě a nezáleží na tom. Můžeme např. indexovat přirozenými čísly tak, že

I = {1,2,3,4,5}

M₁ = M₂ = M₃ = ${\displaystyle \mathbb {Z} \,\!}$

M₄ = M₅ = ${\displaystyle \mathbb {Z} ^{-}\,\!}$

Za číslo 19 pak budou v disjunktním sjednocení prvky (19,1), (19,2), (19,3). Číslo 19 se tedy tímto způsobem vyskytuje ve výsledné množině třikrát, zatímco číslo -7 pětkrát.

Obecná definice tedy zní: Direktní součin kolekce množin ${\displaystyle \{M_{i}|i\in I\}\,\!}$ je definován jako

${\displaystyle \bigsqcup _{i\in I}M_{i}:=\bigcup _{i\in I}M_{i}\times \{i\}\,\!=\{(x,i)|i\in I\wedge x\in M_{i}\}}$

přičemž první výraz je používané označení, druhý význam je definice pomocí kartézského součinu a třetí výraz je rozepsání této definice.

Tato definice dá přesně stejnou množinu, jako předchozí jednodušší definice disjunktního sjednocení dvou množin A,B. Je třeba položit I = {0,1}, M₀ = A, M₁ = B.

Příklad použití

V teorii grafů

Je-li V množina vrcholů grafu, pak je obvyklé definovat, že hranou může být libovolný objekt ${\displaystyle (a,b)}$ nebo ${\displaystyle \{a,b\}}$ pro ${\displaystyle a,b\in V}$ (v prvním případě mluvíme o orientované hraně, v druhém o neorientované; u neorientované nesmí být a=b).

Tato definice je však problematická, protože v závislosti na definici uspořádané dvojice může pro některé vrcholy nastat ${\displaystyle (a,b)=\{c,d\}}$. Tento problém lze vyřešit tak, že hranou může být jakýkoli prvek disjunktního sjednocení množiny možných orientovaných hran a množiny možných neorientovaných hran.

Konstrukce zúplnění

Ke každému metrickému prostoru lze zkonstruovat jeho zúplnění, tedy nejmenší metrický nadprostor, který je úplný. Tato konstrukce se provádí tak, že každý nový bod je reprezentován množinou všech Cauchyovských posloupností, které k němu (neformálně řečeno) konvergují. K tomu, aby některý z těchto nových objektů nebyl identický s některým z původních objektů, lze použít právě disjunktní sjednocení. (Přirozenější je ovšem problém vyřešit tak, že i původní prvky jsou reprezentovány množinami Cauchyovských posloupností).