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.

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

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

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

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

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

Dá se poměrně snadno ověřit, že relace ${\displaystyle \ll \,\!}$ je neostré uspořádání množiny ${\displaystyle R(X)\,\!}$ všech možných rozkladů množiny ${\displaystyle 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 ${\displaystyle R_{2}\ll R_{3}\,\!}$, ani ${\displaystyle R_{3}\ll R_{2}\,\!}$.

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

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

Je vidět, že

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

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

Je-li ${\displaystyle R\,\!}$ rozklad a ${\displaystyle \sim _{R}\,\!}$ jemu odpovídající ekvivalence, potom R je shodný s množinou tříd ekvivalence ${\displaystyle \sim _{R}\,\!}$ a naopak – ${\displaystyle \sim _{R}\,\!}$ lze definovat pomocí rozkladu ${\displaystyle R\,\!}$ takto:
${\displaystyle 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 ${\displaystyle R\,\!}$

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

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

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

• ${\displaystyle E(X)=\{E_{a},E_{b},E_{c},E_{d},E_{e}\}\,\!}$
• ${\displaystyle E_{a}=\{[1,1],[2,2],[3,3]\}\,\!}$
• ${\displaystyle E_{b}=\{[1,1],[2,2],[3,3],[1,2],[2,1]\}\,\!}$
• ${\displaystyle E_{c}=\{[1,1],[2,2],[3,3],[1,3],[3,1]\}\,\!}$
• ${\displaystyle E_{d}=\{[1,1],[2,2],[3,3],[2,3],[3,2]\}\,\!}$
• ${\displaystyle 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í:

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

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.

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