Relacja kongruencji

Aby zapoznać się z terminem używanym w geometrii elementarnej, zobacz kongruencja (geometria) .

W algebrze abstrakcyjnej relacja kongruencji (lub po prostu kongruencja ) jest relacją równoważności na strukturze algebraicznej (takiej jak grupa , pierścień lub przestrzeń wektorowa ), która jest zgodna ze strukturą w tym sensie, że operacje algebraiczne wykonane z równoważnymi elementami dadzą równoważne elementy. Każda relacja kongruencji ma odpowiednią ilorazową , której elementami są klasy równoważności (lub klasy kongruencji ) dla relacji.

Podstawowy przykład

Ta sekcja dotyczy notacji (mod n ) . Informacje na temat binarnej mod można znaleźć w sekcji Operacja modulo .

Prototypowym przykładem relacji kongruencji jest kongruencja modulo $liczb$ zbiorze całkowitych . Dla danej dodatniej liczby całkowitej ${$$i$ całkowite b $\ displaystyle b}$ nazywane są kongruentnymi modulo $\ displaystyle n}$ , zapisane

$n}}}$

jeśli jest $)$ przez (lub równoważnie, jeśli i $taką$$\ displaystyle a}$$mają$ samą resztę z dzielenia przez $n}$ .

Na przykład ${\ Displaystyle 37}$ i ${\ Displaystyle 57}$ są przystające modulo ${\ Displaystyle 10}$ ,

${\ Displaystyle 37 \ równoważnik 57 {\ pmmod {10}}}$

ponieważ ${\ Displaystyle 37-57 = -20}$ jest wielokrotnością 10 lub równoważnie, ponieważ zarówno ${\ Displaystyle 37},$ jak i ${\ Displaystyle 57}$ mają resztę ${\ Displaystyle 7}$ po podzieleniu przez ${\ displaystyle 10}$ .

Kongruencja modulo $)$ dla ustalonego $jest$ zgodna zarówno z dodawaniem , jak i mnożeniem liczb całkowitych To jest,

Jeśli

${\ Displaystyle a_ {1} \ równoważnik a_ {2} {\ pmod {n}}}$ i ${\ Displaystyle b_ {1} \ równoważnik b_ {2}{\pmod {n}}}$

Następnie

${\ Displaystyle a_ {1} + b_ {1} \ równoważnik a_ {2} + b_ {2} {\ pmod {n}}}$ i ${\ Displaystyle a_ {1} b_ {1} \ równoważnik a_ {2} b_ {2} {\ pmod {n}}}$

Odpowiednie dodawanie i mnożenie klas równoważności jest znane jako arytmetyka modularna . Z punktu widzenia algebry abstrakcyjnej kongruencja modulo $jest$ kongruencji na pierścieniu liczb całkowitych, a modulo arytmetyczne $ilorazowym$ na odpowiednim pierścieniu .

Definicja

Definicja kongruencji zależy od rodzaju rozważanej struktury algebraicznej . Konkretne definicje kongruencji można tworzyć dla grup , pierścieni , przestrzeni wektorowych , modułów , półgrup , krat i tak dalej. Wspólnym tematem jest to, że kongruencja jest relacją równoważności na obiekcie algebraicznym, która jest zgodna ze strukturą algebraiczną, w tym sensie, że operacje na klasach równoważności są dobrze zdefiniowane .

Przykład: Grupy

Na przykład grupa jest obiektem algebraicznym składającym się ze zbioru wraz z pojedynczą operacją binarną , spełniającą określone aksjomaty. Jeśli $grupą$ z operacją $relacją$ relacja $}$ na jest równoważności $G$ elementach sol $}$$displaystyle$ satysfakcjonujące

${\ Displaystyle g_ {1} \ równoważnik g_ {2} \ \ \,}$ i ${\ Displaystyle \ \ \, h_ { 1}\równoważnik h_{2}\implikuje g_{1}\ast h_{1}\równoważnik g_{2}\ast h_{2}}$

dla wszystkich ${\ Displaystyle g_ {1}, g_ {2}, h_ {1}, h_ {2} \ w G}$ . Dla kongruencji na grupie klasa równoważności zawierająca element identyczności jest zawsze podgrupą normalną , a inne klasy równoważności są innymi kozbiorami tej podgrupy. Razem te klasy równoważności są elementami grupy ilorazowej .

Przykład: pierścienie

Gdy struktura algebraiczna obejmuje więcej niż jedną operację, wymagane jest, aby relacje kongruencji były zgodne z każdą operacją. Na przykład pierścień posiada zarówno dodawanie, jak i mnożenie, a relacja kongruencji na pierścieniu musi spełniać

${\ Displaystyle r_ {1} + s_ {1} \ równoważnik r_ {2} + s_ {2}}$ i ${\ displaystyle r_ { 1}s_{1}\odpowiednik r_{2}s_{2}}$

ilekroć ${\ displaystyle r_ {1} \ równoważnik r_ {2}}$ i ${\ displaystyle s_ {1} \ równoważny s_ {2}}$ . W przypadku kongruencji na pierścieniu klasa równoważności zawierająca 0 jest zawsze ideałem dwustronnym , a dwie operacje na zbiorze klas równoważności definiują odpowiedni pierścień ilorazowy.

Ogólny

Ogólne pojęcie relacji kongruencji można formalnie zdefiniować w kontekście algebry uniwersalnej , dziedziny, która bada idee wspólne dla wszystkich struktur algebraicznych . W tym ustawieniu relacja na danej strukturze algebraicznej nazywana $jest$ zgodną ​​jeśli

