I. NÉHÁNY FONTOS FOGALOM

´ ANY ´ I. NEH FONTOS FOGALOM 1. Halmazok, rel´ aci´ ok, f¨ uggv´ enyek A matematika alapfogalma a halmaz, amely szemléletesen dolgok o ¨sszességét jelenti. Az al´ abbiakban az u ´gynevezett na´ıv halmazelméletet ismertetj¨ uk, a halmazelmélet rigor´ ozus megalapoz´ asa a matematikai logika t´ argyk¨ orébe tartozik. Kiindul´ asképpen adott halmaz az univerzum (alaphalmaz), amelyben minden dolog benne van, amit vizsg´ alunk. Ha adott egy A halmaz, akkor beszél¨ unk annak halmazelemeir˝ ol, jel¨ olés: a ∈ A, ha a egy dolog. Halmazr´ ol feltessz¨ uk, hogy b´ armely dologr´ ol egyértelm˝ uen eld¨ onthet˝ o, hogy a halmazba tartozike avagy nem, és feltessz´ uk, hogy az alaphalmaz elemei nem halmazok. Halmaz egy halmaz hatv´ anyhalmaza, amelynek elemei a halmaz o ¨sszes r´ eszhalmazai, azaz olyan halmazok, amelyeknek minden eleme szintén eleme a kiindul´ asként vett halmaznak. Jel¨ olések: a B halmaz hatv´ anyhalmaza P(B), illetve A ⊆ B, az A halmaz a B halmaz részhalmaza illetve a B halmaz tartalmazza az A halmazt. Két halmaz egyenl˝ o ha k¨ olcs¨ on¨ osen tartalmazz´ ak egym´ ast, jel¨ olés: A = B. Az A halmaz val´ odi r´ esze a B halmaznak ha részhalmaza B-nek, de nem egyenl˝ o vele, jel¨ olés: A ⊂ B. Kit¨ untetett halmaz az u ¨ reshalmaz, amelyre teljes¨ ul, hogy nincsen egyetlen eleme sem, jel¨ olés: ∅. Ez része b´ armely halmaznak. Halmazt megadhatunk felsorol´ assal, péld´ aul ha az A halmaz elemei a1 , a2 , a3 , a4 , akkor a szok´ asos jel¨ olés A = {a1 , a2 , a3 , a4 }, illetve kiv´ alaszthatjuk halmazunk elemeit egy adott halmaz elemei k¨ oz¨ ul valamely tulajdons´ aggal, jel¨ olés: A = {a ∈ B|P (a)}, ahol a B halmaz elemei k¨ oz¨ ul azok alkotj´ ak az A halmazt, amelyekre teljes¨ ul a P tulajdons´ ag. Tekints¨ uk a ´t a halmazm˝ uveleteket (a m˝ uvelet pontos fogalm´ ar´ ol és a halmazm˝ uveletek tulajdons´ agair´ ol kés˝ obb). Legyen A és B halmaz. Uni´ ojuk, A∪B az a halmaz, amelynek minden eleme eleme A-nak vagy B-nek. Metszet¨ uk, A ∩ B az a halmaz, amelynek minden eleme eleme A-nak és B-nek is. K¨ ul¨ onbs´ eg¨ uk, A \ B az a halmaz, amelynek minden eleme eleme A-nak de nem eleme B-nek. Ha két halmaz metszete az u ¨reshalmaz, akkor azt mondjuk, hogy diszjunkt halmazok. Ha az A halmaz része a B halmaznak, akkor A-nak B-re vonatkoztatott komplementere, A az a halmaz, amelynek minden eleme eleme B-nek de nem eleme A-nak. Szimmetrikus k¨ ul¨ onbs´ eg¨ uk, A4B olyan halmaz, amelynek minden eleme eleme vagy Anak vagy B-nek, de nem mindkett˝ onek. Ha A a P(B) hatv´ anyhalmaz nem¨ ures részhalmaza, akkor képezhetj¨ uk a A halmazrendszer ∪A, ∪A∈A A uni´ oj´ at, amely az a halmaz, amelynek minden eleme eleme legal´ abb egy A-beli A halmaznak. Képezhetj¨ uk a A halmazrendszer ∩A, ∩A∈A A metszetét, amely az a halmaz, amelynek minden eleme eleme mindegyik A-beli A halmaznak. Ha A = {A1 , A2 , . . . , An } véges n elemsz´ am´ u halmazrendszer, akkor az uni´ ora és a metszetre a szok´ asos jel¨ olés ∪ni=1 Ai illetve ∩ni=1 Ai . Legyen A és B nem¨ ures halmaz. Ekkor halmaz A és B Descartes-szorzata, amelynek elemei a rendezett elemp´ arok. Egy A-beli a és egy B-beli b elem hat´ aroz meg egy A × B Descartes-szorzatbeli (a, b) elemp´ art, a-t az elemp´ ar els˝ o és b-t az elemp´ ar m´ asodik tagj´ anak nevezz¨ uk, két elemp´ ar egyenl˝ o, ha megegyeznek els˝ o és m´ asodik tagjaik is. Legyen A1 , A2 , . . . , An halmaz. Ekkor halmaz A1 , A2 , . . . , An Descartes-szorzata, amelynek elemei a rendezett elem n-esek. Ai -beli ai elemek (i = 1, 2, . . . , n) hat´ aroznak meg egy A1 × A2 × · · · × An Descartes-szorzatbeli (a1 , a2 , . . . , an ) elem n-est, ai -t az elem n-es i-edik tagj´ anak nevezz¨ uk (i = 1, 2, . . . , n), két elem n-es egyenl˝ o, ha rendre megegyeznek i-edik tagjaik (i = 1, 2, . . . , n). Az A × B halmaz részhalmazait k´ etv´ altoz´ os rel´ aci´ oknak, az A1 × A2 × · · · × An halmaz részhalmazait n-v´ altoz´ os rel´ aci´ oknak nevezz¨ uk. Az A × A halmaz részhalmazait az A halmazon adott k´ etv´ altoz´ os homog´ en rel´ aci´ oknak, az A × A × · · · × A halmaz részhalmazait | {z } n−szer

1

2

az A halmazon adott homog´ en n-v´ altoz´ os rel´ aci´ oknak nevezz¨ uk. Rel´ aci´ ot, hasonl´ oan mint halmazt, felsorol´ assal vagy tulajdons´ aggal adhatunk meg. Az R ⊆ A×B rel´ aci´ o esetén az {a ∈ A| létezik b ∈ B u ´gy, hogy (a, b) ∈ R} halmazt az R rel´ aci´ o´ ertelmez´ esi tartom´ any´ anak, a B halmazt ´ er´ ekk´ eszlet´ enek, az R(A) = {b ∈ B| létezik a ∈ A u ´gy, hogy (a, b) ∈ R} halmazt k´ ephalmaz´ anak nevezz¨ uk. Egy a ∈ A elem k´ epe a képhalmaz R(a) = {b ∈ B| (a, b) ∈ R} részhalmaza. Az R−1 = {(b, a) ∈ B × A| (a, b) ∈ R} rel´ aci´ ot az R rel´ aci´ o inverz´ enek nevezz¨ uk. Homogén kétv´ altoz´ os rel´ aci´ oknak az al´ abbi fontos t´ıpusait szok´ as vizsg´ alni. Lagyen R ⊂ A× A homogén rel´ aci´ o. Azt modjuk, hogy az R rel´ aci´ o reflex´ıv, ha minden a ∈ A esetén (a, a) ∈ R; tranzit´ıv, ha (a, b) ∈ R és (b, c) ∈ R esetén (a, c) ∈ R; szimmetrikus, ha (a, b) ∈ R-b˝ ol (b, a) ∈ R k¨ ovetkezik; antiszimmetrikus, ha (a, b) ∈ R és (b, a) ∈ R esetén a = b. Rendez´ esi rel´ aci´ onak nevez¨ unk egy olyan kétv´ altoz´ os homogén rel´ aci´ ot, amely reflex´ıv, antiszimmetrikus és tranzit´ıv. Az A halmazon adott rendez´ esi rel´ aci´ o teljes (vagy line´ aris), ha minden a, b ∈ A elemre teljes¨ ul, hogy (a, b) ∈ A vagy (b, a) ∈ A. Ha az A halmazon adott egy (line´ aris) rendezési rel´ aci´ o, akkor azt is szoktuk mondani, hogy A (line´ arisan) rendezett halmaz. Ekvivalenciarel´ aci´ onak nevez¨ unk egy olyan kétv´ altoz´ os homogén rel´ aci´ ot, amely reflex´ıv, szimmetrikus és tranzit´ıv. Ehhez szorosan kapcsol´ od´ o fogalom egy halmaz oszt´ alyoz´ asa: legyen A egy halmaz és C részhalmazainak egy nem¨ ures rendszere, amely elemeit oszt´ alyoknak nevez¨ unk, u ´gy, hogy az oszt´ alyok p´ aronként diszjunktak és uni´ ojuk az egész A halmaz. A két fogalom kapcsolat´ ar´ ol sz´ ol az al´ abbi ´ ıt´ 1.1.All´ as. Legyen A egy nem¨ ures halmaz. Ha adva van egy S ekvivalenciarel´ aci´ o A-n, akkor az ekvivalenciaoszt´ alyok megad´ as´ aval, azaz egy oszt´ alyba sorolva egy adott elemmel rel´ aci´ oban a ´ll´ o elemeket az A halmaz oszt´ alyoz´ as´ at kapjuk. Megford´ıtva, ha adva van egy C oszt´ alyoz´ asa az A halmaznak, akkor ∪{C × C|C ∈ C} ekvivalenciarel´ aci´ o az A halmazon. Bizony´ıt´ as. Mivel ekvivalenciarel´ aci´ o reflex´ıv, az ekvivalenciaoszt´ alyok uni´ oja az egész A halmaz. Ha (a, c), (b, c) ∈ S akkor a szimmetria miatt (a, c), (c, b) ∈ S és a tranzitivit´ as miatt (a, b) ∈ S, és ismét a szimmetria miatt (b, a) ∈ S; ´ıgy ha (a, d) ∈ S akkor a tranzitivit´ as miatt (b, d) ∈ S és R(a) ⊆ R(b). Hasonl´ oan R(b) ⊆ R(a). Kaptuk, hogy ha az a és b elemek ekvivalenciaoszt´ alyainak metszete nem¨ ures, akkor egybeesnek. Megford´ıtva, az R = ∪{C × C|C ∈ C} rel´ aci´ o reflex´ıv, mivel az oszt´ alyok uni´ oja az egész A halmaz. Ha (a, b), (b, c) ∈ R akkor a, b és c ugyanannak az oszt´ alynak az elemei, ´ıgy sz¨ ukségképpen (a, c) ∈ R. Hasonl´ oan ha (a, b ∈ R) akkor a és b ugyanannak az oszt´ alynak az elemei, ´ıgy sz¨ ukségképpen (b, a) ∈ R. R val´ oban ekvivalenciarel´ aci´ o. Az R ekvivalenciarel´ aci´ o oszt´ alyainak halmaz´ at faktorhalmaznak nevezz¨ uk és A/R-rel jel¨ olj¨ uk. Az f ⊆ A × B rel´ aci´ or´ ol azt mondjuk, hogy (egyv´ altoz´ os) f¨ uggv´ eny vagy lek´ epez´ es, ha f értelmezési tartom´ anya az egész A halmaz, és minden a ∈ A elem f (a) = {b} képe egyelem˝ u halmaz. Azt mondjuk, hogy az f f¨ uggvény az a elemhez az f (a) = b elemet rendeli, illetve hogy az a elem k´ epe a b elem. Jel¨ olés: f : A → B, a 7→ f (a) = b. Anal´ og m´ odon hat´ arozhat´ o meg a t¨ obbv´ altoz´ os f¨ uggvény fogalma. Két f¨ uggv´ eny egyenl˝ o, ha megegyeznek értelmezési tartom´ anyaik és értékkészleteik, és ugyanahhoz az elemhez ugyanazt az elemet rendelik. Legegyszer˝ ubb f¨ uggvény az 1A : A → A, a 7→ a identikus lek´ epez´ es. Az f : A → B f¨ uggvényr˝ ol azt mondjuk, hogy injekt´ıv, ha f (a) = f (a0 )-b˝ ol a = a0 k¨ ovetkezik; azt mondjuk, hogy sz¨ urjekt´ıv, ha az f (A) képhalmaz az egész B értékkészlet; azt mondjuk, hogy bijekt´ıv, ha injekt´ıv és sz¨ urjekt´ıv. Két f¨ uggvény, f : A → B és g : B → C meghat´ arozza a kompoz´ıci´ oszorzatukat, a g ◦ f : A → C, a 7→ g ◦ f (a) = g(f (a)) f¨ uggvényt. Az al´ abbi a ´ll´ıt´ as bizony´ıt´ asa gyakorlat.

3

´ ıt´ 1.2.All´ as. Ha f : A → B, g : B → C és h : C → D f¨ uggvények, akkor (h◦g)◦f = h◦(g ◦f ). Egy f¨ uggvény inverze nem mindig f¨ uggvény. Ha egy f¨ uggvény (mint relći´ o) inverze is f¨ uggvény, akkor azt mondjuk, hogy invert´ alhat´ o f¨ uggv´ eny. Az invert´ alhat´ os´ agot jellemzhetj¨ uk az al´ abbi m´ odon. ´ ıt´ 1.3.All´ as. Legyen f : A → B f¨ uggvény. Az al´ abbi a ´ll´ıt´ asok ekvivalensek: (i) f invert´ alhat´ o f¨ uggvény; (ii) létezik g : B → A f¨ uggvény u ´gy, hogy f ◦ g = 1B és g ◦ f = 1A ; (iii) f bijekt´ıv f¨ uggvény. Bizony´ıt´ as. (i)=⇒(ii) Legyen g az f inverzf¨ uggvénye, ´ıgy nyilv´ an teljes¨ ul a (ii)-ben szerepl˝ o két tulajdons´ ag. (ii)=⇒(iii) Ha f (a) = f (a0 ) akkor g ◦ f = 1A miatt a = 1A (a) = g(f (a)) = g(f (a0 )) = 1A (a0 ) = a0 , és az injektivit´ as teljes¨ ul. Az f ◦ g = 1B tulajdons´ ag miatt f (A) ⊇ f (g(B)) = 1B (B) = B, és a sz¨ urjektivit´ as vil´ agos. (iii)=⇒(i) Mivel az f f¨ uggvény sz¨ urjekt´ıv, az f −1 inverzrel´ aci´ o értelmezési tartom´ anya az egész B halmaz. Az injektivit´ as miatt pedig az f −1 (b) halmaz egyelem˝ u. 2. M˝ uveletek, tulajdons´ agaik, algebrai strukt´ ur´ ak Legyen A egy nem¨ ures halmaz. A ∗ : A → A, a 7→ a∗ f¨ uggvényr˝ ol azt mondjuk, hogy egyv´ altoz´ os (un´ er) m˝ uvelet az A halmazon. A ∗ : A × A → A, (a, b) 7→ a ∗ b f¨ uggvényr˝ ol azt mondjuk, hogy k´ etv´ altoz´ os (bin´ er) m˝ uvelet az A halmazon. A ∗ : A × A × · · · × A → | {z } n−szer

A, (a1 , a2 , . . . , an ) 7→ ∗(a1 , a2 , . . . , an ) f¨ uggvényr˝ ol azt mondjuk, hogy n-v´ altoz´ os (n-´ er) m˝ uvelet az A halmazon. Ha az A halmazon adva van n darab ∗, ◦, . . . m˝ uvelet, akkor az (A, ∗, ◦, . . . ) rendezett elem n + 1-est n-m˝ uveletes algebrai strukt´ ur´ anak nevezz¨ uk. Az al´ abbi m˝ uveleti tulajdons´ agokat szok´ as tanulm´ anyozni. Ha m´ asként nem eml´ıtj¨ uk, m˝ uvelet alatt kétv´ altoz´ os m˝ uveletet fogunk érteni. Legyen (A, ∗) algebrai strukt´ ura. A ∗ m˝ uveletr˝ ol azt mondjuk hogy – asszociat´ıv, ha minden a, b, c ∈ A elemre (a ∗ b) ∗ c = a ∗ (b ∗ c); – kommutat´ıv, ha minden a, b ∈ A elemre a ∗ b = b ∗ a; – idempotens, ha minden a ∈ A elemre a ∗ a = a; – invert´ alhat´ o, ha minden a, b ∈ A elemhez létezik u, v ∈ A elem u ´gy, hogy a ∗ u = b és v ∗ a = b. Kit¨ untetett elem az – e ∈ A neutr´ alis elem: minden a ∈ A elem esetén e ∗ a = a ∗ e = a; – z ∈ A z´ eruselem: minden a ∈ A elem esetén z ∗ a = a ∗ z = z; – a ∈ A z´ erusoszt´ o: létezik b ∈ A u ´gy, hogy b 6= z és a ∗ b = z vagy b ∗ a = z, ahol z zéruselem; – az a ∈ A elem b ∈ A inverze: a ∗ b = b ∗ a = e, ahol e neutr´ alis elem. Azokat az elemeket, amelyeknek létezik inverz¨ uk, invert´ alhat´ o elemeknek vagy egys´ egeknek nevezz¨ uk. Azt mondjuk, hogy egy zéruselemet tartalmaz´ o strukt´ ura z´ erusoszt´ omentes, ha az egyed¨ uli zérusoszt´ o a zéruselem. Az a ∈ A elemmel lehet egyszer˝ us´ıteni, ha minden b, c ∈ A elem esetén abb´ ol, hogy a ∗ b = a ∗ c vagy b ∗ a = c ∗ a k¨ ovetkezik b = c. Legyen (A, ∗, ◦) algebrai strukt´ ura. Azt mondjuk, hogy – a ∗ m˝ uvelet disztribut´ıv a ◦ m˝ uveletre nézve, ha minden a, b, c ∈ A elemre a ∗ (b ◦ c) = (a ∗ b) ◦ (a ∗ c) és (a ◦ b) ∗ c = (a ∗ c) ◦ (b ∗ c); – a ∗ m˝ uvelet abszorbt´ıv a ◦ m˝ uveletre nézve, ha minden a, b, c ∈ A elemre a ∗ (a ◦ b) = a.

4

