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 a je čtyřprvková množina , 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 lze určit, zda pochází z A nebo B, a proto pro mohutnost množin platí (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 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

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 . 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 =
M4 = M5 =

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 je definován jako

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 nebo pro (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 . 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í).