Episode I
Alice és Bob
19. fejezet
Alice és Bob ideáljai
Az előző fejezetben megvizsgáltuk, hogyan kell osztási maradékokkal műveleteket végezni. Ezeket a műveleteket moduláris összeadásnak és moduláris szorzásnak neveztük, és igazoltuk, hogy az osztási maradékok halmaza ezzel a két művelettel gyűrűt alkot. Ennek során megmutattuk a 9.5. szakaszban ismertetett Diffie-Hellman kulcscsere protokoll helyességét. Ezután általánosságban is megvizsgáltuk a gyűrűk közötti művelettartó leképezések, azaz a gyűrűhomomorfizmusok tulajdonságait. Ez adta a motivációt a kongruencia fogalmának bevezetéséhez. Megmutattuk, hogy a kongruencia nem függ egy konkrét gyűrűhomomorfizmustól, hanem csak azoktól az elemektől, amelyekhez a célgyűrű nullelemét rendeli hozzá. Ezt a részhalmazt magjának neveztük. Ezzel párhuzamosan definiáltuk az ideál fogalmát, és megmutattuk, hogy egy gyűrűben pontosan az ideálok lehetnek gyűrűhomomorfizmusok magjai. Ehhez meg kellett ismerkednünk a maradékosztálygyűrű fogalmával. Végül egy egyszerű következményként adódott az úgynevezett homomorfizmustétel.
De vajon hogyan néznek ki az egész számok gyűrűjének ideáljai? Mi a kapcsolat az ideálok és a 16. fejezetben bevezetett oszthatósági alapfogalmak között? Mik azok a főideálgyűrűk, és ezeknek milyen jó tulajdonságaik vannak? Mi közük az euklidészi gyűrűkhöz? Hogyan zárható le a számelmélet alaptételének kérdése végérvényesen az ideálok segítségével? Ebben a fejezetben erről lesz szó...
Figyelem! Ez a fejezet erőteljesen épít a 12., 16., 17. és 18. fejezetekben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:
Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a 12., 16., 17. és 18. fejezeteket, mivel gyakran hivatkozni fogunk rájuk.
Az oszthatósági alapfogalmak kapcsán a 16. fejezetben ismerkedtünk meg a felbonthatatlan (vagy prím-) számokkal, és láttuk, hogy ezek bizonyos értelemben az építőkövek szerepét töltik be az egész számok között. A 17. fejezetben ugyanis igazoltuk, hogy egyrészt minden egész szám előállítható prímszámok szorzataként, másrészt pedig azt, hogy ez lényegében csak egyféleképpen tehető meg. Ezt a két állítást – tehát a prímtényezős felbontás létezését és egyértelműségét – együttesen a számelmélet alaptételének neveztük. Mi azonban nem kimondottan az egész számok körében, hanem ennél általánosabban, a gyűrűk – pontosabban az integritástartományok – absztrakciós szintjén vizsgáltuk a kérdést. Ezen a szinten általánosságban már különválik a felbonthatatlan és a prím fogalma. Láttuk, hogy a számelmélet alaptétele bizony nem teljesül minden integritástartományban, ezért megpróbáltuk meghatározni ennek feltételeit. Először ismételjük át ennek főbb lépéseit.
A keresett feltételek megtalálása mindeddig felemásan sikerült. Elsőként a 16.17. Tétel fogalmazott meg egy szükséges feltételt. E tétel alapján a számelmélet alaptétele csak olyan integritástartományokban teljesülhet, amelyekben minden felbonthatatlan elem prímtulajdonságú. Itt egyrészt megemlítettük, hogy ez a feltétel szükséges ugyan, de önmagában még nem elégséges az alaptételhez. Másrészt viszont azt is megemlítettük, hogy "nem hiányzik sok", mivel a feltétel az alaptétel egyértelműségi állításához már elégséges, azaz a prímtényezős felbontás létezését ugyan nem garantálja, ám ha az mégis létezik, akkor egyértelmű a 16.16. Definíció szerinti értelemben.
Ezután a 17. fejezetben megismerkedtünk az úgynevezett euklidészi gyűrűkkel, amelyekben egy bizonyos absztrakt értelemben elvégezhető a maradékos osztás. Ennek két fontos következménye volt. Egyrészt a 17.18. Tétel értelmében bármely két elemnek létezik a kitüntetett közös osztója, amelyből a 17.12. Tétel alapján következik, hogy minden felbonthatatlan elem prímtulajdonságú, és így igaz az alaptétel egyértelműségi állítása.
Másrészt viszont a 17.21. Tétel és a 17.22. Tétel alapján ha egy integritástartományon létezik bármilyen euklidészi függvény, akkor létezik olyan is, amely szigorúan nagyobb értéket ad bármilyen kéttényezős szorzatra, mint a tényezőkre külön-külön – kivéve ha valamelyik tényező egység, amikoris egyenlőség áll fenn. Ebből a 17.23. Tétel alapján már viszonylag egyszerűen következik a prímtényezős felbontás létezéséről szóló állítás.
A maradékos osztás elvégezhetősége tehát egy elégséges feltétel az alaptétel tejesüléséhez, megemlítettük ugyanakkor, hogy sajnos nem szükséges. Léteznek ugyanis olyan integritástartományok, amelyek nem euklidészi gyűrűk, mégis teljesül bennük az alaptétel. Van már tehát egy szükséges, de nem elégséges, és egy elégséges, de nem szükséges feltételünk. Jó volna mostmár végleg lezárni ezt a kérdést, és találni egy olyan feltételrendszert, amely egyszerre szükséges és elégséges is. Szerencsére az előző fejezetben bevezetett ideálok segítségével ebben a fejezetben képesek leszünk megfogalmazni egy ilyen feltételrendszert.
Ez szoros összefüggésben lesz bizonyos ideálok egymáshoz való viszonyával. Minthogy egy gyűrű ideáljai tulajdonképpen halmazok, ezért nem árt először megismerkedni néhány ezekkel kapcsolatos alapfogalommal és jelöléssel. Már csak azért sem, mivel egészen eddig a pontig mi magunk is számtalanszor használtunk halmazokra vonatkozó terminológiát. Itt az ideje hát, hogy ezeket is precíz matematikai formába öntsük.
19.1Halmazelméleti gyorstalpaló
A "halmaz" a matematika egyik legalapvetőbb fogalma, melyet leginkább az "összesség" illetve "sokaság" szavakkal tudunk körülírni. Ezt a fogalmat nem definiáljuk, mivel alapfogalom. Ez ahhoz hasonlatos, mint ahogyan a természetes számokat bevezettük a 11.3. szakaszban. Ha visszaemlékszünk, ott sem mondtuk meg, hogy konkrétan mik azok a természetes számok. Pusztán annyit állítottunk róluk, hogy egy -nel jelölt halmaz elemei, amelyek eleget tesznek négy egyszerű tulajdonságnak. Ezeket a tulajdonságokat Peano-axiómáknak neveztük és a 11.1. Definícióban soroltuk fel őket. Az, hogy kinek milyen intuitív kép él a fejében a természetes számokkal kapcsolatban, mindenkinek a magánügye. Ettől az intuitív képtől függetlenül minden, amit az elmúlt fejezetekben tárgyaltunk, ennek a mindössze négy axiómának a következménye, vagy legalábbis abból eredeztethető.
Míg a természetes és az általánosabb egész számokkal a számelmélet, addig a halmazok tulajdonságaival a halmazelmélet foglalkozik. Végsősoron minden, a matematika által vizsgált objektum halmaz, de legalábbis megadható olyan modellje, amely kizárólag a halmazelmélet alapfogalmait használja. Így annak ellenére, hogy csak a 19. századra fejlődött ki, a halmazelmélet mára a modern matematika minden ágának – a matematikai logika mellett – az alapja lett.
A halmazelmélet korai változatát, az úgynevezett naív halmazelméletet Georg Cantor és Richard Dedekind úttörő munkásságának köszönhetjük. Mi ebben a fejezetben elsősorban ezzel fogunk foglalkozni a könnyebb érthetőség kedvéért. Ugyanakkor megemlítjük, hogy a 20. század elején a naív halmazelméletben bizonyos szélsőséges esetekben komoly logikai ellentmondásokat fedeztek fel, amely az egész matematikát megrengette, így szükségessé vált a halmazelméletet is axiomatikus alapokra helyezni. Ebben a cikksorozatban azonban erre nem fogunk kitérni bővebben. Az általunk használt halmazelméleti eszköztár ugyanis az axiomatikus halmazelméletben is ugyanaz lenne.
Minden matematikai elmélet valamilyen objektumokkal, illetve azok tulajdonságaival foglalkozik. Például a számelméletben ezek az objektumok lehetnek mondjuk az egész számok, egy tulajdonság pedig a -vel való oszthatóság. A halmazelmélet ennél absztraktabb módon tekint a világra: számára csak objektumok és tulajdonságok vannak. "Halmaznak" nevezzük azon objektumok összességét, amelyekre teljesül valamilyen közös tulajdonság. Ám azzal, hogy konkrétan mik ezek az objektumok és a szóban forgó tulajdonság, a halmazelmélet szintjén már nem foglalkozunk. Ezt úgy is meg lehet fogalmazni, hogy magát a tulajdonságot – bármi legyen is az – egy "halmazként", azokat az objektumokat pedig – bármik legyenek is azok –, amelyekre az e halmaz által reprezentált tulajdonság teljesül, a "halmaz elemeiként" képzeljük el.
Az alábbi definíció sem határozza meg a most ismertetett "halmaz" és "eleme lenni" fogalmak jelentését, mivel azok formális logikai szempontból alapfogalmak, így ez lehetetlen lenne. Ehelyett csak az ezekre vonatkozó jelöléseket ismerteti, valamint definiál néhány kapcsolódó fogalmat is, amelyek viszont már nem alapfogalmak:
A 19.1. Definícióban és az utána lévő megjegyzésben szerepelő, kissé homályos "minden objektum" megfogalmazás talán zavaró lehet. Az, hogy ezalatt pontosan mit értünk, mindig attól függ, hogy éppen milyen matematikai objektumokat vizsgálunk a halmazelmélet eszközeivel. Vizsgálhatjuk például az egész számokat, amikoris a "minden objektum" kifejezés alatt épp az egész számok halmazának elemeit értjük – és ezáltal a definícióban szereplő univerzális halmaz is épp ez halmaz lesz. De vizsgálhatjuk például egy valamilyen halmaz bizonyos részhalmazait is. Ebben az esetben az univerzális halmaz -nek a részhalmazaiból fog állni. Ilyen úgynevezett "halmazrendszerekről" lesz szó a 19.2. szakaszban, azután pedig az ott szerzett ismereteket gyűrűk ideáljainak vizsgálatához fogjuk felhasználni.
A szemfüles Olvasónak feltűnhetett, hogy az előző bekezdésben – és egyébként mindeddig számos alkalommal – sunyi módon használtuk a "részhalmaz" kifejezést anélkül, hogy ezt a fogalmat bármikor is definiáltuk volna. Ez egy annyira fontos halmazok közötti reláció, hogy pofátlanság lenne ezt a gyakorlatot tovább folytatni. Ezért most az imént megismert halmazelméleti alapfogalmak segítségével ezt a fogalmat is definiálni fogjuk.
Például az egész számok halmazának egy valódi részhalmazát alkotják a páros számok. Részhalmaz, mert minden páros szám egyben egész szám is, és valódi részhalmaz, mert van olyan egész szám, amely nem páros.
Halmazok között értelmezhetünk kétváltozós műveleteket, amelyek két tetszőleges halmazból képeznek egy újabb halmazt, méghozzá az alábbiak szerint.
Ha például , , és az univerzumnak a pozitív egész számokat tekintjük, akkor az imént definiált halmazműveletek az alábbi halmazokat adják:
A halmazokat, illetve azok viszonyait az úgynevezett Venn-diagramok segítségével ábrázolhatjuk. Itt a halmazokat különböző síkidomok (körök, téglalapok, ellipszisek), míg a halmaz elemeit pontok reprezentálják. Az univerzális halmazt legtöbbször az ábrát körülvevő tégalalappal jelöljük. A Venn-diagram általában csak néhány halmaz szemléltetésére alkalmas, mivel sok egymást kölcsönösen metsző halmaz esetén az ábra elbonyolódik, vagy nem is lehetséges az összes metszetet ábrázolni.
A 19.1. ábrán lévő Venn-diagramokon a fenti példában szereplő halmazműveletek láthatók.
A 19.2. ábrán lévő Venn-diagramon a 19.2. Definíció szerinti tartalmazási relációt szemléltettük.
A 19.3. Definíció szerinti halmazműveletekre érvényesek az alábbi tulajdonságok.
Az alábbi bizonyítás gondolatmeneteinek könnyebb megértése érdekében javasoljuk az Olvasónak a tétel előtt ismertetett Venn-diagramok használatát.
19.2Halmazrendszerek
E rövid halmazelméleti gyorstalpaló után ebben a szakaszban olyan halmazokkal fogunk megismerkedni, amelyeknek az elemei maguk is halmazok. Ezeknek az első hallásra furcsa halmazoknak külön nevük is van, és kontextustól függően általában jelölésben is megkülönböztetjük őket.
Tegyük fel például, hogy az alaphalmazunk az alábbi:
Ekkor a hatványhalmaznak összesen nyolc eleme lesz, méghozzá az halmaz összes lehetséges részhalmaza:
Jól vigyázzunk a jelölésekre! Először is a itt nem a "nulla" egész számot, hanem az üres halmazt jelöli. Nagyon nem mindegy továbbá, hogy -et, vagy pedig -et írunk. Az ugyanis nem a hatványhalmaznak, hanem magának az alaphalmaznak egy eleme. Ezzel szemben az egyetlen elemből álló halmaz már a hatványhalmaznak egy eleme. Látható, hogy a halmazban valóban benne van összes részhalmaza elemként. Még a -val jelölt üres halmaz, sőt, maga az alaphalmaz is.
A definíció szerint tehát maga is egy halmazrendszer felett, méghozzá a lehető legbővebb, ami csak létezik. De tegyük fel, hogy mi -nek csak a nemtriviális részhalmazait szeretnénk vizsgálni. Ezek szintén egy halmazrendszert alkotnak felett, amelyet jelöljünk most -sel. Ekkor az halmazrendszer az alábbi hat elemből fog állni:
Mint ahogyan a definícióban már említettük, az halmazrendszer -nek egy részhalmaza lesz, azaz:
Nyilván, hiszen minden -beli elem egyúttal eleme a hatványhalmaznak is. Előbbi ugyanis az alaphalmaznak csak a nemtriviális részhalmazait tartalmazza elemként, utóbbi pedig az összeset.
Ha esetleg az Olvasó megpróbálta magát az alaphalmazt, illetve a példában szereplő halmazrendszert ugyanazon a Venn-diagramon ábrázolni, akkor ez a kísérlet minden bizonnyal sikertelenül zárult. Ennek az a nagyon egyszerű oka, hogy teljesen más jellegű matematikai objektumokról van szó. Első esetben ugyanis a vizsgált objektumok tulajdonképpen az halmaz elemei, azaz az , , és egész számok, így a tárgyalási univerzumnak az halmazt tekinthetjük. Ennek megfelelően a 19.3. ábrán látható Venn-diagramon az halmaz részhalmazait síkidomokkal ábrázolhatjuk, míg az feletti halmazrendszereket ezen az ábrán nem tudjuk megjeleníteni.
Ezzel szemben a második esetben a vizsgált objektumok az részhalmazai, a tárgyalási univerzum pedig ebben az esetben a hatványhalmaz lesz. Ennek megfelelően a 19.4. ábrán látható Venn-diagramon az halmaz részhalmazait pontokkal jelöljük, és így az feletti halmazrendszereket tudjuk síkodomokként ábrázolni. Itt például a nemtriviális részhalmazokat tartalmazó halmazrendszer mellett egy másik, -vel jelölt halmazrendszert is ábrázoltunk, amely az alaphalmaznak a pontosan egyelemű részhalmazait tartalmazza elemként. Ezen az ábrán viszont az halmaz elemeit – azaz magukat az , és a egész számokat – nem tudjuk megjeleníteni. Az ábra alján lévő ebben az esetben az üres halmazt, és nem pedig a "nulla" egész számot jelöli.
Az ábráról az is leolvasható, hogy az és halmazrendszerek között egyébként az alábbi szigorú tartalmazási reláció is fennáll:
19.3Halmazrendszerek részbenrendezése
A 12. fejezetben a természetes számok szimbólummal jelölt rendezési relációjának kapcsán általánosságban is szó volt az úgynevezett részbenrendezésekről és részbenrendezett halmazokról. Javasoljuk az Olvasónak, hogy a továbbolvasás előtt ismételje át az ott tanult fogalmakat. A 12.14. Definícióban részbenrendezésnek hívtuk azokat a relációkat, amelyek egyszerre reflexívek, antiszimmetrikusak és tranzitívak.
Az alábbi tétel alapján bármilyen halmazrendszer is tulajdonképpen nem más, mint egy részbenrendezett halmaz.
A részbenrendezett halmazok ábrázolására szolgál az úgynevezett Hasse-diagram. Egy ilyen diagramon a halmaz elemeit pontok reprezentálják, és két pont között pontosan akkor megy él, ha ők "közvetlenül egymás után vannak" a vizsgált részbenrendezés szerinti "nagyságrendi sorban". Azt, hogy melyikük a "kisebb" vagy "nagyobb" úgy ábrázoljuk, hogy a "nagyobb" elemet feljebb rajzoljuk az ábrán. Ez az ábrázolásmód azért működik, mert a részbenrendezés "irányát" követve annak most bizonyított tranzitivitása miatt soha nem fordulhat elő, hogy egy pontból kiindulva oda visszatérnénk.
Tekintsük például az előző szakaszban fehozott alaphalmazt, és képezzük ennek a hatványhalmazát. Ez ugye egy halmazrendszer felett, amelynek a Hasse-diagramja látható a 19.5. ábrán, amikoris a részbenrendezés a szimbólummal jelölt részhalmaz reláció.
A diagramon az is jól látszik, hogy a rendezési relációra nem teljesül a trichotómia, ami ugye azt követeli meg, hogy bármely két elem "összehasonlítható" legyen egymással a reláció által. Az egész számok gyűrűjének vagy a természetes számok halmazának rendezése teljesíti ezt az extra tulajdonságot is, ezért neveztük őket teljes rendezésnek. Ezzel szemben a reláció nem egy teljes rendezés, hiszen például az és a részhalmazok között egyik irányban sem teljesül a tartalmazás, így ők nem "összehasonlíthatók" a reláció által. A fenti diagramon ez úgy mutatkozik meg, hogy egyikből sem tudunk eljutni a másikba az éleken keresztül, amennyiben csak lentről felfelé haladhatunk. De például a és az részhalmazok között fennáll a tartalmazási reláció, hiszen -ből felfelé kiindulva két lépés után az -hoz érkezünk két különböző útvonalon is.
A halmazrendszer Hasse-diagramját vizsgálva feltűnhet, hogy az egész számok gyűrűjének rendezésével ellentétben itt létezik "legkisebb" és "legnagyobb" elem. A "legkisebb" elem szerepét itt az üres halmaz tölti be, hiszen nincs másik olyan halmaz, amely "szűkebb" lenne nála. Ehhez hasonlóan a "legnagyobb" elem maga az alaphalmaz, hiszen nincs másik olyan halmaz, amely "bővebb" lenne nála. Az alábbi definíció ezeket a fogalmakat tisztázza általánosságban részbenrendezett halmazok esetén.
Talán egy kicsit furcsa lehet, hogy a definíció megkülönbözteti a "minimális" és a "legkisebb", valamint a "maximális" és a "legnagyobb" fogalmát. Ennek személtetéséhez vizsgáljunk most két halmazrendszert az halmaz felett. Az egyik legyen a teljes hatványhalmaz, a másikat pedig jelöljük -sel, és tartalmazza -nek csak a nemtriviális részhalmazait. A 19.6. ábrán egymás alatt láthatjuk e két halmazrendszer Hasse-diagramját.
Látható, hogy minimuma és maximuma mindkét halmazrendszernek van. A halmazrendszer minimuma a -val jelölt üres halmaz, maximuma pedig a teljes alaphalmaz. Az halmazrendszernek szintén van minimuma és maximuma is, ráadásul több is. Minimuma például az összes egyelemű részhalmaz, hiszen nincs olyan halmaz -ben, amely ezek bármelyikének valódi részhalmaza lenne. Ehhez hasonlóan maximuma az összes háromelemű részhalmaz, hiszen nincs olyan halmaz -ben, amelynek ezek bármelyike valódi részhalmaza lenne.
Ezzel szemben legszűkebb illetve legbővebb eleme csak a halmazrendszernek van, méghozzá szintén az üres halmaz és a teljes alaphalmaz. Előbbi ugyanis a halmazrendszer minden elemének részhalmaza, utóbbinak pedig a halmazrendszer minden eleme részhalmaza. Viszont az halmazrendszerben nem találunk ilyen értelemben legszűkebb és legbővebb elemeket.
A minimum (illetve maximum) esetén tehát csak annyit követelünk meg, hogy ne legyen náluk "szűkebb" (vagy "bővebb") halmaz a rendszerben. De mivel létezhetnek olyan halmazok, amelyek egymással nem összehasonlíthatók a reláció szerint – hiszen részbenrendezésről van szó –, ezért létezhet több minimum (illetve maximum) is a rendszerben, ahogyan azt a fenti példa mutatja. A legszűkebb (illetve legbővebb) halmazokra ennél szigorúbb feltételt határozunk meg, ezektől ugyanis megköveteljük, hogy bármelyik másik halmazzal összehasonlíthatóak legyenek.
Most megmutatjuk, hogy ha egyáltalán létezik legszűkebb (illetve legbővebb) halmaz egy rendszerben, akkor az egyértelmű. Az erről szóló tételt a 19.7. Definícióhoz hasonlóan általánosságban mondjuk ki részbenrendezett halmazokra.
Az iménti tétel szerint tehát egy halmazrendszerben legfeljebb egy legszűkebb, illetve legfeljebb egy legbővebb elem létezhet. Jogosan teheti fel a kérdést az Olvasó, hogy miféle elvetemült halmazrendszer lehet az, amelyben egyáltalán nem léteznek ilyen tulajdonságú halmazok. Azt még csak-csak el lehet képzelni, hogy nincs legbővebb halmaz. Például az egész számok halmaza felett könnyen találhatunk olyan halmazrendszert, amelynek nincs legbővebb eleme. Ilyen például az alábbi halmazokból álló rendszer:
Látható, hogy ennek a halmazokból álló sorozatnak minden tagja valódi részhalmaza a rákövetkező tagnap, így ebben a feletti halmazrendszerben nem létezik legbővebb elem. Ezzel szemben elsőre nehéz elképzelni egy olyan halmazrendszert felett, amelynek ne lenne legszűkebb eleme. Meglepő módon azonban ilyen is létezik. Vegyük például az alábbi konstrukciót:
Ennek a sorozatnak az első tagja tehát a teljes halmaz, amelyből szép sorban elkezdünk kidobálni egyre több, de mindig véges számú egész számot. Nyilvánvalóan ennek a sorozatnak minden tagja valódi részhalmaza a sorozatban előtte lévő tagnak, így ebben a feletti halmazrendszerben nem létezik legszűkebb elem.
De elképzelhetünk egy olyan halmazrendszert is, amelynek alaphalmazát egy síkra rajzolt, a 19.7. ábrán -lal jelölt szakasz pontjai alkotják, és amely ennek az , , , , ... szakaszok által reprezentált részhalmazainak a sorozatából áll. A szakaszokat egymás alá rajzoltuk a szemléltetés miatt, de ezek valójában mindannyian az eredeti szakasz pontjainak részhalmazait alkotják.
Ennek a sorozatnak minden tagja az eredeti szakasz feleakkora részéből áll, mint az őt megelőző tag. Azaz a sorozatban minden tag valódi részhalmaza a sorozatban előtte lévő tagnak, így ebben a rendszerben sincs legszűkebb elem.
A fejezet további részében az eddig szerzett halmazelméleti ismereteinket gyűrűk ideáljainak vizsgálatához fogjuk felhasználni.
19.4Ideálok generálása
Egy gyűrű tulajdonképpen nem más, mint egy alaphalmaz, amelyen értelmezve van két művelet. Ennek megfelelően részgyűrűi és ideáljai is halmazok, méghozzá részhalmazai. Más szavakkal ezek is egy-egy halmazrendszert alkotnak felett. Előszöris megmutatjuk, hogy milyen hatása van a metszetképzésnek ezekre a halmazrendszerekre.
Például az egész számok gyűrűjében a -vel és -mal osztható egész számok egy-egy ideált alkotnak. Ezeket a 18.8. szakaszban bevezetett 18.19. Definíció szerinti komplexusszorzás ismeretében -vel és -vel jelölhetjük. E két ideál metszetét azok az egész számok alkotják, amelyek -vel is és -mal is oszthatók. Ezek épp a -tal osztható egész számok lesznek, azaz:
Ez szintén ideál -ben, épp ahogyan a tétel állítja. Nézzük meg, hogy miért igaz ez általánosságban is.
Most egy gyűrűben azokat a részgyűrűket (vagy ideálokat) fogjuk megvizsgálni, amelyek -nek egy adott részhalmazát tartalmazzák. Ezek a részgyűrűk (vagy ideálok) szintén egy halmazrendszert alkotnak felett, amelynek egy fontos tulajdonságát mondja ki az alábbi tétel.
Ez alapján tehát egy adott gyűrű bármely részhalmaza egyértelműen meghatároz egy ideált. Ez lesz az -et tartalmazó legszűkebb ideál. Ugyanakkor ez a tétel semmit nem mond arról, hogy az által generált ideált lehet-e generálni egy -nél szűkebb részhalmazzal is vagy nem. Amikor tehát azt mondjuk, hogy egy ideál "generálható -szel", ez még nem jelenti azt, hogy az adott ideál kizárólag -szel generálható. Számelméleti szempontból rendkívül fontosak azok az ideálok, amelyek a gyűrű kevés számú – speciálisan akár egyetlen – eleméből alkotott részhalmazaival generálhatók.
19.5A főideálok kapcsolata az oszthatósággal
Ebben a szakaszban integritástartományok – azaz kommutatív, nullosztómentes és egységelemes gyűrűk – főideáljait fogjuk vizsgálni, méghozzá a 16. fejezetben tárgyalt 16.1. Definíció szerinti oszthatósággal való kapcsolatuk szempontjából.
A következő szakaszban az iménti tételt felhasználva a főideálok segítségével mutatni fogunk egy olyan feltételrendszert, amely egyszerre szükséges és elégséges is ahhoz, hogy egy integritástartományban teljesüljön a számelmélet alaptétele. Ezzel végre lezárhatjuk ezt a kérdést, előtte azonban a könnyebb érthetőség kedvéért vizsgáljunk meg egy egyszerű példát.
A halmazrendszerek kapcsán a 19.6. Tételben igazoltuk, hogy a szimbólummal jelölt tartalmazási reláció tulajdonképpen egy részbenrendezés bármilyen halmazrendszer elemei között. Mutattunk néhány példát is arra, hogy egy ilyen részbenrendezés hogyan ábrázolható az úgynevezett Hasse-diagramokon. Ezeket a diagramokat azonban nemcsak konkrétan halmazrendszerek tartalmazási relációjának, hanem tetszőleges halmaz részbenrendezési relációjának megjelenítésére is használhatjuk.
Most felvázolunk egy szép párhuzamot egy integritástartomány főideáljai – mint egy fölötti halmazrendszer elemei – közötti tartalmazási reláció, valamint magának az -nek az elemei közötti oszthatósági reláció között. Ehhez természetesen az kell, hogy a tartalmazási relációhoz hasonlóan az oszthatósági reláció is egy részbenrendezés legyen.
Mivel egységelemes, ezért a 16.2. Tétel 1. pontja alapján minden esetén teljesül az oszthatóság, tehát az oszthatósági reláció reflexív. Ezenkívül ugyanezen tétel 5. pontja alapján tranzitív is, így már csak az antiszimmetria hiányzik ahhoz, hogy részbenrendezés lehessen. Ez a 12.11. Definíció alapján ugye azt jelentené, hogy ha valamilyen és elemek között mindkét irányban teljesül az oszthatóság, akkor abból -nek kéne következnie. A 16.9. Tételben ugyanakkor megmutattuk, hogy sajnos az egyenlőség nem, hanem csak az ennél valamivel gyengébb asszociáltság teljesül.
Ezt a problémát azonban egy trükkel megkerülhetjük. Minthogy az asszociáltság a 16.7. Tétel alapján egy ekvivalenciareláció, így az az gyűrűt a 13.6. Tétel szerint ekvivalencia-osztályokra bontja. Ha mármost minden ilyen ekvivalencia-osztályból legfeljebb egy elemet választunk ki, akkor ilymódon -nek egy olyan részhalmazára térhetünk át, amelyen már az oszthatóság is antiszimmetrikus lesz. Ebben az esetben ugyanis bármely -beli és elemek közötti kölcsönös oszthatóságból következik, hiszen konstrukciója miatt csak ebben az esetben teljesülhet az asszociáltság.
Például az egész számok gyűrűjéből válasszuk ki a nemnegatív osztóit, és nevezzük ezt a halmazt -nek. Ekkor a 16.10. Tétel alapján bármely -beli elempár között csak akkor teljesül az asszociáltság – és így a kölcsönös oszthatóság –, ha a két elem megegyezik. Ezen a halmazon tehát az oszthatóság már egy részbenrendezési reláció, amelynek Hasse-diagramját a 19.8. ábra mutatja.
Most tekintsük azt a fölötti halmazrendszert, amely a -ben lévő elemek által generált főideálokból áll. Ezen a halmazrendszeren a főideálok közötti tartalmazási reláció a 19.6. Tétel alapján szintén egy részbenrendezés lesz, amelynek a Hasse-diagramját a 19.9. ábra mutatja.
Mint látható, a két Hasse-diagram gyakorlatilag megegyezik. Mindössze abban különböznek egymástól, hogy az egyik a másiknak a feje tetejére állított változata. Nos ez nem véletlenül van így, hanem az imént bizonyított 19.12. Tétel miatt. Ez ugye kimondja, hogy az oszthatósági reláció pontosan akkor teljesül, amikor a tartalmazási reláció is teljesül.
A részbenrendezett halmazok nyelvén ezt úgy is meg lehet fogalmazni, hogy az elem pontosan akkor "kisebb" -nél az oszthatósági reláció szerint, amikor az főideál "nagyobb" a főideálnál a tartalmazási reláció szerint, és fordítva. A két részbenrendezési reláció tehát lényegében épp egymás fordítottja, és mivel a halmaz elemei kölcsönösen egyértelműen megfeleltethetők az általuk generált főideáloknak, ezért a két Hasse-diagram csak az irányításban különbözik egymástól. Pontosan ezt fogjuk kihasználni a következő szakaszban.
19.6A főideálok és a számelmélet alaptétele
De vajon az iménti észrevételeknek mi köze van a számelmélet alaptételéhez? Ahhoz, hogy a számelmélet alaptétele teljesüljön egy integritástartományon alapvetően két dolog kell: a prímtényezős felbontás létezése, illetve annak egyértelműsége. Ezt precízen a 16.16. Definícióban fogalmaztuk meg.
Az egyértelműségi állításra már mutattunk egy olyan feltételt, amely szükséges és egyben elégséges is. A 16.17. és a 16.18. Tételek alapján az egyértelműségi állítás akkor és csak akkor teljesül egy integritástartományon, ha minden felbonthatatlan eleme prímtulajdonságú. Ez tehát biztosan része lesz annak a feltételrendszernek, amely pontosan meghatározza, hogy mikor teljesül az alaptétel, és mikor nem. Nem érünk azonban sokat az egyértelműségi garanciával, ha magának a felbontásnak a létezése nem garantált. Ebben a szakaszban arról lesz szó, hogy a létezéshez mire van szükség pontosan.
Ehhez elevenítsük fel egy kicsit az euklidészi gyűrűk fogalmát, amelyekkel a 17.6. szakaszban foglalkoztunk bővebben. Ezeknek az integritástartományoknak az volt a speciális tulajdonságuk, hogy minden nemnulla elemükhöz hozzá tudtunk rendelni egy nemnegatív egész számot egy úgynevezett euklidészi függvény segítségével. Méghozzá a 17.21. Tétel alapján egyrészt olymódon, hogy bármely kéttényezős szorzat tényezőihez ez a függvény legfeljebb akkora számot rendeljen hozzá, mint magához a szorzathoz. Másrészt pedig a 17.22. Tétel alapján olymódon, hogy egyenlőség akkor és csak akkor teljesüljön, ha valamelyik tényező egység.
Tulajdonképpen ez garantálja a prímtényezős felbontás létezését, hiszen bármely elem esetén az alábbi három eset lehetséges:
- Az elem egyáltalán nem bontható szorzatra.
- Az elemnek csak triviális felbontása létezik.
- Az elemnek létezik nemtriviális felbontása alakban.
Az 1. és a 2. esetben -t a 16.11. Definícióban felbonthatatlan elemnek neveztük, amelynek a prímtényezős felbontása alatt a 16.16. Definíció szerint önmagát, mint egytényezős szorzatot értjük. A probléma a 3. esettel lehet, méghozzá akkor, ha a szorzat tényezői a végtelenségig bonthatók tovább nemtriviális módon.
Az euklidészi gyűrűkben azonban az euklidészi függvény említett tulajdonságai szerencsére ezt megakadályozzák. Máskülönben ugyanis az történne, hogy a "felbontási fában" lefelé haladva egy olyan, a gyűrű elemeiből álló végtelen sorozatot tudnánk mutatni, amelynek a tagjaihoz az euklidészi függvény egyre kisebb és kisebb számokat rendel hozzá.
Ez viszont lehetetlen, hiszen az euklidészi függvény értékkészlete a természetes számok halmaza, márpedig a 17.15. Tételben megmutattuk, hogy bármely részhalmazának létezik minimuma. Egy idő után tehát a "felbontási fa" minden ágán garantáltan "bele kell ütköznünk" egy olyan elembe, amely tovább már nem bontható nemtriviálisan. Habár megemlítettük, hogy létezik olyan alaptételes gyűrű is, amely nem euklidészi, ám a "felbonthatatlan elembe ütközés garanciájának" alapgondolata talán átmenthető erre az általános esetre is.
Ehhez a főideálok jelentik a kulcsot. Ugye azt szeretnénk, hogy bármely elem felbontási fájának minden ágán előbb-utóbb garantáltan beleütközzünk egy felbonthatatlan elembe. Ehhez az kell, hogy a gyűrű bármely részhalmazában létezzen "minimális" elem az oszthatósági reláció szerint. A 19.5. szakaszban felvázolt példa alapján ez pontosan akkor fog teljesülni, ha létezik "maximális" főideál a tartalmazási reláció szerint.
Ezt fogalmazza meg precízen az alábbi tétel, amely tehát egy szükséges és elégséges feltételrendszert ad a számelmélet alaptételére bármilyen integritástartomány esetén.
Ezzel végérvényesen lezárthatjuk a számelmélet alaptételének kérdését, hiszen az iménti tétel segítségével már bármilyen integritástartományról egyértelműen eldönthető, hogy alaptételes-e vagy sem.
19.7Főideálgyűrűk
Végül megismerkedünk gyűrűk egy számunkra nagyon fontos osztályával, amelybe – mint látni fogjuk – az egész számok gyűrűje is beletartozik. Ezeknek a speciális gyűrűknek fontos tulajdonságaik vannak a cikksorozat további fejezeteiben tárgyalt kriptográfiai eljárások szempontjából. Előszöris nézzük meg, mik ezek a speciális gyűrűgyűrűk.
Egy főideálgyűrűben tehát minden ideál valamelyik elemből, illetve annak többszöröseiből áll. Minket elsősorban az egész számok gyűrűje fog érdekelni a további fejezetekben. Minden bizonnyal nem lesz túl meglepő, hogy is egy főideálgyűrű. A következő tételben egy ennél erősebb állítást igazolunk.
Felhívnánk a figyelmet arra, hogy az iménti tétel megfordítása nem igaz. Létezik olyan főideálgyűrű, amely nem euklidészi. Ilyenek bizonyos úgynevezett "algebrai egész számokból" alkotott gyűrűk, ám ennek a témakörnek a részleteire a szükséges algebrai ismeretek hiányában egyelőre nem tudunk bővebben kitérni.
A 17.8. szakaszban már igazoltuk, hogy minden euklidészi gyűrű alaptételes. Most ugyanezt fogjuk megmutatni az ennél általánosabb főideálgyűrűkre is, azaz megmutatjuk, hogy minden főideálgyűrű teljesíti az előző szakaszban bizonyított 19.13. Tétel szerinti feltételeket.
Az 1. feltétel ugye azt követeli meg, hogy bármilyen, főideálokból álló halmazrendszerben legyen maximális elem. Ehhez először igazolni fogunk egy segédtételt. A 19.9. Tételben már megmutattuk, hogy ideálok metszete is ideál. De vajon mi a helyzet az olyan halmazokkal, amelyek ideálok úniójaként állnak elő? Az ilyen halmazok általában nem ideálok. Tekintsük például a gyűrűben lévő és főideálokat. Ezek úniója azokból az egész számokból áll, amelyek -vel vagy -mal oszthatók.
Ez a halmaz könnyen láthatóan nem ideál, hiszen még csak nem is részgyűrű, mivel nem zárt az összeadásra. Például a és a benne van ebben az únióhalmazban, de az összegük nem, mivel az nem többszöröse sem -nek, sem pedig -nak. Az alábbi segédtétel egy olyan speciális esetről szól, amikor bizonyos ideálok úniója mégis ideál. Felhívjuk a figyelmet, hogy a segédtétel nem csak integritástartományokra, hanem bármilyen gyűrűre alkalmazható.
Például az imént említett és ideálokra nem alkalmazható a segédtétel, mert sem , sem pedig nem teljesül. Ezzel szemben a ideálokból álló sorozatra teljesül a feltétel, így a segédtétel alapján a únióhalmaz is ideál -ben. Ez végülis nyilvánvaló, hiszen a és a ideál is részhalmaza a ideálnak, így ezek úniója valójában maga a ideál.
Ami már kevésbé nyilvánvaló, hogy a segédtétel végtelen sok ideálból álló halmazrendszerekre is működik. Sőt, még akkor is, ha ezek között esetleg nincs is a 19.7. Definíció szerinti értelemben vett legbővebb ideál. Ilyen lehet például egy ideálokból álló végtelen
sorozat. Nézzük is meg, hogy miért.
Most rátérünk annak igazolására, hogy minden főideálgyűrű teljesíti a 19.13. Tétel szerinti 1. feltételt. Az alábbi tétel valójában egy ennél erősebb állítást mond ki, és 19.16. Lemmához hasonlóan nem csak integritástartományokra, hanem bármilyen gyűrűre működik.
Eszerint tehát ahhoz, hogy egy gyűrű főideáljaira teljesüljön a 19.13. Tétel szerinti 1. feltétel elegendő, ha az ideálok végesen generáltak. Ez speciálisan főideálgyűrűkre nyilván teljesül, hiszen az ezekben lévő ideálok szintén végesen generáltak – konkrétan egyetlen elem által.
Ahhoz, hogy főideálgyűrűkre is igazoljuk az alaptétel teljesülését, hátravan még a 19.13. Tétel szerinti 2. feltétel. Ez azt követeli meg, hogy minden felbonthatatlan elem prímtulajdonságú legyen. Szerencsére ehhez a 17.12. Tétel alapján elegendő azt igazolni, hogy egy főideálgyűrűben bármely két elemnek létezik kitüntetett közös osztója. Ezért most azt fogjuk megnézni, hogy milyen összefüggés van a kitüntetett közös osztó, és a gyűrű ideáljai között.
Mostmár könnyedén igazolhatjuk az alaptétel teljesülését minden főideálgyűrűre.
19.8Összefoglalás
Most tehát már van egy átfogó képünk a különböző típusú gyűrűkről. A 19.10. ábrán ezek egymáshoz való viszonyait ábrázoltuk.
A gyűrűket alapvetően az alábbi három nagy osztályba sorolhatjuk:
- Kommutatív gyűrűk: ezekben az összeadáshoz hasonlóan a szorzás is kommutatív, azaz a tényezők sorrendje felcserélhető.
- Egységelemes gyűrűk: ezekben az összeadáshoz hasonlóan a szorzásra nézve is létezik neutrális elem.
- Nullosztómentes gyűrűk: ezekben két elem szorzata garantáltan csak akkor lehet a nullelem, ha legalább az egyik tényező szintén a nullelem.
Integritástartományoknak azokat a gyűrűket neveztük, amelyek egyszerre kommutatívak, nullosztómentesesek és egységelemesek. Ezek pontosan a fenti három nagy osztály közös metszetében helyezkednek el. Ezeken belül külön osztályt alkotnak azok az integritástartományok, amelyekben teljesül a számelmélet alaptétele. Ezeket alaptételes gyűrűknek nevezzük.
Az alaptételes gyűrűk újabb alosztályát alkotják a 19.7. szakaszban megismert főideálgyűrűk. Ezekben a speciális integritástartományokban bármely két elemnek garantáltan létezik kitüntetett közös osztója, és ez igen fontos lesz számunkra a további fejezetekben. Fontos megjegyezni, hogy léteznek olyan alaptételes gyűrűk, amelyek nem főideálgyűrűk. Ám ilyen példákra a szükséges algebrai ismeretek hiányában ebben a cikksorozatban nem tudunk kitérni.
A 17. fejezetben volt szó az úgynevezett euklidészi gyűrűkről, amelyek egy újabb speciális alosztály alkotnak a főideálgyűrűk között. Ezekben nemcsak a kitüntetett közös osztó létezése garantált, hanem a maradékos osztás elvégezhetősége révén egy gyors algoritmust is kaptunk a kezünkbe ennek kiszámítására. Ezt az eljárást euklidészi algoritmusnak neveztük el, amely szintén egy fontos összetevője a hamarosan terítékre kerülő kriptográfiai eljárásoknak. A 17.20. Tételben igazoltuk, hogy az egész számok gyűrűje is ehhez az alosztályhoz tartozik.
Végül a legspeciálisabb alosztályt a testek alkotják, amelyekben nem csak az összeadás, hanem a szorzás is invertálható. A legkézenfekvőbb példát testre a számfogalom további bővítésével tudnánk mutatni, amelynek során a gyűrűt beágyazzuk a -val jelölt úgynevezett "racionális számtestbe" – ezeket az objektumokat a hétköznapi nyelvezetben "törtszámokként" emlegetjük. Ebben a cikksorozatban erre nem fogunk kitérni, azonban a további fejezetekben más úton ugyan, de fogunk találkozni bizonyos testekkel.
Ebben a fejezetben tehát végérvényesen lezártuk a számelmélet alaptételének kérdését azáltal, hogy egyszerre szükséges és elégséges feltételrendszert mutattunk a teljesülésére. Ehhez egy rövid halmazelméleti gyorstalpaló után az ideálok elméletének néhány alapvető összefüggésével ismerkedtünk meg. Végül bevezettük az euklidészi gyűrűknél általánosabb főideálgyűrűk fogalmát, és igazoltuk, hogy ezekben is mindig teljesül az alaptétel.
A következő fejezettől kezdve elsősorban a főideálgyűrűk – és speciálisan az egész számok gyűrűjének – ideáljaival, valamint az ezek szerinti kongruenciákkal és faktorgyűrűkkel fogunk foglalkozni. Ennek során az RSA algoritmus és a különböző prímtesztelő eljárások számelméleti összetevőivel ismerkedünk meg.