A k¨ ovetkez˝ o nevezetes strukt´ urat´ıpusokat vizsg´ alj´ ak leggyakrabban. Egym˝ uveletes strukt´ ur´ ar´ ol azt mondjuk, hogy – f´ elcsoport, ha a m˝ uvelet asszociat´ıv; – monoid, ha félcsoport, és létezik neutr´ alis eleme; – kommutat´ıv f´ elcsoport, ha félcsoport, és a m˝ uvelet kommutat´ıv; – f´ elh´ al´ o, ha kommutat´ıv félcsoport és a m˝ uvelet idempotens; – csoport, ha monoid és minden elemnek van inverze; – Abel- (vagy kommutat´ıv) csoport ha csoport és a m˝ uvelet kommutat´ıv. Legyen (A, +, ·) kétm˝ uveletes algebrai strukt´ ura, amelyben a két m˝ uvelet az o ¨sszead´ as és a szorz´ as. Az (A, +) strukt´ ur´ at addit´ıv, az (A, ·) strukt´ ur´ at multiplikat´ıv strukt´ ur´ anak nevezz¨ uk. Azt mondjuk, hogy az (A, +, ·) strukt´ ura – gy˝ ur˝ u, ha az addit´ıv strukt´ ura Abel-csoport, a multiplikat´ıv strukt´ ura félcsoport, és a szorz´ as disztribut´ıv az o ¨sszead´ asra nézve; – kommutat´ıv gy˝ ur˝ u, ha gy˝ ur˝ u és a szorz´ as kommutat´ıv; – egys´ egelemes gy˝ ur˝ u, ha legal´ abb kételem˝ u gy˝ ur˝ u és a multiplikat´ıv strukt´ ur´ aban létezik neutr´ alis elem. Gy˝ ur˝ uben szok´ as az addit´ıv neutr´ alis elemet null´ anak nevezni és 0-val jel¨ olni; az a elem addit´ıv inverzét ellentettjének nevezni és −a-val jel¨ olni; a multiplikat´ıv neutr´ alis elemet (ha létezik) egys´ egelemnek nevezni és 1-gyel jel¨ olni; az a elem multiplikat´ıv inverzét reciprok´ anak nevezni és a−1 -gyel jel¨ olni. Az asszociativit´ asb´ ol k¨ ovetkez˝ o egyszer˝ u tulajdons´ agok az al´ abbiak. ´ ıt´ 2.1.All´ as. Legyen (A, ·) félcsoport. Ekkor: (i) Tetsz˝ oleges sz´ am´ u tényez˝ ob˝ ol a ´ll´ o szorzat értéke f¨ uggetlen a z´ ar´ ojelezést˝ ol. (ii) Ha az (A, ·) strukt´ ura neutr´ alis elemes, akkor egyetlen neutr´ alis elem van az A félcsoportban, és ha az a ∈ A elemnek létezik a−1 inverze, akkor az egyértelm˝ u. Bizony´ıt´ as. (i) Legyen az a1 , . . . , an ∈ A elemek tetsz˝ olegesen z´ ar´ ojelezett szorzata tn , és legyen ln = (. . . ((a1 a2 )a3 ) . . . )an balrarendezett szorzat. Indukci´ oval n szerint bel´ atjuk, hogy tn = ln . n = 3 esetén az a ´ll´ıt´ as éppen a szorz´ as asszociativit´ asa. Tegy¨ uk fel, hogy n-nél kisebb tényez˝ os szorzatok (n > 3) tetsz˝ olegesen z´ ar´ ojelezhet˝ ok. Ha t n 6= ln akkor tn = tk u, ahol u az ak+1 , . . . , an elemek valamely szorzata. Indukci´ o alapj´ an tk = lk és u = ak+1 (ak+2 (. . . (an−1 an ) . . . )) jobbrarendezett szorzat, azaz az asszociativit´ as t¨ obbsz¨ ori alkalmaz´ as´ aval tn = lk (ak+1 (ak+2 (. . . (an−1 an ) . . . ))) = (lk ak+1 )(ak+2 (ak+3 (. . . (an−1 an ) . . . ))) = lk+1 (ak+2 (. . . (an−1 an ) . . . )) = · · · = ln−2 (an−1 an ) = ln−1 an = ln . (ii) Legyen e, f neutr´ alis elem. Ekkor mivel f neutr´ alis elem, ef = e, de mivel e is neutr´ alis elem, ef = f , azaz e = f . Ha aa−1 = a−1 a = e és ab = ba = e, akkor b = eb = (a−1 a)b = a−1 (ab) = a−1 e = a−1 . Mivel (multiplikat´ıve ´ırt) monoidban ha az a és b elemnek van inverze akkor az ab elemnek is van, b−1 a−1 , monoid egységei csoportot alkotnak (ellen˝ orizze!), az u ´gynevezett egys´ egcsoportot. Ha A egy halmaz, akkor az o ¨sszes A → A f¨ uggvény halmaz´ an a kompoz´ıci´ oszorz´ as m˝ uvelet, amelyre nézve a f¨ uggvények halmaza félcsoport 1.2 alapj´ an, amelyben az identikus leképezés neutr´ alis elem. 1.3 alapj´ an ezek k¨ oz¨ ul az egységek a bijekt´ıv leképezések, a permut´ aci´ ok, ezeknek a csoportja az A halmaz szimmetrikus csoportja. Gyakorlatként l´ assa be, hogy kommutat´ıv félcsoportban teljes¨ ulnek a hatv´ anyoz´ as azonoss´ agai. Gyakorl´ asképpen l´ assa be, hogy zéruselem csak egy lehet egy strukt´ ur´ aban,

5

monoidban egységgel lehet egyszer˝ us´ıteni, és hogy zéruselemes monoidban egység nem zérusoszt´ o. Legyen A egy halmaz, az u ´gynevezett ´ ab´ ec´ e, elemei a bet˝ uk. Képezz¨ unk a bet˝ ukb˝ ol (véges hossz´ u) szavakat, ezek k¨ oz¨ otti m˝ uvelet legyen a konkaten´ aci´ o, az egym´ asut´ an´ır´ as, amelyet asszociat´ıvnak tekint¨ unk. Kaptuk az u ´gynevezett szabad f´ elcsoportot. B˝ ov´ıts¨ uk ki az A a ´bécét u ´jabb bet˝ ukkel az A ∪ A−1 a ´bécévé, ahol A−1 = {a−1 | a ∈ A}. Tekints¨ uk az A ∪ A−1 a ´bécé bet˝ uib˝ ol képzett szavak W halmaz´ at, amelybe beleértj¨ uk az u ¨res sz´ ot is. Egy W -beli sz´ ot reduk´ alt alak´ unak nevez¨ unk, ha benne nem a ´ll egym´ as mellett a illetve a −1 alak´ u bet˝ u. Tetsz˝ oleges W -beli sz´ ohoz tartozik reduk´ alt alak´ u sz´ o, az aa −1 illetve a−1 a alak´ u sz´ orészletek helyébe az u ¨res sz´ ot ´ırva, esetleg t¨ obb lépésben. Legyen F a reduk´ alt alak´ u szavak halmaza (az u ¨res sz´ oval egy¨ utt). Két F -beli sz´ o konkaten´ altja legyen az egym´ asut´ an´ırt sz´ o (ami W eleme) reduk´ alt alakja (ez m´ ar biztosan F -beli), a konkaten´ aci´ ot ismét asszociat´ıvnak tekintve. Ekkor a konkaten´ aci´ o m˝ uvelet a reduk´ alt alak´ u szavak F halmaz´ an, amely erre a m˝ uveletre nézve csoport (ellen˝ orizze!), amelyet az A a ´bécé feletti szabad csoportnak nevez¨ unk. A disztributivit´ ast felhaszn´ alva kapjuk az al´ abbiakat. ´ ıt´ 2.2.All´ as. Legyen az (A, +, ·) strukt´ ura gy˝ ur˝ u. Ekkor: (i) az addit´ıv neutr´ alis elem multiplikat´ıv zéruselem; (ii) minden a ∈ A elemre (−a)b = a(−b) = −(ab) és (−a)(−b) = ab; (iii) ha (A, +, ·) egységelemes gy˝ ur˝ u, akkor minden a ∈ A elemre −a = (−1)a. Bizony´ıt´ as. (i) Legyen a ∈ A. Ekkor, mivel 0 addit´ıv neutr´ alis elem, és a disztribut´ıv t¨ orvény teljes¨ ul, 0a = (0 + 0)a = 0a + 0a, és mindkét oldalhoz hozz´ aadva −0a-t kapjuk, hogy 0 = 0a. Hasonl´ oan ad´ odik, hogy 0 = a0. (ii) Legyen a, b ∈ A. Ekkor, felhaszn´ alva a disztributivit´ ast és (i)-et, ab + (−a)b = (a + (−a))b = 0b = 0, azaz ab ellentettje (−a)b. Hasonl´ oan ab az a(−b) elem ellentettje is. Ezt a két tényt alkalmazva ad´ odik, hogy (−a)(−b) = ab. (iii) A (ii)-es a ´ll´ıt´ as szerint (−a)b = −ab; legyen a = 1. Gyakorl´ asképpen l´ assa be, hogy kommutat´ıv gy˝ ur˝ uben teljes¨ ul a binomi´ alis tétel. A kommutat´ıv, egységelemes és zérusoszt´ omentes gy˝ ur˝ ut integrit´ astartom´ anynak nevezz¨ uk. A kommutat´ıv, egységelemes gy˝ ur˝ ut, amelyben minden nemnulla elemnek van multiplikat´ıv inverze, testnek nevezz¨ uk. Gyakorl´ asként bizony´ıtsa be, hogy test integrit´ astartom´ any. Az (A, ∨, ∧) strukt´ ur´ at – h´ al´ onak nevezz¨ uk, ha az (A, ∨) és a (A, ∧) strukt´ ura félh´ al´ o, és mindkét m˝ uvelet abszorbt´ıv a m´ asikra nézve. – disztribut´ıv h´ al´ onak nevezz¨ uk, ha h´ al´ o, és mindkét m˝ uvelet disztribut´ıv a m´ asikra nézve. Szok´ as a ∨ m˝ uveletet diszjunkci´ onak, a ∧ m˝ uveletet konjunkci´ onak nevezni. A h´ al´ ok és a rendezett strukt´ ur´ ak k¨ oz¨ ott szoros kapcsolat a ´ll fenn. Legyen A rendezett halmaz a ≤ rel´ aci´ ora nézve. Ha a, b ∈ A, és min{a, b} olyan elem, hogy min{a, b} ≤ a, min{a, b} ≤ b, és ha c ≤ a, c ≤ b akkor c ≤ min{a, b}, akkor azt mondjuk, hogy min{a, b} az a és b elemek minimuma. Ha a, b ∈ A, és max{a, b} olyan elem, hogy a ≤ max{a, b}, b ≤ max{a, b}, és ha a ≤ c, b ≤ c akkor max{a, b} ≤ c, akkor azt mondjuk, hogy max{a, b} az a és b elemek maximuma. Azt mondjuk, hogy a A h´ al´ oszer˝ uen rendezett halmaz, ha b´ armely két elemnek létezik minimuma és maximuma. ´ ıt´ 2.3.All´ as. Legyen A egy halmaz. Ha (A, ∨, ∧) h´ al´ o, akkor az a ≤ b ha a ∨ b = b

6

rel´ aci´ oval A h´ al´ oszer˝ uen rendezett halmaz. Megford´ıtva, ha A h´ al´ oszer˝ uen rendezett halmaz a ≤ rel´ aci´ ora nézve, akkor az (A, max, min) strukt´ ura h´ al´ o. Bizony´ıt´ as. Legyen (A, ∨, ∧) h´ al´ o. Az idempotencia miatt a ∨ a = a és a ≤ rel´ aci´ o reflex´ıv. Ha a ≤ b és b ≤ a azaz a ∨ b = b és b ∨ a = a akkor a kommutativit´ as miatt a = b, és a ≤ rel´ aci´ o antiszimmetrikus. Ha a ≤ b, b ≤ c azaz a ∨ b = b és b ∨ c = c akkor a ∨ c = a ∨ (b ∨ c) = (a ∨ b) ∨ c = b ∨ c = c és a ≤ c, a tranzitivit´ as is vil´ agos. Legyen max{a, b} = a ∨ b. Ekkor a ∨ max{a, b} = a ∨ (a ∨ b) = (a ∨ a) ∨ b = a ∨ b = max{a, b}, és a ≤ max{a, b}; hasonl´ oan b ≤ max{a, b}. Ha a ≤ c és b ≤ c azaz a ∨ c = c és b ∨ c = c akkor max{a, b} ∨ c = (a ∨ b) ∨ c = a ∨ (b ∨ c) = a ∨ c = c és max{a, b} ≤ c, a maximalit´ as teljes¨ ul. Hasonl´ oan kapjuk, hogy a ∧ b minimum (ellen˝ orizze!). Megford´ıtva, legyen A h´ al´ oszer˝ uen rendezett halmaz. Az (A, min) p´ ar nyilv´ an algebrai strukt´ ura. Asszociativit´ as. Legyen u = min{min{a, b}, c} és v = min{a, min{b, c}}. Ekkor u ≤ min{a, b} és u ≤ c, ahonnan u ≤ a, u ≤ b és u ≤ c. Innen u ≤ a és u ≤ min{b, c}, ad´ odik, hogy u ≤ v. Anal´ og m´ odon v ≤ u (ellen˝ orizze!), és az antiszimmetria miatt u = v. Kommutativit´ as, idempotencia. Ezek a tulajdons´ agok nyilv´ anval´ oak a m˝ uvelet defin´ıci´ oj´ ab´ ol. Az (A, min) p´ ar val´ oban félh´ al´ o. Hasonl´ oan kapjuk, hogy az (A, max) p´ ar is félh´ al´ o (ellen˝ orizze!). A két abszorbt´ıv tulajdons´ agb´ ol csak az egyiket tekintj¨ uk, a m´ asik bizony´ıt´ asa gyakorlat. Legyen c = min{a, max{a, b}}. Ekkor nyilv´ an c ≤ a. Tov´ abb´ a a ≤ a és a ≤ max{a, b} miatt a ≤ min{a, max{a, b}} = c, ´ıgy az antiszimmetri´ ab´ ol ad´ odik, hogy a = c. Bel´ attuk az o ¨sszes h´ al´ otulajdons´ agot. Legyen 0 illetve 1 az (A, ∨, ∧) h´ al´ o eleme u ´gy, hogy minden a ∈ A elemre 0 ∨ a = a illetve 1 ∧ a = a. Ekkor 0-t a h´ al´ o z´ eruselem´ enek illetve 1-et a h´ al´ o egys´ egelem´ enek nevezz¨ uk. K¨ onnyen l´ athat´ o, hogy az induk´ alt rendezésre nézve a 0 a legkisebb, 1 a legnagyobb elem. Ha a, a ∈ A olyan elemek, hogy a ∨ a = 1 és a ∧ a = 0 akkor azt mondjuk, hogy a az a elem komplementuma. Boole-algebr´ anak nevezz¨ uk az olyan disztribut´ıv h´ al´ ot, amelyben létezik zéruselem és egységelem, és minden elemnek van komplementuma. Minim´ alis Boole-algebra az igaz és hamis logikai értékek halmaza a ,,vagy” és az ,,és” m˝ uveletekkel. Gyakorl´ asképpen l´ assa be, hogy Boole-algebr´ aban a komplementum egyértelm˝ u. Boole-algebr´ aban teljes¨ ulnek az u ´gynevezett De Morgan-t¨ orvények: ´ ıt´ 2.4.All´ as. Boole-algebra a, b elemeire a ∨ b = a ∧ b és a ∧ b = a ∨ b. Bizony´ıt´ as. Csak az egyik azonoss´ agot l´ atjuk be, a m´ asik bizony´ıt´ asa gyakorlat: (a ∨ b) ∨ (a ∧ b) = a ∨ (b ∨ a ∧ b) = a ∨ ((b ∨ a) ∧ (b ∨ b)) = a ∨ ((b ∨ a) ∧ 1) = a ∨ (b ∨ a) = (a ∨ a) ∨ b = 1 ∨ b = 1 illetve (a ∨ b) ∧ (a ∧ b) = ((a ∨ b) ∧ a) ∧ b) = ((a ∧ a) ∨ (b ∧ a)) ∧ b = (0 ∨ (b ∧ a)) ∧ b = (b ∧ a) ∧ b = (b ∧ b) ∧ a = 0 ∧ a = 0. Innen k¨ ovetkezik az els˝ o De Morgan-t¨ orvény. Legyen H egy halmaz. A P(H) hatv´ anyhalmaz nem¨ ures részhalmaz´ at az uni´ o és a metszet m˝ uveletével egy¨ utt halmaztestnek nevezz¨ uk, ha z´ art az uni´ o, a metszet és a komplementer képzésére nézve. Alapvet˝ o fontoss´ ag´ ua

7

2.5.T´ etel. Halmaztest Boole-algebra. Bizony´ıt´ as. Legyen H a halmaztest. A (H, ∪) p´ ar nyilv´ an strukt´ ura. H´ arom halmaz uni´ oj´ anak elemei, ak´ arhogyan z´ ar´ ojelezve, azok az elemek, amelyek legal´ abb az egyik halmazban benne vannak, ´ıgy az uni´ oképzés asszociat´ıv. Két halmaz uni´ oj´ anak elemei, b´ armilyen sorrendben, azok az elemek, amelyek legal´ abb az egyik halmazban benne vannak, ´ıgy az uni´ oképzés kommutat´ıv. Egy halmaznak o ¨nmag´ aval vett uni´ oj´ anak elemei nyilv´ an a halmaz elemei, ´ıgy az uni´ oképzés idempotens. A (H, ∪) strukt´ ura félh´ al´ o. Hasonl´ oan egyszer˝ u meggondol´ asokkal a (H, ∩) strukt´ ura is félh´ al´ o. A két abszorbt´ıv tulajdons´ agb´ ol az egyiket tekintj¨ uk, a m´ asik ellen˝ orzése gyakorlat. Legyen a ∈ A ∪ (A ∩ B). Ekkor a ∈ A vagy a ∈ A ∩ B, de A ∩ B részhalmaza A-nak, ´ıgy mindenképpen a ∈ A, azaz A ∪ (A ∩ B) ⊆ A. A ford´ıtott A ⊆ A ∪ (A ∩ B) tartalmaz´ as nyilv´ anval´ o, és A = A ∪ (A ∩ B). Eddig bel´ attuk, hogy (H, ∪, ∩) h´ al´ o. A két disztributivit´ asb´ ol csak az egyiket l´ atjuk be, a m´ asik gyakorlat. Legyen a ∈ A∪(B∩C). Ekkor a ∈ A vagy a ∈ B ∩ C. Innen vil´ agos, hogy az a elem benne van az A ∪ B halmazban és az A ∪ C-ben is. Így A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C). Legyen most a ∈ (A ∪ B) ∩ (A ∪ C). Ekkor a ∈ A ∪ B és a ∈ A ∪ C. Ha a ∈ A akkor nyilv´ an a ∈ A ∪ (B ∩ C). Ha a ∈ / A akkor sz¨ ukségképpen a ∈ B és a ∈ C is teljes¨ ul, azaz a ∈ B ∩ C ⊆ A ∪ (B ∩ C). Így (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C). A kétoldali tartalmaz´ as miatt a két halmaz megegyezik. Az uni´ o kommutativit´ asa miatt (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C). Nyilv´ anval´ o, hogy az u ¨reshalmaz illetve az egész H halmaz benne van a halmaztestben, és annak zéruseleme illetve egységeleme, tov´ abb´ a egy halmaz és komplementerének uni´ oja H, metszete az u ¨reshalmaz. Ennek a tételnek bizonyos értelemben igaz a megford´ıt´ asa is.

8

