Zjemnění rozkladu

Zjemnění rozkladu je matematický pojem z oboru teorie množin, který umožňuje uspořádání množiny všech rozkladů určité pevně dané množiny.

Definice

Předpokládejme, že jsou $R_{1}\,\!$ a $R_{2}\,\!$ dva rozklady množiny $X\,\!$ (množina podmnožin množiny $X\,\!$ je rozklad, pokud její sjednocení je rovno $X\,\!$ a každé dva její prvky jsou disjunktní množiny).

Řekneme, že rozklad $R_{1}\,\!$ je zjemněním rozkladu $R_{2}\,\!$ , pokud $R_{1}\,\!$ vznikl z $R_{2}\,\!$ rozdělením některých jeho množin na podmnožiny. Přesněji zapsáno
$(\forall a\in R_{1})(\exists b\in R_{2})(a\subseteq b)\,\!$

Tuto skutečnost zapisujeme symbolem $R_{1}\ll R_{2}\,\!$ .

Příklady

Uvažujme o rozkladech množiny $\omega \,\!$ všech přirozených čísel.

Rozklad na všechny jednoprvkové podmnožiny $\omega /id=\{\{0\},\{1\},\{2\},\ldots \}\,\!$ je nejjemnější rozklad množiny $\omega \,\!$ – pro každý jiný rozklad $R\,\!$ platí
$\omega /id\ll R\,\!$ .
Rozklad množiny $\omega \,\!$ na jednu jedinou množinu obsahující všechny prvky $\omega \,\!$ , značenou $R_{1}=\{\omega \}\,\!$ , je nejhrubší rozklad množiny $\omega \,\!$ – pro každý jiný rozklad $R\,\!$ platí
$R\ll R_{1}\,\!$ .
Je-li $R_{n}\,\!$ rozklad $\omega \,\!$ na zbytkové třídy po dělení číslem n (tj. například $R_{3}=\{\{0,3,6,\ldots \},\{1,4,7,\ldots \},\{2,5,8,\ldots \}\}\,\!$ ), pak platí, že $R_{a}\ll R_{b}\,\!$ , právě když b dělí a. Například $R_{8}\ll R_{4}\ll R_{2}\ll R_{1}\,\!$ nebo $R_{1500}\ll R_{30}\,\!$ .

Zjemnění jako uspořádání

Dá se poměrně snadno ověřit, že relace $\ll \,\!$ je neostré uspořádání množiny $R(X)\,\!$ všech možných rozkladů množiny $X\,\!$ . Určitě se ale nejedná o lineární uspořádání – pokud se vrátíme k předchozímu příkladu, tak neplatí ani $R_{2}\ll R_{3}\,\!$ , ani $R_{3}\ll R_{2}\,\!$ .

Příklad množiny všech rozkladů

Uvažujme o tříprvkové množině $X=\{1,2,3\}\,\!$ . Tato množina má celkem pět rozkladů $R(X)=\{R_{a},R_{b},R_{c},R_{d},R_{e}\}\,\!$ , kde

$R_{a}=\{\{1\},\{2\},\{3\}\}\,\!$
$R_{b}=\{\{1,2\},\{3\}\}\,\!$
$R_{c}=\{\{1,3\},\{2\}\}\,\!$
$R_{d}=\{\{2,3\},\{1\}\}\,\!$
$R_{e}=\{\{1,2,3\}\}\,\!$

Je vidět, že

$R_{a}\ll R_{b}\ll R_{e}\,\!$
$R_{a}\ll R_{c}\ll R_{e}\,\!$
$R_{a}\ll R_{d}\ll R_{e}\,\!$
$R_{b},R_{c},R_{d}\,\!$ nelze porovnat

Vztah rozkladů a ekvivalencí

Jak je uvedeno v článku Ekvivalence (matematika), odpovídá každý rozklad na množině $X\,\!$ vzájemně jednoznačně nějaké ekvivalenci na množině $X\,\!$ .

Je-li $R\,\!$ rozklad a $\sim _{R}\,\!$ jemu odpovídající ekvivalence, potom R je shodný s množinou tříd ekvivalence $\sim _{R}\,\!$ a naopak – $\sim _{R}\,\!$ lze definovat pomocí rozkladu $R\,\!$ takto:
$a\sim _{R}b\Leftrightarrow (\exists y\in R)(a\in y\land b\in y)\,\!$
Lidsky: dva prvky jsou ekvivalentní, pokud náleží do stejné množiny v rozkladu $R\,\!$

Označme $E(X)\,\!$ množinu všech možných ekvivalencí na množině $X\,\!$ .

Dá se ukázat, že relace $\subseteq \,\!$ (tj. "být podmnožinou) se chová na množině $E(X)\,\!$ úplně stejně, jako relace $\ll \,\!$ na množině $R(X)\,\!$ , jinými slovy:
Množina $R(X)\,\!$ při uspořádání $\ll \,\!$ je izomorfní s množinou $E(X)\,\!$ při uspořádání $\subseteq \,\!$ .

Příklad množiny všech ekvivalencí

Vraťme se k tříprvkové množině $X=\{1,2,3\}\,\!$ a spočítejme všechny ekvivalence, které na ní lze vytvořit. Žádný div, že jich je zase pět:

$E(X)=\{E_{a},E_{b},E_{c},E_{d},E_{e}\}\,\!$
$E_{a}=\{[1,1],[2,2],[3,3]\}\,\!$
$E_{b}=\{[1,1],[2,2],[3,3],[1,2],[2,1]\}\,\!$
$E_{c}=\{[1,1],[2,2],[3,3],[1,3],[3,1]\}\,\!$
$E_{d}=\{[1,1],[2,2],[3,3],[2,3],[3,2]\}\,\!$
$E_{e}=\{[1,1],[2,2],[3,3],[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]\}\,\!$

Není ani příliš překvapivé, že mezi těmito ekvivalencemi platí stejné vztahy, jako mezi rozklady – tak už to u izomorfních struktur chodí:

$E_{a}\subseteq E_{b}\subseteq E_{e}\,\!$
$E_{a}\subseteq E_{c}\subseteq E_{e}\,\!$
$E_{a}\subseteq E_{d}\subseteq E_{e}\,\!$
$E_{b},E_{c},E_{d}\,\!$ nelze porovnat

Množina všech rozkladů jako úplný svaz

Na závěr ještě podotkněme, že množina všech rozkladů s uspořádáním pomocí zjemnění tvoří algebraickou strukturu nazývanou úplný svaz – lze na ní tedy zavést operace součtu a součinu a s rozklady počítat podobně, jako by to byla čísla.

Podívajte se také na