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
$(\mathrm{\forall }a\in R_1)(\mathrm{\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\},\dots \}$ 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,\dots \},\{1,4,7,\dots \},\{2,5,8,\dots \}\}$), 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\iff (\mathrm{\exists }y\in R)(a\in y\wedge 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.

Související články

• Ekvivalence
• Uspořádání
• Svaz (matematika)
• Úplný svaz