Tento článek je o matematickém pojmu ekvivalence na algebraické struktuře. Další významy jsou uvedeny na stránce 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í definiceEditovat

Předpokládejme, že   je algebraická struktura s množinou prvků   a operacemi  , operace   je  -ární.

Binární relaci   na X nazveme kongruence, pokud je to ekvivalence a pokud pro každou z vyjmenovaných operací a každé prvky   platí

 

PříkladEditovat

Chceme ověřit, zda na grupě celých čísel je relace "  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  ).   je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže  ).

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   lze provést takto: Pro obě i platí  , čili existují celá čísla   tak, že  . Potom platí:  , což je násobek deseti, takže  

Kongruence zbytkových třídEditovat

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

 

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

Vlastnosti kongruence modulo nEditovat

  •  , jinými slovy: relace   je kongruence vzhledem ke sčítání
  •  , jinými slovy: relace   je kongruence vzhledem k odčítání
  •  , jinými slovy: relace   je kongruence vzhledem k násobení

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

  •  

Význam kongruence modulo nEditovat

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.

FaktoralgebraEditovat

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

 

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  ; v článku je však použito označení   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 faktoralgebryEditovat

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  , která se však obvykle značí  , pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla   sudá čísla". Zvolíme tedy nějaké celé číslo   tak, aby   byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například   . Pak výše uvedený vzorec říká:  

Dosazením do pravé strany dostaneme:  

Takže výsledek operace "lichá čísla   sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např.  , dospěli bychom k výsledku  , což je množina totožná s množinou  . 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

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í  . 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í   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ánkyEditovat