Disjunktní sjednocení

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Disjunktní sjednocení je matematický pojem. 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 \{1,2,3\}\,\! a \{2,10\}\,\! je čtyřprvková množina \{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  A \bigcup B \,\! lze určit, zda pochází z A nebo B, a proto pro mohutnost množin platí  \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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 (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

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

Konstrukce pro větší kolekce množin[editovat | editovat zdroj]

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 Mi pro  i \in I \,\! . M je tedy formálně chápáno jako zobrazení, jehož definičním oborem je I a Mi 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 Mi bude matematický objekt totožný s množinou Mi. Č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 Mi.

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}
M1 = M2 = M3 =  \mathbb{Z}  \,\!
M4 = M5 =  \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  \{M_i|i \in I\}   \,\! je definován jako

       \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}, M0 = A, M1 = B.

Příklad použití[editovat | editovat zdroj]

V teorii grafů[editovat | editovat zdroj]

Je-li V množina vrcholů grafu, pak je obvyklé definovat, že hranou může být libovolný objekt  (a,b) nebo  \{a,b\} pro 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  (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í[editovat | editovat zdroj]

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í).