Kongruence

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Tento článek pojednává o matematickém pojmu ekvivalence na algebraické struktuře. Další významy jsou uvedeny v článku Kongruence (rozcestník).

Kongruence je algebraický pojem označující ekvivalenci na algebře, která je slučitelná se všemi operacemi na této algebře (tedy například, pokud jsou tři páry prvků ekvivalentní a výsledky nějaké operace na těchto párech jsou také ekvivalentní, pak existuje pro tyto páry kongruence).

Formální definice[editovat | editovat zdroj]

Předpokládejme, že  (X, O_1, O_2, \ldots, O_n) \,\! je algebraická struktura s množinou prvků  X \,\! a operacemi  O_1, O_2, \ldots, O_n \,\! , operace  O_i \,\! je  m_i \,\! -ární.

Binární relaci  R \,\! na X nazveme kongruence, pokud je to ekvivalence a pokud pro každou z vyjmenovaných operací a každé prvky  a_1, a_2, \ldots, a_{m_i}, b_1, b_2, \ldots, b_{m_i} \in X platí

 a_1 \sim_R b_1, a_2 \sim_R b_2, \ldots, a_{m_i} \sim_R b_{m_i} \implies O_i(a_1,a_2,\ldots,a_{m_i}) \sim_R O_i(b_1,b_2,\ldots,b_{m_i}) \,\!

Příklad[editovat | editovat zdroj]

Chceme ověřit, zda na grupě celých čísel je relace "x-y je násobkem deseti" kongruencí. Grupu je možné chápat jako strukturu s jednou operací nebo se třemi. Obě konvence jsou ekvivalentní, použijme tedy tu první: jedinou operací je sčítání (proto n=1). \scriptstyle O_1(a,b) je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže \scriptstyle m_i = 2).

Zvolíme-li a1 = 3, a2 = 5, b1 = 13, b2 = 45, pak podle definice kongruence musí platit 3+5 ~ 13 + 45, což platí (8 a 58 se liší o násobek deseti).

Tím jsme ověřili jen konkrétní příklad; důkaz platný pro všechny hodnoty a_i a b_i lze provést takto: Pro obě i platí \scriptstyle a_i \sim_R b_i\,\!, čili existují celá čísla \scriptstyle k_1, k_2\,\! tak, že \scriptstyle b_i = a_i + 10.k_i. Potom platí: \scriptstyle O_1(a_1,a_2) - O_1(b_1,b_2) = a_1 + a_2 - (a_1 + 10.k_1) - (a_2 + 10.k_2) =  -10.(k_1+k_2), což je násobek deseti, takže \scriptstyle O_1(a_1,a_2) \sim_R O_2(b_1,b_2)

Kongruence zbytkových tříd[editovat | editovat zdroj]

Nejznámějším příkladem kongruence je rozklad množiny všech celých čísel na zbytkové třídy po dělení číslem  n \geq 2 \,\! , tj. relace, která je zavedena vztahem:

 a \equiv b \pmod n \Leftrightarrow n \mid (b-a) \,\!

Jinými slovy: dvě čísla jsou ekvivalentní (modulo n), pokud mají stejný zbytek po dělení číslem  n \,\! . Pokud je z kontextu jasné, pro které  n \,\! je kongruence zapsána (nebo na  n \,\! nezáleží, protože zápis je platný pro jeho libovolnou hodnotu), vynechává se konec zápisu a píše se prostě  a \equiv b \,\! . Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n[editovat | editovat zdroj]

  •  a \equiv b \and c \equiv d \implies a+c \equiv b+d \,\! , jinými slovy: relace  \equiv \,\! je kongruence vzhledem ke sčítání
  •  a \equiv b \and c \equiv d \implies a-c \equiv b-d \,\! , jinými slovy: relace  \equiv \,\! je kongruence vzhledem k odčítání
  •  a \equiv b \and c \equiv d \implies a*c \equiv b*d \,\! , jinými slovy: relace  \equiv \,\! je kongruence vzhledem k násobení

Je-li navíc  n \,\! prvočíslo, pak navíc podle Malé Fermatovy věty:

  • a^n \equiv a \pmod n \,\!

Význam kongruence modulo n[editovat | editovat zdroj]