dla każdej operacji $displaystyle n} a'_ {1}}$ na strukturze: za $i$$n$$}$ każdej operacji zdefiniowanej na i ... i ${\ Displaystyle a_ {n} \ mathrel {R} a'_ {n}}$ , wtedy ${\ Displaystyle \ mu (a_ {1}, \ ldots, a_ {n}) \ mathrel {R} \ mu (a'_ {1}, \ ldots, za '_{n})}$ .

Relacja kongruencji w strukturze jest wówczas definiowana jako relacja równoważności, która jest również kompatybilna.

Związek z homomorfizmami

Jeśli jest homomorfizmem między dwiema strukturami algebraicznymi (takimi jak homomorfizm grup lub liniowa mapa między przestrzeniami wektorowymi ), to relacja $\ rightarrow B}$${\ Displaystyle f: A \$ określony przez

${\ Displaystyle a_ {1} \, R \, a_ {2}}$ wtedy i tylko wtedy, gdy ${\ Displaystyle f (a_ {1}) = f ( a_{2})}$

jest relacją kongruencji na ${\ displaystyle A}$ . Zgodnie z pierwszym twierdzeniem o izomorfizmie obraz A pod jest podstrukturą B izomorficzną z ilorazem A przez $kongruencję$ .

$}$ drugiej strony, relacja kongruencji wyjątkowy określony $R$

${\ Displaystyle f (x) = \ {y \ mid x \, R \, y \}}$ .

Istnieje zatem naturalna zgodność między kongruencjami a homomorfizmami dowolnej danej struktury algebraicznej.

Kongruencje grup, normalne podgrupy i ideały

W szczególnym przypadku grup , relacje kongruencji można opisać elementarnie w następujący sposób: Jeżeli G jest grupą (z elementem tożsamości e i działaniem *) i ~ jest relacją binarną na G , to ~ jest kongruencją zawsze wtedy, gdy:

1. Biorąc pod uwagę dowolny element a z G , a ~ a ( zwrotność );
2. uwagę dowolne elementy aib z G , jeśli a ~ b , to b ~ a ( symetria ) ;
3. Biorąc pod uwagę dowolne elementy a , b i c z G , jeśli a ~ b i b ~ c , to a ~ c ( przechodniość );
4. Biorąc pod uwagę dowolne elementy a , a' , b i b' z G , jeśli a ~ a' i b ~ b' , to a * b ~ a' * b' ;
5. Biorąc pod uwagę dowolne elementy a i a' z G , jeśli a ~ a' , to a ⁻¹ ~ a' ⁻¹ (można to faktycznie udowodnić na podstawie pozostałych czterech, , więc jest to całkowicie zbędne).

Warunki 1, 2 i 3 mówią, że ~ jest relacją równoważności .

Kongruencja ~ jest całkowicie określona przez zbiór { a ∈ G : a ~ e } tych elementów G , które są przystające do elementu tożsamości, a zbiór ten jest podgrupą normalną . W szczególności a ~ b wtedy i tylko wtedy, gdy b ⁻¹ * a ~ e . Więc zamiast mówić o kongruencjach w grupach, ludzie zwykle mówią o ich normalnych podgrupach; w rzeczywistości każda kongruencja odpowiada jednoznacznie jakiejś normalnej podgrupie G .

Ideały pierścieni i przypadek ogólny

Podobna sztuczka pozwala mówić o jądrach w teorii pierścieni jako ideałach zamiast relacji kongruencji, aw teorii modułów jako podmodułach zamiast relacji kongruencji.

Bardziej ogólna sytuacja, w której ta sztuczka jest możliwa, dotyczy grup Omega (w ogólnym sensie pozwalając operatorom z wieloma liczbami). Ale nie można tego zrobić na przykład z monoidami , więc badanie relacji kongruencji odgrywa bardziej centralną rolę w teorii monoidów.

Algebra uniwersalna

Ogólne pojęcie kongruencji jest szczególnie przydatne w algebrze uniwersalnej . Równoważne sformułowanie w tym kontekście jest następujące:

na algebrze A jest podzbiorem iloczynu bezpośredniego A × A , który jest zarówno relacją równoważności na A , jak i podalgebrą A × A .

Jądrem homomorfizmu jest zawsze kongruencja. Rzeczywiście, każda kongruencja powstaje jako jądro. Dla danej kongruencji na A , zbiorowi A /~ klas równoważności można w naturalny sposób nadać strukturę algebry, algebry ilorazowej . Funkcją, która odwzorowuje każdy element A na jego klasę równoważności, jest homomorfizm, a jądro tego homomorfizmu to ~.

Krata Con ( A ) wszystkich relacji kongruencji na algebrze A jest algebraiczna .

John M. Howie opisał, jak teoria półgrup ilustruje relacje kongruencji w algebrze uniwersalnej:

W grupie kongruencja jest określana, jeśli znamy pojedynczą klasę kongruencji, w szczególności, jeśli znamy podgrupę normalną, która jest klasą zawierającą tożsamość. Podobnie w pierścieniu kongruencja jest określana, jeśli znamy ideał, którym jest klasa kongruencji zawierająca zero. W półgrupach nie ma takiego szczęśliwego zdarzenia i dlatego stajemy przed koniecznością badania kongruencji jako takiej. Bardziej niż cokolwiek innego, to właśnie ta konieczność nadaje teorii półgrup jej charakterystyczny smak. Półgrupy są w rzeczywistości pierwszym i najprostszym typem algebry, do którego należy zastosować metody algebry uniwersalnej…

Zobacz też

• Chińskie twierdzenie o resztach
• Problem kraty kongruencji
• Tabela kongruencji

Notatki

•   Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2 . (Sekcja 4.5 omawia kongruencję macierzy).
•   Rosen, Kenneth H (2012). Matematyka dyskretna i jej zastosowania . Edukacja McGraw-Hill. ISBN 978-0077418939 .