´ ´ ´ ´ II. A SZAMFOGALOM FELEP ITESE 3. A term´ eszetes ´ es eg´ esz sz´ amok Feltessz¨ uk, hogy adva van egy halmaz, a term´ eszetes sz´ amok halmaza, amelyet N-nel jel¨ ol¨ unk, elemei a term´ eszetes sz´ amok, és teljes¨ ulnek az al´ abbi u ´gynevezett Peano-axi´ om´ ak: (1) létezik egy null´ anak nevezett, 0-val jel¨ olt eleme N-nek; (2) létezik egy 0 : N → N, a 7→ a0 injekt´ıv leképezés, ahol az a0 természetes sz´ amot az a természetes sz´ am r´ ak¨ ovetkez˝ ojének nevezz¨ uk, és amelyre teljes¨ ul az al´ abbi két tulajdons´ ag: (3) nem létezik a ∈ N természetes sz´ am , amelyre a0 = 0; (4) (a teljes indukci´ o axi´ om´ aja) ha A az N halmaz részhalmaza, A-nak eleme a 0 és A tetsz˝ oleges elemével egy¨ utt tartalmazza annak r´ ak¨ ovetkez˝ ojét is, akkor A = N. A szok´ asos jel¨ olések és elnevezések: 0’=1 egy, 1’=2 kett˝ o, 2’=3 h´ arom, és ´ıgy tov´ abb. V´ egtelen halmaznak nevez¨ unk egy halmazt, ha létezik bijekci´ o a halmaz és val´ odi részhalmaza k¨ oz¨ ott. A r´ ak¨ ovetkezés leképezés bijekci´ o az N és N \ {0} halmazok k¨ oz¨ ott (ellen˝ orizze!), ezért a természetes sz´ amok halmaza végtelen. Ellenkez˝ o esetben v´ eges halmazr´ ol beszél¨ unk. Az utols´ o Peano-axi´ om´ an alapul a rekurz´ıv defin´ıci´ o m´ odszere. Természetes sz´ amot, mint paramétert tartalmaz´ o fogalmakat vagy elemeket hat´ arozunk meg oly m´ odon, hogy megadjuk a 0-hoz tartoz´ ot, és azt, hogy tetsz˝ oleges n természetes sz´ am esetén az n-hez tartoz´ o fogalom illetve elem ismeretében hogyan hat´ arozhat´ o meg az n0 r´ ak¨ ovetkez˝ oh¨ oz tartoz´ o. A term´ eszetes sz´ amok k¨ oz¨ otti o ¨sszead´ as ´ es szorz´ as m˝ uveletét ´ıgy defini´ aljuk: tetsz˝ oleges a ∈ N természetes sz´ amra legyen a+0 = a, a·0 = 0, tov´ abb´ a ha b ∈ N természetes sz´ am, akkor legyen a + b0 = (a + b)0 és ab0 = ab + a. Teljes¨ ulnek a megszokott m˝ uveleti tulajdons´ agok, mint azt l´ atni fogjuk. A bizony´ıt´ as m´ odszere a teljes indukci´ o: egy a ´ll´ıt´ ast, amelyet az o ¨sszes természetes sz´ amra l´ atunk be, az utols´ o Peano-axi´ oma alapj´ an elegend˝ o igazolni 0-ra és, feltételezve, hogy igaz valamely n természetes sz´ amra, n 0 -re. 3.1.T´ etel. (i) az (N, +) strukt´ ura kommutat´ıv félcsoport, amelyben lehet egyszer˝ us´ıteni, neutr´ alis eleme a 0; (ii) az (N, ·) strukt´ ura kommutat´ıv félcsoport, neutr´ alis eleme az 1, nemnulla elemmel lehet egyszer˝ us´ıteni; (iii) a szorz´ as az o ¨sszead´ asra nézve disztribut´ıv. Bizony´ıt´ as. Legyen a, b és c természetes sz´ am. (i) Asszociativit´ as. Nyilv´ an (a + b) + 0 = a + b = a + (b + 0), és tegy¨ uk fel, hogy (a + b) + c = a+(b+c). Ekkor, a defin´ıci´ o és az indukci´ os feltétel alkalmaz´ as´ aval (a+b)+c 0 = ((a+b)+c)0 = a + (b + c)0 = a + (b + c0 ). Neutr´ alis elem. A defin´ıci´ o szerint a + 0 = a. Nyilv´ an 0 + 0 = 0, és tegy¨ uk f¨ ol, hogy 0 + a = a. Ekkor 0 + a0 = (0 + a)0 = a0 . Kommutativit´ as. Mivel 0 neutr´ alis elem, a + 0 = 0 + a, és tegy¨ uk f¨ ol, hogy a + b = b + a. Ekkor a + b0 = (a + b)0 = (b + a)0 = b + a0 , ´ıgy elegend˝ o bel´ atni, hogy b + a0 = b0 + a, u ´jb´ ol indukci´ oval. Nyilv´ an b + 00 = (b + 0)0 = b0 = b0 + 0, és tegy¨ uk f¨ ol, hogy b + a0 = b0 + a. Ekkor b + a00 = (b + a0 )0 = (b0 + a)0 = b0 + a0 . Egyszer˝ us´ıtés. A kommutativit´ as miatt elég a jobboldali egyszer˝ us´ıtést bel´ atni. Mivel 0 neutr´ alis elem, a + 0 = b + 0-b´ ol k¨ ovetkezik a = b. Tegy¨ uk f¨ ol, hogy a + c = b + c esetén

9

a = b. Legyen a + c0 = b + c0 ; ekkor (a + c)0 = (b + c)0 , és a r´ ak¨ ovetkezés injektivit´ asa miatt a + c = b + c, ahonnan az indukci´ os feltétel miatt a = b k¨ ovetkezik. A (ii) a ´ll´ıt´ as bel´ at´ asa gyakorlat. A disztributivit´ ast is k¨ onnyen igazolhatjuk: a(b + 0) = ab = ab+0 = ab+a0, és tegy¨ uk f¨ ol, hogy a(b+c) = ab+ac. Ekkor a(b+c 0 ) = a(b+c)0 = a(b+c)+a = (ab + ac) + a = ab + (ac + a) = ab + ac0 . Mivel a szorz´ as kommutat´ıv, (a + b)c = ac + bc is teljes¨ ul. Azt mondjuk, hogy az a term´ eszetes sz´ am kisebb vagy egyenl˝ o mint a b természetes sz´ am, ha valamely c természetes sz´ amra b = a + c, jel¨ olés: a ≤ b, illetve az éles egyenl˝ otlenségé a < b. Gyakorl´ asképpen l´ assa be, hogy ez line´ aris rendezés a természetes sz´ amok halmaz´ an, és természetes sz´ amok tetsz˝ oleges nem¨ ures halmaz´ aban van legkisebb elem. Nyilv´ an a 0 minim´ alis elem. A természetes sz´ amok k¨ orében a négy alapm˝ uvelet k¨ oz¨ ul kett˝ ot el lehet végezni. Ahhoz, hogy a kivon´ ast is el lehessen végezni, b˝ ov´ıteni kell a sz´ amhalmazt. Legyen a 1 és a2 természetes sz´ am. Az a1 − a2 k¨ ul¨ onbséget (ami nem biztos, hogy természetes sz´ am) jelképezze az (a1 , a2 ) kissebb´ıtend˝ o – kivonand´ o elemp´ ar. Ennek megfelel˝ oen két elemp´ ar megegyezik, ha ugyanannyi az a1 − a2 = b1 − b2 k¨ ul¨ onbség¨ uk, azaz a1 + b2 = a2 + b1 . Az o ¨sszead´ ast és a szorz´ ast is elvégezhetj¨ uk a kissebb´ıtend˝ o – kivonand´ o elemp´ arok k¨ oz¨ ott: (a1 −a2 )+(b1 −b2 ) = (a1 +b1 )−(a2 +b2 ) illetve (a1 −a2 )(b1 −b2 ) = (a1 b1 +a2 b2 )−(a1 b2 +a2 b1 ). Ezeket az észrevételeket szem el˝ ott tartva konstru´ alhatjuk meg az egész sz´ amokat. 3.2.T´ etel. Legyen Z = N × N Descartes-szorzat, és defini´ aljuk a ρ rel´ aci´ ot a Z halmazon a k¨ ovetkez˝ oképpen: (a1 , a2 )ρ(b1 , b2 ) ha a1 + b2 = a2 + b1 , Ekkor ρ ekvivalencia-rel´ aci´ o, (a1 , a2 ) ekvivalencia-oszt´ aly´ at jel¨ olje (a1 , a2 ), az ekvivalencia-oszt´ alyok faktorhalmaz´ at jel¨ olje Z. Legyen tov´ abb´ a (a1 , a2 ) + (b1 , b2 ) = (a1 + b1 , a2 + b2 ),

(a1 , a2 ) · (b1 , b2 ) = (a1 b1 + a2 b2 , a1 b2 + a2 b1 )

az o ¨sszead´ as és a szorz´ as m˝ uvelete. Ekkor a (Z, +, ·) strukt´ ura integrit´ astartom´ any. Bizony´ıt´ as. A bizony´ıt´ as folyam´ an felhaszn´ aljuk k¨ ul¨ on hivatkoz´ as nélk¨ ul a 3.1 tételt. Legyen a1 , a2 , b1 , b2 , c1 , c2 , d1 , d2 természetes sz´ am. A ρ rel´ aci´ o ekvivalencia. A ρ rel´ aci´ o reflex´ıv, mivel a 1 +a2 = a2 +a1 ; szimmetrikus, mivel ha ((a1 , a2 ), (b1 , b2 )) ∈ ρ azaz a1 + b2 = a2 + b1 akkor b1 + a2 = b2 + a1 azaz ((b1 , b2 ), (a1 , a2 )) ∈ ρ; tranzit´ıv, mivel ha ((a1 , a2 ), (b1 , b2 )) ∈ ρ és ((b1 , b2 ), (c1 , c2 )) ∈ ρ azaz a1 + b2 = a2 + b1 és b1 + c2 = b2 + c1 akkor a1 + b1 + c2 = a1 + b2 + c1 , ahonnan a1 + b1 + c2 = a2 + b1 + c1 , és egyszer˝ us´ıtés ut´ an a1 + c2 = a2 + c1 ad´ odik, azaz ((a1 , a2 ), (c1 , c2 )) ∈ ρ. A tov´ abbiakban legyen a = (a1 , a2 ), b = (b1 , b2 ), c = (c1 , c2 ), d = (d1 , d2 ). Az o ¨sszead´ as j´ oldefini´ alt. Legyen a = c és b = d, azaz a 1 + c2 = a2 + c1 és b1 + d2 = b2 + d1 . Be kell l´ atni, hogy a + b = c + d, azaz a1 + b1 + c2 + d2 = a2 + b2 + c1 + d1 . Ez igaz, ha a2 + b1 + c1 + d2 = a2 + b2 + c1 + d1 , ami teljes¨ ul, ha a2 + b1 + d2 = a2 + b2 + d1 , ami pedig a m´ asodik feltételb˝ ol k¨ ovetkezik. Az o ¨sszead´ as asszociat´ıv és kommutat´ıv. Nyilv´ anval´ o, mivel a természetes sz´ amok o ¨sszead´ asa is ilyen. A (0, 0) elem neutr´ alis elem, és a ellentettje −a = (a2 , a1 ). Vil´ agos, hogy (a1 , a2 ) + (0, 0) = (0, 0)+(a1 , a2 ) = (a1 , a2 ); tov´ abb´ a (a1 , a2 )+(a2 , a1 ) = (a2 , a1 )+(a1 , a2 ) = (a1 + a2 , a1 + a2 ) = (0, 0). Eddig bel´ attuk, hogy az addit´ıv strukt´ ura Abel-csoport. A szorz´ as j´ oldefini´ alt. Legyen a = c és b = d, azaz a1 + c2 = a2 + c1 és b1 + d2 = b2 + d1 . Be kell l´ atni, hogy ab = cd, azaz a1 b1 + a2 b2 + c1 d2 + c2 d1 = a1 b2 + a2 b1 + c1 d1 + c2 d2 .

10

Ez teljes¨ ul, ha (a1 b1 + c2 b1 ) + a2 b2 + c1 d2 + c2 d1 = a1 b2 + a2 b1 + c1 d1 + (c2 b1 + c2 d2 ) azaz (a1 + c2 )b1 + a2 b2 + c1 d2 + c2 d1 = a1 b2 + a2 b1 + c1 d1 + c2 (b1 + d2 ). A feltételeket felhaszn´ alva ez fenn´ all, ha (a2 + c1 )b1 + a2 b2 + c1 d2 + c2 d1 = a1 b2 + a2 b1 + c1 d1 + c2 (b2 + d1 ), egyszer˝ us´ıtve c1 b1 + a2 b2 + c1 d2 = a1 b2 + c1 d1 + c2 b2 . Ez teljes¨ ul, ha c1 (b1 + d2 ) + a2 b2 = (a1 + c2 )b2 + c1 d1 azaz a feltételek miatt c1 (b2 + d1 ) + a2 b2 = (a2 + c1 )b2 + c1 d1 , ami azonoss´ aghoz vezet. A szorz´ as asszociativit´ asa és kommutativit´ asa és az a tény, hogy (1, 0) neutr´ alis elem egyszer˝ uen l´ athat´ o be, gyakorlat. Disztributivit´ as. A szorz´ as kommutativit´ asa miatt elegend˝ o bel´ atni, hogy a(b + c) = ab + ac. Nyilv´ an a(b+c) = a(b1 + c1 , b2 + c2 ) = (a1 b1 + a1 c1 + a2 b2 + a2 c2 , a1 b2 + a1 c2 + a2 b1 + a2 c1 ), illetve ab + ac = (a1 b1 + a2 b2 , a1 b2 + a2 b1 ) + (a1 c1 + a2 c2 , a1 c2 + a2 c1 ) = (a1 b1 + a1 c1 + a2 b2 + a2 c2 , a1 b2 + a1 c2 + a2 b1 + a2 c1 ). Eddig bel´ attuk, hogy a (Z, +, ·) strukt´ ura kommutat´ıv egységelemes gy˝ ur˝ u. Az (a, 0) alak´ u elemeket azonos´ıthatjuk a természetes sz´ amokkal. L´ assuk be, hogy Z = {0, 1, 2, 3, . . . } ∪ {−1, −2, −3, . . . }. Val´ oban, a rendezés linearit´ asa miatt az a, b természetes sz´ amokra a = b + c vagy b = a + c valamely c természetes sz´ ammal, azaz (a, b) = (b + c, b) = (c, 0) vagy (a, b) = (a, a + c) = (0, c) = −(c, 0). Ezut´ an a zérusoszt´ omentesség k¨ ovetkezik 2.2-b˝ ol és abb´ ol, hogy nemnulla természetes sz´ ammal a szorz´ asn´ al lehet egyszer˝ us´ıteni. A (Z, +, ·) strukt´ ur´ at az eg´ esz sz´ amok gy˝ ur˝ uj´ enek, elemeit eg´ esz sz´ amoknak nevez¨ unk. A bizony´ıt´ as utols´ o részében eml´ıtett azonos´ıt´ assal a természetes sz´ amok N halmaz´ at az egész sz´ amok Z halmaz´ anak részhalmazaként tekintj¨ uk. A rendezést nyilv´ anval´ o m´ odon kiterjesztve az egész sz´ amokra u ´jb´ ol line´ aris rendezést kapunk, amelyben m´ ar nincsen legkisebb elem. Az 1,2,3,. . . sz´ amokat pozit´ıv, a -1,-2,-3,. . . sz´ amokat negat´ıv eg´ esz sz´ amoknak nevezz¨ uk. Ellen˝ orizze, hogy ha a ≤ b és c egész sz´ amok, d pozit´ıv egész sz´ am, akkor a + c ≤ b + c és ad ≤ bd. 4. A racion´ alis ´ es val´ os sz´ amok Az egész sz´ amok k¨ orében a negyedik alapm˝ uvelet, az oszt´ as nem mindig végezhet˝ o el. Ezért a k¨ ovetkez˝ o tételben bevezetj¨ uk a racion´ alis sz´ am fogalm´ at. A racion´ alis sz´ amokat egész sz´ amokb´ ol alkotott sz´ aml´ al´ o – nevez˝ o rendezett elemp´ arnak tekintj¨ uk, ahol a nevez˝ o nem o, ha a1 b2 = a2 b1 . Az o ¨sszead´ as m˝ uveletét k¨ oz¨ os nevez˝ ore lehet nulla. Két t¨ ort, aa12 és bb21 egyenl˝ hoz´ as ut´ an végezhetj¨ uk el, a szorz´ ast pedig a megszokott ,,sz´ aml´ al´ ot a sz´ aml´ al´ oval, nevez˝ ot a nevez˝ ovel” szab´ aly szerint. 4.1.T´ etel. Legyen Q = Z × Z \ {0} Descartes-szorzat, és a ρ ⊆ Q × Q rel´ aci´ o legyen a k¨ ovetkez˝ oképpen meghat´ arozva: ((a1 , a2 ), (b1 , b2 )) ∈ ρ ha a1 b2 = a2 b1 . Ekkor ρ ekvivalenciarel´ aci´ o, az ekvivalenciaoszt´ alyok halmaz´ at jel¨ olje Q, az (a 1 , a2 ) elemp´ arral reprezent´ alt ekvivaalyok k¨ oz¨ otti m˝ uveletek legyenek az al´ abbi m´ odon megadva: lenciaoszt´ alyt jel¨ olje aa21 . Az oszt´ a1 b1 a 1 b2 + a 2 b1 a 1 b1 a 1 b1 + = , = . a2 b2 a 2 b2 a 2 b2 a 2 b2 Ekkor a (Q, +, ·) strukt´ ura test. Bizony´ıt´ as. ρ ekvivalenciarel´ aci´ o. A ρ rel´ aci´ o nyilv´ an reflex´ıv és szimmetrikus. Ha ((a1 , a2 ), (b1 , b2 )) ∈ ρ és ((b1 , b2 ), (c1 , c2 )) ∈ ρ akkor a1 b2 = a2 b1 és b1 c2 = b2 c1 . Ekkor a1 c2 = a2 c1 teljes¨ ul, ha a1 b2 c2 = a2 b2 c1 (mivel b2 nemnulla) azaz a feltételekb˝ ol a2 b1 c2 = ´ a2 b1 c2 , ami azonoss´ ag. Igy ((a1 , a2 ), (c1 , c2 )) ∈ ρ, a tranzitivit´ as vil´ agos.

11

Legyen aa12 , bb12 , cc12 , dd12 ∈ Q ekvivalenciaoszt´ aly. Az o ¨sszead´ as és a szorz´ as m˝ uvelet, mivel nemnulla egész sz´ amok szorzata nemnulla. Az o ¨sszead´ as j´ oldefini´ alt. Legyen aa12 = cc21 és bb12 = dd12 , azaz a1 c2 = a2 c1 és b1 d2 = b2 d1 . 2 b1 2 d1 = c1 dc22+c , azaz (a1 b2 + a2 b1 )c2 d2 = Be kell l´ atni, hogy aa21 + bb21 = cc12 + dd21 , azaz a1 ba22+a b2 d2 a2 b2 (c1 d2 + c2 d1 ). A disztributivit´ ast és a feltételeket felhaszn´ alva ez teljes¨ ul, ha a 2 b2 c1 d2 + a2 b2 c2 d1 = a2 b2 c1 d2 + a2 b2 c2 d1 , ami azonoss´ ag. Az o ¨sszead´ as asszociat´ıv. Nyilv´ an a1 c1 b1 a 1 b2 + a 2 b1 c1 a 1 b2 c2 + a 2 b1 c2 + a 2 b2 c1 + + = + = , a2 b2 c2 a 2 b2 c2 a 2 b2 c2 m´ asrészr˝ ol a1 + a2

c1 b1 + b2 c2

=

b1 c2 + b 2 c1 a 1 b2 c2 + a 2 b1 c2 + a 2 b2 c1 a1 + = . a2 b2 c2 a 2 b2 c2

Az o ¨sszead´ as kommutat´ıv. A defin´ıci´ ob´ ol l´ atszik. 1 alis elem, és az aa21 oszt´ aly addit´ıv inverze −a Neutr´ alis elem, inverz. Nyilv´ an 10 neutr´ a2 . Eddig bel´ attuk, hogy az addit´ıv strukt´ ura Abel-csoport. A szorz´ as j´ oldefini´ alt. Legyen aa12 = cc12 és bb21 = dd12 , azaz a1 c2 = a2 c1 és b1 d2 = b2 d1 . Be kell l´ atni, hogy aa12 bb21 = cc12 dd12 , azaz aa21 bb21 = cc12 dd12 , azaz a1 b1 c2 d2 = a2 b2 c1 d1 , ami a két feltételt felhaszn´ alva azonoss´ aghoz vezet. K¨ ozvetlen sz´ amol´ as bel´ atni a szorz´ as asscociativit´ as´ at, kommutativit´ as´ at, azt, hogy 11 neutr´ alis elem, illetve a disztributivit´ ast (gyakorlat!). Eddig bel´ attuk, hogy a (Q, +, ·) strukt´ ura kommutat´ıv egységelemes gy˝ ur˝ u. Mivel 01 = {(0, a2 )| a2 ∈ Z \ {0}} és 11 = {(a1 , a1 )| a1 ∈ Z \ {0}}, ha aa21 nemnulla elem, akkor multiplikat´ıv inverze nyilv´ an aa12 , és a strukt´ ura test. A Q testet a racion´ alis sz´ amok test´ enek, elemeit racion´ alis sz´ amoknak nevezz¨ uk. alis sz´ amokat, ´ıgy az egész sz´ amok Z halAzonos´ıthatjuk az a egész sz´ amokat és az a1 racion´ maza részhalmaza a racion´ alis sz´ amok Q halmaz´ anak, és a racion´ alis sz´ amok k¨ oz¨ otti o ¨sszead´ as és szorz´ as az egész sz´ amok k¨ oz¨ otti o ¨sszead´ as és szorz´ as m˝ uveletének kiterjesztése, tov´ abb´ a minden racion´ alis sz´ am el˝ oa ´ll két egész sz´ am h´ anyadosaként. A rendez´ est kiterjeszthetj¨ uk a racion´ alis sz´ amokra nyilv´ anval´ o m´ odon, a rendezés tov´ abbra is line´ aris marad; vil´ agos az is, hogy mit ért¨ unk abszol´ ut ´ ert´ ek alatt. Gyakorl´ asképpen l´ assa be, hogy a, b racion´ alis ´ sz´ amokra |ab| = |a||b| és |a+b| ≤ |a|+|b|. Erdekes tulajdons´ ag, hogy m´ıg az egész sz´ amhoz van el˝ oz˝ o és r´ ak¨ ovetkez˝ o egész sz´ am, addig b´ armely két racion´ alis sz´ am k¨ oz¨ ott van egy harmadik racion´ alis sz´ am. Geometri´ ab´ ol tudjuk, hogy vannak nem o ¨sszemérhet˝ o szakaszok, azaz amelyek hossza nem racion´ alis sz´ am, péld´ aul az egységnégyzet a ´tl´ oj´ anak hossza. Ez azt mutatja, hogy a sz´ amfogalom tov´ abb b˝ ov´ıthet˝ o. Az al´ abbiakban ezt tessz¨ uk analitikus m´ odszerrel. Tekints¨ uk a racion´ alis sorozatokat, azaz az a : N → Q, n 7→ an leképezéseket. Ezek k¨ oz¨ ott vannak konvergensek, azaz olyanok, amelyekhez létezik olyan u racion´ alis sz´ am, hogy tetsz˝ olegesen kicsiny ε pozit´ıv racion´ alis sz´ amhoz létezik N természtes sz´ am, hogy az |u − an | < ε hacsak n > N . Ilyenkor azt mondjuk, hogy az an sorozat hat´ ar´ ert´ eke az u racion´ alis sz´ am, jel¨ olés: limn→∞ an = u. Nullsorozatnak nevezz¨ uk a null´ ahoz konverg´ al´ o racion´ alis sorozatot. Gyakorl´ asképpen l´ assa be, hogy a m˝ uveletek és a hat´ ar´ atmenet sorrendje felcserélhet˝ o: ha an és bn konvergens sorozatok, c racion´ alis sz´ am, akkor an + bn , can , an bn , illetve bn 6= 0, limn→∞ bn 6= 0 esetén abnn is konvergens sorozatok, és limn→∞ (an + bn ) = n→∞ an limn→∞ an + limn→∞ bn , limn→∞ can = c limn→∞ an , limn→∞ abnn = lim limn→∞ bn .

