Izomorfismus

Z Wikipedie, otevřené encyklopedie

Izomorfismus je matematický pojem z oboru algebry a teorie množin, který představuje určité zobrazení mezi dvěma množinami, pomocí kterého můžeme mezi nimi beze ztráty jakékoliv informace libovolně přecházet. Jinými slovy, každému prvku množiny jedné odpovídá právě jeden prvek množiny druhé a to včetně zachování veškerých jeho strukturálních vlastností (vztahů k ostatním prvkům). Pokud takové zobrazení existuje (tedy jsou množiny izomorfní), je tedy laicky řečeno jedno, ve které množině momentálně pracujeme, a můžeme kdykoliv přestoupit do té druhé.

[editovat] Definice

Předpokládejme, že na množině $X \,\!$ jsou definovány relace $R_1, R_2, \ldots , R_n \,\!$ a na množině $Y \,\!$ jsou definovány relace $S_1, S_2, \ldots , S_n \,\!$ . Řekneme, že zobrazení $F \,\!$ je izomorfismus mezi $X \,\!$ a $Y \,\!$ vzhledem k relacím $R_1, R_2, \ldots , R_n \,\!$ a $S_1, S_2, \ldots , S_n \,\!$ , pokud platí:

$F \,\!$ je vzájemně jednoznačné zobrazení mezi $X \,\!$ a $Y \,\!$
pokud jsou $R_i, S_i \,\!$ j-ární relace, potom $(\forall x_1,x_2,\ldots,x_j) ([x_1,x_2,\ldots,x_j] \isin R_i \Leftrightarrow ([F(x_1),F(x_2),\ldots,F(x_j)] \isin S_i \,\!$ .

Řekneme, že struktury $X, R_1, R_2, \ldots , R_n \,\!$ a $Y, S_1, S_2, \ldots , S_n \,\!$ jsou izomorfní, pokud mezi nimi existuje nějaký izomorfismus ve smyslu výše uvedené definice.

[editovat] Význam definice

I když vypadá definice hrozivě a nepřehledně, zachycuje přesně to, co je řečeno v úvodním přiblížení:

V rámci izomorfismu se nesmí žádné prvky ztrácet ani objevovat, obě množiny musí mít stejný počet prvků (v případě nekonečných množin stejnou mohutnost).
Izomorfismus musí zachovávat všechny vztahy, tj. relace - pokud jsou v původní množině nějaké prvky v nějakém vztahu, musí být v nové množině také v odpovídajícím vztahu a naopak.

[editovat] Uspořádané množiny

Uvažujme o množinách $X, Y \,\!$ , které mají uspořádání $R, S \,\!$ . Izomorfismus v tomto případě znamená, že pokud je $a,b \isin X, a \leq_R b \,\!$ , pak musí být $F(a) \leq_S F(b) \,\!$ .

Dá se snadno ukázat, že v izomorfismu se musí nejmenší prvek zobrazit opět na nejmenší prvek, infimum na infimum, minimální prvek na minimální prvek…

Množina všech přirozených čísel a množina všech sudých čísel jsou izomorfní vzhledem k uspořádání podle velikosti podle funkce $F(x) = 2.x \,\!$ .
Pro množiny všech přirozených čísel a všech celých čísel neexistuje izomorfismus - přirozená čísla mají nejmenší prvek 0, ale celá čísla žádný nemají.

[editovat] Algebraický izomorfismus

V algebře izomorfismem mezi dvěma algebrami rozumíme bijektivní homomorfismus, tedy zobrazení slučitelné se všemi operacemi na algebře, které je zároveň bijekcí (každému prvku z jedné množiny přiřadí právě jeden prvek z druhé).

Opět se jedná o zvláštní případ výše uvedené definice - uvědommne si, že operace není nic jiného, než konkrétní typ relace.

Dá se snadno ukázat, že v izomorfismu se musí neutrální prvek operace zobrazit na neutrální prvek jí odpovídající operace v druhé množině, obdobně například inverzní prvek opět na inverzní prvek.

Algebry zbytkových tříd po dělení sedmi a zbytkových tříd po dělení devíti nejsou izomorfní - to vyplývá z faktu, že nemají stejný počet prvků, takže mezi nimi neexistuje žádné vzájemně jednoznačné zobrazení.
Dvouprvková Booleova algebra s běžnými logickými operacemi konjunkce, disjunkce a negace $\and, \vee, \neg \,\!$ je izomorfní s dvouprvkovou množinou $X = \{ \emptyset, \{ \emptyset \} \} \,\!$ s množinovými operacemi sjednocení, průniku a doplňku $\cap, \cup, neg(a)$ , kde $neg(a) = X - a \,\!$ .

[editovat] Izomorfismus na grafech

V teorii grafů řekneme, že dva grafy jsou izomorfní, pokud $\exists\ F\colon V(G) \to V(G'): \{x,y\} \in E(G) \Leftrightarrow \{f(x),f(y)\} \in E(G')$ .

Graf je opět jedním z příkladů množiny (vrcholů) a nějaké relace (množiny hran) na této množině, proto se opět jedná o zvláštní případ obecné definice.

I u grafů zachovává izomorfismus všechny důležité vlastnosti grafu - zobrazuje každý podgraf na izomorfní podgraf, cestu opět na cestu, kružnici opět na kružnici, izomorfní graf lze obarvit stejným způsobem, jako původní graf.