Kongruensforhold - Congruence relation

I abstrakt algebra er en kongruensforhold (eller ganske enkelt kongruens ) en ekvivalensrelasjon på en algebraisk struktur (for eksempel en gruppe , ring eller vektorrom ) som er kompatibel med strukturen i den forstand at algebraiske operasjoner utført med likeverdige elementer vil gi tilsvarende elementer. Hver kongruensforhold har en tilsvarende kvotientstruktur , hvis elementer er ekvivalensklassene (eller kongruensklassene ) for relasjonen.

Grunnleggende eksempel

Det prototypiske eksemplet på en kongruensforhold er kongruensmodulo${\ displaystyle n}$ på settet med heltall . For et gitt positivt heltall , to heltall og kalles kongruent modulo , skrevet ${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle n}$

${\ displaystyle a \ equiv b {\ pmod {n}}}$

hvis er delelig med (eller tilsvarende hvis og har den samme resten når den deles med ). ${\ displaystyle ab}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle n}$

For eksempel, og er kongruente modulo , ${\ displaystyle 37}$${\ displaystyle 57}$${\ displaystyle 10}$

${\ displaystyle 37 \ equiv 57 {\ pmod {10}}}$

siden er et multiplum av 10, eller tilsvarende siden begge og har resten av når det deles med . ${\ displaystyle 37-57 = -20}$${\ displaystyle 37}$${\ displaystyle 57}$${\ displaystyle 7}$${\ displaystyle 10}$

Congruence modulo (for en fast ) er kompatibel med både addisjon og multiplikasjon på heltallene. Det er, ${\ displaystyle n}$${\ displaystyle n}$

hvis

${\ displaystyle a_ {1} \ equiv a_ {2} {\ pmod {n}}}$ og ${\ displaystyle b_ {1} \ equiv b_ {2} {\ pmod {n}}}$

deretter

${\ displaystyle a_ {1}+b_ {1} \ equiv a_ {2}+b_ {2} {\ pmod {n}}}$ og ${\ displaystyle a_ {1} b_ {1} \ equiv a_ {2} b_ {2} {\ pmod {n}}}$

Den tilsvarende tillegg og multiplikasjon av ekvivalensklasser er kjent som modulær aritmetikk . Fra synspunktet til abstrakt algebra er kongruensmodul et kongruensforhold på ringen av heltall, og aritmetisk modulo forekommer på den tilsvarende kvotientringen . ${\ displaystyle n}$${\ displaystyle n}$

Definisjon

Definisjonen av kongruens avhenger av hvilken type algebraisk struktur som vurderes. Spesielle definisjoner av kongruens kan gjøres for grupper , ringer , vektorrom , moduler , semigrupper , gitter og så videre. Det vanlige temaet er at en kongruens er et ekvivalensforhold på et algebraisk objekt som er kompatibelt med den algebraiske strukturen, i den forstand at operasjonene er veldefinerte på ekvivalensklassene .

Eksempel: Grupper

For eksempel er en gruppe et algebraisk objekt som består av et sett sammen med en enkelt binær operasjon , som tilfredsstiller visse aksiomer. Hvis er en gruppe med operasjon , er en kongruensforhold på en ekvivalensrelasjon på elementene tilfredsstillende ${\ displaystyle G}$${\ displaystyle \ ast}$${\ displaystyle G}$${\ displaystyle \ equiv}$${\ displaystyle G}$

${\ displaystyle g_ {1} \ equiv g_ {2} \ \ \,}$ og ${\ displaystyle \ \ \, h_ {1} \ equiv h_ {2} \ innebærer g_ {1} \ ast h_ {1} \ equiv g_ {2} \ ast h_ {2}}$

for alle . For en kongruens på en gruppe er ekvivalensklassen som inneholder identitetselementet alltid en normal undergruppe , og de andre ekvivalensklassene er cosets av denne undergruppen. Til sammen er disse ekvivalensklassene elementene i en kvotiegruppe . ${\ displaystyle g_ {1}, g_ {2}, h_ {1}, h_ {2} \ i G}$

Eksempel: Ringer

Når en algebraisk struktur inkluderer mer enn én operasjon, må kongruensforhold være kompatible med hver operasjon. For eksempel har en ring både addisjon og multiplikasjon, og et kongruensforhold på en ring må tilfredsstille

${\ displaystyle r_ {1}+s_ {1} \ equiv r_ {2}+s_ {2}}$ og ${\ displaystyle r_ {1} s_ {1} \ equiv r_ {2} s_ {2}}$

når som helst og . For kongruens på en ring er ekvivalensklassen som inneholder 0 alltid et tosidig ideal , og de to operasjonene på settet med ekvivalensklasser definerer den tilsvarende kvotieringen. ${\ displaystyle r_ {1} \ equiv r_ {2}}$${\ displaystyle s_ {1} \ equiv s_ {2}}$

Generell

Den generelle oppfatningen om kongruensforhold kan formelt defineres i sammenheng med universell algebra , et felt som studerer ideer som er felles for alle algebraiske strukturer . I denne innstillingen kalles en relasjon til en gitt algebraisk struktur kompatibel hvis ${\ displaystyle R}$