Vlastnosti kongruence modulo n umožňují počítat pouze se zbytkovými třídami a výsledek pak zobecnit na všechna čísla - v takovýchto výpočtech zastupuje například číslo 3 v modulu 5 všechna čísla s ním kongruentní - 8,13,18,…, ale také -2,-7,… Kongruenci lze při výpočtech týkajících se dělitelnosti do jisté míry používat podobně jako rovnost při úpravách algebraických výrazů nebo při řešení rovnice.

Faktoralgebra[editovat | editovat zdroj]

Je-li R kongruence, pak faktormnožině X / R může být dána přirozená struktura takto (výsledek nezávisí na volbě reprezentantů):

 \hat{O_i}([x_1]_R, [x_2]_R, \ldots, [x_{m_i}]_R) = [O_i(x_1, x_2, \ldots, x_{m_i})]_R

Faktormnožina s těmito operacemi se nazývá faktoralgebra a její operace se obvykle značí stejně, jako operace původní algebry (v tomto případě tedy O_i \,\!; v článku je však použito označení  \hat{O_i} pro zdůraznění, že se nejedná o tutéž operaci).

Toto je nejběžnější způsob, jak formálně definovat okruh modulo n.

Příklad faktoralgebry[editovat | editovat zdroj]

Na okruhu celých čísel uvažujme kongruenci "x-y je sudé číslo". Faktormnožina bude mít dva prvky: množina sudých celých čísel a množina lichých celých čísel . Na této faktormnožině lze přirozeně zavést operaci \scriptstyle \hat{+}, která se však obvykle značí \scriptstyle +, pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla \scriptstyle \hat{+} sudá čísla". Zvolíme tedy nějaké celé číslo \scriptstyle [x_1] tak, aby \scriptstyle [x_1]_R byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například \scriptstyle x_1 = 11, x_2 = 8 . Pak výše uvedený vzorec říká: \scriptstyle [x_1]_R \hat{+} [x_2]_R = [x_1 + x_2]_R

Dosazením do pravé strany dostaneme: \scriptstyle [x_1]_R \hat{+} [x_2]_R = [x_1 + x_2]_R = [11 + 8]_R = [19]_R

Takže výsledek operace "lichá čísla \scriptstyle \hat{+} sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např. \scriptstyle x_1 = 41, x_2 = 42, dospěli bychom k výsledku \scriptstyle [83]_R, což je množina totožná s množinou \scriptstyle [19]_R. To je ilustrací (nikoli však důkazem), že výsledek je nezávislý na volbě reprezentantů. Kdyby nezávislý nebyl, pak by definice byla nekorektní.

Vztah kongruence a homomorfismů[editovat | editovat zdroj]

Binární relace na A je kongruencí právě tehdy, pokud je jádrem nějakého homomorfismu z A do nějaké struktury B.

Pro každý homomorfismus f z A do B platí, že jádro homomorfismu Ker f je kongruence na A. (Pojem jádro homomorfismu je někdy chápán jako podstruktura A, ale zde se držíme obecnější definice, že jde o relaci na A.) Proto každý homomorfismus definuje faktoralgebru. Podle první věty o izomorfismu je tato faktoralgebra izomorfní s oborem hodnot f.

Platí i opačný vztah: Každá kongruence R je jádrem nějakého homomorfismu. Příkladem takového homomorfismu je zobrazení f(x): A \to A / R, f(x) = [x]_R . V příkladě níže toto zobrazení jakémukoli lichému číslu (např. 3) přiřadí množinu všech lichých čísel a sudému číslu množinu všech sudých čísel. Nejedná se o izomorfismus, neboť zobrazení není prosté .

Příklad: Zobrazení  f: Z \to Z, f(n) = (-1)^n přiřadí každému sudému číslu hodnotu 1 a lichému číslu -1. Jádrem tohoto zobrazení je právě výše zmíněná relace "x-y je sudé číslo". Faktoralgebra i obor hodnot jsou dvouprvkové množiny. Izomorfismus mezi nimi přiřadí množině všech sudých čísel hodnotu 1 a množině všech lichých čísel -1. Tento izomorfismus není totožný se zobrazením f, neboť jeho argumentem jsou množiny čísel, zatímco argumentem f jsou čísla.

Související články[editovat | editovat zdroj]