12

Vannak racion´ alis Cauchy-sorozatok: az an sorozat ilyen, ha minden ε tetsz˝ olegesen kicsiny pozit´ıv racion´ alis sz´ amhoz létezik N természetes sz´ am, hogy |a n −bm | < ε hacsak n, m > N . Nyilv´ anval´ oan konvergens sorozat Cauchy-tulajdons´ ag´ u (ellen˝ orizze!), a megford´ıt´ as nem teljes¨ ul: bizonyos racion´ alis Cauchy-sorozatok ,,irracion´ alis sz´ amokhoz konverg´ alnak”, azaz a racion´ alis pontok nem fedik be teljesen a sz´ amegyenest. Az irracion´ alis pontokkal kib˝ ov´ıtve a sz´ amfogalmat, és a m˝ uveleteket a folytonos hat´ ar´ atmenet seg´ıtségével értelmezve kapjuk a k¨ ovetkez˝ o tételt. 4.2.T´ etel. Legyen R a racion´ alis Cauchy-sorozatok halmaza, és legyen a ρ ⊆ R × R rel´ aci´ o a k¨ ovetkez˝ oképpen meghat´ arozva: (an , bn ) ∈ ρ ha an − bn nullsorozat. Ekkor a ρ rel´ aci´ o ekvivalenciarel´ aci´ o, az ekvivalenciaoszt´ alyok halmaz´ at jel¨ olje R. Az o ¨sszead´ as és a szorz´ as m˝ uveletét az R halmazon defini´ aljuk az al´ abbi m´ odon: a n + bn = an + bn ; an bn = an bn . Ekkor az (R, +, ·) strukt´ ura test. Bizony´ıt´ as. Legyen an , bn , cn , dn racion´ alis Cauchy-sorozat. ρ ekvivalenciarel´ aci´ o. Nyilv´ an a ρ rel´ aci´ o reflex´ıv és szimmetrikus. Legyen a n − bn és bn − cn nullsorozat, és legyen ε pozit´ıv racion´ alis sz´ am, N1 és N2 olyan természetes sz´ am, hogy |an − bn | < 2ε hacsak n > N1 és |bn − cn | < 2ε hacsak n > N2 . Ekkor |an − cn | = |(an − bn ) + (bn − cn )| ≤ |an − bn | + |bn − cn | < 2ε + 2ε = ε hacsak n > max{N1 , N2 }, azaz an − cn nullsorozat, és a ρ rel´ aci´ o tranzit´ıv. Az o ¨sszead´ as és a szorz´ as m˝ uvelet. Be kell l´ atni, hoyg Cauchy-sorozatok o ¨sszege és szorzata is Cauchy-tulajdons´ ag´ u. Legyen az N1 természetes sz´ am olyan, hogy |an − am | < 2ε hacsak n, m > N1 , és az N2 olyan, hogy |bn − bm | < 2ε hacsak n, m > N2 . Ekkor, ha n, m > max{N1 , N2 }, |(an +bn )−(am +bm )| = |(an −am )+(bn −bm )| ≤ |an −am |+|bn −bm | < 2ε + 2ε = ε, és az an + bn sorozat Cauchy-tulajdons´ ag´ u. Most l´ assuk be, hogy az an Cauchy-sorozat korl´ atos, azaz van olyan A pozit´ıv racion´ alis sz´ am, hogy |an | ≤ A minden n természetes sz´ amra. Val´ oban, legyen az N term´szetes sz´ am olyan, hogy |an − am | < 1 hacsak n, m > N . Vil´ agos, hogy A = max{|a1 |, |a2 |, . . . , |aN |, |aN +1 | + 1} megfelel˝ o korl´ at. Legyen az an sorozat korl´ atja az A racion´ alis sz´ am és a bn sorozat korl´ atja a B racion´ alis ε sz´ am. Legyen tov´ abb´ a az N1 természetes sz´ am olyan, hogy |an − am | < 2B hacsak n, m > N1 , ε és az N2 olyan, hogy |bn − bm | < 2A hacsak n, m > N2 . Ekkor, ha n, m > max{N1 , N2 }, |an bn − am bm | = |an bn − am bn + am bn − am bm | = |(an − am )bn + am (bn − bm )| ≤ |(an − am )bn | + |am (bn − bm )| = |an − am ||bn | + |am ||bn − bm | <

ε ε B+A = ε, 2B 2A

azaz az an bn sorozat is Cauchy-tulajdons´ ag´ u. Legyen α = an , β = bn , γ = cn , δ = dn az R halmaz elemei. Az o ¨sszead´ as és a szorz´ as j´ oldefini´ alt. Be kell l´ atni, hogy ha α = γ, azaz a n − cn nullsorozat, és β = δ, azaz bn − dn nullsorozat, akkor α + β = γ + δ, azaz (an + bn ) − (cn + dn ) = (an − cn ) + (bn − dn ) nullsorozat; illetve αβ = γδ, azaz an bn − cn dn = an (bn − dn ) + (an − cn )dn nullsorozat. Ez a két tulajdos´ ag azokb´ ol a nyilv´ anval´ o tényekb˝ ol ad´ odik, hogy nullsorozatok o ¨sszege nullsorozat, és egy korl´ atos sorozat és egy nullsorozat szorzata nullsorozat (ellen˝ orizze!). Az o ¨sszead´ as asszociat´ıv. Nyilv´ an (α + β) + γ = an + bn + γ = an + bn + cn és α + (β + γ) = α + bn + cn = an + bn + cn . Az o ¨sszead´ as kommutat´ıv. Nyilv´ an α + β = an + bn = bn + an = β + α. Neutr´ alis elem, ellentett. Nyilv´ an a konstans 0 sorozat oszt´ alya (azaz a nullsorozatok halmaza) neutr´ alis elem, és −α = −an . A szorz´ as asszociat´ıv. Nyilv´ an (αβ)γ = an bn γ = an bn cn és α(βγ) = αbn cn = an bn cn .

13

A szorz´ as kommutat´ıv. Nyilv´ an αβ = an bn = bn an = βα. Neutr´ alis elem, inverz. Nyilv´ an a konstans 1 sorozat oszt´ alya (azaz az 1-hez konverg´ al´ o sorozatok halmaza) neutr´ alis elem. Legyen α nemnulla elem, azaz nem a nullsorozatok halmaza. Be kell l´ atni, hogy van olyan sorozat az α halmazban, amelynek egyik tagja sem 0. Val´ oban, vegy¨ unk egy sorozatot az α halmazb´ ol. Nem lehet végtelen sok tagja 0, mivel azonnal l´ atjuk, hogy ekkor, Cauchy sorozat lévén, konverg´ alna a 0-hoz. Így csak véges sok tagja 0, ezek mindegyike a sorozat N -nél kisebbik index˝ u tagja. Ekkor az az a n sorozat, amelyik els˝ o N tagja 1, a t¨ obbi megegyezik az eredeti sorozattal, eleme az α oszt´ alynak, és egyik tagja sem 0. Nyilv´ an a1n is Cauchy-soroxat, és α1 = a1n a keresett reciprok. A disztributivit´ as nyilv´ anval´ o, bel´ at´ asa gyakorlat. A R testet a val´ os sz´ amok test´ enek, elemeit val´ os sz´ amoknak nevezz¨ uk. Azonos´ıthatjuk a racion´ alis konstans sorozatok oszt´ alyait és a racion´ alis sz´ amokat, ´ıgy a racion´ alis sz´ amok Q halmaza részhalmaza a val´ os sz´ amok R halmaz´ anak, és a val´ os sz´ amok k¨ oz¨ otti o ¨sszead´ as és szorz´ as a racion´ alis sz´ amok k¨ oz¨ otti o ¨sszead´ as és szorz´ as m˝ uveletének kiterjesztése, tov´ abb´ a minden val´ os sz´ am valamely racion´ alis sorozat hat´ arértéke, és minden val´ os Cauchy sorozat konvergens. A rendez´ est kiterjeszthetj¨ uk a val´ os sz´ amokra nyilv´ anval´ o m´ odon: α ≤ β, ha létezik an ∈ α, bn ∈ β sorozat, hogy an ≤ bn minden n sz´ amra; a rendezés tov´ abbra is line´ aris marad. Gyakorl´ asképpen l´ assa be, hogy b´ armely α, β pozit´ıv val´ os sz´ amhoz létezik n természetes sz´ am, hogy α ≤ nβ; minden nemelfajul´ o ny´ılt intervallumban végtelen sok racion´ alis sz´ am van; z´ art intervallumok cs¨ okken˝ o sorozat´ anak k¨ oz¨ os része nem¨ ures. 5. A komplex sz´ amok K¨ onnyen l´ athat´ o, hogy p´ aratlan foksz´ am´ u val´ os egy¨ utthat´ os polinomnak mindig van val´ os gy¨ oke, azonban péld´ aul az x2 + 1 polinomnak nincs val´ os gy¨ oke. Jel¨ olje az i szimb´ olum egy gy¨ okét, és nevezz¨ uk el k´ epzetes egys´ egnek, mivel nem val´ os, hanem ,,elképzelt” sz´ amr´ ol van sz´ o, hiszen négyzete −1. Tekints¨ uk az a1 + a2 i alak´ u form´ alis o ¨sszegeket, ahol az a1 val´ os sz´ amot val´ os r´ esznek, az a2 val´ os sz´ amot k´ epzetes r´ esznek nevezz¨ uk. Az o ¨sszead´ as és a szorz´ as m˝ uveletét végezz¨ uk el ahogyan megszoktuk kéttagok esetén, a kapott strukt´ ura minden, sz´ amokt´ ol elv´ art m˝ uveleti tulajdons´ aggal rendelkezik. Az a 1 + a2 i nemnulla elem reciprok´ anak megkereséséhez vegy¨ uk észre, hogy (a 1 + a2 i)(a1 − a2 i) = a21 + a22 nemnulla val´ os 1 = sz´ am, ´ıgy az egyenl˝ oséget az a21 + a22 és a1 + a2 i sz´ ammal elosztva kapjuk, hogy a1 +a 2i 1 (a − a i). A prec´ ız bizony´ ıt´ a shoz ezeket az ,,elk´ e pzelt” sz´ a mokat val´ o s r´ e sz – k´ e pzetes 2 2 1 2 a1 +a2 rész rendezett sz´ amp´ aroknak tekintj¨ uk. 5.1.T´ etel. Legyen C = R × R Descartes szorzat, és az o ¨sszead´ as és szorz´ as m˝ uveletét a k¨ ovetkez˝ oképpen hat´ arozzuk meg: (a1 , a2 ) + (b1 , b2 ) = (a1 + b1 , a2 + b2 ), (a1 , a2 )(b1 , b2 ) = (a1 b1 − a2 b2 , a1 b2 + a2 b1 ). Ekkor a (C, +, ·) strukt´ ura test. Bizony´ıt´ as. Legyenek a = (a1 , a2 ), b = (b1 , b2 ), c = (c1 , c2 ) a C halmaz elemei. Vil´ agos, hogy az o ¨sszead´ as és szorz´ as m˝ uvelet. A bizony´ıt´ as sor´ an hivatkoz´ as nélk¨ ul felhaszn´ aljuk a val´ os sz´ amok m˝ uveleti tulajdons´ agait. Az addit´ıv strukt´ ura Abel-csoport. Az asszociativit´ as és kommutativit´ as a val´ os sz´ amok o ¨sszead´ asa megfelel˝ o tulajdons´ againak k¨ ozvetlen k¨ ovetkezménye. Nyilv´ an (0, 0) neutr´ alis elem, az a elem ellentettje −a = (−a1 , −a2 ).

14

K¨ ozvetlen sz´ amol´ assal kapjuk, hogy egyrészt a(bc) = a(b 1 c1 − b2 c2 , b1 c2 + b2 c1 ) = (a1 b1 c1 − a1 b2 c2 − a2 b1 c2 − a2 b2 c1 , a1 b1 c2 + a1 b2 c1 + a2 b1 c1 − a2 b2 c2 ), m´ asrészt (ab)c = (a1 b1 − a2 b2 , a1 b2 + a2 b1 )c = (a1 b1 c1 − a2 b2 c1 − a1 b2 c2 − a2 b1 c2 , a1 b1 c2 − a2 b2 c2 + a1 b2 c1 + a2 b1 c1 ), amely sz´ amp´ arok megegyeznek. A szorz´ as kommutativit´ asa a defin´ıci´ ob´ ol l´ atszik. Neutr´ alis elem és inverz. Az (1, 0) elem nyilv´ an neutr´ alis elem. Legyen a nemnulla elem, azaz a1 vagy a2 nemnulla val´ os sz´ am. Ekkor a21 + a22 nemnulla, és (a1 , a2 )(

a1 −a2 , ) = (1, 0), a21 + a22 a21 + a22

−a2 1 azaz, a szorz´ as kommutativit´ as´ at is felhaszn´ alva, a nemnulla a elem reciproka ( a2a+a 2 , a2 +a2 ). 1 2 1 2 A disztributivit´ as k¨ ozvetlen sz´ amol´ as, gyakorlat. Bel´ attuk, hogy a strukt´ ura test.

A C strukt´ ur´ at a komplex sz´ amok test´ enek, elemeit komplex sz´ amoknak nevezz¨ uk. Azonos´ıthatjuk az (a, 0) alak´ u komplex sz´ amokat az a val´ os sz´ amokkal, ´ıgy a val´ os sz´ amok R halmaza részhalmaza a komplex sz´ amok C halmaz´ anak, és a komplex sz´ amok k¨ oz¨ otti o ¨sszead´ as és szorz´ as a val´ os sz´ amok k¨ oz¨ otti m˝ uveletek kiterjesztése. Legyen i = (0, 1). Ekkor a = (a1 , a2 ) = (a1 , 0) + (a2 , 0)i, illetve az a1 = (a1 , 0), a2 = (a2 , 0) azonos´ıt´ ast felhaszn´ alva a = a1 + a2 i, amely alakot a komplex sz´ am algebrai alakj´ anak nevezz¨ uk. A reciprok megkeresésénél m´ ar alkalmaztuk a komplex sz´ am konjug´ altj´ at: az a = a 1 +a2 i am. Ennek a m˝ uveletnek a tulajdos´ agai komplex sz´ am konjug´ altja az a = a1 − a2 i komplex sz´ az al´ abbiak. ´ ıt´ 5.2.All´ as. Legyenek a = a1 + a2 i és b = b1 + b2 i tetsz˝ oleges komplex sz´ amok. Ekkor: (i) a + b = a + b; (ii) ab = ab; (iii) a = a; (iv) aa = a21 + a22 val´ os sz´ am, és a = a pontosan akkor, ha a val´ os sz´ am. Bizony´ıt´ as. (i) Egyrészt a + b = (a1 + b1 ) + (a2 + b2 )i = (a1 + b1 ) − (a2 + b2 )i, m´ asrészt a + b = (a1 − a2 i) + (b1 − b2 i) = (a1 + b1 ) − (a2 + b2 )i. (ii) Egyrészt ab = (a1 b1 − a2 b2 ) + (a1 b2 + a2 b1 )i = (a1 b1 − a2 b2 ) − (a1 b2 + a2 b1 )i, m´ asrészt ab = (a1 − a2 i)(b1 − b2 i) = (a1 b1 − a2 b2 ) − (a1 b2 + a2 b1 )i. (iii),(iv). Az utols´ o két a ´ll´ıt´ as nyilv´ anval´ o. Az a = a1 + a2 i komplex sz´ amra p az ||a|| = a21 + a22 nemnegat´ıv val´ os sz´ amot a komplex 2 2 sz´ am norm´ aj´ anak illetve az |a| = a1 + a2 négyzetgy¨ okét abszol´ ut´ ert´ ek´ enek nevezz¨ uk. Az abszol´ ut érték tulajdons´ agai a megszokottak.

15

´ ıt´ 5.3.All´ as. Legyen a és b tetsz˝ oleges komplex sz´ am. (i) |a| ≥ 0 és a = 0 pontosan akkor, ha a = 0; (ii) (h´ aromsz¨ og-egyenl˝ otlenség) |a + b| ≤ |a| + |b|; (iii) |a − b| ≥ ||a| − |b||; (iv) |ab| = |a| |b|. Bizony´ıt´ as. (i) Nyilv´ anval´ o. (ii) Az egyenl˝ otlenség teljes¨ ul, ha ||a + b|| ≤ (|a| + |b|)2 , azaz (a + b)a + b = ||a|| + ||b|| + ab + ab ≤ ||a|| + ||b|| + 2|a||b|, otlenség fenn´ all, ha 4(a 1 b1 +a2 b2 )2 ≤ ehhez elegend˝ o, hogy ab+ab ≤ 2|a||b| legyen. Ez az egyenl˝ 4||a|| ||b||, azaz a21 b21 + a22 b22 + 2a1 a2 b1 b2 ≤ a21 b21 + a22 b22 + a21 b22 + a22 b21 . Egyszer˝ us´ıtés és a ´trendezés ut´ an a nyilv´ anval´ o 0 ≤ (a 1 b2 − a2 b1 )2 egyenl˝ otlenséget kapjuk. (iii) A h´ aromsz¨ og-egyenl˝ otlenségben el˝ osz¨ or a helyére ´ırjunk a − b-t: |a| ≤ |a − b| + |b|. azaz |a| − |b| ≤ |a − b|. M´ asodszor ´ırjunk b helyére b − a-t: |b| ≤ |a| + |b − a|. azaz |b| − |a| ≤ |a − b|. A kapott két egyenl˝ otlenségb˝ ol az a ´ll´ıt´ as k¨ ovetkezik. (iv) Elegend˝ o bel´ atni az ||ab|| = ||a|| ||b|| egyenl˝ oséget. Egyrészt ||ab|| = (a1 b1 − a2 b2 )2 + (a1 b2 + a2 b1 )2 = a21 b21 + a22 b22 + a21 b22 + a22 b21 , m´ asrészt ||a|| ||b|| = (a21 + a22 )(b21 + b22 ) = a21 b21 + a22 b22 + a21 b22 + a22 b21 .