for hver og hver -ary operasjon er definert på følgende strukturformel: når og ... og , så .${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle \ mu}$${\ displaystyle a_ {1} \ mathrel {R} a '_ {1}}$${\ displaystyle a_ {n} \ mathrel {R} a '_ {n}}$${\ displaystyle \ mu (a_ {1}, \ ldots, a_ {n}) \ mathrel {R} \ mu (a '_ {1}, \ ldots, a' _ {n})}$

En kongruensforhold på strukturen blir deretter definert som et ekvivalensforhold som også er kompatibelt.

Forholdet til homomorfismer

Hvis er en homomorfisme mellom to algebraiske strukturer (for eksempel homomorfisme av grupper eller et lineært kart mellom vektorrom ), så er forholdet definert av ${\ displaystyle f: A \, \ høyre pil B}$${\ displaystyle R}$

${\ displaystyle a_ {1} \, R \, a_ {2}}$ hvis og bare hvis ${\ displaystyle f (a_ {1}) = f (a_ {2})}$

er en kongruensforhold på . Ved den første isomorfismens teorem er bildet av A under en understruktur av B -isomorf til kvotienten A ved denne kongruensen. ${\ displaystyle A}$${\ displaystyle f}$

På den annen side induserer forholdet en unik homomorfisme gitt av ${\ displaystyle R}$${\ displaystyle f: A \ høyre pil A/R}$

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

Dermed er det en naturlig samsvar mellom kongruensene og homomorfismene til en gitt struktur.

Kongresser av grupper, og normale undergrupper og idealer

I det spesielle tilfellet med grupper kan kongruensforhold beskrives i elementære termer som følger: Hvis G er en gruppe (med identitetselement e og operasjon *) og ~ er en binær relasjon til G , så er ~ en kongruens når som helst:

1. Gitt et element a av G , a ~ a ( refleksivitet );
2. Gitt alle elementene a og b i G , hvis a ~ b , så b ~ a ( symmetri );
3. Gitt alle elementene a , b og c i G , hvis a ~ b og b ~ c , så a ~ c ( transitivitet );
4. Gitt alle elementene a , a ' , b og b' i G , hvis a ~ a ' og b ~ b' , så a * b ~ a ' * b' ;
5. Gitt alle elementer en og en ' av G , hvis en ~ a' , da en ^-1 ~ a' ^-1 (dette kan faktisk bli påvist fra de andre fire, så er strengt tatt overflødig).

Betingelser 1, 2 og 3 sier at ~ er et ekvivalensforhold .

En kongruens ~ bestemmes helt av settet { a ∈ G  : a ~ e } av elementene i G som er kongruente med identitetselementet, og dette settet er en normal undergruppe . Spesielt a ~ b hvis og bare hvis b ⁻¹ * a ~ e . Så i stedet for å snakke om kongruenser på grupper, snakker folk vanligvis i form av normale undergrupper av dem; faktisk, tilsvarer hver kongruens unikt til noen normal undergruppe av G .

Idéer om ringer og den generelle saken

Et lignende triks lar en snakke om kjerner i ringteorien som idealer i stedet for kongruensforhold, og i modulteori som submoduler i stedet for kongruensforhold.

En mer generell situasjon hvor dette trikset er mulig er med Omega-grupper (i generell forstand tillater operatører med flere arity). Men dette kan ikke gjøres med for eksempel monoider , så studiet av kongruensforhold spiller en mer sentral rolle i monoidteorien.

Universell algebra

Den generelle oppfatningen om kongruens er spesielt nyttig i universell algebra . En tilsvarende formulering i denne sammenhengen er følgende:

En kongruens forhold på en algebra A er et delsett av det direkte produkt A x A som er både en ekvivalent forhold på A og en subalgebra av A x A .

Den kjernen av en homomorfi er alltid en kongruens. Hver kongruens oppstår faktisk som en kjerne. For en gitt kongruens ~ på A kan settet A /~ for ekvivalensklasser gis strukturen til en algebra på en naturlig måte, kvotientalgebraen . Funksjonen som tilordner hvert element i A til sin ekvivalensklasse er en homomorfisme, og kjernen til denne homomorfismen er ~.

Den gitter Con ( A ) av alle kongruenslikninger relasjoner på en algebra A er algebraisk .

John M. Howie beskrev hvordan semigruppeteori illustrerer kongruensforhold i universell algebra:

I en gruppe bestemmes en kongruens hvis vi kjenner en enkelt kongruensklasse, spesielt hvis vi kjenner den normale undergruppen som er klassen som inneholder identiteten. På samme måte bestemmes en kongruens i en ring hvis vi kjenner idealet som er kongruensklassen som inneholder null. I semigrupper er det ingen slik heldig forekomst, og vi står derfor overfor nødvendigheten av å studere kongruenser som sådan. Mer enn noe annet er det denne nødvendigheten som gir semigruppeteorien sin karakteristiske smak. Semigrupper er faktisk den første og enkleste typen algebra som metodene for universell algebra må brukes på ...

Se også

• Tabell over kongruenser
• Lineær kongruenssetning
• Kongruensgitterproblem

Merknader

Referanser

• Horn og Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN  0-521-38632-2 . (Del 4.5 diskuterer kongruens av matriser.)
• Rosen, Kenneth H (2012). Diskret matematikk og dens anvendelser . McGraw-Hill Education. ISBN 978-0077418939.