; TeX output 1995.11.06:1345Z'nMK`y cmr1090d[*'nMdMj&XQ cmr12KAPITELISIIQY-Nff cmbx12AlgebraischeffGrundstrukturen-F,N cmbx121.WHalbgrupp`en,MonoideundGruppen#XWir\habSenindenerstenbeidenKapitelngewisseGesetzekren-nengelernrt,wieetwadasAssoziativgesetzoSderdasKommuta-tivgesetz,]die[bSeisounrterschiedlichen[Strukturen,wiederMen-genalgebraoSderderAdditionbzw.OMultiplikXationvronZahleneineRollespielen.IndiesemKapitelwrerdendieallgemeinenEigenscrhaftensolcherGesetzestudiert.#Wirwerdensehen,#dadieseGesetzeinsehrvielenmathematiscrhenObjektenauftretenund8dasieaucrhbSeiStrukturen,8diefyurdieInformatikwicrhtigsind,eineganzwresentlicheRollespielen.De nition1.1.sSei'g cmmi12GeineMenge. Eine(binyare)4@ cmti12OpfferationoSderVerkn'yupfung\VinGisteineAbbildung q:ʏGZ(!", cmsy10G !G.\DasBild3 ((a;b))einesPraares(a;b)i2GKG3wirdjenacrhKontextbSezeicrhnetmitc_ab;a+b;ab;a\b;a[b;ab;d.h.stattdesvrorangestelltenFVunktionszeichens(Prya xqnotationoSderumgekehrtepffolnischeNotation) ((a;b))oSdereinfacrh (a;b)vrerwendetmangewyohnlicrheinzwischendiezweiArgumentean91\'nM92S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MundKbgestelltesFVunktionszeicrhen(In xqnotation).L Einnachge-stelltes:JFVunktionszeicrhen,:z.B.ab+,wirdaucrhPost xqnotationoSderpffolnische35Notationgenannrt.De nition1.2.sSeiop:GGop3(a;b)7!abop2GeineOpSera-tion.FSyurdieOpSerationgiltdas=)ו(1)=AssoziativJgesetz:q()UR8a;b;c2G[(a9b)c=a(bc)]:&(22cmmi8l!)=Gesetz]vromlinksneutrffalenElement:()9el2G8a2=G[elpaUR=a];%E3(2rb)=GesetzvromrffechtsneutralenܜElement:()9er !h2G8a2=G[aer=URa];&(3l!)=Gesetzvromlinksinversen0UElement(fallseinlinksneutrales=Elemenrtel pexistiert):()8aUR2G9a2K cmsy80#2G[a20xa=el!];%E3(3rb)=Gesetz4vromrffechtsinversenElement4(fallseinrechtsneu-=tralesElemenrter& existiert):()8aUR2G9a20N920q2G[aa20N920==erb];)ו(4)=KommutativJgesetz:()8a;bUR2G[abUR=ba]:PpxUbung:'FVormrulieren$SiedasAssoziativgesetzinPost xnotation.WVarumwrerdendabSeikeineKlammernbSenyotigt?DasjAssoziativgesetzkXannnatSyurlicrhauchbSeimehralsdreiFVak-torenxeingesetztwrerdenundgestattetauchdannbSeliebigesUm-klammern.%DaskXannaucrhformalbSewiesenwerden.%MankXanndaherbSeiderProduktbildungdieKlammernvyolligfortlassen.De nition1.3.sEineMengeGzusammenmiteinerOpSeration n:URGG !Gheit=)ו(1)=Halbffgruppe:()(1)gilt;)ו(2)=Monoid:()(1),(2l!)und(2rb)gelten;)ו(3)=Gruppffe:()(1),(2l!),(2rb),(3l)und(3rb)gelten;)ו(4)=kommutative sHoSderabffelscheGruppe:()(1),(2),(3)=und(4)gelten.Beispiele1.4.la)( msbm10N;+)isteineHalbgruppSe,+aberkreinMonoid.b)(N;)isteinMonoid,abSerkreineGruppe.]'nMJö1.UUHALBGRUPPEN,MONOIDEUNDGRUPPEN&93d&Mc)DieMengeGUR:=Abb2k(M;M@)derAbbildungenvronM*insichzusammenmitderKompSositionvronAbbildungenisteinMo-noid,abSerkreineGruppe.d)frDieMengederbijektivrenAbbildungenf#:f1;:::ʚ;ng 1!f1;:::ʚ;ngwirdmitderKompSositionvronAbbildungenwegenI. 2.22eineGruppSeSnP,Tdiesogenannrtesymmetrische? GruppffeoSderPermutationsgruppffe.e)(Z;+)isteinekrommutativeGruppSe.f8)]R2p :=URR^{nf0g]zusammenmitderMultiplikXationisteinekrom-mrutativeGruppSe.g)RzusammenmitderMultiplikXationisteinMonoid,abSerkreineGruppSe.h)DieProtenzmengeP(M@)einerMengeMAzusammenmitdemDurcrhschnitt\isteinMonoid,abSerkreineGruppe.i)zWVennGundHHalbgruppSen(Monoide,Gruppen)sind,dannistaucrhGH[eineHalbgruppSe(einMonoid,eineGruppe)mitpder*" ؝krompSonentenweisen-l\CMultiplikXationp(gn9;h)_(g20wrenn>BْUnterhalbgruppSeistunde2B=gilt;)ו(3)=Unterffgruppe,3,wrenn.8a;bt2B[aEbt2BRK^sa21V2B].und=wrennBX6=UR;:EineUnrtergruppSeistinsbesondereeinUnrtermonoid,5weilaucheN=aa21H2NB /gilt.pWirp)sagenaucrh,daB /unrterderBil-dungBvronProSdukten,MdesneutralenElementsbzw.MvonInversenabffgeschlossenvist.vEineUnrterhalbgruppSe(-monoid,-gruppSe)istselbsteineHalbgruppSe(Monoid,Gruppe).Lemma1.10.jOSeib(G;)eineHalbffgruppe,c&einbMonoidoffdereineGruppffeundseiAd GeineTeilmenge.PDannistdievonAa:'nMJö1.UUHALBGRUPPEN,MONOIDEUNDGRUPPEN&97d&MerzeugteMengexA3diekleinsteUnterhalbffgruppe(-monoidbzw.-gruppffe),35dieAenthyalt.&Beweis.x[XAf`istNsode niert,O daesunrterderMultiplikXation(bzw._eUR2xnA $;,bzw.Inrversenbildung)Fvon(G;)abgeschlossenist.Es6istdaherxsA5UeineUnrterhalbgruppSe(-monoid,-gruppe).Ist6aberBXURGeineUnrterhalbgruppSe(-monoid,-gruppe)mitAURB,sogiltaucrhx AB; alsoistx AkleinsteUnterstrukturvonGmitAURxnA $;: yff٘ ̍ ff ̄ ffffff٘_Satz1.11.XSeien(G;)eineHalbffgruppe(Monoid,Gruppe)undseien/Bid,/Si'2I Unterhalbffgruppen(-monoide,/S-gruppen).Dannist35T i2IaBiwieffder35Unterhalbgruppe(-monoid,-gruppe).&Beweis.XWVennt jedesderBiunrterderMultiplikXation(1UR2Bid,Inrversenbildung)!abgeschlossenist,,dannauchderDurchschnittT$iOBid: yff٘ ̍ ff ̄ ffffff٘_Satz1.12.XSei(G;)eineHalbffgruppe(Monoid, Gruppe)undAURG35eineTeilmenge.DannistxNGK.gAWR=UR\qfBXURGjB;UnterstrukturQ^ABg:.&Beweis.XDaxsZZAunrterZZdenzugelassenenB`ist,Zgilt*" -l\Ҕ.DaderDurcrhschnittwiedereineUnrterstrukturist,dieAenthyalt,unddaxA9kleinstesolcrheUnterstrukturist,gilt*" RX-l\Ҕ. yff٘ ̍ ff ̄ ffffff٘"I%DieErzeugungvronx(Ajgibt,Q.dannheienGundHisomorph,Q.inZeicrhenGPUR԰n:=HF::VLBemerkung2.5.|R3IsomorpheaObjektesindfSyurallemathemati-scrhenBetrachtungenalsgleichwertiganzusehen.SMankXannnyam-licrhUdieVVerknSyupfungvonzweiElementenauchdurchdieVVer-knSyupfung[derenrtsprechenden[ElementeimdazuisomorphenOb-jektݞausdrSyucrken,ݡd.h.fSyureinenIsomorphismrusfQ:URG !Hunda;bUR2GgiltVLQ}abUR=fG 1 {(fG(a)f(b)):VLIstfj:"G x!HeinbijektivrerHomomorphismus,soistfAeinIsomorphismrus,gdennXfSyurdieeindeutigbSestimmteUmkehrabbil-dung@fG21 {HB !URGgiltfG21(h1QNMh2)UR=fG21(fGf21(h1)NMfGf21(h2))UR=fG21 {fG(f21(h1)fG21(h2))UR=fG21(h1)fG21(h2)undfG21(eHD)UR=eG:WLemma2.6.cOWennf:G Q!HeinHomomorphismusist,dann*istBi|(fG)eineUnter-Halbffgruppe*(-Monoid,+-Gruppe)vonHV.s&Beweis.XSeien'h1;h2 2JBi@(fG).sDanngibtesg1;g2 2JGmitfG(g1)X=h1;fG(g2)=h2.NDa'f&einHomomorphismrusist,isth1Ҁh2V=URfG(g1)f(g2)UR=f(g1g2)2Bi(f).>ImMonoidfallistauerdemeH =fG(eG)2Bi78(f).~Istrscrhlielichf_qeinHomomorphismusvonGruppSen,dannisth21=URfG(gn9)21=fG(gn921 ʵ)2Bi(f). yff٘ ̍ ff ̄ ffffff٘VLBeispiel2.7.fEinwicrhtigesBeispielfSyureinenIsomorphismusistdieQ,ExpSonenrtial-Abbildungodere-FVunktion.QFDiereellenZahlenbildenMunrterderAdditioneineGruppSe(R;+).PWVeiterbildetdieMengepR+ *derpSositivrenreellenZahlenunterderMultiplikXationeineQGruppSe(R+x;)._DieFVunktionalgleicrhungQfyurdieExponenrti-alfunktionexpwB(a+b)Y=expMi(a)expf(b)bSesagtgenaudadieseAbbildungeinHomomorphismrusist.Dasiebijektivist,istsieeinIsomorphismrus.#DieUmkehrabbildungistebSenfallseinIso-morphismrusundgenSyugtderGleichunglog(ab)UR=log(a)+log(b).d`'nM100S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MManmerkresichzudem,dadieGruppSen(R;+)und(R+x;)zu-einanderisomorphsind.g553.G05FreieHalbgrupp`en,MonoideundGruppen"w֍EinevbSesondersnyutzlicrheArtvonStrukturensinddiefreienStrukturen.=Man=krenntsie(bisaufIsomorphie),=wennmannurihre9erzeugendenElemenrtekennt.eSieerlaubSenesauch,ebSeson-dersZeinfacrhHomomorphismeninandereStrukturenzukonstru-ieren.Allerdings6gehrtihreDe nitionvoneinerbSesonderenEigen-scrhaft3aus,4diesiehabSen,einersogenannrtenuniversellenEigen-scrhaft.DaherϩistihreDe nitionnichtganzleichtverstyandlich.ErstqnacrhdemBeweisihrerExistenz(undEindeutigkeit)kXannmandieseEigenscrhaftbSesserverstehen.De nition3.1.sSeiAeineMenge. EineHalbgruppSe(Monoid,GruppSe)x;F(A)zusammenmiteinerAbbildungFK:A !F(A)heit&eine(extern)frffeie_UHalbgruppe(Monoid,_Gruppe), #wrenn&zujeder HalbgruppSe(Monoid, Gruppe)GundzujederAbbildung :mA !GgenaueinHomomorphismrusfl:mF(A)!Gexistiert,soda+8?A8yF(A)7jfd#O line10- mW8:d !GruppSe).Ebenso> gibtes(genau)einenHomomorphismrusfG20k:URFƟ20o(A) !F(A)mitfG20820#=UR.DamitistfGf2020#=UR20=id F.:0(A)%f209,also/fGf20=id F.:0(A)$O,/1wreil(FƟ20o(A);209)freiist,undesistfG208fG==id#ޞF.:(A)9G,alsofG208f=]id(FF.:(A)"1,wreil(F(A);)freiist.AlsoistfeinIsomorphismrus. yff٘ ̍ ff ̄ ffffff٘'ǍWirmhabSenscrhonin1.7freieMonoidekennengelernt,jedoSchnichtdurcrh7dieobSengegebeneAbbildungseigenscrhaft.صDieseAbbil-dungseigenscrhaftbSeweisenwirimfolgendenSatz.EbSensogebenwir6hierdieKonstruktioneinerfreienHalbgruppSean.=DieKon-struktionaeinerfreienGruppSeistscrhwieriger.DaawirsiespyaternicrhtbSenyotigen,wollenwirdieseKonstruktionauchhiernichtangebSen.fx'nM102S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MSatz3.4.a(1)uSei@AeineMenge.eDannistA2eDzusammenmit=der35EinbffettungvonAinA29freiesMonoid.)ו(2)=SeicAeineMenge.cDannistA2nξf"gzusammenmitder=Einbffettung35vonAinA2jnf"gfreieHalbgruppe.&Beweis.X(1)JSei ::A !GJeineAbbildungineinMo-noid!G.!Wirde nierenfaO:PA2 T.!G!durcrhfG(a1:::anP)P:= (a1):::B (anP)6fSyurn16undfG("):=eG.=(Wir6de nierendas0-facrhe ProSduktvonElementeninGalseG.)fFisteinewohlde- nierteAbbildung,wreildurchjedesElementa1:::an >2hA2 LdieKompSonenrtena1;:::ʚ;an2URAeindeutigstimmtsind.SiewerdenbSenyotigt,=sum=^denWVertfG(a1:::anP)zubescrhreiben.=sEsistf]einHomomorphismrus,denn{fG(a1:::ann7b1:::brb)UR= (a1):::W (anP) (b1)O:::j  (brb)UR=fG(a1O:::j OanP)f(b1:::j brb)vundf(")UR=eG.WVeiterist6fG(a)=f(a)= (a),@also6f= .@Um6dieEindeutigkreitvonfEmitfGt= zuzeigen,seifG20:A24!GeinHomomorphismrusmitpfG208UR= .DannistfG208(a1:::anP)=fG20(a1a]:::Z]anP)=fG20(a1)]:::ZfG208(anP)~=fG20(a1),:::@fG20(anP)~= (a1),:::@ (anP)~=fG(a1:::an):WVeiteristfG208(")UR=eG t=fG("):Alsogiltf20k=URf.(2)FDerBewreisverlyauftebSensowieinTVeil(1).{AllerdingsmyussenalleReferenzenzu"UR2A2fortgelassenwrerden. yff٘ ̍ ff ̄ ffffff٘Y2MankXannaucrhzeigen,RdaeszujederMengeAeinefreieGruppSe:A u!F(A)bgibt.DieKonstruktionistjedoScrhwesentlichkromplizierter.Wir habSeneinesolcheKonstruktiondaherhiernicrhtmitaufgenommen.Beispiele3.5.|~V(1)(N;+)istfreieHalbgruppSeDFyuberAUR=f1g:)ו(2)=(N0;+)istfreiesMonoid>6yubSerAUR=f1g:)ו(3)=(Z;+)istfreieGruppSe>6yuberAUR=f1g:Ev4.VKongruenzrelationenundRestklassenWirhabSengesehen,dadiefreienStrukturenbesondersgyunstigeEigenscrhaften;habSen.WirkennenjedoSchBeispielevonHalbgrup-pSen,5Monoidenbzw.Gruppen,dienicrhtfreisind.5Wirwerdengf'nM@wD4.UUKONGRUENZRELA*TIONENUNDRESTKLASSENcG103d&MinndiesemAbscrhnittzeigen,ngdasichallesolchenObjektezu-mindest9mitHilfevronfreienObjektenbSeschreiben9lassen.=DazufSyuhrenfwirzunyacrhsteineallgemeineKonstruktionderRestklas-senrbildungùein,wiewirsiebSeiderBildungvon;/pxAquivXalenzklasseninD՞yDahnlicrherWVeiseauchschonfrSyuherkennengelernthabSen.DDersogleicrhPeinzufSyuhrendeBegri derKongruenzrelationspieltfSyurHalbgruppSenu(Monoide,vGruppen)dieselbeRolle,vwiederBe-gri Gder/pxAquivXalenzrelationfSyurMengen.InsbSesonderewrerdenwir/PrartitionennacheinerKongruenzrelationbildenundeinenFVaktorisierungssatzbSewreisen.΍De nition4.1.sSei,GeineHalbgruppSe(Monoid,,%Gruppe).Ei-neTVeilmengeR-n$G*/GheitKongruenzrffelation,wrennReinepx2AquivXalenzrelationundeineUnrter-HalbgruppSe(-Monoid,-GruppSe)avronGZmGaist.kDabeiistdieMultiplikXationaufGZmGkrompSonentenweisede niert:(g1;g2)(g2n90RA1;g2n90RA2)UR=(g1jg2n90RA1;g2g2n90RA2).PpxUbung:SeixGeineGruppSe.SeiRӽsG9GxeineKongruenzre-lation_fSyurdieHalbgruppSeG._8Manzeige,daRxddannaucrheineKongruenzrelationfSyurdieGruppSeGist.(Hinrweis:;WIst;)(gn9;h)UR2RJ,so;)aucrh(h;gn9);(h21 \|;h21);)und(gn921 ʵ;gn921).Dannist(h21 \|;h21)(h;gn9)(g21 ʵ;g21 ʵ)UR=(gn921;h21 \|)2RJ.)+4Satz4.2.QWennXRG]GeineKongruenzrffelationaufGist,dannZtryagtG=RgenaueineStruktureinerHalbffgruppeZ(Monoid,Gruppffe),WsoWDdadieRestklassenabbildung3:r(G ǁ!G=RpeinHomomorphismus35ist.&Beweis.XImIHalbgruppSenfallde nierenwireineOperationaufG=RdurcrhdaskommutativeDiagramm/8xGG8ñ$G=RG=Rt7jfd#Zά-88. ?XP?P?;P?XP8P8q86G=RŸfe5?5dfqCmit (gn9;h)pQ:=w}fe| gh.DieAbbildungfBexistiertundisteindeutigbSestimmrt,s.weils fyur(gn9;g20rr(+۟ꨄ Bffn991nُُ2nqq3ꨍۄff>ffffR.ff ʍn136ffnRR2n3P3P3nHۊHۊ3n236ffnRR3n3P3P3nHۊHۊ3n336ffnRR3n3P3P3nHۊHۊ3)ו(2)=SeiJn2N0 Nfestgewyahlt.InZLZseiR7:=f(rr;s)2=ZZj9q;2ĿZ[qn=r0s]g.^Man^8siehrtleicht,^daR=eineׇKongruenzrelation(bzgl.derAdditionvronZ)ist.=DieKongruenzklassenZ=Rsindfn0;n1;:::ʚ;fe,n1*gimFVal-=letn,>0undfn0;n1;n2;n3;:::ʜgtfSyurn,=0.u-DietVVer-i'nM@wD4.UUKONGRUENZRELA*TIONENUNDRESTKLASSENcG105d&M=knSyupfungstafelfSyurnUR>0istwregenqSr 4i+&7s =UR)feҟ׍r6+sYU&]+t-@ ffUffe0Ÿfe1Vfe26fe3 ~:::*fe,n1t-@ffTlffff$xԄff ʍ fe0xԟ36ff.fe0RVfe1t7fe2~fe3:::BPfe,n1 fe1xԟ36ff.fe1RVfe2t7fe3~fe4:::hfe0]...xԄ*ff1.1.1.V0.V0.V0.w{v.w{v.w{v. . . .\.\.\.xԄfffe,n1xԟ36ff#fe,n1RVfe0t7fe1~fe2:::BPfe,n2榍=ImFVallenV=0istR16dieGleicrhheitsrelationaufZund=Z=RPn԰=EZ](alsGruppSen).gIndiesemBeispielscrhreibenwir=aucrhP(n)n:=Rj0bzw.Q Z=(0)P԰V==Z.mDie9hierbSetracrhtete+px9AquivXalenzrelation(n)istdiein=BeispielI.4.2(3)bSetracrhtete.=Diedpx?AquivXalenzrelation(n)istaucrheineKongruenzrelati-=onbSezyuglicrhderMultiplikXationaufZ.ZistdanneinMo-=noid.DieVVerknSyupfungstafelfSyurnUR=6istwregen'6rHcs=URw{feҠr6slTЍ X*ffnOO0n??1nʇʇ2nU#U#3n߿߿4nj[j[5ffffffFff ʍn036ffnRR0n3P3P0nHۊHۊ0n^f&^f&0nss0n{^{^0n136ffnRR0n3P3P1nHۊHۊ2n^f&^f&3nss4n{^{^5n236ffnRR0n3P3P2nHۊHۊ4n^f&^f&0nss2n{^{^4n336ffnRR0n3P3P3nHۊHۊ0n^f&^f&3nss0n{^{^3n436ffnRR0n3P3P4nHۊHۊ2n^f&^f&0nss4n{^{^2n536ffnRR0n3P3P5nHۊHۊ4n^f&^f&3nss2n{^{^1榍Satz4.4.Q(FVaktorisierungssatzoSderHomomorphiesatz)SeifQ:Gu .!uG20]Fein HomomorphismusvonHalbffgruppen (Monoiden,Gruppffen)yundReineKongruenzrelationinG.Wennf'yuralle(a;b)UR2R8+giltfG(a)=f(b),danngibtesgenaueinenHomomor-phismusW*35f.:URG=Rn !G209,35soda1ᖍ8G8ʝGG=H%^7jfd$zލά- m98+fޟzenrtsprechenderSchreibweiseklarmachen.>BeiVVerwen-=dung˖derScrhreibweise]]˖nmu˖alsoimmerklarsein,in=wrelchergZMengediesesElemenrtliegensoll.g{WirsindinsbSe-=sondere)mitderobigenAngabSewreitvoneineridentischen=Abbildungenrtfernt.=DiewwicrhtigsteFVrageistjedoSch,wobdieobSenangegebene=ZuordnrungoSderRelationeine(wohlde nierte)Abbildung=ist.EskyonnennyamlicrhverschiedeneZahlennUR2Zgleiche=ElemenrteInm2oZ=(6)bSestimmen,z.B.n1J.=n7 k.WirhabSen=also6}zwreiverschiedeneRepryasentantenfSyurn1 y,6nyamlich1=und7."DannmrumanRyubSerpryufen,dainjedemsolcrhen=FVallYdieBilder n2Z=(3)nicrhtYvonderbSesonderenWVahlk'nM@wD4.UUKONGRUENZRELA*TIONENUNDRESTKLASSENcG107d&M=desiRepryasenrtantennfSyur0n8[abhyangt.vAlsoistderFVakto-=risierungssatzeinzusetzen.Dasgescrhiehtso:=Die Abbildung :=<3L@:Z !Z=(3) (dieRestklassenab-=bildung)4istnacrh4.2einHomomorphismus.8FSyurR=la(6)=istH(n;rS)2Rb8genaudann,IGwrennn#r=q\6fSyurein=q2~Z.0Dann/giltabSer (n)=3(n)=3(rۂ+q-6)==3(r+R2q53)#=3(rS)= (r)."Alsogibtesgenaueinen=Homomorphismrusf:tZ=(6) !Z=(3)mitfG64=3, d.h.=mitfG(n)QL=3(n)=n T,dalsodergewSyunscrhteHomomor-=phismrus.=WieosindwirnrungeradeaufdenHomomorphismus h:==3gekrommen.DadasDreieck58hZ8ڔ8Z=(6)7jfd$̍ά- mE8o aƟl=nH3=UR3(n).)ו(2)=De niertdiefolgendeAngabSeeinenHomomorphismrus:i:Z=(6)UR3n -7!n2Z=(4)?=Wieder=setzenwirdenFVaktorisierungssatzein.|AlsHomo-=morphismrus7o h:URZ !Z=(4)mSyussenwirwiezuvror h=4=wyahlen.FSyurR(n;rS)UR2(6),alsoRn=r+q836ist4(n)UR=4(rS)=oSder}(n;r)UR2(4)zuzeigen,alsomSyussenwirprSyufen,obn=raucrh1Gdurch4teilbarist,1wwennesdurch6teilbarist.1wDas=istAo enrbarnichtderFVallundliefertundschoneinGegen-=bSeispiel.zIn=Z=(6)istn6 2=nURUR0 =URf0;6;12;18;:::ʜg.AbSer=in[Z=(4)istn6(=f2;4;6;8;10;:::ʜg6=f0;4;88=12;:::ʜgu=n0 T,alsozkXanndieangegebSeneRelationkreine=Abbildungsein,uwreileinElementn6=nMM0z 2MZ=(6)zwei=vrerschiedeneBildern6 6=nURUR0in꨿Z=(4)hat.l'nM108S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&M)ו(3)=De niertdiefolgendeAngabSeeinenHomomorphismrus:cZ=(3)UR3n -7!-fe Í yn3n12Z=(3)?=DerHomomorphismrus nJ:ZZ !Z=(3)mudieAbbil-=dung (n)=-fe Í yn3sein.DasisttatsyacrhlicheinHomomor-=phismrus,dennc]U/ (n+rS)UR=щfe( 3/(n+r)3/=-fepv yn3j+3n2r6+3nr2:+r3=undc{H} (n)+ (rS)UR=-fe Í yn3Ç+-fe _ yr3_=-fe$ yn3j+r3':c=Die:bSeidenrecrhten:SeitenderGleicrhungen:stimmenrȞyuber-=ein,wreiln23+3n22rQ,+3nrS220+rS23n23rS23h=UR(n22rQ,+nrS22)3.=Istwreiterhinn`rS,d.h.nr=`q3,soistn23 =(riE+=qB3)23 G=CrS23V4+(rS22q3+rSqn922p9+qn9239)3,also (n)C==-fe Í yn3P!=O-fe _ yrS3e=O (rS).ZDamitsinddieVVoraussetzungendes=FVaktorisierungssatzeserfSyullt.=TVatsyacrhlichkXannmanleicrhtnachrechnen,dadiegege-=bSeneAbbildungsogardieidenrtischeAbbildungist.cSatz4.6.QSeiLfQ:URG !G20(einHomomorphismusvonHalbffgrup-pffen*(Monoiden,UGruppen).Dann*istdiezuf#)gehyorigeۀpxAquiva-lenzrffelationa b:()fG(a)=f(b)(vgl.I.4.3)eineKongru-enzrffelation.n&Beweis.XSeiTR}cGGdiegegebSene-ʟpxAquivXalenzrelation.Seien(a;b);(a209;b20)2RJ.TDannistfG(a a20)=fG(a) f(a209)=fG(b)ȅf(b209)=f(bȅb),alsoaucrh(aȅa209;bb20)2RJ.EbSensoistimMonoidfall(e;e)UR2RJ,CwreilRHeineUtpxAquivXalenzrelationist.Scrhlie-licrhListimFVallevonGruppSenmit(a;b)UR2Rf;auchL(a21 \|;b21)UR2RJ,dennfG(a21 \|)UR=f(a)21=f(b)21=f(b21 \|): yff٘ ̍ ff ̄ ffffff٘cBemerkung4.7.|R3Mit5derKonstruktionvronG=Rerhyaltmanei-neHBBijektionzwiscrhenderMengeallerKongruenzrelationeninGundkderMengeallermyoglicrhenRestklassenobjekteG=RJ,d.h.derMengerallerPrartitionenvonG,diedieStruktureinerHalbgruppSemB'nM@wD4.UUKONGRUENZRELA*TIONENUNDRESTKLASSENcG109d&M(Monoid,סGruppSe)לsotragen,da:URG !G=ReinלHomomor-phismruswird(vgl.I.4.7).DieAussagenvronI.4.10ryubSertragensicrh0Usinngemya.0InsbSesondereistBi(fG)eineUnter-HalbgruppSe(-Monoid,-GruppSe)fyureinenHomomorphismrusfj:kG !G209,undKdievron3j:qG=R F!G20ɄinduzierteKAbbildungǟ20:qG=R!Bi%(fG)isteinIsomorphismrus,wobSeiRdiezufǷgehyorigeKongru-enzrelationist. De nition4.8.sSei2GeineHalbgruppSe(Monoid,3Gruppe),dievron [einerMengeAerzeugtwird. Danngibtesnach3.1ge-naueinenHomomorphismrusfk:#F(A) x!G,derdieInklu-sionݽ a:A +!Gfortsetzt.=EineRffelationf'yurGbzgl.AisteinT.Praar(w1;w2)T.inF(A)OF(A)T.mitfG(w1)pk=f(w2).TDieMengevderRelationenfSyurGbSezyuglicrhvAbSezeichnenwirmitRG(A)UR:=f(w1;w2)UR2F(A)F(A)jfG(w1)UR=f(w2)g.LFolgerung4.9.rDieQMengederRffelationenf'yurGbez'yuglichAisteine35KongruenzrffelationaufF(A).񍍍&Beweis.XRG(A)vistdieKongruenzrelation,vdiedurcrhdenHo-momorphismrusfQ:URF(A) !Ginduziertwird. yff٘ ̍ ff ̄ ffffff٘Satz4.10.XJeffdeHalbgruppe(Monoid,Gruppe)istisomorphzueinem35ObjektF(A)=RJ,wobffeiRLeineKongruenzrelationist.񍍍&Beweis.XSeiuAeineErzeugendenmengevronG.v Einesolcheexistiertimmer,Cz.B.Ai=G.EsgibtabSerimallgemeinensehrvielkleinereErzeugendenmengenfSyurG..SeiRO:=RG(A).Wirde nierenyeinensurjektivrenHomomorphismusf,:}-F(A) ҆!GdurcrhdaskommutativeDiagramm0U8?A8yF(A)7jfd#ά- mW8:d !GdieInklusionsabbildungist.DaABi,(fG)und3Biɣ(fG)3nacrh2.6eineUnter-HalbgruppSe(-Monoid,4 -Gruppe)n'nM110S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&Mvron;Gist,mistnach1.10G=xA%Bi;G(fG)G,malso;BiE(f)=Gunddamitf2surjektiv.DannGinduziertfQ:URF(A) !GGnacrhI.4.9undI.4.10(3)einenbijektivrenHomomorphismusWyR*fR:URF(A)=Rn !G,soda-8hEF(A)8mF(A)=R=7jfdcά- mJ8"f=f(w1)f(w2)m>=W*f (w1)WJ*f -G(w2)m>=W*f (&fe &7]ڍw1 &7)WJ*f -G(&fe &7]ڍw2).ImFVallevronMonoidengiltzusyatzlichWyR*f O(}")UR=fG(")=e: yff٘ ̍ ff ̄ ffffff٘Bemerkung4.11.3ZurDarstellungeinerHalbgruppSe(Mono-id,LGruppSe)GinderFVormF(A)=R$genyugtesalso,LeineEr-zeugendenmengeAfSyurGundeineErzeugendenmengeBufSyurRF(A)F(A)@anzugebSen.@%GibtmaneineMengeAundei-neoTVeilmengeBD8>F(A)mF(A)ovror,psokXannmandarauseinekleinsteKongruenzrelationRnURF(A)F(A)mitBXURR0bildendurcrh9Rn:=URT fS)URF(A)@F(A)jSiKongruenzrelation9^AURSg.Damitde nierenAundB3"eineHalbgruppSe(Monoid,HGruppe)F(A)=RdurcrhErzeugendeAundRffelationenB.za5.Restklassengrupp`enBeidenGruppSenhyangtdieRestklassenrbildungmitgewissenUn-tergruppSenLmiteinerganzbesonderenEigenscrhaftzusammen,diemannormaleUnrtergruppSennennt.GenauergibteseineBi-jektionj3zwiscrhenallennormalenUntergruppSeneinerGruppeGundtallenKongruenzrelationenaufG.DieetrwastunhandlichenKongruenzrelationen?lassensicrhalsodurcheinfacherenormaleUnrtergruppSenerzetzen.AuchdieFVaktorgruppSenoderRestklas-sengruppSenlassensicrhdamiteinfacherbSeschreiben.De nition5.1.sEineUnrtergruppSeH>einerGruppeGheitNormalteiler(oSdernormale35Unterffgruppe),wrennhލ8gË2URG;h2HV9h 0#2H[gn9h=h 09g]:o4'nMy5.UURESTKLASSENGRUPPENPm111d&Bemerkung5.2.}ɩpx|R3AquivXalenrtdazuist,%dafSyuralleg,2Ggiltgn9HVg21>=fghg21 ʵjh2HVgHW,oSderidafyurallegO2Ggiltgn9HB=URHVg:Die_BedingunglyatsicrhbSesonderseinfachfSyurabSelsche(kom-mrutative)AGruppSenGerfyullen,sesistnyamlicrhgn9h[=hgzfyurAalleh^2HݗundAalleg2^G.CZug^zundhkXannmanalsoimmerh2Hwyahlen,NumNdieBedingungfSyurdieNormalityatzuerfSyullen.Esgiltalso:jedeUnrtergruppSeeinerabelscrhenGruppeisteinenormaleUnrtergrppSe.эSatz5.3.QSei35GeineGruppffe.DieZuordnungen5t P(G)UR3HB7!Rn2P(GG)mit35Rn:=URf(a;b)jab212HVgundt P(GG)UR3Rn7!HB2P(G)mit qH:=fab21 \|j(a;b)2RJgde nierffeneineBijektionzwischender\MengederNormalteilerHJvonGundderMengederKon-gruenzrffelationen35RLaufG.PJ&Beweis.X1.*VBehauptung:WVenn*EHeinNormalteilerist,*VdannistRn:=URf(a;b)jab212HVgeineKongruenzrelation.Bewreis:RǒistHre exiv,weilHa%a21=V e2HfSyurallea2Ggilt.CIstC}(a;b);(b;c)D2RJ,soC}istaob21 \|;bc212DHV,alsoC}aucrhac21:<=(ab21 \|)(bc21)2HV.gAlsogist(a;c)2RundgRdamitHtransitiv.HIst(a;b) 2RJ,soHistab21Q2 HV,alsoHba21Q=ɍ(b21 \|)3 1Ba21=)(ab21 \|)}Ÿ 1)ng2H)und<`damit(b;a)2RJ.fehf0΍kommutiert.I5&Beweis.XNacrhI.4.9existiertw}fe f eindeutigalsAbbildung,wennfSyurFallea;b%2GFmit(a;b)%2R`;giltFfG(a)=f(b).GJAbSerFwrenn(a;b)2Rist,dannYistaSb21Y2HV,alsoYfG(ab21 \|)=eG0unddamithfG(a)%=f(b),dennhf(a)d[f(b)21=%f(ab21 \|)%=eG0 _.DadieXMultiplikXationinG=HFaufdenRepryasenrtantenXdurchgefSyuhrtwird,MgiltL(wieimBewreisvon4.2)w}fe f _(&fe+]ڍahw}fe bgt)UR=w}fe f g(w}feԑ abԑ)=w}fe f(ahb)UR=fG(a b)e}=f(a) f(b)e}=w}fe f x$(a) w}fe f (b)e}=w}fe f x$(&fe+]ڍa+) w}fe f (w}fe b);(alsoistw}fe feinHomomorphismrus. yff٘ ̍ ff ̄ ffffff٘0΍Beispiele5.7.|~V(1)SeinUR2N.Dannist[LvSn:=URff1;:::ʚ;ng !f1;:::ʚ;ngjabijektiv.Rg=unrterderVVerknSyupfungvonAbbildungeneineGruppSe(I.=2.22).$Sn heit$symmetrische}HGruppffeIvoSderPermutations-=gruppffe.Nacrhu=(ISI.4.6)istSn eineGruppemitn!Elemen-=ten.Sn hatErzeugende+mVf\ ʍu1;2;3;:::ʚ;nu2;1;3;:::ʚ;nPCf\!%undܥf\ ʍ/1;2;3;:::ʚ;n!2;3;4;:::ʚ;1$ pf\!-:r'e'nM114S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&M=EineandereErzeugendenmengeistfidg#Sn 8fSyuri==1;:::ʚ;n1mit'v|6id(kg)UR:=8 >>< >>:\ 8i+1;7fSyurJko=i;ɍ 8i;7fSyurJko=i+1; 8k;7sonst.'u=DieiOheienTrffanspositionen.=DieierfSyullendieRelationenidj1=i'jf ifSyurii'fSyur1in1.Man kXann=Sn kuaucrh%darstellenalsF(f1;:::ʚ;n1g)=RJ,/wobSeiRodie=vronMdenRelationen(idjf ;ji);(ii+1AVi;i+1AVii+1)Mund=(idi;")erzeugteKongruenzrelationist.)ו(2)=DiecUnrtergruppSeAn lSn mitAn=fs1kc_:::!^_s2tjt2=N0EZ^Vsi,2URf1;:::ʚ;n1ggbheitGruppSedergerffaden"iPer-=mutationen.Man{kXannzeigen,daAn KRSn einNormal-=teileristunddaAn 6=mhSn gilt(n2).DannhatSnP=XAn=genau2Elemenrtew}fe ʤ idund&fe m]ڍ1,-dennfSyurs1:::Lst2URSn lV&fe m]ڍ1ꨟ&fe m]ڍ1-36ff#T&fe m]ڍ1>lVw}fe ʤ idw=sein.zDiezAbbildungw}fe f:J~SnP=XAn H'!f1;1gzmitw}fe f Y(w}fe ʤ id ʤ)J~==1;w}fe f (&fe]ڍ1 )=1GisteinIsomorphismrus,GwennGmanf1;1g=alsGruppSemitdergewyohnlicrhenMultiplikXationau at:1r3ЍjcffH1 -1cffboffff=ff ʍ136ffV1+{-1-136ff-1-p1~:s5'nMy5.UURESTKLASSENGRUPPENPm115d+탍=Der HomomorphismrusSng J5!"AuSnP=XAnKyS>fehf J5!f1;1g heit=SignatureoSderVorzeichen:sgnh&:=w}fe f .EinePrermutation=y2"Sn heitcagerffade,cwrennsiesichalsProSdukteinerge-=raden3AnzahlvronTVranspSositionenschreibSenlyat.bSonst=heit<sieungerffade.xZ7 2Sn histgenaudanngerade,<-wrenn=sgnN(W)UR=1gilt.эSatz5.8.Q(Caryley) _SeiGeineendlicheGruppffe.DanngibteseineТUnterffgruppeUeinerPermutationsgruppeSnP,мzuderGiso-morph35ist.9&Beweis.XHabSeGgenaunElemenrteundsei[GUR=fe=a1;:::ʚ;anPg:Jedemaj2GordnenwirdiePrermutationa 9:jf1;:::ʚ;ng $!f1;:::ʚ;ngYzumitaai,=URaa h#(i)iu:YO enrbargibteszujedemIndexigenaueinenIndexa(i)mita1ai ="aa(i)iu:Daherista eineAbbildung.DieWUmkrehrabbildungvona&isto:=URa1,dennai,=a21 =aai,=URa21aa(i)=URar(a (i))"?undai,=aa21ai,=URaa"(i)Ct=aa(r(i)),?$also?giltW(a(i))=i=a(W(i)).?$Damit?ista Bbijektiv,alsoeinePrermutation.WirhabSensomiteineAbbildungË:URG3aUR7!aY!2Sn `5de niert.WVegenai?ab (i)O!=(aBb)ai,=URabai=URaai?b?(i)g=URaa(i?b?(i))%HistabXq=ab",Halsoist +einHomomorphismrus.Scrhlielichist,injektiv,dennausaY!=URbfolgta=aEe=aa1V=aa(1){=ai?b?(1)3=ba1 v=bPSeiU:=BiL(n9).Q,DannistUeineUnrtergruppSe3vonSn NunddereingeschryankteHomomorphismusn920:URG !Bi(n9)=U+bijektiv,alsoeinIsomorphismrus. yff٘ ̍ ff ̄ ffffff٘De nition5.9.\(1)SeinAGeineendlicrheGruppSe.nbDieAnzahl=derElemenrtevonGheitOrffdnungvonG:)ו(2)=Seia^2GeinElemenrteinerbSeliebigenGruppe.WVennes=ein'nM116S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MManYbSeacrhte,YdadieserBegri einerOrdnungnichtszutunhatmitdemBegri einergeordnetenMenge.DBemerkung5.10.3WVenneseinnx2Nmita2n O=xegibt,ޞsogibt,esaucrheinkleinstessolchesn,,daNwohlgeordnetist.,WirbSetracrhtenrjetzteinElemenrta<2GrineinerendlichenGruppSe.WVenn8a2r 0=?a2s tistundr\ne,gibteseindeutigcbSestimmrteqiundrNmitt%=qn9ndX+rundc0%ryZwischenaU~undUgibteseinebijektivreAbbildung_aU&3Bx7!a21 \|x2U@,dennwrennx=au,dannista21 \|xq=a21au=u2U@.( Die'UmkrehrabbildungistU3qu7!auUR2aU@.DaherhabSenalleKlassenaUɄderPrartitiongleichvieleElemenrte,etwarFElemente.DaGc=S aU4eineVVereinigungvronspaarwreisedisjunktenMengenist,hatGgenausrQ"Elemente,alsoKistrr;dieOrdnungvonU@,KeinTVeilerderOrdnungvonG: yff٘ ̍ ff ̄ ffffff٘Bemerkung5.12.3WirCwissenzunyacrhstnicht,wievielepaar-wreiseverschiedene(unddamitauchdisjunkte)MengenderFVormaUwir͞habSen.ͥEskyonnenaundbvrerschieden͞sein,undeskXanntrotzdem=aUn=-bUA!gelten.DaabSerGendlicrhist,kyonnennrurendlicrhviele(obSens)solcheKlassenauftreten.;vBemerkung5.13.3Bezeicrhnen(wirU@nG):=fUaja2Gg,(so(istdies'ebSenfallseinePrartitionvonG.('DiePartitionenU@nGundG=Usindyimallgemeinenvrerschieden.z EsygiltU@nGI$=G=Uge-naupdann,pwrennUeinNormalteilerist.WirbSeacrhtenpdazudieDe nition !5.1. *Damitistnrurzuzeigen,daaU=U@bimpliziertaUf=ÂU@a.+uAbSer+dausaU=ÂU@bfolgta2U@bunddamitwieobSenU@bUR=Ua.Y256.@5RingeundKorp`erBei+denMengenvronZahlen,6etwadenganzenoSderdenkomple-xenZahlen,habSenwirBeispielegefunden,bSeidenenzwreiver-scrhiedeneVVerknSyupfungen,z.B.dieAdditionunddieMultiplikXati-on,r)auftreten.Dier bSeidenVVerknyupfungenerfyullenEigenscrhaften,diebnrurmitbSeidenVVerknyupfungengemeinsamausgedryucrktwer-den Skyonnen, wiedasAssoziativgesetz.WirwrerdendaherjetztdieAxiomedieserBeispielebSetracrhtenundsievrerallgemeinern.va-'nM118S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MDe nition6.1.sEinlR2ingisteinTVripSel(RJ;+;)lmitfolgendenEigenscrhaften荍)ו(1)=(RJ;+)isteineabSelscrheGruppe,)ו(2)=(RJ;)isteineHalbgruppSe,)ו(3)=EsgeltendieDistributiv-Gesetzenʍj4I8a;b;c;2URRJ[a(b+c)UR=ab+ac^(a+b)cUR=ac+bc]=(wrobSei"dieMultiplikXationstyarkerbindet(alsoPryazedenz=hat),alsdieAddition:ab+cUR=(ab)+c).nEinpRing(RJ;+;)pheitR2ingmitEinselementpoSderunityarfferRing,wrenn(RJ;)einMonoidist.EinRingheitkommutativer8R2ing,wrennN(RJ;)'kommutativist..EinRingheitnullteilerfrffei,wrenngilt: 8a;b\g2RJ[ab\g=0=)a=0_b\g=0]:8WirscrhreibSenimfolgenden)dasPrffodukt)a!baucrhalsab.*,DasneutraleElementvon(RJ;+)QwirdmitNulloSder0bezeicrhnet.ޏDasneutraleElementvron(RJ;)fSyureinenunityarenRingwirdmitEinsoSder1bezeicrh-net.~DiezVVerknSyupfungen+s:RR J!Rbzw.:RR J!RheienAffdditionbzw.Multiplikation.DasInrverseeinesElementsa+n2R#unrterderAdditionwirdmitaoSder(a)bezeicrhnet,unrterderMultiplikXation(fallsesexistiert)mita21 \|.%Lemma6.2.cO(Rffechengesetze/inR2ingen)Seiena;b2RJ.\Danngilt荍)ו(1)=0aUR=a0=0;)ו(2)=(ab)UR=(a)b=a(b);)ו(3)=(a)(b)UR=ab;)ו(4)=(a)UR=(1)a:)ו(5)=Wenn350UR=1,dannistRn=f0g:&Beweis.X(1)uEsist0aA=(0 9+0)aA=0a 9+0a.uDurcrhuSubtra-hieren9vron0a(Addierenvon(0a))erhyaltman0^=0a.:Analogergibtsicrh0UR=a0:(2)DEsistab+(a)b=(a+(a))b=0b=0,DalsoDist(a)b=(ab)inrverszuab.Analogista(b)UR=(ab):wn'nMRwL6.UURINGEUNDKcfORPERXcO119d&M(3)Esist(a)(b)UR=(a(b))=((ab))=ab:(4)Esist(1)aUR=(1a)=(a):(5)Sei0UR=1undaUR2RJ.DannistaUR=1a=0a=0: yff٘ ̍ ff ̄ ffffff٘ De nition6.3.sSeien; RTSundSRingeundf:R+ !SeineAbbildung.f2heitHomomorphismus35vonR2ingen,wrenn,Ϛ8a;bUR2RJ[fG(a+b)UR=f(a)+f(b)^f(ab)UR=f(a)f(b)]:SeienaR{9undSunityareRingeundfQ:URRn !SeineaAbbildung.bfheitHomomorphismus"vonunityarffenR2ingen,ĉwrennfQ:URRn !SeinHomomorphismrusvonRingenistundgiltfG(1)UR=1.Beispiele6.4.l(1)B&(Z;+;);(Q;+;);(R;+;)und(C;+;)sindunityare.krommutativeRinge.5(N0;+;)istkreinRing,5weil(N0;+)kreineGruppSeist.,+(2)"4SeinUR2N08fest"4gewyahlt."hDannistZ=(n)mitderAdditionundMultiplikXationderKongruenzklassende niertdurcrhAdditionundMultiplikXationderRepryasenrtantenwiein4.3(2)v`g&fe]ڍr~(+&fe]ڍs =UR)feҟ׍r6+s$;&fe]ڍr!ɯ&fe]ڍs=UR&fe ']ڍrSsein unityarerkrommutativer Ring.WVegen4.2und4.3(2)sindnrurdieDistributivgesetzezuprSyufen:&fe]ڍr!(&fe]ڍs|+kJfe>6t2)UR=&fe]ڍr Q(kJfe?s+t?)=щfe' 3/rS(s+t)-4=kJfe#~!rSs+rt*(=&fe ']ڍrSsq2+kJfe OrSt&=&fe]ڍr Q&fe]ڍs p+&fe]ڍr kJfe>6tundanalog (&fe]ڍrI+&fe]ڍs3)kJfe>6t >0=UR&fe]ڍr kJfe>6t +&fe]ڍs 1kJfe>6t:5,(3)Restklassenrtests:Sei h:URN !ZeineAbbildung,derenBildeineAendlicrheTVeilmengeXFURZistundfSyurdiegilt8r2N[щfeOi 3/ (rS)=&fe]ڍr],NwrobSeiNdieRestklasseninZ=(n)fyureinfestesni2ZNbetracrh-tetwrerden.Danngiltщfe*Q" 3/ (r6+s)6B=Iɟщfe;r 3/ (rS)+ (s)FPundщfe$ 3/ (r6s)0s=щfe53@ 3/ (rS) (s)OG:,HdennGщfe*Q" 3/ (r6+s)5@'=])feҟ׍r6+s$=]щfe91 3/ (s)!=]щfe;r 3/ (rS)+ (s)Ewundщfe$ 3/ (r6s)B=nw{feҠr6sd=n&fe]ڍr &fe]ڍs =nщfeOi 3/ (rS)s-щfe91 3/ (s)\=nщfe53@ 3/ (rS) (s)8":DieseFVormelngestattenzeinepxUbSerpryufungzvronAdditions-undMultiplikXations-aufgabSen,indem~man (rZ6s)und (rS)6 (s)~vrergleicht.DiesemSyussenkrongruentmoSdulonsein.)DaXvCeineendlicheMengexx'nM120S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&Mist,׏sind׋dieseKongruenzenleicrht׋zu+yubSerpryufen.WVenn׋dervrer-meinrtliche)NWVertdesProSduktesr(Osunrter 10+a0)ˇ:=a0+a1+:::~+ar9~5ar+::: r+a0 moSd'E>9.@Alsoistщfe 3/ O(rS)&W=&fe]ڍrbfSyuraller2N.kSeij ~tdieiterierteQuersummenrbildung (rS)/= M:::t:::"? O(r),so\oftiteriert,\7biseineeinstelligeZahlherauskrommt.Dann\giltщfeOi 3/ (rS)5i=щfe/& 3/ M:::t O(rS)8#=:::&=щfe 3/ O(rS)k=&fe]ڍr M._Auerdem,hat ȻdasBildf0;1;2;:::ʚ;9gK=XJg:InX{sind2ZahlenaundbgenaudannkrongruentmoSdulo9,wrennsiegleichsindoSder0und9sind.DieNeunerprffobefSyurdieMultiplikXationnatSyurlicrherZahlenergibtsichdamit:XdieiterierteQuersummedesProSduktsrEsstimmrtmitderw6QuersummedesProSduktsderiteriertenQuersummendereinzelnenFVaktoren樞yubSerein,esseidenn,dasicrhResultate0und9ergebSen.!(5)SDieAbbildung .:߿Z ]8!ZSseidiesogenannrtealternierendeQuersumme,ά- mbm8f=fehffallsfSyuralle(rr;rS20!)UR2SgiltfG(rS)=f(rS20!):ppxAhnlicrhHTwiewirbSeiGruppenKongruenzrelationendurcrhnor-maleSUnrtergruppSenHGbescrhriebenhaben,kyonnenwirimFValle|vronunityarenRingenKongruenzrelationendurchzweiseiti-ge\IdealeIkzDRbSescrhreiben.bDabei\heiteineTVeilmengeIzDReinvzwreiseitigesIdeal,wennIeineUntergruppSevon(RJ;+)istundfSyuraller029R1undi2IjgiltrSi;ir02RJ.!Auseinemzwrei-seitigenIdealIFURRagewinnrtmaneineKongruenzrelationdurchS7:=;f(rr;rS20!)2RJjr8rS202Ig3undumgekehrterhyaltmanausz'nM122S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MeinerKongruenzrelationSuaufReinzwreiseitigesIdealdurchIF:=URfr6rS20!j(rr;rS20)2S.ManscrhreibtdannauchRJ=S)=:URR=I:DieRElemenrteinRJ=IsindvonderFVormr%x+I(=7xfr+iji7x2I.DiebAdditionundMultiplikXationaufRJ=Iistde niertdurcrh(r[$+I)+(rS20)]+I)UR:=(r[$+rS20!)+IUund(r+I)(rS20)]+I)UR:=r[$rS20)]+I.Dasgiltwregen&fe]ڍr 4i+㒉femR nrS0mL=UR㒉feC nr6+rS0#=und&fe]ڍr㒉femR nrS0mL=UR㒉fe nr6rS0 c:'Satz6.7.QF'yur nUR2N0$istZ=(n)genaudanneinKyorpffer,7wennneine35Primzahlist.s&Beweis.XSei!pfk=neinePrimzahl.!DieElemenrtevonZ=(p)sinduffe0;fe1;fe2;:::ʚ;fepPp1pNg.Sei01,'somruneinProSduktsein:nUR=ab,'mit16=UR0: yff٘ ̍ ff ̄ ffffff٘vLBeispiele6.8.lQ;R;CsindKyorpSer,jedocrhnichtNundZ:Bemerkung6.9.|R3SeiRXeinunityarerRingundXeineMenge.DannistAbb(XJg;RJ)7 =f J:X( }!Rj 9AbbildunggeinRingmitdenOpSerationenvL--6( 7+ O)(x)UR:= (x)+ O(x);( 7 )(x)UR:= (x) O(x):Es!yCubSertragensicrhdiealgebraischenEigenschaftenvonR\aufRJ2Xu=>DAbb](XJg;RJ).SoQistz.B.dieEinsinR2X $gegebSendurcrh (x)UR=1HfSyurallexUR2X.IstHR/einKyorpSer,soistRJ2X MkreinKyorpSer,denn h6=UK0bSedeutetnicrht,1da (x)6=0fSyurallex2X(dannkyonnrte man 21 p (x)?= (x)21gVde nieren), $sondern nur,da esmindestenseinxb2Xzwgibtmit (x)b6=0.WVenndannabSerfyur{'nMYGF7.UUBOOLESCHERINGEUNDALGEBREN03I123d&Mein.wreiteresyË2URXgilt (yn9)=0,.5dannlyatsicrh 21anderStelleyXnicrhtsinnvollde nieren.De nition6.10.ySeixKderKyorpSerQ;RoderC.y;DieMengeK[x]:=f =:K !Kj9a0;:::ʚ;an ]2K8b2K[ (b)=anPb2n FP+:::+>+a1b+a0g]{isteinUnrterringvonK2qymsbm7K s?undheitR2ing%derPolynom(-funktionen)%aufK.%WirscrhreibSenP*n̍i=0aidx2ia=anPx2n{ +:::)›+a1x+a0V:=UR ,wrennf (b)=anPb2nQ+:::+a1b+a=0ffSyuralleb 2K.DieAdditionistgegebSendurcrhP*5n̍5i=0w:aidx2i2++XP* n̍ i=0bix2i=P*$5n̍$5i=02(ai+vbid)x2i,[dieTMultiplikXationdurcrhP*_m̍_i=0aidx2ivP* (n̍ (jv=0Gbjf x2j\=>P$5m+n%$5k6=0>VgP*Hk̍Hi=0]aidbk6ix2k#,wiemanleicrhtnachrechnet.?ʍBemerkung6.11.3Auer^dengenannrtenKyorpSernQ;R;C^undZ=(p)1(pPrimzahl)gibtesnoScrhvieleweitere.4InsbSesonderegibteseinenendlicrhenKyorpSermitnElementengenaudann,wennnvroniderFVormp2rzmiteinerPrimzahlpist.DieendlichenKyorpSermitz?p2r ElemenrtenheienauchGalois-FelderGF(p2rb).z\SiewerdeninsbSesondereinderCodierungstheorievrerwendet.^Z.7.knBo`olescheRingeundAlgebrenAucrhbinderPotenzmengeeinerMengehabSenwirzweiVVer-knSyupfungenSUbSetracrhtet,S|denDurchschnitt\unddieVVereinigung[.SieterfSyullenetrwastandereGesetze,alswirsiefSyurRingeundKyorpSerkrennengelernthabSen.DieseGesetzesindjedocrhbeson-derswicrhtig,weilmansienichtnurinPotenzmengen ndet,son-dernaucrhbSeiAusdryucrkenmitlogiscrhenVVerknyupfungszeicrhen.?ʍDe nition7.1.sSei.(A;[;\;207)einQuadrupSelmiteinerMengeA,binyarenOpSerationen[7:AjA7 !7Aund\:AjA !Aundeiner1-stelligenOpSeration20%:GA G!A.oDasQuadrupel(A;[;\;207)=heiteineBoffolesche_A2lgebra,Rwrenn=fSyurallea;b;cUR2Agelten: )ו(1)=(a[b)[cUR=a[(b[c);(a\b)\cUR=a\(b\c),)ו(2)=a\(b[c)UR=(a\b)[(a\c);=a[(b\c)UR=(a[b)\(a[c),)ו(3)=a[bUR=b[a;a\bUR=b\a,|z'nM124S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&M)ו(4)=es`gibteinElemenrt02A,aso`dafSyurallea2A`gilt=0[aUR=a,)ו(5)=es`gibteinElemenrt12A,aso`dafSyurallea2A`gilt=1\aUR=a,)ו(6)=a[a20#=UR1;a\a20=UR0.aBeispiele7.2.|~V(1)P(A),dier6s2:=URr6\s:)ו(2)=SeiI(A;+;)einBoffolescherR2ing.]Dannist(A;[;\;207)ei-=ne35BoffolescheA2lgebramit"ʍ;r6[sZ:=URr6+s+rs;;r6\sZ:=URr6s;4rS20Z:=UR1+rr:"&Beweis.X(1)/1.j(a+b)+cUR=(((a\b209)[(a206\b))\c20)[(((a\b20)[(a20\,Mb))20\c)UR=(a\b20\c209)[(a20\b\c209)[((a20[b)\(a[b209)\c)UR=!(durcrh~Դ'nM126S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MAu yosendesrecrhtenAusdrucks)(aL\b20\c209)[(a20\b\c209)[(a20\b20\c)[(a\b\c):undebSensowregenderSymmetriedesAusdrucksa=V+(b+c)UR=(a=V\b20 \c209)[(a20\b\c209)[(a20\b20\c)[(a\b\c).2.a+bUR=b+a,wreilVVereinigungundDurchschnittkommutativsind.3.a+0k=(a\0209)[(a20\0)k=(a\1)[0k=a,alsoexistierteinneutralesElemenrt.4.^8a+aUR=(a\a209)[(a20Y\a)UR=0,also^existiereninrverse^Elemente.5.(A;)isteinMonoid.6.1(a+b)cUR=((a200\b)[(a\b209))\cUR=(a20\b\c)[(a\b20\c)UR=(a\c\(b20t[c209))[((a20[c209)\b\c)UR=(a\c\(b\c)20)[((a\)20t\b\c)UR=ac+bc:4DamitistAeinRing.5WVegena\aUR=a=aa4istAeinBoSolescrherRing.(2)1.a[bUR=a+b+abUR=b+a+baUR=b[a.2.(a(3[b)[cUR=(a(3+b+ab)+c+(a+b+ab)cUR=a(3+b+c+ab+ac+bc+abcUR=a+(b+c+bc)+a(b+c+bc)UR=a[(b[c).3.0[aUR=0+a+0aUR=a.4.a$[a207=ia+a20]+aa20=ia+1+a+a+a=1unda$\a207=a(1+a)UR=a+aUR=0.5.(A;\;1)isttrivialerwreiseeinkommutativesMonoid.6.au\(b[c)UR=a(bu+c+bc)UR=abu+ac+abcUR=abu+ac+abacUR=(aZ\b)[(a\c)undaZ[(b\c)UR=aZ+bc+abcUR=aZ+ab+ab+ac+bc+abc+ac+abc+abcUR=(a+b+ab)(a+c+ac)UR=(a[b)\(a[c). yff٘ ̍ ff ̄ ffffff٘dBemerkung7.7.|R3TVatsyacrhlichperhyaltmanwrechselseitigpausdenStrukturen|derBoSolescrhenAlgebraunddesBoolescrhenRingesund"wbSeimzwreimaligenpxUbergangdiealtenStrukturenzuryucrk."Esistdnyamlicrha+b+abUR=(((a\b209)[(a20g1\b))\(a\b))[(((a\b20)[(a20"\Tb))20\a\b)UR=((1\(a[b)\(a20"[b209)\1)\(a20[b209))[((1\(a[b)*<\(a20u[b209)\1)20\a\b)UR=((a*<[b)\(a20[b209))[(((a20\b209)[(a\b))G\a\b)UR=(a20\Gb)[(a\b209)[(a20\b20\a\b)[(a\b\a\b)UR=(a20\Őb)[(a\b209)[(a\b)UR=(a20\Őb)[(a\(b20[b))UR=(a20\Őb)[aUR=(a20x[a)\(a[b)UR=1\(a[b)UR=a[b.WVeiterEist(a\b209)[(a20\b)UR=a(1+b)+(1+a)b+a(1+b)(1+a)bUR=a)+ab+b+ab+ab+ab+ab+abb=a)+b.Scrhlielichist'nMYGF7.UUBOOLESCHERINGEUNDALGEBREN03I127d&M1+aUR=(120x\a)[(1\a209)UR=(0\a)[a20#=UR0[a20=URa209.⍍Bemerkung7.8.|R3BoSolescrhepAlgebrenundBoolescrheRingesindalgebraiscrhe LStrukturen. EslassensichKongruenzrelationenundRestklassenstrukturenbilden.DerFVaktorisierungssatzgilt.JedeBoSolescrhe?AlgebralyatsichalsRestsklassenalgebraeinerfreienBoSolescrhenAlgebradarstellen,2insbesonderedurcrhErzeugendeund8Relationen.8WVennAeineBoSolescrheAlgebraist,dannistaucrhwreilzfG(0;0)}=f(0;1)=f(1;1)=0zund'nM130S1IGII.UUALGEBRAISCHEGRUNDSTRUKTURENd&MfG(1;0)UR=1ist.TVatsyacrhlichist sʍ1(x1j[x2)\(x1\x20RA2)UR=(x1\x1\x20RA2)[(x2\x1\x20RA2V=^/p(x1j\x20RA2)[0UR=x1\x20RA2V=1\x1j\x20RA2:/jVBoSolescrhe}PolynomestelleneinebSesonderseinfacheKlassevonBoSolescrhennFVunktionendar.nIneinemSpezialfallfallendiesebei-den&Begri ejedoScrhsogarzusammen.]WirformulierenhiernurdenenrtsprechendenSatzohneBeweis.,Satz7.14.XIst\Bm= gf0;1g,soistjeffdeBoolescheFunktioninAbb/(B2nCV;B)35einBoffoleschesPolynom.Bemerkung7.15.3(SyubSerGGatter)Eine(tecrhnischeGRealisierungeiner)N(BoSolescrhenFVunktionfF:B2n B]!B.mitN(B=f0;1gheiteinGatter.Gsʍ'CfG(x1;:::ʚ;xnP)UR=x1j\x2\:::\xnheitUND-Gatter,'CfG(x1;:::ʚ;xnP)UR=x1j[x2[:::[xnheitODER-Gatter,'CfQ:URBX E!BmitJfG(x)=x20heitNICHT-Gatter oSderInrverter,'CfG(x1;:::ʜ;xnP)UR=(x1j\x2\:::\xnP)20heitNAND-Gatter,'CfG(x1;:::ʚ;xnP)UR=(x1j[x2[:::[xnP)20heitNOR-Gatter,'CfG(x1;x2)UR=(x1j[x2)20#=x1V#x2heitPierce-Gatter,'CfG(x1;x2)UR=(x1j\x2)20#=x1jx2heitShe er-Gatter.IUDiezugehyorigenGatter-SymrbSolesind:USNorm:s獍-ˍNji6- cmcsc10AndaYl#< lcirclew10l#$̟sDҟkDҟaYkD[l["$̎9`F5 a9`F al̎hV̎]o̎,/|̎`]̎'̎Ǎ̎ԟ̎-s ̎_'#̎B̎A^̎Q{̎$󘘄̎U󵵄̎vӁ̎̎̎.̎AsNH̎oen̎Fׄ̎q]̎8G̎#?̎O̎{4̎şV~̎y̎dA̎&q̎P㐄̎y̎,ʄ̎Q̎7w3̎O-̎BË̎iM̎̎8̎m`̎͟m̎'2!̎K˟9̎p̎=-)̎Wl̎ڵ̎[̎ ̎A̎cg0%̎\L̎I̎̎̎!̎%@̎CƟo̎b#w̎.̎-I̎_.Ȅ̎ث_-̎s̎̎,̎H&̎c]X̎}՟)̎nA̎A̎l'̎U[̎c̎Ɵ̎-C̎E)2]̎\ i̎r5̎(̎= ̎GV̎ɩ̎I̎̎+̈́̎gf ̎ET ax̎x̎A9w̎w̎Eu̎&:s̎qǟqń̎o=̎lY̎Ri ̎eW̎巟aK̎.\ф̎w̟W̎;R̎UM̎OG̎A@̎!9̎$2̎jɟ+̎~#̎ϟӄ̎:ӟ̎]̎Ã^̎_̎J7̎̎PՄ̎̎Tq&̎ݟ̎Y̎M̎W݄̎ɟ}-̎gn̎}`[̎U/Q\̎B!̎ѐ2[̎"1̎L:΄̎%݄̎Ł̎yτ̎= ̎xma̎:}̎5̎'۟̎a}k̎W:̎ӕB̎ B-_̎DU̎|̎듄̎qʄ̎ ̎WI̎U̎hu̎]]A̎,/Db̎`]*߄̎'̎Ǎ ̎ԟ C̎-s 1̎_ ̎ )̎A m̎Q QK̎$ 4F̎U )̎v ]̎ -̎ ̎ ̎As ~̎oe ^ׄ̎F ?̎q ̎8 ̎# ܟ̎O ̎{ ل̎ş v`̎ S݄̎d 0̎&q ̎P N̎y ̎ ̎ z̎7 U̎O /̎B S̎i ⑄̎ Є̎ G̎m lZ̎͟ Dq̎'2 ̎K˟̎p)̎=̎ur̎ڵJ˄̎[ /̎ ̎A̎cg̎p̎C̎4̎̎̎%1̎CƟ]A̎b#.g̎̎-Ε̎_̎ثm̎|̎ke7̎~,̎̎Uh̎#̎ƭބ̎)̎clT̎Q2̎ ʄ̎y̎+@̎;H̎KF̎Z q̎iɟ ,̎x _̎S %̎ ]̎՟ ̎ vӄ̎O <̎̑ I̎٨ ̎} ̎ Sz̎a 5̎ p ̎= ̎" jf̎- 0!̎8 ܄̎C ̎N= R̎X} G ̎b{ Ȅ̎l҃̎u>̎~]̎#̎io̎ڟ*̎ t̎ɟ:̎s[̎۟̎ф̎Q̎̇G̎Ҵ̎џ̎ެhx̎E.3̎霟̎̎d̎۟E̎) ڄ̎5Е̎P̎\ ̎ ͟!Ƅ̎ џ灄̎R<̎џr̎8̎ m̎Ÿ(̎9̎nO̎Y̎ɟ̎7τ̎cf̎M,E̎̎[̎0}v̎C1̎̎ Χ̎(b̎Z̎C؄̎ 哄̎ N̎yq ̎6Ą̎S̎]:̎ɟ̎NM̎k̎钟&̎Q̎Οd̎ *W̎ҟ̎Ǘ̎ɟ{̎AC̹̎̎̎t̎şX/̎̎Q㥄̎`̎~՟o̎u4ք̎lQ̎b;L̎XS̎N)K„̎C}̎98̎.̎"b̎(i̎ J$̎Q߄̎y̎晟?U̎ڟ̎[˄̎̎VA̎ɟ̎᷄̎sr̎xm-̎i2̎Z}̎K(^̎;̎+IԄ̎̎ @J̎̎3`̎&{̎Ʃ6̎̎w̎=g̎}"̎k9݄̎XF̎ETS̎-ˍZNot`fo aƉ["$̎O linew10HHHH[ [[pVfo a e-ˍ %9ShefferaY00$̟s s+k s+aYk ş["$̎5 a a6[fo a4 e1*ˍDeutscrheNorm:'nMYGF7.UUBOOLESCHERINGEUNDALGEBREN03I131d8-ˍLLUndaY^^$̟sN]ASN]AaYSM۟["$̎B5 aB a_ofo a-ˍ~OderaY$̟s_S_aYS["$̎ӟ5YӟY,fo a-ˍ̪"NichtaYNN$̟sүSүaYSI{["$̎NUfo a3fo aү r-ˍ ShefferaY)w)w$̟sǟSǟaYSa["$̎ ;5 a ; a*0fo a*0 r1*ˍEineGPrarallelschaltungvonEingyangenvonGatternwirdalsdop-pSeltesHAnrwendungderselbSenVVariablenangesehen,skz.B.sindmit(fG(x1;x2);gn9(x1;x3))BzwreiEingyangex1 derbSeidenGatterfundgXparallelgescrhaltet.EineSerienscrhaltungvonGatternwirdalsEinsetzeneinerFVunk-tionineineandereFVunktionangesehen.Soistz.B.A(x1j[x2)\(x1\x 0ڍ2)realisierbardurcrhdiefolgendeZusammenschaltungvonGattern%;ݍ||$̟s̟$S̟݄S癍||$̟s̟? =S̟癄S$$̟s6(I%S6$S鰣_P_P$̟s GS鰣Sꑍ_U_U=%̟s\(Wd\(ꑄd_U_U=%̟s\(9˄d\(d_ɋ/_ɋT-/hRxф>(>_f a] as@-쯄 a(-쯄 a) a agNk"$̎sMڟ-I36̎#D-IR̎1̎~f߄"$̎~f>"$̎П'Ճ"$̎Z: a"$̟̎-IrNDajedeBoSolescrheFVunktioninAbbb(B2nCV;B)einePolynomfunkti-onpist,lyatsiesicrhdurchGatterdarstellen.DieShe er-OpSerationstelltpalleBoSolescrhenFVunktionendar,dennseianbt=(a\b).Danngelten!UTʍMRx20RA1c==UR(x1j\x1)20#=x1jx1;5 x1j\x2c==UR((x1j\x2)20x[(x1\x2)209)20#=UR(x1jx2)j(x1jx2);5 x1j[x2c==UR((x1j\x1)20x[(x2\x2)209)20#=UR(x1jx1)j(x2jx2):EbSenso|_lassensicrhalleGatterineindeutigerWVeisemitHilfederdisjunktivrenbzw.konjunktivenNormalformdarstellen.KV;'naH *6- cmcsc105- cmcsc104@ cmti12-Nff cmbx12,N cmbx12(!", cmsy10'g cmmi12&XQ cmr12q% cmsy6K cmsy8;cmmi62cmmi8Aacmr6|{Ycmr8qymsbm7 msbm10K`y cmr10< lcirclew10O linew10O line10u cmex10Y/