Azonos´ıtsuk a Descartes-féle koordin´ atas´ık pontjait a val´ os rendezett sz´ amp´ arokkal, azaz a komplex sz´ amokkal, ilyenkor a s´ıkot Gauss-f´ ele sz´ ams´ıknak nevezz¨ uk. Ekkor a nemnulla komplex sz´ amot meghat´ arozhatjuk az odamutat´ o helyvektor hossz´ aval és ir´ ap nysz¨ ogével, és kapjuk a trigonometrikus alakot: a = a1 +a2 i = r(cos α+i sin α) ahol a r = a21 + a22 = |a| a helyvektor (és egy´ uttal a komplex sz´ am) hossza, és α = arg a a helyvektor ir´ anysz¨ oge vagy a komplex sz´ am argumentuma. Az a ´ttérés a nemnulla a = a1 + a2 i komplex sz´ am algebrai alakj´ ar´ ol a trigonometrikus alakra a k¨ ovetkez˝ oképpen lehetséges. Nyilv´ an a = a 1 + a2 i = a2 a1 a2 a1 + |a| )i, mivel az |a| és az |a| val´ os sz´ amok négyzet¨ osszege 1, valamely α sz¨ og koszinusz´ aval |a|( |a| π és szinusz´ aval egyenl˝ oek. Ha a1 = 0 és a2 > 0 akkor α = 2 ; ha a1 = 0 és a2 < 0 akkor α = 3π 2 ; a2 arctg a1 , ha a1 > 0; α= a2 π + arctg a1 , ha a1 < 0 ] intervallumbeli sz¨ oget ad meg.) (Ez a visszakeresés (− π2 , 3π 2 A trigonometrikus alakban egyszer˝ uen végezhet˝ o el a szorz´ as, oszt´ as, hatv´ anyoz´ as és a komplex gy¨ okvon´ as m˝ uvelete: az a nemnulla komplex sz´ a m n-edik gy¨ o k´ e nek (n ≥ 2) nevezz¨ uk √ az xn − a polinom komplex gy¨ okeit, és n a-val jel¨ olj¨ uk. Nevezetes tény, hogy ilyen komplex gy¨ ok n darab k¨ ul¨ onb¨ oz˝ o van. ´ ıt´ 5.4.All´ as. Legyen a és b tetsz˝ oleges nemnulla komplex sz´ am. Ekkor: (i) |ab| = |a| |b| és arg ab = arg a + arg b; (ii) (Moivre képlete) |an | = |a|n és arg an = n arg a, ahol n pozit´ıv egész; (iii) | ab | = |a| es arg ab = arg a − arg b; |b| ´ p √ √ (iv) | n a| = n |a| (ez ut´ obbi val´ os n-edik gy¨ okvon´ as) és arg n a = arg a+2kπ (k = 1, 2, . . . , n − n 1), ahol n > 1 egész.

16

Bizony´ıt´ as. (i) A hosszra vonatkoz´ o a ´ll´ıt´ as azonos 5.3.4-gyel. Az add´ıci´ os képleteket felhaszn´ alva (cos α + i sin α)(cos β + i sin β) = (cos α cos β − sin α sin β) + i(cos α sin β + sin α cos β) = cos(α + β) + i sin(α + β), ami az argumentumra vonatkoz´ oa ´ll´ıt´ ast adja. (ii) Vil´ agos az els˝ oa ´ll´ıt´ asb´ ol indukci´ oval. (iii) Mivel 1 = b 1b , kapjuk, hogy 1 = |1| = |b 1b | = |b| | 1b | az els˝ oa ´ll´ıt´ ast felhaszn´ alva, azaz 1 | 1b | = |b| . Tov´ abb´ a 0 = arg 1 = arg b 1b = arg b + arg 1b az els˝ o a ´ll´ıt´ ast felhaszn´ alva, azaz ´ ol az els˝ arg 1b = − arg b. Ujb´ oa ´ll´ıt´ ast alkalmazva kapjuk, amit be kellett l´ atni. (iv) A képlet n k¨ ul¨ onb¨ oz˝ o komplex sz´ amot hat´ aroz meg, ´ıgy elegend˝ o bel´ atni, hogy nedik hatv´ anyuk a, ami Moivre képlete és a szinusz, koszinusz f¨ uggvények peri´ odusa alapj´ an vil´ agos. Jelent˝ osek az u ´gynevezett n-edik komplex egys´ eggy¨ ok¨ ok (n ≥ 2): ezek az 1 komplex n-edik gy¨ okei, azaz a 2kπ 2kπ + i sin εk = cos n n komplex sz´ amok, amelyek a Gauss-féle sz´ ams´ıkon az egységk¨ ornek szab´ alyos n-sz¨ oget alkot´ o pontjai. Ezek k¨ oz¨ ul speci´ alisak azok, amelyek hatv´ anyaiként el˝ oa ´ll az o ¨sszes t¨ obbi n-edik egységgy¨ ok: ezek a primit´ıv n-edik egys´ eggy¨ ok¨ ok. Nem nehéz bel´ atni, hogy ε k primit´ıv pontosan akkor, ha k és n relat´ıv pr´ımek. Gyakorl´ asképpen bizony´ıtsa be, hogy az n-edik komplex egységgy¨ ok¨ ok a szorz´ asra nézve Abel-csoportot alkotnak, és az o ¨sszeg¨ uk zérus.

17

´ ´ III. ELEMI SZAMELM ELET 6. Oszthat´ os´ ag az eg´ esz sz´ amok k¨ or´ eben Azt mondjuk, hogy az a eg´ esz sz´ am osztja a b eg´ esz sz´ amot, ha létezik c egész sz´ am, hogy b = ac, jel¨ olés: a|b. Azt mondjuk, hogy a b eg´ esz sz´ am az a eg´ esz sz´ am asszoci´ altja, ha b = ac, ahol c egység, azaz 1 vagy −1; jel¨ olés: a ∼ b. Nyilv´ anval´ o, hogy az asszoci´ alts´ ag ekvivalenciarel´ aci´ o az egészek halmaz´ an (´ altal´ anos´ıtva az asszoci´ alts´ agi rel´ aci´ ot tetsz˝ oleges integrit´ astartom´ anyra ez érvényben marad). Oszthat´ os´ agi szempontb´ ol elem és asszoci´ altja k¨ oz¨ ott k¨ ul¨ onbs´ get tenni nem tudunk, ´ıgy az oszthat´ os´ agi tulajdons´ agok ink´ abb az elem asszoci´ alt oszt´ aly´ anak a saj´ atjai, azonban a k´ onnyebb érthet˝ oség kedvéért nem fogjuk ezt a felfog´ ast k¨ ovetni. Alapvet˝ o tulajdons´ agai az oszthat´ os´ agi rel´ aci´ onak az al´ abbiak: ´ ıt´ 6.1.All´ as. (i) Egész sz´ am osztja o ¨nmag´ at; (ii) ha az a egész sz´ am osztja a b egész sz´ amot, és a b egész sz´ am osztja a c egész sz´ amot, akkor a osztja a c egész sz´ amot; (iii) ha az a egész sz´ am osztja a b egész sz´ amot, és a b egész sz´ am osztja az a egész sz´ amot akkor az a és b egész sz´ amok asszoci´ altak; (iv) ha az a egész sz´ am osztja a b egész sz´ amot, és a osztja a c egész sz´ amot akkor a osztja a bu + cv egész sz´ amot, ahol u és v tetsz˝ oleges egész sz´ amok; (v) ha az a egész sz´ am osztja a c egész sz´ amot, és a b egész sz´ am osztja a d egész sz´ amot akkor az ab sz´ am osztja a cd sz´ amot. Bizony´ıt´ as. (i) Nyilv´ an a = a1. (ii) Ha b = as és c = bt, ahol s és t egész sz´ amok, akkor c = (as)t = a(st), és a osztja a c egész sz´ amot. (iii) Ha b = as és a = bt, ahol s és t egész sz´ amok, akkor b = bts. Ha b = 0, akkor a = bt = 0t = 0; ha b 6= 0 akkor b(1 − ts) = 0 és a zérusoszt´ omentesség miatt 1 − ts = 0 és ts = 1, azaz t és s egységek, az a és b egész sz´ amok asszoci´ altak. (iv) Ha b = as és c = at, ahol s és t egész sz´ amok, akkor bu + cv = asu + atv = a(su + tv) és a osztja a bu + cv egész sz´ amot. (v) Ha c = as és d = bt, ahol s és t egész sz´ amok, akkor cd = asbt = ab(st) és az ab sz´ am osztja a cd sz´ amot. A fentiek tetsz˝ oleges integrit´ astartom´ anyban igazak anal´ og bizony´ıt´ assal. Az els˝ o h´ arom a ´ll´ıt´ as azt jelenti, hogy az oszthat´ os´ ag rendezési rel´ aci´ o az asszoci´ alts´ agi oszt´ alyok halmaz´ an; az egészek esetén a természetes sz´ amok halmaz´ an. Nagy fontoss´ aggal b´ır a maradékos vagy euklideszi oszt´ as tétele. 6.2.T´ etel. A b és a nemnulla egész sz´ amokhoz egyértelm˝ uen létezik q és r egész sz´ am u ´gy, hogy b = aq + r és 0 ≤ r < |a|. Bizony´ıt´ as. Egzisztencia. Tekints¨ uk azokat az u egész sz´ amokat, amelyekre b − au ≥ 0. Ilyen egész sz´ amok léteznek, és ekkor a {b − au ∈ N| u ∈ Z} halmaz természetes sz´ amok nem¨ ures halmaza. Legyen ebben a halmazban b − aq = r a legkisebb elem. Ahhoz, hogy az r < |a| teljes¨ ulését bel´ assuk, az u ´gynevezett indirekt bizony´ıt´ ast alkamazzuk: feltessz¨ uk az ellenkez˝ ojét, és ellentmond´ ashoz jutunk. Ha az r ≥ |a| egyenl˝ otlenség a ´ll fenn, akkor r−|a| = b−a(q±1) ≥ 0 ellentmond r minim´ alis volt´ anak; ezért r < |a| val´ oban teljes¨ ul.

18

Unicit´ as. Indirekte érvel¨ unk. Legyen b = aq + r és b = aq 0 + r0 , ahol a q, q 0 k¨ ul¨ onb¨ oz˝ o és r, r 0 0 0 0 0 egészek teljes´ıtik a tétel feltételeit. Ekkor 0 = a(q − q ) + (r − r ) és |a||q − q | = |r − r | fenn´ all, ahol a baloldal nem kisebb, mint |a|, a jobboldal pedig kisebb, mint |a|, ellentmod´ as. A maradékos oszt´ as tételében szerepl˝ o a sz´ amot oszt´ onak, a b sz´ amot osztand´ onak, a q sz´ amot h´ anyadosnak, az r sz´ amot marad´ eknak nevezz¨ uk. A maradékos oszt´ ason alapul az euklideszi algoritmus. Legyen b és a nemnulla egész sz´ am, a vel¨ uk végzett maradékos oszt´ as h´ anyadosa legyen q1 , maradéka r1 . Az a és r1 nemnulla egész sz´ amokon végzett maradékos oszt´ as h´ anyadosa legyen q2 , maradéka r2 . Az r1 és r2 nemnulla egész sz´ amokon végzett ´ ´ıgy tov´ maradékos oszt´ as h´ anyadosa legyen q3 , maradéka r3 . Es abb. Mivel a maradékok természetes sz´ amok szigor´ u monoton cs¨ okken˝ o sorozat´ at alkotj´ ak, véges sok lépés ut´ an a maradék 0 kell, hogy legyen: Az rn−2 és rn−1 nemnulla egész sz´ amokon végzett maradékos oszt´ as h´ anyadosa qn , maradéka rn = 0, amely az algoritmus utols´ o lépése. Kaptuk a maradékos oszt´ asok k¨ ovetkez˝ o sorozat´ at: b = aq1 + r1 , 0 < r1 < |a| a = r 1 q2 + r 2 , 0 < r 2 < r 1 r1 = r 2 q3 + r 3 , 0 < r 3 < r 2 .............................. rn−3 = rn−2 qn−1 + rn−1 , 0 < rn−1 < rn−2 rn−2 = rn−1 qn + rn , 0 = rn < rn−1 . Ha a és b nemnulla egész sz´ amok, akkor legnagyobb k¨ oz¨ os oszt´ ojuknak nevezz¨ uk azt a d természetes sz´ amot, amelyre teljes¨ ul, hogy d osztja az a és a b sz´ amot is, és ha egy c egész sz´ am szintén osztja az a és a b sz´ amot, akkor c osztja a d sz´ amot is. Jel¨ olés: (a, b). A legnagyobb k¨ oz¨ os oszt´ o létezését az euklideszi algoritmus biztos´ıtja. ´ ıt´ 6.3.All´ as. B´ armely két nemnulla egész sz´ amnak létezik legnagyobb k¨ oz¨ os oszt´ oja, nevezetesen a rajtuk végrehajtott euklideszi algoritmus utols´ o nemnulla maradéka. Bizony´ıt´ as. Legyen b és a nemnulla egész sz´ am, b = aq1 + r1 , 0 < r1 < |a|

a = r 1 q2 + r 2 , 0 < r 2 < r 1 r1 = r 2 q3 + r 3 , 0 < r 3 < r 2 rn−3

.............................. = rn−2 qn−1 + rn−1 , 0 < rn−1 < rn−2

rn−2 = rn−1 qn + rn , 0 = rn < rn−1 . az euklideszi algoritmus. Az utols´ o lépés miatt az rn−1 természetes sz´ am osztja az rn−2 sz´ amot. Az utols´ o el˝ otti lépésben az egyenl˝ oség jobb oldal´ at vizsg´ alva az r n−1 sz´ am osztja az rn−2 qn−1 és rn−1 sz´ amokat, ´ıgy osztja az egyenl˝ oség jobb oldal´ at, ezért osztja az r n−3 ´ ´ıgy tov´ sz´ amot is. Es abb, visszafelé haladva a lépésekben kapjuk, hogy az r n−1 sz´ am osztja valamennyi maradékot. A m´ asodik lépésben az egyenl˝ oség jobb oldal´ at vizsg´ alva az r n−1 sz´ am osztja r1 q2 és r2 sz´ amokat, ´ıgy osztja az egyenl˝ oség jobb oldal´ at, ezért osztja az a sz´ amot is. Az els˝ o lépésben az egyenl˝ oség jobb oldal´ at vizsg´ alva az r n−1 sz´ an osztja aq1 és r1 sz´ amokat, ´ıgy osztja az egyenl˝ oség jobb oldal´ at, ezért osztja a b sz´ amot is, azaz az r n−1 sz´ am az a és b sz´ amok k¨ oz¨ os oszt´ oja.

19

Most legyen a c egész sz´ am az a és b sz´ amok k¨ oz¨ os oszt´ oja. Ekkor az algoritmus els˝ o lépésében a c sz´ am osztja az egyenl˝ oség bal oldal´ at és az aq 1 sz´ amot, ´ıgy osztja az r1 sz´ amot is. A m´ asodik lépésben a c sz´ am osztja az egyenl˝ oség bal oldal´ at és a r 1 q2 sz´ amot, ´ıgy osztja az ´ ´ıgy tov´ r2 sz´ amot is. Es abb, az algoritmusban el˝ orefelé haladva kapjuk, hogy a c sz´ am osztja az r1 , r2 , . . . , rn−2 sz´ amokat. Az utols´ o el˝ otti lépésben a c sz´ am osztja az egyenl˝ oség bal oldal´ at és a rn−2 qn−1 sz´ amot, ´ıgy osztja az rn−1 sz´ amot is. Az rn−1 sz´ am val´ oban legnagyobb k¨ oz¨ os oszt´ o. Vil´ agos, hogy legnagyobb k¨ oz¨ os oszt´ o egyértelm˝ uen létezik (ellen˝ orizze!). ´ ıt´ 6.4.All´ as. Az a és b nemnulla egész sz´ amok legnagyobb k¨ oz¨ os oszt´ oja fel´ırhat´ o au + bv alakban valamely u, v egészekre. Bizony´ıt´ as. Legyen b és a nemnulla egész sz´ am, b = aq1 + r1 , 0 < r1 < |a| a = r 1 q2 + r 2 , 0 < r 2 < r 1 r1 = r 2 q3 + r 3 , 0 < r 3 < r 2 .............................. rn−3 = rn−2 qn−1 + rn−1 , 0 < rn−1 < rn−2 rn−2 = rn−1 qn + rn , 0 = rn < rn−1 . az euklideszi algoritmus. Az els˝ o lépés alapj´ an r1 = a(−q1 ) + b, azaz az r1 maradék fel´ırhat´ o a keresett alakban. A m´ asodik lépés alapj´ an r2 = a − r1 q2 = a(1 + q1 q2 ) + b(−q2 ). Indukci´ o alapj´ an érvel¨ unk. Tegy¨ uk fel, hogy rk−2 = ae + bf és rk−1 = ag + bh teljes¨ ul valamely e, f, g és h egészekre. Ekkor az algoritmus k-adik lépése alapj´ an r k−2 = rk−1 qk−1 + rk , amibe behelyettes´ıtve a feltételeket kapjuk, hogy rk = a(e − gqk−1 ) + b(f − hqk−1 ), ami a k´ıv´ ant alak. K¨ ovetkezésképpen a legnagyobb k¨ oz¨ os oszt´ oval egyenl˝ o r n−1 maradék is fel´ırhat´ o a k´ıv´ ant alakban. A legnagyobb k¨ oz¨ os oszt´ o képzése m˝ uvelet a nemnulla egész sz´ amokon. Tulajdons´ agai az al´ abbiak. ´ ıt´ 6.5.All´ as. (i) A legnagyobb k¨ oz¨ os oszt´ o képzésére nézve a nemnulla természetes sz´ amok félh´ al´ ot alkotnak. (ii) Minden nemnulla a, b, c természetes sz´ amra (ac, bc) = (a, b)c. (iii) Minden nemnulla a, b, c természetes sz´ amra (a, b) = (a + bc, b). (iv) Minden nemnulla a, b, c természetes sz´ amra (a, b) = a pontosan akkor, ha az a sz´ am osztja a b sz´ amot. Bizony´ıt´ as. (i) A kommutativit´ as a defin´ıci´ o szimmetri´ aj´ ab´ ol vil´ agos. Szintén nyilv´ anval´ o az idempotencia. Az asszociativit´ as bel´ at´ as´ ahoz legyen a, b és c nemnulla természetes sz´ am, és u = ((a, b), c) illetve v = (a, (b, c)). Mivel u oszt´ oja az (a, b) legnagyobb k¨ oz¨ os oszt´ onak, osztja az a és a b sz´ amot, tov´ abb´ a a c sz´ amot is. Ezért osztja az a sz´ amot és a (b, c) legnagyobb k¨ oz¨ os oszt´ ot is. Ebb˝ ol kapjuk, hogy osztja ezek v legnagyobb k¨ oz¨ os oszt´ oj´ at. Hasonl´ oan ad´ odik, hogy v osztja az u sz´ amot, k¨ ovetkezésképp u = v. (ii) Mivel az (a, b) legnagyobb k¨ oz¨ os oszt´ o osztja az a sz´ amot és a b sz´ amot is, az (a, b)c sz´ am osztja az ac és bc sz´ amokat, k¨ ovetkezésképp osztja a legnagyobb k¨ oz¨ os oszt´ ojukat is, azaz (ac, bc) = (a, b)ct valamely t természetes sz´ amra. Nyilv´ an (ac, bc)r = ac és (ac, bc)s = bc valamely r, s természetes sz´ amokra, ´ıgy (a, b)ctr = ac és (a, b)cts = bc, ahonnan egyszer˝ us´ıtés

20

ut´ an (a, b)tr = a és (a, b)ts = b ad´ odik. Ekkor az (a, b)t sz´ am az a és b sz´ amok k¨ oz¨ os oszt´ oja, és osztania kell az (a, b) legnagyobb k¨ oz¨ os oszt´ ojukat is, azaz (a, b)tw = (a, b) valamely w egész sz´ amra. Ez csak akkor lehetséges, ha t = 1. (iii) Legyen u = (a, b) és v = (a + bc, b). Mivel az u sz´ am osztja az a és a b sz´ amokat is, osztja az a + bc és a b sz´ amokat, k¨ ovetkezésképp osztja a v legnagyobb k¨ oz¨ os oszt´ ojukat is. Mivel a v sz´ am osztja az a + bc és a b sz´ amokat is, osztja az a és a b sz´ amokat, k¨ ovetkezésképp osztja az u legnagyobb k¨ oz¨ os oszt´ ojukat is. Ez csak akkor lehetséges, ha u = v. (iv) Legyen (a, b) = a. Ekkor nyilv´ an az a sz´ am osztja a b sz´ amot. Megford´ıtva, tegy¨ uk fel, hogy az a sz´ am osztja a b sz´ amot. Ekkor a az a és b sz´ amok k¨ oz¨ os oszt´ oja. Egy m´ asik k¨ oz¨ os oszt´ o nyilv´ an osztja az a sz´ amot, ´ıgy ez legnagyobb k¨ oz¨ os oszt´ o. Azt mondjuk, hogy az a és b nemnulla eg´ esz sz´ amok relat´ıv pr´ımek, ha legnagyobb k¨ oz¨ os oszt´ ojuk 1. Fontos tulajdons´ ag az u ´gynevezett a ´ltal´ anos´ıtott pr´ımtulajdons´ ag: ha az a egész osztja a bc szorzatot, és a és b sz´ amok relat´ıv pr´ımek, akkor az a sz´ am osztja a c sz´ amot. b a és a (a,b) sz´ amok relat´ıv pr´ımek. (Ellen˝ orizze ezeket az Tov´ abb´ a nyilv´ anval´ o, hogy az (a,b) a ´ll´ıt´ asokat!). A fenti tulajdons´ agok érvényben maradnak egész sz´ amokra is, ha a tulajdons´ agokban az egyenl˝ oséget asszoci´ alts´ ag rel´ aci´ ora cserélj¨ uk ki; illetve a nemnulla egészek asszoci´ alts´ agi oszt´ alyai a legnagyobb k¨ oz¨ os oszt´ o képzésére nézve félh´ al´ ot alkotnak. A legnagyobb k¨ oz¨ os oszt´ o fogalma és (létezés esetén) a tulajdons´ agai a nyilv´ anval´ o m´ odon a ´ltal´ anos´ıthat´ ok integrit´ astartom´ anyokra. Azt mondjuk, hogy az a és b nemnulla egész sz´ amok legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose az m természetes sz´ am, ha az a és a b sz´ am is osztja az m sz´ amot, m´ assz´ oval k¨ oz¨ os t¨ obbsz¨ or¨ os¨ uk, és ha a c sz´ am szintén k¨ oz¨ os t¨ obbsz¨ or¨ ose az a és a b sz´ amoknak, akkor t¨ obbsz¨ or¨ ose az m sz´ amnak is. Jel¨ olés: [a, b]. A legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os nyilv´ an egyértelm˝ u, és a létezését 6.4-gyel egy¨ utt garant´ alja a ´ ıt´ 6.6.All´ as. Az m =

|ab| (a,b)

sz´ am az a és b nemnulla egész sz´ amok legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose.

|a| |b| = |b| (a,b) sz´ am k¨ oz¨ os t¨ obbsz¨ or¨ os. Bizony´ıt´ as. Nyilv´ an az m = |a| (a,b) Legyen a c egész az a és b egész sz´ amok k¨ oz¨ os t¨ obbsz¨ or¨ ose, azaz c = as = bt valmely s és a b a b t egészekre. Ekkor az (a,b) sz´ am osztja a (a,b) t sz´ amot, és, mivel az (a,b) és a (a,b) sz´ amok a a sz´ am osztja a t sz´ amot, azaz t = (a,b) u valamely u egészre. Kapjuk, relat´ıv pr´ımek, az (a,b) a hogy c = b (a,b) u = ±mu, azaz az m sz´ am osztja a c k¨ oz¨ os t¨ obbsz¨ or¨ ost. Az m sz´ am val´ oban legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os.

A m˝ uvelet tulajdons´ agai az al´ abbiak. ´ ıt´ 6.7.All´ as. (i) A nemnulla természetes sz´ amok a legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os képzésére nézve félh´ al´ ot alkotnak; (ii) Tetsz˝ oleges nemnulla a, b és c természetes sz´ amokra [ac, bc] = [a, b]c. Bizony´ıt´ as. Legyenek a, b és c nemnulla természetes sz´ amok. (i) A kommutativit´ as és az idempotencia a defin´ıci´ o k¨ ozvetlen k¨ ovetkezménye. Legyen u = [[a, b], c] és v = [a, [b, c]]. Bel´ atjuk, hogy az u sz´ am osztja a v sz´ amot, és megford´ıtva. Mivel az u sz´ am k¨ oz¨ os t¨ obbsz¨ or¨ os, az [a, b] és a c sz´ amok osztj´ ak u-t. Tov´ abb´ a, mivel az [a, b] sz´ am k¨ oz¨ os t¨ obbsz¨ or¨ os, az u sz´ amot osztj´ ak az a illetve a b, c sz´ amok is. Mivel a [b, c] sz´ am legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os, innen kapjuk, hogy az u sz´ amot osztja az a és a [b, c] sz´ am is. Tekintve, hogy a v sz´ am legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os, osztania kell az u sz´ amot. Hasonl´ oan érvelve ad´ odik, hogy a v sz´ am osztja az u sz´ amot, azaz u = v. Az asszociativit´ as vil´ agos.

21

(ii) Legyen [ac, bc] = u és [a, b]c = v. Bel´ atjuk, hogy az u sz´ am osztja a v sz´ amot, és megford´ıtva. Mivel az a és b sz´ am osztja az [a, b] legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ost, az ac és bc sz´ am osztja a v = [a, b]c sz´ amot. Ennélfogva az u legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os osztja a v sz´ amot. Mivel az ac és bc sz´ amok osztj´ ak az u legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ost, u = acs = bct valamely s és t egészekre. Egyszer˝ us´ıtve kapjuk, hogy as = bt, és az a és b sz´ am osztja az as sz´ amot. Ezért az [a, b] legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os is osztja az as sz´ amot, ´ıgy a v = [a, b]c sz´ am osztja az asc = u sz´ amot. A fenti tulajdons´ agok érvényben maradnak egész sz´ amokra is, ha a tulajdons´ agokban az egyenl˝ oséget asszoci´ alts´ ag rel´ aci´ ora cserélj¨ uk ki; illetve a nemnulla egészek asszoci´ alts´ agi oszt´ alyai a legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os képzésére nézve félh´ al´ ot alkotnak. Gyakorl´ asképpen l´ assa be, hogy a nemnulla természetes sz´ amokon a legnagyobb k¨ oz¨ os oszt´ o és a legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os m˝ uveletek k¨ olcs¨ on¨ osen abszorbt´ıvak, azaz az (N \ {0}, [], ()) strukt´ ura h´ al´ o. Az induk´ alt rendezés nyilv´ an az oszthat´ os´ ag. A legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os fogalma és (létezés esetén) a tulajdons´ agai a nyilv´ anval´ o m´ odon a ´ltal´ anos´ıthat´ ok integrit´ astartom´ anyokra. 1-nél nagyobb természetes sz´ amr´ ol azt mondjuk, hogy pr´ımsz´ am, ha valah´ anyszor oszt egy bc szorzatot (b és c egészek), akkor osztja legal´ abb egyik tényez˝ ojét is. 1-nél nagyobb u természetes sz´ amr´ ol azt mondjuk, hogy t¨ orzssz´ am, ha u = ab (a és b egészek) egy faktoriz´ aci´ oja, akkor valamelyik tényez˝ o egység, azaz 1 vagy -1. Ellentettjeikkel egy¨ utt pr´ımelemekr˝ ol illetve irreducibilis elemekr˝ ol beszél¨ unk. ´ ıt´ 6.8.All´ as. A pr´ımsz´ am és a t¨ orzssz´ am fogalma egybeesik. Bizony´ıt´ as. Legyen u pr´ımsz´ am, és tegy¨ uk fel, hogy u = ab alakban ´ırhat´ o. Mivel az u pr´ımsz´ am osztja az ab szorzatot, osztja legal´ abb egyik tényez˝ ojét is. Ha az u sz´ am osztja az a sz´ amot, azaz a = us valamely s egészre, akkor az u = usb egyenl˝ oségb˝ ol egyszer˝ us´ıtés ut´ an sb = 1 k¨ ovetkezik, azaz s egység, az a és u sz´ amok asszoci´ altak és a b sz´ am egység. Ha az u sz´ am osztja a b sz´ amot, akkor hasonl´ oan kapjuk, hogy a b és u sz´ amok asszoci´ altak és az a sz´ am egység. Az u sz´ am t¨ orzssz´ am is. Legyen most u t¨ orzssz´ am és oszt´ oja az ab szorzatnak. Feltehetj¨ uk, hogy az u sz´ am nem osztja az a sz´ amot. Mivel u t¨ orzssz´ am, u és a ekkor relat´ıv pr´ımek, és az a ´ltal´ anos´ıtott pr´ımtulajdons´ ag alapj´ an az u sz´ amnak osztania kell a b sz´ amot. Bel´ attuk, hogy u pr´ımsz´ am. Ez alapj´ an az egészeken nyilv´ an a pr´ımelem és az irreducibilis elem fogalma is egybeesik. Lényeges a k¨ ovetkez˝ o, sz´ amelmélet alaptételeként eml´ıtett 6.9.T´ etel. Tetsz˝ oleges 1-nél nagyobb természetes sz´ am sorrendt˝ ol eltekintve egyértelm˝ uen bonthat´ o fel pr´ımsz´ amok szorzat´ ara. Bizony´ıt´ as. Egzisztencia. Legyen a 1-nél nagyobb természetes sz´ am. L´ assuk be el˝ osz¨ or, hogy létezik pr´ımoszt´ oja. Ha maga a pr´ımsz´ am, akkor megtal´ altuk a pr´ımoszt´ ot. Ha nem, akkor nem t¨ orzssz´ am, ezért a = a1 t1 , ahol a1 , t1 1-nél nagyobb természetes sz´ amok. Ha a1 pr´ımsz´ am, megtal´ altuk a pr´ımoszt´ ot. Ha nem, akkor a1 nem t¨ orzssz´ am, ezért a1 = a2 t2 , ahol a2 , t2 1-nél ´ ´ıgy tov´ nagyobb természetes sz´ amok. Es abb, ez az elj´ ar´ as nem folytathat´ o csak véges sok lépésig, mivel a > a1 > a2 > · · · természetes sz´ amok szigor´ u monoton cs¨ okken˝ o sorozata, amelynek el˝ obb-ut´ obb az a sz´ am egy pr´ımoszt´ oj´ aban kell végz˝ odjék. Legyen u1 az a sz´ am pr´ımoszt´ oja. Ekkor a = u1 b1 . Ha b1 = 1 vagy pr´ımsz´ am, akkor megtal´ altuk a pr´ımtényez˝ os felbont´ ast. Ha nem, akkor b1 -nek van u2 pr´ımoszt´ oja, és a = ´ ´ıgy tov´ u1 u2 b2 . Ha b2 pr´ımsz´ am, akkor megtal´ altuk a pr´ımtényez˝ os felbont´ ast. Es abb, ez az elj´ ar´ as nem folytathat´ o csak véges sok lépésig, mivel a > b 1 > b2 > · · · természetes sz´ amok

22

szigor´ u monoton cs¨ okken˝ o sorozata, amelynek el˝ obb–ut´ obb az a sz´ am egy pr´ımoszt´ oj´ aban kell végz˝ odjék. Unicit´ as. Legyen a = u1 u2 · · · ur = v1 v2 · · · vs kétféle pr´ımtényez˝ os felbont´ as, r ≤ s. Mivel az u1 pr´ımsz´ am, amely osztja a jobboldali szorzatot, osztja valamelyik v i1 tényez˝ ojét. Mivel vi1 t¨ orzssz´ am, u1 = vi1 , a ´tindexelés és egyszer˝ us´ıtés ut´ an u1 u2 · · · ur−1 = v1 v2 · · · vs−1 , Ezt az elj´ ar´ ast folytatva r − 1 lépés ut´ an kapjuk, hogy u1 = v1 v2 · · · vs−r+1 , Mivel u1 t¨ orzssz´ am, ez csak u ´gy lehetséges, ha r = s és (az a ´tindexelések ut´ an) u 1 = v1 . ´ Ertelmeszer˝ uen az egész sz´ amok pr´ımtényez˝ os felbont´ as´ aban a tényez˝ ok lehetnek negat´ıv pr´ımelemek is, és a felbont´ as egyértelm˝ uségében az egységtényez˝ okt˝ ol is el kell tekinteni. ´ Altal´ anosan is teljes¨ ul, hogy ha egy integrit´ astartom´ anyban a maradékos oszt´ ast el lehet végezni, akkor teljes¨ ul az egyértelm˝ u pr´ımfaktoriz´ aci´ o. Legyen a és b nemnulla nem egység egész sz´ am, |a| = pk11 pk22 · · · pkr r és |b| = pl11 pl22 · · · plrr felbont´ as, ahol p1 , p2 , . . . , pr k¨ ul¨ onb¨ oz˝ o pr´ımsz´ amok, a nem k¨ oz¨ os pr´ımoszt´ ok egyik kitev˝ oje zérus. Ekkor (ellen˝ orizze!): min{k1 ,l1 } min{k2 ,l2 } p2

(a, b) = p1

max{k1 ,l1 } max{k2 ,l2 } p2

r ,lr } · · · pmin{k , [a, b] = p1 r

· · · prmax{kr ,lr } .

Nevezetes tényt k¨ oz¨ ol a ´ ıt´ 6.10.All´ as. Végtelen sok pr´ımsz´ am van. Bizony´ıt´ as. Indirekte érvel¨ unk. Legyen az o ¨sszes pr´ımsz´ am p 1 , p2 , . . . , pr , ahol r természetes sz´ am. Ekkor az 1 + p1 p2 · · · pr sz´ amnak egyrészt létezik pr´ımoszt´ oja a sz´ amelmélet alaptétele miatt, m´ asrészt a p1 , p2 , . . . , pr pr´ımsz´ amok k¨ oz¨ ul egyik sem osztja. 7. Diofantoszi egyenlet, kongruencia Egy egyenletet diofantoszi egyenletnek nevez¨ unk, ha egész megold´ asait keress¨ uk. Sokféle ilyen egyenletet vizsg´ altak, itt az els˝ ofok´ u k´ etismeretlenes diofantoszi egyenlettel ´ foglalkozunk. Altal´ anos alakja ax + by = c, ahol a, b nemnulla és c tetsz˝ oleges adott egész sz´ am. A megold´ as a k¨ ovetkez˝ oképpen lehetséges: 7.1.T´ etel. Legyen a, b nemnulla egész sz´ am és c tetsz˝ oleges egész sz´ am. Az ax + by = c diofantoszi egyenlet megoldhat´ o pontosan akkor, ha az (a, b) legnagyobb k¨ oz¨ os oszt´ o osztja a c sz´ amot. Tov´ abb´ a ha az (x0 , y0 ) egész sz´ amp´ ar megold´ asa a diofantoszi egyenletnek, akkor tetsz˝ oleges megold´ as b t (a, b) a y = y0 − t (a, b)

x = x0 +

alak´ u valamely t egészre, és minden ilyen (x, y) sz´ amp´ ar az egyenlet megold´ asa. Bizony´ıt´ as. Tegy¨ uk fel, hogy az egyenletnek az (x0 , y0 ) sz´ amp´ ar megold´ asa, azaz ax0 +by0 = c teljes¨ ul. Az egyenl˝ oség baloldal´ at osztja az (a, b) legnagyobb k¨ oz¨ os oszt´ o, ezért osztja a c sz´ amot is. Megford´ıtva, tegy¨ uk fel most azt, hogy az (a, b) legnagyobb k¨ oz¨ os oszt´ o osztja a c sz´ amot. A 6.4 a ´ll´ıt´ as alapj´ an au + bv = (a, b) teljes¨ ul valamely u, v egészekre, amely egyenl˝ oséget uc vc c egész sz´ ammal kapjuk, hogy a (a,b) + b (a,b) = c, és a diofantoszi egyenlet beszorozva a (a,b) megoldhat´ o.

23

Legyen ax0 + by0 = c és az (x, y) egész sz´ amp´ ar megold´ as, azaz ax + by = c. A két egyenl˝ oséget kivonva egym´ asb´ ol kapjuk, hogy a(x − x0 ) + b(y − y0 ) = 0. Elegend˝ o teh´ at az ax + by = 0 u ´gynevezett homog´ e n egyenlet a ´ ltal´ a nos megold´ a s´ a t megkeresni. a b t + b − (a,b) t = 0 tetsz˝ oleges t egész sz´ amra. Legyen az (x0 , y 0 ) sz´ amp´ ar Nyilv´ an a (a,b)

olyan, hogy ax0 + by 0 = 0, azaz ax0 = −by 0 . Leosztva az (a, b) legnagyobb k¨ oz¨ os oszt´ oval a b b kapjuk, hogy (a,b) x0 = − (a,b) y 0 . Mivel a (a,b) sz´ am osztja a baloldalt, és relat´ıv pr´ım az a b amhoz, az a ´ltal´ anos´ıtott pr´ımtulajdons´ ag miatt osztja az x 0 sz´ amot, azaz x0 = (a,b) t és (a,b) sz´ ab (a,b) t

b a = − (a,b) y 0 . Egyszer˝ us´ıtés ut´ an y 0 = − (a,b) t ad´ odik.

A megoldhat´ os´ ag ellen˝ orzése ut´ an a bizony´ıt´ as m´ odszert ad az euklideszi algoritmus seg´ıtségével az (x0 , y0 ) partikul´ aris megold´ as megkeresésére. Az a ´ltal´ anos megold´ ast a képletbe val´ o egyszer˝ u behelyettes´ıtés adja. Legyen m 1-nél nagyobb természetes sz´ am. Azt mondjuk, hogy az a eg´ esz sz´ am kongruens a b eg´ esz sz´ ammal modulo m ha az m sz´ am osztja a b − a k¨ ul¨ onbséget. Jel¨ olés: a ≡ b( mod m). Az m sz´ amot a kongruencia modulus´ anak nevezz¨ uk. A modulo m kongruencia tulajdons´ agai a k¨ ovetkez˝ ok: ´ ıt´ 7.2.All´ as. Legyen m, m0 1-nél nagyobb természetes sz´ am, a, b, c, d tetsz˝ oleges egész sz´ amok. Ekkor az al´ abbi a ´ll´ıt´ asok teljes¨ ulnek: (i) A modulo m kongruencia ekvivalenciarel´ aci´ o az egész sz´ amok halmaz´ an; (ii) ha a ≡ c( mod m) és b ≡ d( mod m), akkor a + b ≡ c + d( mod m) és ab ≡ cd( mod m); m (iii) ha az m sz´ am nem osztja a c sz´ amot és ac ≡ bc( mod m), akkor a ≡ b( mod (m,c) ); 0 0 (iv) ha a ≡ b( mod m) és a ≡ b( mod m ), akkor a ≡ b( mod [m, m ]) Bizony´ıt´ as. (i) A reflexivit´ as és a szimmetria vil´ agos. Legyen a ≡ b( mod m) és b ≡ c( mod m), azaz az m sz´ am osztja a b−a és c−b sz´ amokat is. Ekkor, mivel c−a = (c−b)+(b−a), az m sz´ am osztja a c − a sz´ amot is, azaz a ≡ c( mod m), ami a tranzitivit´ ast mutatja. (ii) Legyen a ≡ c( mod m) és b ≡ d( mod m), azaz az m sz´ am osztja a c − a és a d − b sz´ amokat. Ekkor, mivel (c + d) − (a + b) = (c − a) + (d − b) és cd − ab = cd − cb + cb − ab = c(d − b) + (c − a)b, az m sz´ am osztja a (c + d) − (a + b) és a cd − ab sz´ amot. Kaptuk, hogy a + b ≡ c + d( mod m) és ab ≡ cd( mod m). (iii) Legyen ac ≡ bc( mod m), azaz az m sz´ am osztja a bc − ac = (b − a)c sz´ amot, (b − a)c = m m c = (m,c) s, és az (m,c) sz´ am osztja a b − a sz´ amot, ms valamely s egészre. Innen (b − a) (m,c) m azaz a ≡ b( mod (m,c) ). (iv) Legyen a ≡ b( mod m) és a ≡ b( mod m0 ), azaz az m és az m0 sz´ am osztja a b − a sz´ amot. Ekkor, a legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os defin´ıci´ oja miatt az [m, m 0 ] legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os is osztja a b − a sz´ amot, azaz a ≡ b( mod [m, m0 ]). A modulo m kongruencia ekvivalenciaoszt´ alyait marad´ ekoszt´ alyoknak nevezz¨ uk. Egy oszt´ alyba azok az elemek tartoznak, amelyek ugyanazt a maradékot adj´ ak m-mel osztva maradékosan. Így a modulo m maradékoszt´ alyok sz´ ama éppen m: 0, 1, . . . , m − 1. ´ ıt´ 7.3.All´ as. Legyen m 1-nél nagyobb természetes sz´ am. A modulo m maradékoszt´ alyok Z m halmaza az a + b = a + b illetve az ab = ab m˝ uveletekre nézve kommutat´ıv egységelemes gy˝ ur˝ ut alkot.

Bizony´ıt´ as. A m˝ uveletek a 6.10.2 a ´ll´ıt´ as szerint j´ oldefini´ altak, a m˝ uveleti tulajdons´ agok a m˝ uveletek defin´ıci´ oja és az egész sz´ amok megfelel˝ o m˝ uveleti tulajdons´ againak a k¨ ovetkezményei. (A részletes kifejtés gyakorlat.)

24

A Zm gy˝ ur˝ ut modulo m marad´ ekoszt´ alygy˝ ur˝ unek nevezz¨ uk. Az ax ≡ b( mod m) egyismeretlenes els˝ ofok´ u kongruencia egyenlet megold´ as´ at visszavezethetj¨ uk a kétismeretlenes diofantoszi egyenlet megold´ as´ ara. 7.4.T´ etel. Legyen a nemnulla egész sz´ am, b tetsz˝ oleges egész sz´ am és m 1-nél nagyobb természetes sz´ am. Az ax ≡ b( mod m) egyismeretlenes els˝ ofok´ u kongruencia egyenlet megoldhat´ o pontosan akkor, ha az (a, m) legnagyobb k¨ oz¨ os oszt´ o osztja a b sz´ amot. A kongruencia m t, ahol az x0 egész a kongruegyenlet modulo m inkongruens o ¨sszes megold´ asa x = x0 + (a,m) encia egyenlet egy megold´ asa, és t = 0, 1, . . . , (a, m) − 1. Bizony´ıt´ as. Nyilv´ an a kongruencia egyenlet ekvivalens az ax + my = b diofantoszi egyenlettel, ´ıgy a kongruencia megoldhat´ os´ ag´ anak sz¨ ukséges és elegend˝ o feltétele vil´ agos 7.1 alapj´ an. m Szintén innen k¨ ovetkezik, hogy a kongruencia tetsz˝ oleges megold´ asa x = x 0 + (a,m) t alak´ u. Nyilv´ an 0 ≤ t ≤ (a, m) − 1 esetén ezek az értékek inkongruensek modulo m, és az o ¨sszes t¨ obbi érték kongruens ezek k¨ oz¨ ul valamelyikkel modulo m. 7.5.K¨ ovetkezm´ eny. A Zm maradékoszt´ alygy˝ ur˝ u test pontosan akkor, ha m pr´ımsz´ am. Bizony´ıt´ as. Ha a Zm gy˝ ur˝ u test, akkor minden nemnulla eleme egység, azaz az ax ≡ 1( mod m) kongruencia megoldhat´ o ha m nem osztja az a sz´ amot. Azonban ha m nem t¨ orzssz´ am, akkor van w val´ odi (nem egység és nem asszoci´ alt) oszt´ oja, és ekkor a wx ≡ 1( mod m) kongruencia nem oldhat´ o meg, noha m nem osztja a w sz´ amot. Megford´ıtva, ha m pr´ımsz´ am, akkor 1, 2, . . . , m − 1 sz´ amok mindegyike relat´ıv pr´ım m-hez, és minden 1 ≤ a ≤ m − 1 egészre az ax ≡ 1( mod m) kongruencia megoldhat´ o, azaz nemnulla maradékoszt´ alynak van multiplikat´ıv inverze. Ez azt jelenti, hogy a Z m maradékoszt´ alygy˝ ur˝ u test. Ezeket a testeket pr´ımelem˝ u testeknek szok´ as nevezni. Ha az a sz´ am relat´ıv pr´ım az m modulushoz, akkor az a maradékoszt´ alyt reduk´ alt marad´ ekoszt´ alynak nevezz¨ uk. Sz´ amukat, azaz a 0, 1, 2, . . . , m−1 sz´ amok k¨ oz¨ ul az m sz´ amhoz relat´ıv pr´ımek sz´ am´ at ϕ(m)-mel szok´ as jel¨ olni, és a ϕ f¨ uggvényt Euler-f´ ele ϕ-f¨ uggv´ enynek nevezni. Azt is mondhatjuk, hogy a modulo m maradékoszt´ alygy˝ ur˝ u egységeinek sz´ ama ϕ(m). ´ ekének meghat´ Ert´ aroz´ as´ ahoz sz¨ ukség van az al´ abbi formul´ ara, amelyben |W | a W halmaz elemeinek a sz´ am´ at jelenti. ´ ıt´ 7.6.All´ as. Legyen A véges halmaz, Ai az A halmaz részhalmaza (i = 1, 2, . . . , n). Ekkor |A1 ∪ A2 ∪ · · · ∪ An | = |A1 ∪A2 ∪· · ·∪An | = |A|−(|A1 |+|A2 |+· · ·+|An |)+(|A1 ∩A2 |+|A1 ∩A3 |+· · ·+|An−1 ∩An |)−· · ·+· · · +(−1)k

X

1≤i1
|Ai1 ∩ Ai2 ∩ · ∩ Aik | + · · · − · · · + (−1)n |A1 ∩ A2 ∩ · · · ∩ An |.

Bizony´ıt´ as. Indukci´ o alapj´ an érvel¨ unk. Az n = 2 esetben a nyilv´ anval´ o |A 1 ∪ A2 | = |A| − (|A1 | + |A2 |) + |A1 ∩ A2 | o ¨sszef¨ uggést adja a formula. Jel¨ olje an a formula jobb oldal´ anak az értékét. Tegy¨ uk fel, hogy a formula teljes¨ ul n − 1-re. L´ atjuk, hogy an−1 − an = |An | − (|A1 ∩ An | + |A2 ∩ An | + · · · + |An−1 ∩ An |) + · · · − · · · + (−1)k−1

X

1≤i1
|Ai1 ∩ Ai2 ∩ · ∩ Aik−1 ∩ An | + · · ·− · · ·+ (−1)n−1 |A1 ∩ A2 ∩ · · ·∩ An |.

25

Alkalmazva a formul´ at az A = An halmazra és az Ai ∩ An részhalmazaira (i = 1, 2, . . . , n − 1) kapjuk, hogy an−1 − an a B = An \ (A1 ∪ A2 ∪ · · · ∪ An−1 ) halmaz elemeinek a sz´ ama. Vil´ agos, hogy az A1 ∪ A2 ∪ · · · ∪ An−1 halmaz az A1 ∪ A2 ∪ · · · ∪ An és a B halmazok diszjunkt uni´ oja, és emiatt an−1 = |A1 ∪ A2 ∪ · · · ∪ An | + an−1 − an azaz an = |A1 ∪ A2 ∪ · · · ∪ An |.

A formula alapj´ an kisz´ amolhatjuk az A = {0, 1, . . . , m−1} halmazban az m = p k11 pk22 · · · pknn természtes sz´ amhoz relat´ıv pr´ımek sz´ am´ at (itt a pi sz´ amok k¨ ul¨ onb¨ oz˝ o pr´ımsz´ amok, a ki kitev˝ ok nemnulla természetes sz´ amok). Legyen Ai az A halmazban a pi pr´ımsz´ am t¨ obbsz¨ or¨ oseinek a halmaza. Ekkor ϕ(m) = |A1 ∪ A2 ∪ · · · ∪ An | = m m m m m m m−( + ··· ) +( + ··· ) + ··· − ···+ p1 p2 pn p1 p2 p1 p3 pn−1 pn X m m + · · · − · · · + (−1)n , (−1)k p i1 p i2 · · · p ik p1 p2 · · · pn 1≤i1
amely kifejezést szorzatt´ a alak´ıtva kapjuk a ϕ(m) = (pk11 − pk11 −1 )(pk22 − pk22 −1 ) · · · (pknn − pk1n −1 )

o ¨sszef¨ uggést. Euler-Fermat tételként ismert a k¨ ovetkez˝ o

7.7.T´ etel. Legyen m 1-nél nagyobb természetes sz´ am, és az a egész sz´ am relat´ıv pr´ım az m sz´ amhoz. Ekkor aϕ(m) ≡ 1( mod m).

Bizony´ıt´ as. Nyilv´ an reduk´ alt maradékoszt´ alyok szorzata reduk´ alt maradékoszt´ aly. Az a reduk´ alt maradékoszt´ aly o ¨sszes pozit´ıv egész kitev˝ os hatv´ anya nem lehet k¨ ul¨ onb¨ oz˝ o, ezért ak = al valamely pozit´ıv egész k < l sz´ amra. Ekkor, felhaszn´ alva a 7.2.3 a ´ll´ıt´ ast, al−k = 1 ad´ odik. Legyen n a legkisebb pozit´ıv egész, amelyre an = 1. Ekkor az {1, a, a2 , . . . , an−1 } n-elem˝ u halmaz, és, mivel 7.2.3 szerint reduk´ alt maradékoszt´ allyal lehet egyszer˝ us´ıteni, a reduk´ alt maradékoszt´ alyok halmaza el˝ oa ´ll mint az A = {1, a, a 2 , . . . , an−1 }, Ab2 = {b2 , b2 a, b2 a2 , . . . , b2 an−1 }, . . . , Abs = {bs , bs a, bs a2 , . . . , bs an−1 } halmazok diszjunkt ¨ uni´ oja, ahol a bi elemek alkalmas reduk´ alt maradékoszt´ alyok. Osszesz´ aml´ alva az elemeket kapjuk, hogy ϕ(m) = sn, és aϕ(m) = asn = (an )s = 1s = 1, ami a ´t´ırva kongruenci´ av´ a a k´ıv´ ant a ´ll´ıt´ ast adja. 8. Sz´ amrendszerek, racion´ alis sz´ amok tizedes t¨ ort alakja A természetes sz´ amok k¨ ul¨ onféle alap´ u sz´ amrendszerekben val´ o el˝ oa ´ll´ıt´ as´ ar´ ol sz´ ol a 8.1.T´ etel. Legyen u 1-nél nagyobb természetes sz´ am és a nemnulla természetes sz´ am. Ekkor egyértelm˝ uen létezik s természetes sz´ am és 0 ≤ ai ≤ u − 1 természetes sz´ am (i = 0, 1, . . . , s), as 6= 0 u ´gy, hogy s X a i ui . a= i=0

Bizony´ıt´ as. Egzisztencia. Végezz¨ uk el maradékos oszt´ asok al´ abbi sorozat´ at: a = uq0 + a0 , 0 ≤ a0 < u

q0 = uq1 + a1 , 0 ≤ a1 < u

q1 = uq2 + a2 , 0 ≤ a1 < u ........................

qi−1 = uqi + ai , 0 ≤ ai < u ........................

26

Mivel a > q0 > q1 > q2 > · · · > qi > · · · természetes sz´ amok szigor´ u monoton cs¨ okken˝ o sorozata, véges sok lépés ut´ an qs−1 kisebb lesz, mint u, és az utols´ o lépésben qs−1 = u0 + as , az utols´ o h´ anyados qs = 0. A végér˝ ol visszafelé haladva lépésenként kapjuk, hogy qs−1 = as qs−2 = as u + as−1 qs−3 = as u2 + as−1 u + as−2 ............................. s−1

q0 = a s u + as−1 us−2 + · · · + a2 u + a1 a = as us + as−1 us−1 + · · · + a1 u + a0 Pt 0 i Unicit´ as. Ha a = asik ilyen fel´ır´ as, akkor sz¨ ukségképpen az a0i értékek i=0 ai u egy m´ rendre asok P maradékaival kell, hogy megegyezzenek, mivel a = Pt a fenti marad´ Pet kos oszt´ t u i=1 a0i ui−1 + a00 , i=1 a0i ui−1 = u i=2 a0i ui−2 + a1 , és ´ıgy tov´ abb. K¨ ovetkezésképp s = t 0 és ai = ai . A tételben szerepl˝ o u sz´ amot a sz´ amrendszer alapj´ anak, az ai sz´ amot az a sz´ am ui helyi´ ert´ ek˝ u sz´ amjegy´ enek nevezz¨ uk, és az a = as as−1 . . . a1 a0u jel¨ olést alkalmazzuk. Nevezetes sz´ amrendszerek a 2-alap´ u bin´ aris, a 16-alap´ u hexadecim´ alis, a 10-alap´ u decim´ alis. Nevezetesek a tizes sz´ amrendszerbeli oszthat´ os´ agi szab´ alyok: – egy természetes sz´ am oszthat´ o 2-vel illetve 4-gyel, ha az utols´ o egy illetve kett˝ o sz´ amjegyéb˝ ol alkotott sz´ am oszthat´ o 2-vel illetve 4-gyel; – egy természetes sz´ am oszthat´ o 5-tel illetve 25-tel, ha az utols´ o egy illetve kett˝ o sz´ amjegyéb˝ ol alkotott sz´ am oszthat´ o 5-tel illetve 25-tel; – egy természetes sz´ am oszthat´ o 3-mal illetve 9-cel, ha a sz´ amjegyeinek o ¨sszege oszthat´ o 3-mal illetve 9-cel; – egy természetes sz´ am oszthat´ o 11-gyel ha a sz´ amjegyeinek v´ altakoz´ o el˝ ojellel vett o ¨sszege oszthat´ o 11-gyel. Ezek bizony´ıt´ asa gyakorlat; példaként az utols´ o bel´ at´ as´ ahoz vegy¨ uk észre, hogy 10 ≡ −1( mod 11), 10i ≡ (−1)i ( mod 11), és ennélfogva a=

s X i=0

ai 10i ≡

s X

ai (−1)i ( mod 11).

i=0

Legyen a nemnulla racion´ alis sz´ am. Ekkor, mivel egyszer˝ us´ıthet¨ unk a sz´ aml´ al´ o és a nevez˝ o legnagyobb k¨ oz¨ os oszt´ oj´ aval, el˝ ojelt˝ ol eltekintve egyértelm˝ uen létezik p és q relat´ıv pr´ım egész alis sz´ am reduk´ alt k¨ oz¨ ons´ eges t¨ ort alakja. Legyen sz´ am u ´gy, hogy a = pq , a racion´ amok. Végezz¨ uk el 0 < a < 1 racion´ alis sz´ am reduk´ alt alakja a = pq , ahol p < q természetes sz´ a maradékos oszt´ asok al´ abbi sorozat´ at: 10p = qa1 + r1 10r1 = qa2 + r2 .............. 10rk−1 = qak + rk ..............

27

Nyilv´ an a h´ anyadosokra 0 ≤ ai ≤ 9 teljes¨ ul. Ekkor, lépésenként visszahelyettes´ıtve, r1 r2 p = a1 10−1 + = a1 10−1 + a2 10−2 + 2 = · · · = q 10q 10 q a1 10−1 + a2 10−2 + · · · + ak 10−k +

rk = ··· 10k q

Mivel az ri maradékok 0 és q k¨ ozé esnek, létezik egy legkisebb i index és t természetes sz´ am, hogy ri = ri+t , és a t¨ obbi maradék m´ ar ismétl˝ odik, azaz j ≥ i indexekre rj = rj+t teljes¨ ul. Ha i = 1 akkor azt mondjuk, hogy az a racion´ alis sz´ am tiszta szakaszos tizedes t¨ ort alakba ´ırhat´ o, és az a = 0, a˙1 a2 . . . a˙t jel¨ olést alkalmazzuk. A fenti o ¨sszef¨ uggésekb˝ ol vil´ agos, hogy a=

∞ a1 10t−1 + a2 10t−2 + · · · + at 10t a1 10t−1 + a2 10t−2 + · · · + at X 1 = = 10t 10it 10t 10t − 1 i=0

a1 10t−1 + a2 10t−2 + · · · + at 10t − 1

a mértani sor o ¨sszegképlete alapj´ an, azaz tiszta szakaszos tizedes t¨ ortet u ´gy ´ırunk a ´t k¨ oz¨ onséges t¨ ort alakba, hogy a sz´ aml´ al´ o a szakasz sz´ amjegyeib˝ ol képzett sz´ am, a nevez˝ o pedig annyi 9-esb˝ ol képzett sz´ am, ah´ any sz´ amjegyb˝ ol a ´ll a szakasz. Ha i > 1 akkor azt mondjuk, hogy az a racion´ alis sz´ am vegyes szakaszos tizedes t¨ ort alakba ´ırhat´ o, és az a = 0, a1 a2 . . . ai−1 a˙i ai+1 . . . ai+t−1 ˙ jel¨ olést alkalmazzuk, ahol a1 a2 . . . ai−1 az el˝ oszakasz illetve a˙i ai+1 . . . ai+t−1 ˙ a szakasz. A fenti o ¨sszef¨ uggésekb˝ ol vil´ agos, hogy a=

∞ a1 10i−2 + a2 10i−3 + · · · + ai−1 ai 10t−1 + ai+1 10t−2 + · · · + ai+t−1 X 1 + = 10i−1 10t+i−1 10it i=0

ai 10t−1 + ai+1 10t−2 + · · · + ai+t−1 10t a1 10i−2 + a2 10i−3 + · · · + ai−1 + = 10i−1 10t+i−1 10t − 1

=

a1 10i+t−2 + · · · + ai−1 10t + ai 10t−1 + · · · + ai+t−1 − (a1 10i−2 + a2 10i−3 + · · · + ai−1 ) (10t − 1)10i−1

azaz vegyes szakaszos tizedes t¨ ortet u ´gy ´ırunk a ´t k¨ oz¨ onséges t¨ ort alakba, hogy a sz´ aml´ al´ o az el˝ oszakasz és a szakasz sz´ amjegyeib˝ ol képzett sz´ amb´ ol kivonva az el˝ oszakasz sz´ amjegyeib˝ ol képzett sz´ am, a nevez˝ o pedig annyi 9-esb˝ ol illetve ut´ ana annyi 0-b´ ol képzett sz´ am, ah´ any sz´ amjegyb˝ ol a ´ll a szakasz illetve az el˝ oszakasz. Speci´ alisan ha a szakasz a 0 sz´ amjegy, akkor azt mondjuk, hogy a racion´ alis sz´ am v´ eges tizedes t¨ ort alakba ´ırhat´ o, és az a = 0, a1 a2 . . . ai−1 jel¨ olést alkalmazzuk. Az el˝ oa ´ll´ıt´ as nem egyértelm˝ u, véges tizedes t¨ orteknek van végtelen tizedes t¨ ort alakjuk is, péld´ aul 1, 5 = 1, 4 9˙ (ellen˝ orizze!). Nemnegat´ıv racion´ alis sz´ am egész része a n´ ala nem nagyobb legnagyobb természetes sz´ am, t¨ ortrésze a sz´ am és egészrészének k¨ ul¨ onbsége. Az egész részt tizes sz´ amrendszerbe, a t¨ ortrészt tizedes t¨ ort alakba ´ırva kapjuk a sz´ am as as−1 . . . a0 , a−1 a−2 . . . tizedes t¨ ort alakj´ at. Az el˝ ojelet elé´ırva hat´ arozhatjuk meg ellentettjének tizedes t¨ ort alakj´ at. ´ ıt´ 8.2.All´ as. Legyen 0 < a < 1 racion´ alis sz´ am, reduk´ alt k¨ oz¨ onséges t¨ ort alakja pq . Ekkor a k¨ ovetkez˝ oa ´ll´ıt´ asok teljes¨ ulnek: (i) az a sz´ am tiszta szakaszos tizedes t¨ ort alakba ´ırhat´ o pontosan akkor ha a q természetes sz´ am és 10 relat´ıv pr´ımek;

28

(ii) az a sz´ am vegyes szakaszos tizedes t¨ ort alakba ´ırhat´ o pontosan akkor ha a q természetes sz´ am és 10 nem relat´ıv pr´ımek; (iii) az a sz´ am véges tizedes t¨ ort alakba ´ırhat´ o pontosan akkor ha a q természetes sz´ amnak a 2 és 5 pr´ımeken k´ıv¨ ul m´ as pr´ımoszt´ oja nincsen. Bizony´ıt´ as. Nyilv´ an az a racion´ alis sz´ am vagy tiszta vagy vegyes szakaszos tizedes t¨ ort alakba ´ırhat´ o. Tegy¨ uk fel, hogy az a = pq racion´ alis sz´ am tiszta szakaszos tizedes t¨ ort alakba ´ırhat´ o, szakasz´ anak t darab sz´ amjegyéb˝ ol képzett természetes sz´ am legyen c. Ekkor a = 10tc−1 és a q sz´ am osztja a 10t − 1 sz´ amot; nyilv´ an q és 10 relat´ıv pr´ımek. alis sz´ am olyan, hogy q és 10 relat´ıv pr´ımek és az a sz´ am Tegy¨ uk fel, hogy az a = pq racion´ mégis vegyes szakaszos tizedes t¨ ort alakba ´ırhat´ o. Legyen az el˝ oszakasz s darab sz´ amjegyéb˝ ol képzett természetes sz´ am b, és szakasz´ anak t darab sz´ amjegyéb˝ ol képzett természetes sz´ am 10t b+c−b oz¨ onséges t¨ ortnek egyszer˝ us´ıthet˝ onek kell lennie 10 s -nel, azaz c. Ekkor az a = (10 t −1)10s k¨ 10s -nek osztania kell a 10t b + c − b sz´ aml´ al´ ot. Ha t ≥ s akkor 10s -nek osztania kell a c − b sz´ amot, ami csak akkor lehetséges, ha a c sz´ am utols´ o s sz´ amjegye megegyezik b sz´ amjegyeivel, ami azt jelenti, hogy az el˝ oa ´ll´ıt´ as tiszta szakaszos, a szakasz az els˝ o t tizedesjegy. Ha t < s akkor a b sz´ am utols´ o s − t sz´ amjegyének és a c sz´ am sz´ amjegyeinek meg kell egyeznie a b sz´ am sz´ amjegyeivel, ami szintén azt jelenti, hogy az el˝ oa ´ll´ıt´ as tiszta szakaszos, a szakasz az els˝ ot tizedesjegy. Az (i) a ´ll´ıt´ ast bel´ attuk, ennek a (ii) a ´ll´ıt´ as k¨ ozvetlen k¨ ovetkezménye. A (iii) a ´ll´ıt´ as nyilv´ anval´ o. Azt mondjuk, hogy az α val´ os sz´ am tizedes t¨ ort alakja c, a1 a2 . . . , ahol c egy decim´ alis alakban fel´ırt egész sz´ am és a1 , a2 , . . . tizedesjegyek, ha az u0 = c, u1 = c, a1 , u2 = c, a1 a2 , . . . racion´ alis sz´ amsorozatot tartalmazza az α oszt´ aly (m´ assz´ oval az u n sorozat val´ os hat´ arértéke α). 8.4.T´ etel. Minden val´ os sz´ am fel´ırhat´ o tizedes t¨ ort alakban, ezek k¨ oz¨ ul a racion´ alisak pontosan a szakaszos tizedes t¨ ort alakba ´ırhat´ ok. Bizony´ıt´ as. Nyilv´ an elegend˝ o a fel´ırhat´ os´ agot pozit´ıv val´ os α sz´ amra bel´ atni. Legyen u 0 = c a n´ ala nem nagyobb legnagyobb egész sz´ am; u1 = c, a1 a n´ ala nem nagyobb legnagyobb sz´ am a {c, 0; c, 1; . . . c, 9} sz´ amok k¨ oz¨ ul; u2 = c, a1 a2 a n´ ala nem nagyobb legnagyobb sz´ am a {c, a1 0; c, a1 1; . . . c, a1 9} sz´ amok k¨ oz¨ ul; és ´ıgy tov´ abb. A kapott un sorozat nyilv´ an tart az α val´ os sz´ amhoz. Be kell még l´ atni, hogy racion´ alis sz´ amnak nem lehet nem szakaszos fel´ır´ asa. Legyen az a racion´ alis sz´ amnak egyszerre szakaszos és nem szakaszos fel´ır´ asa; feltehetj¨ uk, hogy 0 < a < 1. Az els˝ o k¨ ul¨ onb¨ oz˝ o tizedesjegy legyen a t-edik, és legyen b illetve c az ezut´ an k¨ ovetkez˝ o tizedesjegyek lev´ ag´ as´ aval keletkezett véges tizedes t¨ ort a szakaszos illetve a nem szakaszos fel´ır´ asban. Ha b < c akkor, mivel a nem szakaszos fel´ır´ asban a lev´ agott végtelen rész értéke nagyobb, mint 0, a ≤ b + 10−t ≤ c < a, ami lehetetlen. Ha c < b akkor, mivel a nem szakaszos fel´ır´ asban a lev´ agott végtelen rész értéke kisebb, mint 10 −t , a < c + 10−t ≤ b ≤ a, ami lehetetlen. Kaptuk, hogy a nem szakaszos tizedes t¨ ortek éppen az irracion´ alis sz´ amok el˝ oa ´ll´ıt´ asai. 9. A polinomgy˝ ur˝ u Legyen A kommutat´ıv egységelemes gy˝ ur˝ u, x ∈ / A hat´ arozatlannak nevezett szimb´ olum. Az f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 alak´ u form´ alis o ¨sszeget, ahol az ai egy¨ utthat´ ok

29

az A gy˝ ur˝ u elemei, an 6= 0, n természetes sz´ am, az A gy˝ ur˝ u feletti egyhat´ arozatlan´ u polinomnak, n-et, ha nem minden egy¨ utthat´ o 0, a polinom foksz´ am´ anak nevezz¨ uk és f ◦ rel jel¨ olj¨ uk. Ha az an egy¨ utthat´ o 1, akkor f˝ opolinomr´ ol beszél¨ unk. A polinomok k¨ oz¨ otti o ¨sszead´ as és szorz´ as minden megszokott m˝ uveleti tulajdons´ ag felhaszn´ al´ as´ aval t¨ orténik. Nem nehéz bel´ atni, hogy ezekkel a m˝ uveletekkel a polinomok halmaza egységelemes kommutat´ıv gy˝ ur˝ ut alkot. Preciz´ırozott bizony´ıt´ assal az al´ abbi tételt l´ atjuk be. 9.1.T´ etel. Legyen A kommutat´ıv egységelemes gy˝ ur˝ u. Jel¨ olje A[x] az olyan A-beli sorozatok halmaz´ at, amelyeknek csak véges sok tagja nemnulla. Legyen a, b ∈ A[x], o ¨sszeg¨ uket és szorzatukat hat´ arozzuk meg az al´ abbi m´ odon: (a + b)n = an + bn , (ab)n =

n X

ai bn−i .

i=0

Ekkor az (A[x], +, ·) strukt´ ura kommutat´ıv egységelemes gy˝ ur˝ u, tov´ abb´ a ha az A strukt´ ura integrit´ astartom´ any, akkor az A[x] strukt´ ura is integrit´ astartom´ any Bizony´ıt´ as. Legyen a, b, c az A[x] halmaz eleme. Nyilv´ an az o ¨sszead´ as és szorz´ as m˝ uvelet. Az addit´ıv strukt´ ura Abel-csoport. Nyilv´ anval´ o az A gy˝ ur˝ u megfelel˝ o tulajdons´ agaib´ ol. A multiplikat´ıv strukt´ ura asszociat´ıv. Egyrészt ((ab)c)n =

n X

(ab)i cn−i =

(a(bc))n =

n X

ai (bc)n−i =

aj bi−j cn−i ,

n X n−i X

ai bj cn−i−j .

i=0 j=0

i=0

m´ asrészt

n X i X

i=0

i=0 j=0

P Mindkét kapott kifejezés egyenl˝ o a i+j≤n ai bj cn−i−j o ¨sszeggel. A szorz´ as kommutativit´ asa nyilv´ anval´ o. Az a sorozat, amelynek nulladik tagja 1 a t¨ obbi 0 egységelem. Disztributivit´ as. A kommutativit´ as miatt elegend˝ o az egyik tulajdons´ agot bel´ atni. Nyilv´ an ((a + b)c)n =

n X

(a + b)i cn−i =

i=0

n X i=0

n X i=0

ai cn−i +

n X

(ai + bi )cn−i =

n X

(ai cn−i + bi cn−i ) =

i=0

bi cn−i = (ac)n + (bc)n .

i=0

Zérusoszt´ omentesség. Legyen a és b két nem konstans nulla sorozat olyan, hogy maxim´ alis index˝ u nemnulla tagjaik an és bm . Ekkor (ab)n+m = an bm 6= 0. A sorozatok fenti szorzat´ at szok´ as konvol´ uci´ oszorz´ asnak nevezni. Jel¨ olje 1 azt a sorozatot, amelynek nulladik tagja 1 a t¨ obbi 0; jel¨ olje x azt a sorozatot, amelynek els˝ o tagja 1 a t¨ obbi 0; jel¨ olje x2 azt a sorozatot, amelynek m´ asodik tagja 1 a t¨ obbi 0, és ´ıgy tov´ abb. A fenti jel¨ oléssel illetve azonos´ıtva az A-beli skal´ arokat azokkal a sorozatokkal, amelyeknek nulladik tagja az adott elem a t¨ obbi 0, az f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 form´ alis o ¨sszegekben lev˝ o ,,m˝ uveletek” az A[x] gy˝ ur˝ ubeli m˝ uveletekként értelmezhet˝ oek, és minden A[x] halmazbeli sorozat fel´ırhat´ o ilyen alakban. A tov´ abbiakban a polinomokat ilyen el˝ oa ´ll´ıt´ asban fogjuk

30

tekinteni. Az A[x] strukt´ ur´ at az A gy˝ ur˝ u feletti egyhat´ arozatlan´ u polinomgy˝ ur˝ unek nevezz¨ uk. Azt mondjuk, hogy az a(x) A[x] polinom osztja a b(x) ∈ A[x] polinomot, ha létezik c(x) ∈ A[x] polinom, hogy b(x) = a(x)c(x), jel¨ olés: a(x)|b(x). Az oszthat´ os´ ag tulajdons´ agai az egész sz´ amok esetével anal´ og m´ odon bizony´ıthat´ ok (l´ asd 6.1.). Az egységeket egyszer˝ uen megkereshetj¨ uk a polinomok k¨ oz¨ ott. ´ ıt´ 9.2.All´ as. Az A[x] A integrit´ astartom´ any feletti polinomgy˝ ur˝ u egységei az A gy˝ ur˝ u egységei. Bizony´ıt´ as. Nyilv´ an az A-beli skal´ ar egységek a polinomgy˝ ur˝ uben is egységek. Ha az f (x), g(x) polinomokra f (x)g(x) = 1, akkor, mivel nyilv´ an szorzatpolinom foksz´ ama a foksz´ amok o ¨sszege, f ◦ + g ◦ = 0, ami csak u ´gy lehet, ha mindkét polinom foksz´ ama nulla, azaz skal´ ar egységek. Azt mondjuk, hogy a b(x) ∈ A[x] polinom az a(x) ∈ A[x] polinom asszoci´ altja, ha b(x) = a(x)c(x), ahol c(x) egység, azaz egység az A polinomgy˝ ur˝ uben; jel¨ olés: a(x) ∼ b(x). Az asszoci´ alts´ ag nyilv´ an ekvivalenciarel´ aci´ o. Ha az egy¨ utthat´ ok strukt´ ur´ aja test, akkor elvégezhet˝ o benne a maradékos oszt´ as az u ´gynevezett polinom oszt´ asa polinommal algoritmus alapj´ an. 9.3.T´ etel. Legyen K test, g(x), f (x) a K[x] polinomgy˝ ur˝ u nemnulla elemei. Ekkor egyértelm˝ uen létezik q(x), r(x) polinom a K[x] polinomgy˝ ur˝ ub˝ ol, hogy g(x) = f (x)q(x) + r(x), és az r(x) polinom a zéruspolinom, vagy r ◦ < f ◦ . Bizony´ıt´ as. Egzisztencia. Legyen az f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 illetve g(x) = bm xn + bm−1 xn−1 + · · · b1 x + b0 polinom foksz´ ama n illetve m. Ha n > m akkor a q(x) = 0 és r(x) = g(x) v´ alaszt´ as megfelel˝ o. Legyen cm−n = bamn . Ekkor a g(1) (x) = g(x) − f (x)cm−n xm−n polinom foksz´ ama kisebb, mint m, ha n-nél is kisebb, akkor q(x) = cm−n xm−n és r(x) = g(1) (x) v´ alaszt´ assal megkaptuk a h´ anyadost és a maradékot. Legyen a g (1) (x) polinom m − 1edfok´ u tagj´ anak (esetlegesen zérus) egy¨ utthat´ oja u1 és cm−n−1 = aun1 . Ekkor a g(2) (x) = m−n−1 g(1) (x) − f (x)cm−n−1 x polinom foksz´ ama kisebb, mint m − 1, ha n-nél is kisebb, akkor q(x) = cm−n xm−n + cm−n−1 xm−n−1 és r(x) = g(2) (x) v´ alaszt´ assal megkaptuk a h´ anyadost ´ és a maradékot. Es ´ıgy tov´ abb, legf¨ oljebb az m − n-edik lépésben az elj´ ar´ as véget ér: a g(m−n) (x) polinom n-edfok´ u tag´ anak egy¨ utthat´ oja legyem um−n és c0 = um−n an . Ekkor az r(x) = g(m−n) (x) − f (x)c0 polinom foksz´ ama kisebb, mint n, és a q(x) = cm−n xm−n + cm−n−1 xm−n−1 + · · · + c0 v´ alaszt´ assal megkaptuk a h´ anyadost és a maradékot. Unicit´ as Indirekte érvel¨ unk. Legyen g(x) = f (x)q(x) + r(x) és g(x) = f (x)t(x) + w(x) a feltételeknek megfelel˝ o két maradékos oszt´ as, q(x) 6= t(x). A két egyenl˝ oséget kivonva egym´ asb´ ol 0 = f (x)(q(x) − t(x)) + (r(x) − w(x)) azaz f (x)(t(x) − q(x)) = r(x) − w(x), ahol a bal oldal foksz´ ama legal´ abb n, a jobboldal foksz´ ama kisebb, mint n, ami ellentmond´ as. Az egészekhez hasonl´ o elnevezéseket haszn´ alunk: osztand´ o, oszt´ o, h´ anyados, marad´ ek. A maradékos oszt´ ason alapul´ o euklideszi algoritmus is anal´ og m´ odon végezhet˝ o el az a(x), b(x) ∈ K[x] polinomokon: b(x) = a(x)q1 (x) + r1 (x), r1◦ < a◦ a(x) = r1 (x)q2 (x) + r2 (x), r2◦ < r1◦ r1 (x) = r2 (x)q3 (x) + r3 (x), r3◦ < r2◦ .............................. ◦ ◦ rn−3 (x) = rn−2 (x)qn−1 (x) + rn−1 (x), rn−1 < rn−2 rn−2 (x) = rn−1 (x)qn (x) + rn (x), rn (x) = 0.

31

Ha a(x) ∈ K[x] és b(x) ∈ K[x] nemnulla polinomok, akkor legnagyobb k¨ oz¨ os oszt´ ojuknak nevezz¨ uk azt a d(x) ∈ K[x] f˝ opolinomot, amelyre teljes¨ ul, hogy d(x) osztja az a(x) és a b(x) polinomot is, és ha egy c(x) ∈ K[x] polinom szintén osztja az a(x) és a b(x) polinomot, akkor c(x) osztja a d(x) polinomot is. Jel¨ olés: (a(x), b(x)). A legnagyobb k¨ oz¨ os oszt´ o létezését az euklideszi algoritmus biztos´ıtja. B´ armely két nemnulla polinomnak a K[x] testf¨ ol¨ otti polinomgy˝ ur˝ ub˝ ol létezik legnagyobb k¨ oz¨ os oszt´ oja, nevezetesen a rajtuk végrehajtott euklideszi algoritmus utols´ o nemnulla maradék´ aval asszoci´ alt f˝ opolinom, a bizony´ıt´ as anal´ og a 6.3 a ´ll´ıt´ aséval. A legnagyobb k¨ oz¨ os oszt´ o képzésének tulajdons´ agai f˝ opolinomokra megegyeznek a természetes sz´ amokn´ al kapottakkal, l´ asd a 6.4 és 6.5 a ´ll´ıt´ ast. Azt mondjuk, hogy az a(x), b(x) ∈ K[x] nemnulla polinomok legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose az m(x) ∈ K[x] f˝ opolinom, ha az a(x) és a b(x) polinom is osztja az m(x) polinomot, m´ assz´ oval k¨ oz¨ os t¨ obbsz¨ or¨ os¨ uk, és ha a c(x) ∈ K[x] polinom szintén k¨ oz¨ os t¨ obbsz¨ or¨ ose az a(x) és a b(x) polinomoknak, akkor t¨ obbsz¨ or¨ ose az m(x) polinommnak is. Jel¨ olés: [a(x), b(x)]. a(x)b(x) polinommal asszoci´ alt m(x) f˝ opolinom az a(x), b(x) ∈ K[x] nemnulla poliAz (a(x),b(x)) nomok legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose, a bizony´ıt´ as anal´ og a 6.6 a ´ll´ıt´ aséval. A legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os képzésének tulajdons´ agai f˝ opolinomokra megegyeznek a természetes sz´ amokn´ al kapottakkal, l´ asd a 6.7 a ´ll´ıt´ ast. Nemnulla és nem egység K[x]-beli polinomr´ ol azt mondjuk, hogy pr´ımpolinom, ha valah´ anyszor oszt egy b(x)c(x) szorzatot (b(x), c(x) ∈ K[x] polinomok), akkor osztja legal´ abb egyik tényez˝ ojét is. Nemnulla és nem egység u(x) ∈ K[x] polinomr´ ol azt mondjuk, hogy irreducibilis polinom, ha u(x) = a(x)b(x) (a(x), b(x) ∈ K[x] polinomok) egy faktoriz´ aci´ oja, akkor valamelyik tényez˝ o egység, azaz nemnulla nulladfok´ u polinom. Testfeletti polinom pr´ım akkor és akkor, ha irreducibilis, a bizony´ıt´ as anal´ og a 6.9 a ´ll´ıt´ aséval. A 6.10. tételhez hasonl´ oan l´ athat´ o be a polinomelmélet alaptétele, a részletezés gyakorlat.. 9.4.T´ etel. Tetsz˝ oleges nemnulla nem egység testf¨ ol¨ otti polinom sorrendt˝ ol és egységtényez˝ ot˝ ol eltekintve egyértelm˝ uen bonthat´ o fel pr´ımpolinomok szorzat´ ara. Az egészekéhez hasonl´ o elmélet ép´ıthet˝ o fel a test f¨ ol¨ otti polinomgy˝ ur˝ uben a diofantoszi egyenletekre, a kongruenci´ ara és a kongruencia egyenletekre. Euklideszi gy˝ ur˝ unek nevezz¨ uk az A integrit´ astartom´ anyt, ha létezik egy α : A \ {0} → N euklideszi norm´ anak nevezett leképezés u ´gy, hogy b´ armely a, b ∈ A nemnulla elemhez létezik q, r ∈ A elem, melyre teljes¨ ul, hogy b = aq + r, és r = 0 vagy α(r) < α(a). Az egészeknél az euklideszi norma az abszol´ utérték, a test f¨ ol¨ otti polinomgy˝ ur˝ uben a foksz´ am, ´ıgy ezek euklideszi gy˝ ur˝ uk. Mivel a bizony´ıt´ asok sor´ an csak olyan tulajdons´ agokat haszn´ altunk fel, amelyek az euklideszi gy˝ ur˝ ukben teljes¨ ulnek, euklideszi gy˝ ur˝ uben az egészekével és a test f¨ ol¨ otti polinomgy˝ ur˝ uével anal´ og oszthat´ os´ agelmélet ép´ıthet˝ o fel.

I. NÉHÁNY FONTOS FOGALOM

Recommend Documents