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 $f$ gyűrűhomomorfizmustól, hanem csak azoktól az elemektől, amelyekhez $f$ a célgyűrű nullelemét rendeli hozzá. Ezt a részhalmazt $f$ 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 $N$ -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 $2$ -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:

19.1. Definíció (Halmazelméleti alapfogalmak):

A halmazelmélet mindössze két alapfogalmat használ. Ezek: a "halmaz" és az "eleme lenni" reláció. A halmazokat konvencionálisan nyomtatott nagybetűkkel jelöljük.

Azt, hogy egy $a$ objektum eleme az $A$ halmaznak, így jelöljük:

a \in A

Azt, hogy $a$ nem eleme $A$ -nak, így jelöljük:

a \in / A

E két állítás közül minden esetben pontosan az egyik teljesül.

Két halmazra akkor mondjuk, hogy egyenlőek egymással, ha pontosan ugyanazok az elemeik. Ha tehát $A$ és $B$ halmazok, akkor az $A = B$ kifejezés azt jelenti, hogy minden $a$ objektum esetén $a \in A$ akkor és csak akkor teljesül, ha $a \in B$ is teljesül.

Azt a halmazt, amelynek egyetlen eleme sincsen, üres halmaznak nevezzük, és így jelöljük: $\emptyset$ . Tehát minden $a$ objektum esetén

a \in / \emptyset

Ezzel szemben azt a halmazt, amelynek minden objektum eleme, univerzális halmaznak, tárgyalási univerzumnak, vagy egyszerűen csak univerzumnak nevezzük, és így jelöljük: $U$ . Tehát minden $a$ objektum esetén

a \in U

Egy halmaz (elemeinek) megadása kapcsos zárójelek között történik. Erre néhány példa látható a definíció utáni megjegyzésben. Bármilyen leírást is használunk, akkor mondjuk, hogy megadtunk egy halmazt, ha a tárgyalási univerzum minden objektumáról el lehet dönteni, hogy eleme-e a halmaznak vagy nem.

♣

Megjegyzés:

Jelöljük például $P$ -vel a páros számok halmazát, és adjuk meg $P$ -t az elemek intuitív módon történő felsorolásával:

P = {\dots; - 4; - 2; 0; 2; 4; \dots}

Ugyanezt a $P$ halmazt megadhatjuk az úgynevezett döntési szabállyal is, amely alapján bármilyen $x$ objektumról el lehet dönteni, hogy eleme-e $P$ -nek vagy nem.

P = {x : 2∣ x}

Kiolvasva: "olyan $x$ -ek, amelyek oszthatók $2$ -vel".

De akár szövegesen is megadhatjuk a $P$ halmazt, ha az az adott kontextusban kellőképpen egyértelmű:

P = {p \overset{a}{ˊ} ros eg \overset{e}{ˊ} szek}

A definícióval kapcsolatban megjegyezzük az alábbiakat:

Az üres halmaz egyértelmű, azaz csak egy üres halmaz létezik. Tegyük fel ugyanis indirekt, hogy két üres halmaz is létezik, amelyek különbözőek. Jelöljük ezeket

\emptyset_{1}

-gyel és

\emptyset_{2}

-vel. Ezek különbözősége a definíció szerint azt jelenti, hogy van olyan

a

objektum, amely esetén

a \in / \emptyset_{1}

, de

a \in \emptyset_{2}

, vagy pedig

a \in \emptyset_{1}

, de

a \in / \emptyset_{2}

. De ez ellentmond annak a ténynek, hogy a

\emptyset_{1}

és a

\emptyset_{2}

halmazoknak nincs egyetlen eleme sem.

Hasonló okok miatt az

U

univerzális halmaz is egyértelmű. Tegyük fel ugyanis indirekt, hogy két univerzális halmaz is létezik, amelyek különbözőek. Jelöljük ezeket

U_{1}

-gyel és

U_{2}

-vel. Ezek különbözősége a definíció szerint azt jelenti, hogy van olyan

a

objektum, amely esetén

a \in / U_{1}

, de

a \in U_{2}

, vagy pedig

a \in U_{1}

, de

a \in / U_{2}

. De ez ellentmond annak a ténynek, hogy az

U_{1}

és az

U_{2}

halmazoknak minden objektum eleme.

A definícióban szereplő "halmaz" és "eleme lenni" kifejezések az alapfogalmak szerepét töltik be ugyanúgy, mint a 11.1. Definíció szerinti Peano-axiómarendszerben szereplő "nulla" és "rákövetkező" szavak. Ezeket nem definiáljuk, hanem helyette az axiómákban fogalmazzuk meg a velük szemben támasztott követelményeket.

A definícióban implicit módon csak két axióma szerepel. Az egyik arról szól, hogy minden objektum vagy eleme egy adott halmaznak, vagy pedig nem, harmadik lehetőség nincs. Ezt a matematikai logikában a "kizárt harmadik elvének" nevezzük. A másik axióma azt fogalmazza meg, hogy mikor nevezünk egyenlőnek két halmazt. Ezt meghatározottsági (vagy extenzionalitási) axiómának nevezzük. A naív halmazelméletben nincsenek további axiómák.

♣

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 $Z$ 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 $S$ halmaz bizonyos részhalmazait is. Ebben az esetben az univerzális halmaz $S$ -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.

19.2. Definíció (Részhalmaz):

Legyenek $A$ és $B$ valamilyen halmazok. Tegyük fel továbbá, hogy minden olyan esetben, amikor $a \in A$ teljesül, egyúttal teljesül $a \in B$ is. Ekkor azt mondjuk, hogy az $A$ halmaz részhalmaza a $B$ halmaznak, vagy más szavakkal a $B$ halmaz tartalmazza az $A$ halmazt. Ezt így jelöljük:

A \subseteq B

Bármilyen $B$ halmaz esetén az üres halmaz és maga a teljes $B$ nyilvánvalóan részhalmaza $B$ -nek. Ezeket triviális részhalmazoknak nevezzük. Azt, hogy egy valamilyen $A$ halmaz részhalmaza $B$ -nek, de $A \neq = B$ így jelöljük:

A \subset B

Ilyenkor azt mondjuk, hogy $A$ valódi részhalmaza $B$ -nek, vagy $A$ és $B$ között szigorú tartalmazás áll fenn.

♣

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.

Megjegyzés:

Az imént bevezetett

\subseteq

szimbólummal jelölt tartalmazási relációt ne keverjük össze a 19.1. Definícióban bevezetett

\in

relációval. Nagyon nem ugyanaz a két fogalom! Ha például

A

és

B

két halmaz, akkor

A \subseteq B

azt fejezi ki, hogy

A

összes eleme egyúttal

B

-nek is eleme. Ezzel szemben

A \in B

azt fejezi ki, hogy

B

egy olyan halmaz, amelynek elemei maguk is halmazok, és ezek közül az

A

halmaz az egyik. A 18.8. szakaszban a 18.23. Tétel szerinti maradékosztálygyűrűknek például az elemei maradékosztályok, amelyek ugye maguk is halmazok. Gyakran fogjuk ugyanakkor használni a "

B

tartalmazza

A

-t elemként" kifejezést. Ilyenkor értelemszerűen mindig az

A \in B

"eleme lenni"-relációra, és nem pedig az

A \subseteq B

tartalmazási relációra gondolunk.

\emptyset

-vel jelölt üres halmaz részhalmaza tetszőleges

A

halmaznak, máskülönben létezne olyan

a \in \emptyset

, amelyre viszont

a \in / B

. Ez ellentmondás, ugyanis a 19.1. Definíció alapján tetszőleges

a

esetén

a \in / \emptyset

, azaz az üres halmaznak egyetlen eleme sincs.

Minden

A

halmaz esetén

A \subseteq A

, máskülönben létezne olyan

a

objektum, amelyre

a \in A

és

a \in / A

egyszerre teljesül. Ez ellentmondana a 19.1. Definíció utáni megjegyzés 4. pontjában szereplő "kizárt harmadik elvének".

Minden

A

halmaz részhalmaza továbbá az

U

univerzális halmaznak, máskülönben létezne olyan

a

objektum, amelyre

a \in A

teljesül ugyan, azonban

a \in / U

. Ez ellentmondás, ugyanis a 19.1. Definíció alapján tetszőleges

a

esetén

a \in U

, azaz univerzális halmaznak eleme minden objektum.

Két halmaz akkor és csak akkor egyenlő egymással, ha részhalmazai egymásnak. Ha ugyanis

A = B

, akkor a 3. pont miatt

A \subseteq B

és

B \subseteq A

nyilván teljesül. Visszafelé: Egyrészt, ha

A \subseteq B

teljesül, akkor

a \in A

-ból következik

a \in B

. Másrészt ha

B \subseteq A

is teljesül, akkor

a \in B

-ből is következik

a \in A

. Ebben az esetben tehát

a \in A

akkor és csak akkor, ha

a \in B

, azaz a két halmaznak pontosan ugyanazok az elemei, és így a 19.1. Definíció alapján egyenlőek egymással.

♣

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.

19.3. Definíció (Halmazműveletek):

Legyen $A$ és $B$ két tetszőleges halmaz. Ekkor az $A$ és $B$ halmazok úniójának (vagy egyesítésének) nevezett halmaznak azok az objektumok az elemei, amelyek elemei az $A$ és $B$ közül legalább az egyiknek. Ezt a halmazt így jelöljük:

A \cup B

Az $A$ és $B$ halmazok metszetének (vagy közös részének) nevezett halmaznak azok az objektumok az elemei, amelyek elemei az $A$ halmaznak is és a $B$ halmaznak is. Ezt a halmazt így jelöljük:

A \cap B

Ha $A$ és $B$ metszetének egyáltalán nincsenek elemei – azaz $A \cap B = \emptyset$ –, akkor őket diszjunkt halmazoknak nevezzük.

Végül az $A$ és $B$ halmazok különbségének nevezett halmaznak azok az objektumok az elemei, amelyek elemei az $A$ halmaznak, de nem elemei a $B$ halmaznak. Ezt a halmazt így jelöljük:

A ∖ B

Amennyiben $B \subseteq A$ , akkor az $A ∖ B$ halmazra azt mondjuk, hogy ő a $B$ halmaz komplementere $A$ -ban. Beszélhetünk egy valamilyen $A$ halmaznak egyszerűen csak a komplementeréről, amely alatt az $U ∖ A$ halmazt értjük, ahol $U$ jelöli a 19.1. Definíció szerinti univerzális halmazt. Az $A$ halmaz komplementerét így jelöljük:

\overline{A}

♣

Ha például $A = {1; 2; 3}$ , $B = {3; 4; 5}$ , és az $U$ 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 \cup B A \cap B A ∖ B B ∖ A \overline{A} \overline{B} = {1; 2; 3; 4; 5} = {3} = {1; 2} = {4; 5} = {4; 5; 6; \dots} = {1; 2; 6; 7; 8; \dots}

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.

**19.1. ábra:** Halmazműveletek szemléltetése Venn-diagramokon

**19.2. ábra:** Tartalmazási reláció szemléltetése Venn-diagramon

A 19.3. Definíció szerinti halmazműveletekre érvényesek az alábbi tulajdonságok.

19.4. Tétel (Halmazműveletek tulajdonságai):

Legyenek $A$ , $B$ és $C$ tetszőleges halmazok, valamint jelölje $U$ az univerzális, $\emptyset$ pedig az üres halmazt. Ekkor teljesülnek az alábbiak:

Az üres halmaz az unióképzés, az univerzális halmaz pedig a metszetképzés műveletére nézve neutrális elem, azaz:

A \cup \emptyset A \cap U = A = A

Mindkét műveletre teljesül az úgynevezet idempotencia, azaz:

A \cup A A \cap A = A = A

Mindkét művelet kommutatív, azaz:

A \cup B A \cap B = B \cup A = B \cap A

Mindkét művelet asszociatív, azaz:

(A \cup B) \cup C (A \cap B) \cap C = A \cup (B \cup C) = A \cap (B \cap C)

A két művelet kölcsönösen disztributív egymásra nézve, azaz:

A \cup (B \cap C) A \cap (B \cup C) = (A \cup B) \cap (A \cup C) = (A \cap B) \cup (A \cap C)

Mindkét műveletre teljesül az úgynevezett elnyelési tulajdonság, azaz:

A \cup (A \cap B) A \cap (A \cup B) = A = A

Az üres halmaz és az univerzális halmaz egymás komplementerei, azaz:

\overline{\emptyset} \overline{U} = U = \emptyset

A komplementerképzést duplán elvégezve az eredeti halmazt kapjuk vissza, azaz:

\overline{\overline{A}} = A

Bármely halmaz és komplementerének úniója az univerzális halmaz, metszetük pedig az üres halmaz, azaz:

A \cup \overline{A} A \cap \overline{A} = U = \emptyset

10.

Teljesülnek az úgynevezett de Morgan-azonosságok, azaz:

\overline{A \cup B} \overline{A \cap B} = \overline{A} \cap \overline{B} = \overline{A} \cup \overline{B}

♣

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.

Bizonyítás:

Az 1. tulajdonság: Ez nyilvánvalóan következik az üres halmaz és az univerzális halmaz definíciójából. Az üres halmaznak ugyanis nincs egyetlen eleme sem, így a vele végzett únióképzés nem ad hozzá elemeket semmilyen halmazhoz. Ehhez hasonlóan az univerzális halmaznak minden objektum az eleme, így a vele végzett metszetképzés nem vesz el elemeket semmilyen halmazból.

A 2. tulajdonság: Ez is teljesen nyilvánvalóan adódik az únió- és a metszetképzés definíciójából.

A 3. tulajdonság: Ha $a \in A$ vagy $a \in B$ közül legalább az egyik teljesül, akkor ez nyilván nem változik a két feltétel megcserélésével sem. Így tehát az $A \cup B$ halmaz pontosan meg fog egyezni a $B \cup A$ halmazzal. Ugyanez a gondolatmenet a metszetképzéssel is végigjátszható.

A 4. tulajdonság Az únióképzésre vonatkozó asszociativitás mindkét oldalán az a halmaz szerepel, amelynek minden $a$ eleme esetén $a \in A$ , $a \in B$ vagy $a \in C$ közül legalább az egyik teljesül, hiszen teljesen mindegy, hogy ezt a három feltételt milyen sorrendben ellenőrizzük le. A metszetképzés vonatkozó asszociativitásra ugyanez a gondolatmenet végigjátszható.

Az 5. tulajdonság: Csak az első disztributivitási szabályt fogjuk igazolni, a másik nagyon hasonló gondolatmenettel igazolható. A 19.2. Definíció utáni megjegyzés 5. pontja alapján azt kell megmutatnunk, hogy a kifejezés két oldalán lévő halmazok kölcsönösen részhalmazai egymásnak. E két tartalmazási reláció igazolásának technikai részleteit az alábbiakban ismertetjük.

A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)

Tegyük fel, hogy egy $x$ objektum benne van a baloldali, azaz az $A \cup (B \cap C)$ únióhalmazban. Itt az únió miatt két eset lehetséges. Első esetben $x \in A$ , és ekkor nyilván $x \in A \cup B$ és $x \in A \cup C$ is teljesül, tehát $x \in (A \cup B) \cap (A \cup C)$ is. Második esetben $x \in / A$ , de ekkor viszont az únió miatt $x \in B \cap C$ , tehát $x \in B$ és $x \in C$ egyszerre teljesül. Ilyenkor megintcsak teljesülnek az $x \in A \cup B$ és $x \in A \cup C$ relációk, azaz $x \in (A \cup B) \cap (A \cup C)$ is. Mindkét esetben azt kaptuk, hogyha $x$ eleme a baloldali halmaznak, akkor eleme a jobboldalinak is, tehát a baloldali halmaz valóban részhalmaza a jobboldali halmaznak.

A \cup (B \cap C) \supseteq (A \cup B) \cap (A \cup C)

Most tegyük fel, hogy $x$ benne van a jobboldali, azaz az $(A \cup B) \cap (A \cup C)$ metszethalmazban. Itt a metszet miatt tehát $x \in A \cup B$ és $x \in A \cup C$ is teljesül. Ez két ok miatt teljesülhet. Egyrészt, ha $x \in A$ , akkor jók vagyunk, mert ekkor $x$ benne van minkét únióban, és így ezek metszetében is. Ha $x \in / A$ , akkor viszont $x \in B$ és $x \in C$ kell teljesüljön, ami azt jelenti, hogy $x \in B \cap C$ . Azt kaptuk, hogy $x \in A$ vagy $x \in B \cap C$ közül legalább az egyik teljesül, azaz $x \in A \cup (B \cap C)$ is. Ha tehát $x$ eleme a jobboldali halmaznak, akkor eleme a baloldalinak is, tehát a jobboldali halmaz valóban részhalmaza a baloldali halmaznak.

A 6. tulajdonság: Nézzük először az $A \cup (A \cap B)$ kifejezést. Mivel a metszetképzés miatt bármilyen $x$ objektum esetén ha $x \in A \cap B$ , akkor $x \in A$ , ezért ez egyben azt is jelenti, hogy a zárójelben lévő metszet részhalmaza $A$ -nak. A fenti kifejezésben tehát tulajdonképpen az $A$ halmaznak egy $X$ részhalmazával vett úniója szerepel. Az $A \cup X$ únió viszont nyilvánvalóan $A$ -val egyezik meg, mivel $X$ -nek nincs olyan eleme, ami ne lenne magának $A$ -nak is eleme – hiszen $X \subseteq A$ . Valóban igaz tehát, hogy $A \cup (A \cap B) = A$ , azaz teljesül az első elnyelési tulajdonság.

A második elnyelési tulajdonság az 5. pontban igazolt disztributivitásból és a 2. pontban igazolt idempotenciából következik:

A \cap (A \cup B) = (= A A \cap A) \cup (A \cap B) = A \cup (A \cap B) = A

A 7. tulajdonság: Az üres halmaz komplementere az $U ∖ \emptyset$ különbséghalmaz, amely a 19.3. Definíció alapján azokat az elemeket tartalmazza, amelyek benne vannak $U$ -ban, de nincsenek benne az üres halmazban. Tekintve, hogy az üres halmazban egyáltalán nincsenek elemek, ezért ez a különbséghalmaz magával $U$ -val egyezik meg. Ehhez hasonlóan az univerzális halmaz komplementere az $U ∖ U$ különbséghalmaz, amely tehát azokat az elemeket tartalmazza, amelyek benne is vannak és nincsenek is benne $U$ -ban. Ilyen elem létezése a 19.1. Definíció utáni megjegyzés 4. pontjában említett "kizárt harmadik elve" alapján ellentmondás lenne, ezért ez a különbséghalmaz csak az üres halmaz lehet.

A 8. tulajdonság: Az $\overline{A}$ komplementerhalmaz azokat az elemeket tartalmazza, amelyekre nem igaz az, hogy elemei $A$ -nak. Ennek a komplementere pedig azokat, amelyekre nem igaz az, hogy nem elemei $A$ -nak. Ezek viszont a dupla tagadás miatt épp $A$ elemei, azaz valóban $\overline{\overline{A}} = A$ .

A 9. tulajdonság: Az $A$ halmaz és komplementerének úniója azokat az $x$ elemeket tartalmazza, amelyekre $x \in A$ vagy $x \in / A$ közül legalább az egyik teljesül. Ez viszont a 19.1. Definíció utáni megjegyzés 4. pontjában említett "kizárt harmadik elve" alapján minden létező $x$ -re igaz, így tehát valóban $A \cup \overline{A} = U$ . Ehhez hasonlóan az $A$ halmaz és komplementerének metszete az üres halmaz, máskülönben létezne olyan $x$ , amelyre $x \in A$ és $x \in / A$ egyszerre teljesülne, ami ellentmond a "kizárt harmadik elvének". Így tehát valóban $A \cap \overline{A} = \emptyset$ .

Végül a 10. tulajdonság: Az $A \cup B$ komplementerébe azok az $x$ elemek tartoznak, amelyekre nem igaz az, hogy $x \in A$ vagy $x \in B$ közül legalább az egyik teljesül. Másként fogalmazva ezek az elemek sem $A$ -ban, sem pedig $B$ -ben nincsenek benne, azaz ezekre $x \in / A$ és $x \in / B$ egyszerre teljesül. Ez viszont épp $A$ és $B$ komplementerhalmazainak a metszete. Ehhez hasonlóan az $A \cap B$ komplementerébe azok az $x$ elemek tartoznak, amelyekre nem igaz az, hogy $x \in A$ és $x \in B$ egyszerre teljesül. Másként fogalmazva ezek az elemek $A$ és $B$ közül legalább az egyikben nincsenek benne, azaz ezekre $x \in / A$ vagy $x \in / B$ közül legalább az egyik teljesül. Ez viszont épp $A$ és $B$ komplementerhalmazainak az úniója.

∎

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.

19.5. Definíció (Halmazrendszerek):

Legyen $S$ egy tetszőleges halmaz, valamint jelöljük $S$ -sel azt a halmazt, amelynek elemei $S$ -nek bizonyos részhalmazai – de nem feltétlenül az összes. Ekkor az $S$ halmazt egy $S$ feletti halmazrendszernek, magát az $S$ halmazt pedig e halmazrendszer alaphalmazának nevezzük.

Speciálisan azt az $S$ feletti halmazrendszert, amely $S$ összes részhalmazaiból áll – beleértve az üres halmazt és magát $S$ -t is, mint triviális részhalmazokat –, az $S$ halmaz hatványhalmazának nevezzük, és így jelöljük:

P (S)

Az $S$ feletti halmazrendszerek tehát pontosan a $P (S)$ hatványhalmaz részhalmazai.

♣

Tegyük fel például, hogy az alaphalmazunk az alábbi:

S = {1; 2; 3}

Ekkor a $P (S)$ hatványhalmaznak összesen nyolc eleme lesz, méghozzá az $S$ halmaz összes lehetséges részhalmaza:

P (S) = {= \emptyset {}; {1}; {2}; {3}; {1; 2}; {1; 3}; {2; 3}; = S {1; 2; 3}}

Jól vigyázzunk a jelölésekre! Először is a $\emptyset$ itt nem a "nulla" egész számot, hanem az üres halmazt jelöli. Nagyon nem mindegy továbbá, hogy $1$ -et, vagy pedig ${1}$ -et írunk. Az $1$ ugyanis nem a $P (S)$ hatványhalmaznak, hanem magának az $S$ alaphalmaznak egy eleme. Ezzel szemben az egyetlen elemből álló ${1}$ halmaz már a $P (S)$ hatványhalmaznak egy eleme. Látható, hogy a $P (S)$ halmazban valóban benne van $S$ összes részhalmaza elemként. Még a $\emptyset$ -val jelölt üres halmaz, sőt, maga az $S$ alaphalmaz is.

A definíció szerint tehát $P (S)$ maga is egy halmazrendszer $S$ felett, méghozzá a lehető legbővebb, ami csak létezik. De tegyük fel, hogy mi $S$ -nek csak a nemtriviális részhalmazait szeretnénk vizsgálni. Ezek szintén egy halmazrendszert alkotnak $S$ felett, amelyet jelöljünk most $S$ -sel. Ekkor az $S$ halmazrendszer az alábbi hat elemből fog állni:

S = {{1}; {2}; {3}; {1; 2}; {1; 3}; {2; 3}}

Mint ahogyan a definícióban már említettük, az $S$ halmazrendszer $P (S)$ -nek egy részhalmaza lesz, azaz:

S \subseteq P (S)

Nyilván, hiszen minden $S$ -beli elem egyúttal eleme a $P (S)$ hatványhalmaznak is. Előbbi ugyanis az $S$ alaphalmaznak csak a nemtriviális részhalmazait tartalmazza elemként, utóbbi pedig az összeset.

**19.3. ábra:** Alaphalmaz részhalmazainak ábrázolása Venn-diagramon

**19.4. ábra:** Hatványhalmaz ábrázolása Venn-diagramon

Az ábráról az is leolvasható, hogy az $S$ és $T$ halmazrendszerek között egyébként az alábbi szigorú tartalmazási reláció is fennáll:

T \subset S

19.3Halmazrendszerek részbenrendezése

A 12. fejezetben a természetes számok $\leq$ 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 $S$ halmazrendszer is tulajdonképpen nem más, mint egy részbenrendezett halmaz.

19.6. Tétel (Halmazrendszerek részbenrendezése):

Legyen $S$ egy tetszőleges halmaz, $S$ pedig egy $S$ feletti halmazrendszer. Ekkor a 19.2. Definíció szerinti $\subseteq$ reláció egy részbenrendezés az $S$ halmazrendszer elemei között. Azaz a $\subseteq$ reláció reflexív, antiszimmetrikus és tranzitív.

A $\subset$ szigorú tartalmazási reláció ezzel szemben nem részbenrendezés, mivel nem reflexív és nem antiszimmetrikus. A tranzitivitást viszont ez a reláció is teljesíti.

♣

Bizonyítás:

A 19.2. Definíció utáni megjegyzés 3. és 5. pontjai alapján a $\subseteq$ reláció reflexív és antiszimmetrikus. Így már csak azt kell megmutatni, hogy teljesül a tranzitivitás is, azaz $S$ tetszőleges $A$ , $B$ és $C$ elemei esetén ha $A \subseteq B$ és $B \subseteq C$ , akkor $A \subseteq C$ . Ez viszont könnyedén adódik a részhalmaz definíciójából.

Legyen ugyanis $x$ egy tetszőleges elem az $S$ alaphalmazban. Mivel $A \subseteq B$ , ezért ha $x \in A$ teljesül, akkor $x \in B$ is teljesül. Ugyanakkor $B \subseteq C$ is igaz, ezért egyúttal $x \in C$ is teljesül. Mivel azt kaptuk, hogy $x \in A$ -ból következik $x \in C$ , ezért valóban $A \subseteq C$ .

Most térjünk át a $\subset$ relációra vonatkozó állításokra. Ez nyilvánvalóan nem reflexív, ugyanis $A \subset A$ a 19.2. Definíció alapján azt jelentené, hogy $A \subseteq A$ és $A \neq = A$ . Ez utóbbi nyilván lehetetlen, mivel minden halmaz azonos önmagával. De antiszimmetrikus sem lehet, máskülönben a 12.11. Definíció miatt $A \subset B$ és $B \subset A$ esetén $A = B$ következne. Ez ugye lehetetlen, mert például $A \subset B$ azt jelenti, hogy $A \subseteq B$ és $A \neq = B$ .

Végül megmutatjuk, hogy $\subset$ tranzitív. Tegyük fel, hogy $A \subset B$ és $B \subset C$ . Ezek a feltételek a 19.2. Definíció alapján azt jelentik, hogy egyrészt $A \subseteq B$ és $B \subseteq C$ , másrészt pedig $A \neq = B$ és $B \neq = C$ . Az első két feltételből a $\subseteq$ reláció már bizonyított tranzitivitása miatt $A \subseteq C$ következik, tehát a $\subset$ reláció tranzitivitásához elegendő azt megmutatni, hogy $A \neq = C$ .

A $B \subseteq C$ tartalmazás miatt egyrészt tudjuk, hogy $B$ minden eleme $C$ -nek is eleme. Másrészt $B \neq = C$ miatt azt is tudjuk, hogy $C$ -nek van olyan $x$ eleme, ami viszont nem eleme $B$ -nek, azaz $x \in / B$ . Azt kell igazolni, hogy $x \in / A$ is igaz. Ez viszont nyilvánvaló, máskülönben $A \subseteq B$ miatt $x \in B$ mégiscsak teljesülne, ami ellentmondás. A $\subset$ -val jelölt szigorú tartalmazási reláció tehát valóban tranzitív.

∎

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.

**19.5. ábra:** Hatványhalmaz Hasse-diagramja

A diagramon az is jól látszik, hogy a $\subseteq$ 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 $Z$ gyűrűjének vagy a természetes számok $N$ halmazának rendezése teljesíti ezt az extra tulajdonságot is, ezért neveztük őket teljes rendezésnek. Ezzel szemben a $\subseteq$ reláció nem egy teljes rendezés, hiszen például az ${1; 2}$ és a ${2; 3}$ részhalmazok között egyik irányban sem teljesül a tartalmazás, így ők nem "összehasonlíthatók" a $\subseteq$ 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 ${2}$ és az ${1; 2; 3}$ részhalmazok között fennáll a tartalmazási reláció, hiszen ${2}$ -ből felfelé kiindulva két lépés után az ${1; 2; 3}$ -hoz érkezünk két különböző útvonalon is.

A $P (S)$ halmazrendszer Hasse-diagramját vizsgálva feltűnhet, hogy az egész számok $Z$ 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 $S$ 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.

19.7. Definíció (Minimális és maximális elem):

Legyen $S$ egy tetszőleges halmaz, $\leq$ pedig egy $S$ -en értelmezett részbenrendezési reláció. Vezessük be továbbá az $a < b$ jelölést annak kifejezésére, hogy $a \leq b$ és $a \neq = b$ .

Az $a \in S$ elemet minimális elemnek nevezzük, ha nem létezik $x \in S$ úgy, hogy $x < a$ teljesülne.

Az $a \in S$ elemet legkisebb (vagy legszűkebb) elemnek nevezzük, ha minden $x \in S$ esetén $a \leq x$ teljesül.

Ehhez hasonlóan az $a \in S$ elemet maximális elemnek nevezzük, ha nem létezik $x \in S$ úgy, hogy $a < x$ teljesülne.

Az $a \in S$ elemet legnagyobb (vagy legbővebb) elemnek nevezzük, ha minden $x \in S$ esetén $x \leq a$ teljesül.

♣

Megjegyzés:

Tekintve, hogy a 19.6. Tétel értelmében minden halmazrendszer maga is egy részbenrendezett halmaz a $\subseteq$ szimbólummal jelölt tartalmazási relációra nézve, ezért természetesen e fogalmak ezekre is könnyen átfogalmazhatók. Csak ekkor az iménti definícióban szereplő $S$ halmaz szerepét egy valamilyen $T$ alaphalmaz feletti $T$ halmazrendszer, a $\leq$ részbenrendezési reláció szerepét a $\subseteq$ tartalmazási reláció, a $<$ reláció szerepét a $\subset$ szigorú tartalmazás, végül az elemek szerepét a $T$ halmazrendszer elemei, azaz a $T$ alaphalmaz részhalmazai veszik át. Ilyenkor általában a "legkisebb" vagy a "legnagyobb" elemek helyett a "legszűkebb" vagy a "legbővebb" részhalmazokról beszélünk.

♣

A P(S) és S halmazrendszerek Hasse-diagramja — **19.6. ábra:** A $P (S)$ és $S$ halmazrendszerek Hasse-diagramja

Látható, hogy minimuma és maximuma mindkét halmazrendszernek van. A $P (S)$ halmazrendszer minimuma a $\emptyset$ -val jelölt üres halmaz, maximuma pedig a teljes $S$ alaphalmaz. Az $S$ 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 $S$ -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 $S$ -ben, amelynek ezek bármelyike valódi részhalmaza lenne.

Ezzel szemben legszűkebb illetve legbővebb eleme csak a $P (S)$ halmazrendszernek van, méghozzá szintén az üres halmaz és a teljes $S$ alaphalmaz. Előbbi ugyanis a halmazrendszer minden elemének részhalmaza, utóbbinak pedig a halmazrendszer minden eleme részhalmaza. Viszont az $S$ 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 $\subseteq$ 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.

19.8. Tétel:

Legyen $S$ egy tetszőleges részbenrendezett halmaz. Ekkor $S$ -ben legfeljebb egy legkisebb (illetve legnagyobb) elem létezhet.

Ezen túlmenően, ha $a \in S$ a legkisebb (illetve legnagyobb) elem, akkor egyrészt $a$ minimális (illetve maximális) elem, másrészt ilyenkor ő az egyetlen minimális (illetve maximális) elem.

♣

Megjegyzés:

Természetesen a tétel halmazrendszerekre is kimondható, csak ekkor a 19.7. Definíció utáni megjegyzésben foglaltak szerint kell átfogalmazni.

♣

Bizonyítás:

Jelöljük a $\leq$ szimbólummal az $S$ halmazon értelmezett részbenrendezési relációt, továbbá vezessük be az $a < b$ jelölést annak kifejezésére, hogy $a \leq b$ és $a \neq = b$ .

Tegyük fel, hogy $a$ és $b$ is legkisebb elem $S$ -ben. Mivel $a$ legkisebb elem, ezért tetszőleges $x \in S$ -re $a \leq x$ teljesül. Többek között például $b$ -re is, azaz $a \leq b$ . Másrészt, mivel $b$ is legkisebb elem, ezért ugyanilyen gondolatmenettel $a \geq b$ is teljesül. Ám mivel a $\leq$ reláció antiszimmetrikus, ezért a 12.11. Definíció utáni megjegyzés miatt $a = b$ . Egy részbenrendezett halmaz legkisebb eleme tehát – amennyiben egyáltalán létezik – egyértelmű. Ugyanilyen gondolatmenettel belátható, hogy a legnagyobb elem is egyértelmű.

Tegyük fel most indirekt, hogy $a \in S$ a legkisebb elem, azonban mégsem minimális. Ez egyrészt azt jelentené, hogy létezik olyan $x \in S$ , amelyre $x < a$ teljesül. Másrészt, mivel $a$ a legkisebb elem $S$ -ben, ezért $a \leq x$ -nek is teljesülnie kéne. Ez viszont lehetetlen, hiszen a bevezetett jelölés értelmében $x < a$ ugye azt jelenti, hogy $x \leq a$ de $x \neq = a$ . Ugyanakkor, mivel indirekt feltételezésünk szerint $a \leq x$ , ezért az antiszimmetria miatt $a = x$ , ami ellentmondás. Egy részbenrendezett halmaz legkisebb eleme tehát – amennyiben egyáltalán létezik – mindenképpen minimális. Ugyanilyen gondolatmenettel belátható, hogy a legnagyobb elem pedig mindenképpen maximális.

Végül tegyük fel, hogy $a \in S$ legkisebb elem, amely tehát minimális, de létezik egy másik minimális elem is, amelyet jelöljünk most $b$ -vel. Mivel $a$ a legkisebb elem, ezért $a \leq b$ teljesül. Ugyanakkor, mivel $b$ minimális, ezért $a < b$ nem teljesülhet. Ez a bizonyítás elején bevezetett $<$ jelölés értelmében csak $a = b$ esetén lehetséges, hiszen azt már láttuk, hogy $a \leq b$ teljesül. Tehát valóban $a$ az egyetlen minimális elem. Ugyanilyen gondolatmenettel belátható, hogy amennyiben $a$ a legnagyobb elem $S$ -ben, akkor egyúttal ő az egyetlen maximális elem.

∎

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 $Z$ halmaza felett könnyen találhatunk olyan halmazrendszert, amelynek nincs legbővebb eleme. Ilyen például az alábbi halmazokból álló rendszer:

A_{0} A_{1} A_{2} A_{3} A_{4} = \emptyset = {1} = {1; 2} = {1; 2; 3} = {1; 2; 3; 4} ⋮

Látható, hogy ennek a halmazokból álló sorozatnak minden tagja valódi részhalmaza a rákövetkező tagnap, így ebben a $Z$ feletti halmazrendszerben nem létezik legbővebb elem. Ezzel szemben elsőre nehéz elképzelni egy olyan halmazrendszert $Z$ 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:

A_{0} A_{1} A_{2} A_{3} A_{4} = Z = Z ∖ {1} = Z ∖ {1; 2} = Z ∖ {1; 2; 3} = Z ∖ {1; 2; 3; 4} ⋮

Ennek a sorozatnak az első tagja tehát a teljes $Z$ 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 $Z$ feletti halmazrendszerben nem létezik legszűkebb elem.

**19.7. ábra:** Szakasz feletti halmazrendszer

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 $R$ alaphalmaz, amelyen értelmezve van két művelet. Ennek megfelelően $R$ részgyűrűi és ideáljai is halmazok, méghozzá $R$ részhalmazai. Más szavakkal ezek is egy-egy halmazrendszert alkotnak $R$ felett. Előszöris megmutatjuk, hogy milyen hatása van a metszetképzésnek ezekre a halmazrendszerekre.

19.9. Tétel:

Legyen $R$ egy tetszőleges gyűrű, valamint legyen $S$ egy olyan $R$ feletti halmazrendszer, amely $R$ valahány – akár végtelen számú – részgyűrűjéből áll. Ekkor az $S$ -ben lévő halmazok metszete is részgyűrű $R$ -ben.

Ehhez hasonlóan ha az $I$ egy olyan halmazrendszer, amely $R$ valahány – akár végtelen számú – balideáljából (illetve jobbideáljából) áll, akkor az $I$ -ben lévő halmazok metszete is balideál (illetve jobbideál) $R$ -ben.

Végül ha $J$ egy olyan halmazrendszer, amely $R$ valahány – akár végtelen számú – (kétoldali) ideáljából áll, akkor a $J$ -ben lévő halmazok metszete is (kétoldali) ideál $R$ -ben.

♣

Például az egész számok $Z$ gyűrűjében a $2$ -vel és $3$ -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 $2 Z$ -vel és $3 Z$ -vel jelölhetjük. E két ideál metszetét azok az egész számok alkotják, amelyek $2$ -vel is és $3$ -mal is oszthatók. Ezek épp a $6$ -tal osztható egész számok lesznek, azaz:

2 Z \cap 3 Z = 6 Z

Ez szintén ideál $Z$ -ben, épp ahogyan a tétel állítja. Nézzük meg, hogy miért igaz ez általánosságban is.

Bizonyítás:

Nézzük először a részgyűrűk metszetére vonatkozó állítást! Jelöljük $S$ -sel az $S$ halmazrendszerben lévő részgyűrűk metszetét. Azt kell megmutatni, hogy $S$ részgyűrű $R$ -ben. Ez a 18.15. Tétel szerint pontosan akkor teljesül, ha $S$ zárt az $R$ -beli összeadásra, szorzásra és ellentettképzésre, valamint tartalmazza az $R$ gyűrű nullelemét.

Mivel $S$ minden eleme részgyűrű, így a 18.15. Tétel miatt mindegyik tartalmazza az $R$ gyűrű nullelemét. A nullelem tehát valóban benne van ezek metszetében, azaz $S$ -ben.

Legyen most $x$ az $S$ halmaz egy tetszőleges eleme. Mivel $S$ az $S$ -beli részgyűrűk metszete, így $x$ e részgyűrűk mindegyikének szintén eleme, amelyek viszont ismét a 18.15. Tétel miatt zártak az ellentettképzésre. Így $- x$ is eleme az összes $S$ -beli részgyűrűnek, vagyis valóban benne van ezek metszetében, azaz $S$ -ben.

Végül legyen $x$ és $y$ az $S$ halmaz két tetszőleges eleme. Mivel $S$ az $S$ -beli részgyűrűk metszete, így $x$ és $y$ e részgyűrűk mindegyikének szintén eleme, amelyek viszont ismét a 18.15. Tétel miatt zártak az összeadásra és szorzásra. Így az $x + y$ összeg, valamint az $x \cdot y$ szorzat is eleme az összes $S$ -beli részgyűrűnek, vagyis valóban benne vannak ezek metszetében, azaz $S$ -ben. Az $S$ tehát valóban részgyűrű $R$ -ben, ahogyan a tétel állítja.

Most nézzük a balideálok metszetére vonatkozó állítást! Jelöljük $I$ -vel az $I$ halmazrendszerben lévő balideálok metszetét. Azt kell megmutatni, hogy $I$ balideál $R$ -ben. Ez a 18.18. Definíció szerint azt jelenti, hogy egyrészt $I$ részgyűrű $R$ -ben, másrészt akármelyik $a \in I$ elemet balról megszorozva akármelyik $r \in R$ elemmel, az így kapott $r \cdot a$ szorzat szintén benne van $I$ -ben. Minthogy $I$ minden eleme részgyűrű $R$ -ben – hiszen balideál –, ezért a már bizonyított állítás alapján $I$ is részgyűrű $R$ -ben. Elegendő tehát csak a baloldali szorzásra vonatkozó feltételt ellenőrizni.

Tegyük fel, hogy $a$ az $I$ részgyűrű, $r$ pedig az $R$ gyűrű egy tetszőleges eleme. Mivel $I$ az $I$ -beli balideálok metszete, így $a$ e balideálok mindegyikének szintén eleme. Emiatt az $r \cdot a$ szorzat is benne van az összes $I$ -beli balideálban, tehát ezek metszetében is, azaz $I$ -ben. Emiatt $I$ valóban balideál $R$ -ben.

A jobbideálok metszetére vonatkozó állítás értelemszerűen ugyanezzel a gondolatmenettel igazolható azzal a különbséggel, hogy ekkor az $r \cdot a$ szorzat helyett az $a \cdot r$ szorzatot kell tekinteni.

Végül a (kétoldali) ideálok metszetére vonatkozó állítás triviálisan adódik, hiszen minden (kétoldali) ideál egyszerre bal- és jobbideál.

∎

Most egy $R$ gyűrűben azokat a részgyűrűket (vagy ideálokat) fogjuk megvizsgálni, amelyek $R$ -nek egy adott $X$ részhalmazát tartalmazzák. Ezek a részgyűrűk (vagy ideálok) szintén egy halmazrendszert alkotnak $R$ felett, amelynek egy fontos tulajdonságát mondja ki az alábbi tétel.

19.10. Tétel (Generált részgyűrű és ideál):

Legyen $R$ egy tetszőleges gyűrű, továbbá $X$ az $R$ gyűrűnek egy tetszőleges részhalmaza. Jelöljük $X$ -szel azt az $R$ fölötti halmazrendszert, amelynek elemei pontosan azok a részgyűrűk $R$ -ben, amelyek tartalmazzák $X$ -et.

Ekkor $X$ -ben létezik pontosan egy legszűkebb elem, amelyet az $X$ által generált részgyűrűnek nevezünk, és $⟨ X ⟩$ -szel jelölünk. Ilyenkor azt mondjuk, hogy az $X$ részhalmaz generálja ezt a bizonyos részgyűrűt – amely természetesen lehet maga a teljes $R$ is, mint triviális részgyűrű.

Ugyanilyen értelemben beszélhetünk az $X$ által generált bal-, jobb- vagy kétoldali ideálról is.

♣

Bizonyítás:

A 19.8. Tétel alapján egy halmazrendszerben legfeljebb egy legszűkebb elem létezhet. Így elegendő megmutatni, hogy létezik legszűkebb elem, az ugyanis garantáltan az egyetlen lesz.

Mivel $X$ az $R$ gyűrű tetszőleges részhalmaza lehet, ezért előszöris kérdés, hogy létezik-e egyáltalán olyan részgyűrű, amely tartalmazza $X$ -et? Erre természetesen igen a válasz, hiszen "legrosszabb esetben" maga a teljes $R$ egy ilyen részgyűrű. Az $X$ halmazrendszer tehát biztosan nem üres.

Most képezzük az $X$ halmazrendszer összes elemének metszetét, és jelöljük ezt a halmazt $S$ -sel. Minthogy $X$ elemei részgyűrűk $R$ -ben, így a 19.9. Tétel alapján $S$ is részgyűrű $R$ -ben. Továbbá az $X$ -ről azt mondtuk, hogy ő részhalmaza minden $X$ -beli részgyűrűnek, emiatt részhalmaza ezek metszetének, azaz $S$ -nek is.

Ez viszont azt jelenti, hogy $S$ maga is az $X$ halmazrendszer eleme, hiszen ő is egy $X$ -et tartalmazó részgyűrű $R$ -ben. Ráadásul mivel ő a metszete $X$ összes elemének, ezért egyben részhalmaza is azoknak. Másként fogalmazva bármilyen $T \in X$ részgyűrűre teljesül, hogy $S \subseteq T$ . Ez a 19.7. Definíció szerint viszont épp azt jelenti, hogy $S$ nem más, mint az $X$ halmazrendszer legszűkebb eleme. Más szavakkal $S$ a legszűkebb olyan részgyűrű $R$ -ben, amely tartalmazza az $X$ részhalmazt, azaz a tételbeli jelölést használva:

S = ⟨ X ⟩

A legszűkebb $X$ -et tartalmazó bal-, jobb-, illetve kétoldali ideál létezésére és egyértelműségére vonatkozó állítás a fentiekhez teljesen hasonló módon igazolható.

∎

Ez alapján tehát egy adott $R$ gyűrű bármely $X$ részhalmaza egyértelműen meghatároz egy ideált. Ez lesz az $X$ -et tartalmazó legszűkebb ideál. Ugyanakkor ez a tétel semmit nem mond arról, hogy az $X$ által generált $⟨ X ⟩$ ideált lehet-e generálni egy $X$ -nél szűkebb részhalmazzal is vagy nem. Amikor tehát azt mondjuk, hogy egy ideál "generálható $X$ -szel", ez még nem jelenti azt, hogy az adott ideál kizárólag $X$ -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.11. Definíció (Végesen generált ideálok és főideálok):

Legyen $R$ tetszőleges gyűrű, $I$ pedig valamilyen ideál $R$ -ben. Amennyiben $R$ -nek létezik olyan véges számú elemet tartalmazó $X = {a_{1}; a_{2}; \dots; a_{n}}$ részhalmaza, amely esetén $⟨ X ⟩ = I$ , akkor azt mondjuk, hogy az $I$ ideál végesen generált. Ezt így jelöljük:

I = (a_{1}, a_{2}, \dots, a_{n})

Speciálisan ha $I$ generálható az $R$ gyűrű egyetlen $a$ elemével – azaz $X = {a}$ –, akkor $I$ -t főidálnak nevezzük. Az $a \in R$ által generált $I$ főideált így jelöljük:

I = (a)

♣

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.

19.12. Tétel:

Legyen $R$ tetszőleges integritástartomány, valamint legyenek $a$ és $b$ az $R$ tetszőleges elemei. Ekkor teljesülnek az alábbiak:

(a) \subseteq (b)

tartalmazási reláció akkor és csak akkor teljesül, ha a

b ∣ a

oszthatóság is teljesül.

(a) = (b)

egyenlőség akkor és csak akkor teljesül, ha

a \sim b

, azaz

a

és

b

egymás asszociáltjai.

♣

Bizonyítás:

Előszöris vizsgáljuk meg az $(a)$ és $(b)$ főideálok szerkezetét. A 19.11. Definíció alapján az $(a)$ főideál az a legszűkebb ideál, amely tartalmazza az $a$ elemet. Mivel $a \in (a)$ , ezért a 18.18. Definíció szerint tetszőleges $r \in R$ esetén szükségképpen $r a \in (a)$ is teljesül. Azaz az $(a)$ ideál biztosan tartalmazza az $a$ elemen kívül annak összes többszörösét is. Egyéb elemet viszont nem tartalmaz, hiszen úgy már nem ő lenne az $a$ elemet tartalmazó legszűkebb ideál. Ugyanezen okok miatt a $(b)$ főideál pedig a $b$ elemet és annak többszöröseit tartalmazza, és ezeken kívül nincs más eleme. Ezek után már igazolhatjuk a tétel állításait.

Az 1. állítás: Egyrészt azt kell bizonyítani, hogy ha teljesül a $b ∣ a$ oszthatóság, akkor bármilyen $c \in (a)$ esetén $c \in (b)$ is teljesül, azaz $(a) \subseteq (b)$ . A $c \in (a)$ a fentiek alapján azt jelenti, hogy $c$ vagy megegyezik $a$ -val, vagy pedig annak többszöröse. Mivel $R$ egységelemes, ezért mindkét feltételből az következik, hogy teljesül az $a ∣ c$ oszthatóság. De mivel kiindulási feltételünk szerint teljesül a $b ∣ a$ oszthatóság, ezért a 16.2. Tétel 5. pontja alapján teljesül a $b ∣ c$ oszthatóság is. Ez viszont egységelemes gyűrűkben azt jelenti, hogy $c$ megegyezik $b$ -vel, vagy pedig egyike a többszöröseinek, azaz $c \in (b)$ . Mivel megmutattuk, hogy az $(a)$ főideál bármely eleme egyúttal eleme a $(b)$ főideálnak is, így a 19.2. Definíció alapján valóban $(a) \subseteq (b)$ .

Másrészt bizonyítani kell az ellentétes irányú következtetést is, vagyis azt, hogy ha $(a) \subseteq (b)$ , akkor teljesül a $b ∣ a$ oszthatóság. Az $(a) \subseteq (b)$ tartalmazási reláció a 19.2. Definíció alapján azt jelenti, hogy az $(a)$ főideál bármely eleme egyúttal eleme a $(b)$ főideálnak is. Ez természetesen magára $a$ -ra is igaz, azaz $a \in (b)$ . Így tehát $a$ vagy megegyezik $b$ -vel, vagy pedig egyike a $b$ elem többszöröseinek. Mivel $R$ egységelemes, ezért mindkét feltételből az következik, hogy teljesül a $b ∣ a$ oszthatóság.

A 2. állítás: Ez már könnyen adódik az 1. állításból. A 19.2. Definíció utáni megjegyzés 5. pontja alapján ugyanis az $(a) = (b)$ halmazegyenlőség akkor és csak akkor teljesül, ha $(a)$ és $(b)$ kölcsönösen egymás részhalmazai. Ez az 1. állítás miatt azzal ekvivalens, hogy egyszerre teljesülnek az $a ∣ b$ , valamint a $b ∣ a$ oszthatóságok. A 16.9. Tétel alapján azonban a kölcsönös oszthatóság kommutatív és egységelemes gyűrűkben akkor és csak akkor teljesül, ha $a$ és $b$ egymás asszociáltjai.

∎

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 $\subseteq$ 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 $R$ integritástartomány főideáljai – mint egy $R$ fölötti halmazrendszer elemei – közötti tartalmazási reláció, valamint magának az $R$ -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 $R$ egységelemes, ezért a 16.2. Tétel 1. pontja alapján minden $a \in R$ esetén teljesül az $a ∣ a$ 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 $a$ és $b$ elemek között mindkét irányban teljesül az oszthatóság, akkor abból $a = b$ -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 $a \sim b$ 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 $R$ 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 $R$ -nek egy olyan $S$ részhalmazára térhetünk át, amelyen már az oszthatóság is antiszimmetrikus lesz. Ebben az esetben ugyanis bármely $S$ -beli $a$ és $b$ elemek közötti kölcsönös oszthatóságból $a = b$ következik, hiszen $S$ konstrukciója miatt csak ebben az esetben teljesülhet az $a \sim b$ asszociáltság.

**19.8. ábra:** Nemnegatív osztók Hasse-diagramja

**19.9. ábra:** Nemnegatív osztók által generált főideálok Hasse-diagramja

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 $a ∣ b$ oszthatósági reláció pontosan akkor teljesül, amikor a $(b) \subseteq (a)$ tartalmazási reláció is teljesül.

A részbenrendezett halmazok nyelvén ezt úgy is meg lehet fogalmazni, hogy az $a$ elem pontosan akkor "kisebb" $b$ -nél az oszthatósági reláció szerint, amikor az $(a)$ főideál "nagyobb" a $(b)$ 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 $D$ 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 $R$ integritástartományon, ha $R$ 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 $a$ elem esetén az alábbi három eset lehetséges:

Az $a$ elem egyáltalán nem bontható szorzatra.
Az $a$ elemnek csak triviális felbontása létezik.
Az $a$ elemnek létezik nemtriviális felbontása $a = b c$ alakban.

Az 1. és a 2. esetben $a$ -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 $b c$ 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 $N$ halmaza, márpedig a 17.15. Tételben megmutattuk, hogy $N$ 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.

19.13. Tétel:

Legyen $R$ tetszőleges integritástartomány. A számelmélet alaptétele akkor és csak akkor teljesül $R$ -ben, ha fennállnak az alábbi feltételek:

R

tetszőleges, főideálokból álló nemüres halmazrendszer

R

fölött, akkor

R

-ben létezik maximális elem a 19.7. Definíció szerinti értelemben.

R

integritástartományban minden felbonthatatlan elem prímtulajdonságú.

♣

Bizonyítás:

Nézzük elégségességet! Azaz tegyük fel, hogy $R$ -re teljesül a tételben említett mindkét feltétel, és mutassuk meg, hogy ekkor $R$ -ben teljesül a számelmélet alaptétele. Az 1. feltétel azt jelenti, hogy akárhogyan is választunk ki valahány – akár végtelen sok – főideált $R$ -ben, azok között mindig lesz maximális elem a 19.7. Definíció szerinti értelemben. Tegyük fel továbbá indirekt, hogy ennek ellenére léteznek olyan, a nullelemtől és egységektől különböző elemek $R$ -ben, amelyek nem bonthatók fel felbonthatatlanok szorzatára a 16.16. Definíció szerinti értelemben. Minden ilyen hipotetikus elemhez készítsük el az általa generált főideált, és jelöljük $R$ -rel az összes ilyen főideál halmazát. Az 1. feltétel miatt $R$ -ben létezik maximális elem. Jelöljük ezt a főideált $(m)$ -mel, amely tehát az $m$ elemet és annak többszöröseit tartalmazza.

Az indirekt feltevésünk alapján ugye $m$ -nek nem létezik prímtényezős felbontása. Emiatt az $m$ elem maga nem lehet felbonthatatlan, máskülönben ő – a 16.16. Definíció értelmében – saját magának az egytényezős felbontása lenne. Mivel $m$ nem felbonthatatlan, ezért a 16.11. Definíció alapján ő felírható $m = ab$ alakban, méghozzá olymódon, hogy sem $a$ , sem pedig $b$ nem egység, és nem is asszociáltjai $m$ -nek. Ezt összevetve azzal, hogy teljesülnek az $a ∣ m$ és a $b ∣ m$ oszthatóságok, a 19.12. Tétel alapján fennállnak az $(m) \subset (a)$ és az $(m) \subset (b)$ szigorú tartalmazási relációk.

Mivel az $(m)$ főideálról azt mondtuk, hogy az $R$ halmazrendszer maximális eleme, így sem az $(a)$ , sem pedig a $(b)$ főideálok nem lehetnek elemei $R$ -nek. Ezért nekik már létezik prímtényezős felbontásuk:

a b = p_{1} p_{2} \dots p_{k} = q_{1} q_{2} \dots q_{n}

Ám ekkor $m = ab$ miatt:

m = = a p_{1} p_{2} \dots p_{k} \cdot = b q_{1} q_{2} \dots q_{n}

Ez épp $m$ -nek lenne egy prímtényezős felbontása, ami indirekt feltételezésünk szerint nem létezhetne. Ez ellentmondás, azaz mégiscsak minden nemnulla és nem egység elemenek létezik prímtényezős felbontása $R$ -ben. Továbbá a 2. feltétel miatt minden felbonthatatlan elem prímtulajdonságú, ezért a 16.18. Tétel értelmében egy ilyen prímtényezős felbontás – a tényezők sorrendjétől és asszociáltságtól eltekintve – egyértelmű.

Most igazoljuk a szükségességet! Azaz tegyük fel, hogy $R$ -ben teljesül a számelmélet alaptétele, és mutassuk meg, hogy ebben az esetben a tételben említett feltételek is teljesülnek. Ha teljesül az alaptétel, akkor a 16.17. Tétel alapján minden felbonthatatlan elem prímtulajdonságú, azaz teljesül a 2. feltétel, és így már csak az 1. feltételt kell igazolni. Tegyük fel indirekt, hogy nem teljesül az 1. feltétel, azaz létezik olyan főideálokból álló halmazrendszer $R$ fölött, amelyben nincs maximális elem a 19.7. Definíció szerinti értelemben.

Ezt vessük össze azzal, hogy a 19.6. Tétel alapján a $\subset$ szigorú tartalmazási reláció tranzitív. Emiatt szükségképpen létezik olyan végtelen, főideálokból álló sorozat, amelyben minden főideál szigorúan tartalmazza a sorozatban előtte lévőt:

(a_{1}) \subset (a_{2}) \subset (a_{3}) \subset \dots

A 19.12. Tétel miatt az $a_{1}, a_{2}, a_{3}, \dots$ elemek közül semelyik sem asszociáltja a sorozatban utána lévő elemnek, és mivel a 16.7. Tétel alapján az asszociáltság ekvivalenciareláció, ezért semelyik másiknak sem. Továbbá szintén a 19.12. Tétel miatt teljesülnek az alábbi oszthatóságok:

a_{2} a_{3} a_{4} ∣ a_{1} ∣ a_{2} ∣ a_{3} ⋮

Ezen túlmenően kijelenthetjük azt is, hogy egyrészt legkésőbb $a_{2}$ -től kezdve a sorozat egyik tagja sem lehet a nullelem. Máskülönben ugyanis egy ilyen $a_{i} = 0$ elem által generált $(a_{i})$ főideál csak a nullelemet tartalmazná, és így a 18.15. Tétel szerinti 3. tulajdonság miatt nem létezhetne a nála szűkebb $(a_{i - 1})$ főideál. Másrészt az is igaz, hogy a sorozat egyetlen tagja sem lehet egység, máskülönben ugyanis az általa generált $(a_{i})$ főideál a teljes $R$ gyűrű lenne – hiszen a 16.3. Definíció alapján egy egységnek minden elem többszöröse –, és így nem létezhetne a nála bővebb $(a_{i + 1})$ főideál.

Az $a_{2}$ tehát egy olyan elem, amely nem a nullelem és nem is egység, továbbá az oszthatóság tranzitivitása miatt végtelen sok olyan osztója van, amelyek közül egyik sem egység, és egyik sem asszociáltja $a_{2}$ -nek. Így tehát $a_{2}$ -nek nem létezik prímtényezős felbontása, ami viszont lehetetlen, hiszen azt mondtuk, hogy $R$ -ben teljesül a számelmélet alaptétele. Csak az indirekt feltevésünk lehetett hibás, azaz bármilyen főideálokból álló halmazrendszernek szükségképpen létezik maximális eleme.

∎

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 $Z$ 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.

19.14. Definíció (Főideálgyűrűk):

Legyen $R$ tetszőleges integritástartomány. Amennyiben $R$ minden ideálja főideál – azaz generálható egyetlen elemmel –, akkor $R$ -t főideálgyűrűnek nevezzü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 $Z$ gyűrűje fog érdekelni a további fejezetekben. Minden bizonnyal nem lesz túl meglepő, hogy $Z$ is egy főideálgyűrű. A következő tételben egy ennél erősebb állítást igazolunk.

19.15. Tétel:

Minden euklidészi gyűrű – és így a 17.20. Tétel miatt az egész számok $Z$ gyűrűje is – főideálgyűrű.

♣

Bizonyítás:

Legyen $R$ egy tetszőleges euklidészi gyűrű, $I$ pedig egy tetszőleges ideál $R$ -ben. Azt kell megmutatnunk, hogy létezik olyan $r \in R$ , amely generálja $I$ -t, azaz amelyre $I = (r)$ teljesül. Jelöljük az $R$ euklidészi gyűrű nullelemét $0_{R}$ -rel. Ha $I$ csak a nullelemből áll, akkor $I = (0_{R})$ nyilván teljesül. Feltehetjük tehát, hogy $I$ nem csak a nullelemből áll.

Mivel $R$ euklidészi gyűrű, ezért ennek nemnulla elemein értelmezhető egy $f$ euklidészi függvény, amely eleget tesz a 17.17. Definícióban szereplő feltételeknek. Az $f$ euklidészi függvény tehát az $I$ ideál minden nemnulla eleméhez hozzárendel valamilyen természetes számot. A 17.15. Tétel alapján ennek a számhalmaznak mindenképpen van minimuma függetlenül attól, hogy $I$ végtelen sok elemet tartalmaz-e vagy sem. Legyen $b$ az $I$ ideál egy olyan nemnulla eleme, amelyhez $f$ épp ezt a minimumot rendeli hozzá. Azt kell megmutatni, hogy $b$ generálja az $I$ ideált, azaz $I = (b)$ .

Az egyrészt nyilvánvaló, hogy mivel $b \in I$ , ezért $b$ -nek bármilyen többszöröse is $I$ -ben van. Ez az ideál a 18.18. Definíciójából következik. Másrészt azt kell még igazolnunk, hogy $I$ -nek ezeken kívül nincs is más eleme. Tegyük fel tehát, hogy $a \in I$ , és mutassuk meg, hogy $a$ szükségképpen többszöröse $b$ -nek. Mivel $b \neq = 0_{R}$ , és $R$ euklidészi gyűrű, ezért $a$ és $b$ között a 17.17. Definíció 1. pontja alapján elvégezhető a maradékos osztás. Azaz létezik olyan $k$ hányados és $r$ maradék, hogy:

a = k b + r

Továbbá a 17.17. Definíció 2. pontja alapján az $r$ maradékra az alábbiak közül legalább az egyik teljesül:

r f (r) = 0_{R} < f (b)

Ha $r = 0_{R}$ , akkor $a = k b$ , azaz ekkor $a$ valóban többszöröse $b$ -nek. Tegyük fel indirekt, hogy nem ez a helyzet, azaz $r \neq = 0_{R}$ . Ekkor viszont a másik feltételnek kell teljesülnie, hiszen azt mondtuk, hogy legalább az egyik teljesül. Azaz:

f (r) < f (b)

Egyrészt, mivel $I$ ideál, és $b \in I$ , ezért a 18.18. Definíció miatt $k b \in I$ . Másrészt a kiindulási feltételünk miatt $a \in I$ , és így – mivel $I$ egyben részgyűrű is – a 18.15. Tétel 4. és 1. pontja alapján az $r = a - k b$ maradék is benne van $I$ -ben.

Ez viszont ellentmondás, hiszen a $b$ elemet úgy választottuk meg, hogy ahhoz az $f$ euklidészi függvény a lehető legkisebb természetes számot rendelje hozzá azok közül, amelyeket egyébként az $I$ ideál elemeihez hozzárendel. Az $a$ és $b$ közötti maradékos osztást elvégezve tehát a maradék csak $0_{R}$ lehet, azaz valójában teljesül a $b ∣ a$ oszthatóság. Az $a$ elem tehát többszöröse $b$ -nek, és így $a \in (b)$ teljesül. Más szavakkal a $b$ elem tényleg generálja az $I$ ideált:

I = (b)

Minthogy ez a gondolatmenet tetszőleges ideállal végigjátszható, ezért $R$ valóban főideálgyűrű, ahogyan a tétel állítja.

∎

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 $Z$ gyűrűben lévő $(2)$ és $(3)$ főideálokat. Ezek úniója azokból az egész számokból áll, amelyek $2$ -vel vagy $3$ -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 $2$ és a $3$ benne van ebben az únióhalmazban, de az összegük nem, mivel az $5$ nem többszöröse sem $2$ -nek, sem pedig $3$ -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ó.

19.16. Lemma:

Legyen $R$ egy gyűrű, valamint legyen $S$ egy olyan, részgyűrűkből álló halmazrendszer $R$ fölött, amelyben bármely két részgyűrű között legalább az egyik irányban fennáll a $\subseteq$ szimbólummal jelölt tartalmazási reláció. Ekkor az $S$ -ben lévő részgyűrűk úniója is részgyűrű $R$ -ben.

Ehhez hasonlóan legyen $I$ egy olyan, balideálokból (illetve jobbideálokból) álló halmazrendszer $R$ fölött, amelyben bármely két balideál (illetve jobbideál) között legalább az egyik irányban fennáll a $\subseteq$ szimbólummal jelölt tartalmazási reláció. Ekkor az $I$ -ben lévő balideálok (illetve jobbideálok) úniója is balideál (illetve jobbideál) $R$ -ben.

Végül ha $J$ egy olyan, (kétoldali) ideálokból álló halmazrendszer $R$ fölött, amelyben bármely két (kétoldali) ideál között legalább az egyik irányban fennáll a $\subseteq$ szimbólummal jelölt tartalmazási reláció, akkor a $J$ -ben lévő (kétoldali) ideálok úniója is (kétoldali) ideál $R$ -ben.

♣

Például az imént említett $(2)$ és $(3)$ ideálokra nem alkalmazható a segédtétel, mert sem $(2) \subseteq (3)$ , sem pedig $(3) \subseteq (2)$ nem teljesül. Ezzel szemben a $(8) \subseteq (4) \subseteq (2)$ ideálokból álló sorozatra teljesül a feltétel, így a segédtétel alapján a $(8) \cup (4) \cup (2)$ únióhalmaz is ideál $Z$ -ben. Ez végülis nyilvánvaló, hiszen a $(8)$ és a $(4)$ ideál is részhalmaza a $(2)$ ideálnak, így ezek úniója valójában maga a $(2)$ 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

I_{1} \subseteq I_{2} \subseteq I_{3} \subseteq \dots

sorozat. Nézzük is meg, hogy miért.

Bizonyítás:

Nézzük először a részgyűrűkre vonatkozó állítást! Jelöljük $S$ -sel az $S$ halmazrendszerben lévő részgyűrűk únióját. Azt kell megmutatni, hogy $S$ részgyűrű $R$ -ben. Ez a 18.15. Tétel szerint pontosan akkor teljesül, ha $S$ zárt az $R$ -beli összeadásra, szorzásra és ellentettképzésre, valamint tartalmazza az $R$ gyűrű nullelemét.

Mivel $S$ minden eleme részgyűrű, így a 18.15. Tétel 3. pontja miatt mindegyik tartalmazza $R$ nullelemét. Az tehát valóban benne van ezek úniójában, azaz $S$ -ben.

Legyen most $x$ az $S$ halmaz egy tetszőleges elem. Mivel $S$ az $S$ -beli részgyűrűk úniója, így ezek között biztosan létezik legalább egy olyan $X$ részgyűrű, amelynek $x$ szintén eleme. Az $X$ viszont a 18.15. Tétel 4. pontja miatt zárt az ellentettképzésre. Így $- x$ is eleme $X$ -nek, és emiatt $S$ -nek is.

Végül legyen $x$ és $y$ az $S$ halmaz két tetszőleges eleme. Mivel $S$ az $S$ -beli részgyűrűk úniója, így ezek között biztosan léteznek olyan $X$ és $Y$ részgyűrűk, hogy $x \in X$ és $y \in Y$ teljesül. Mivel az $S$ halmazrendszerben bármely két részgyűrű között legalább az egyik irányban fennáll a tartalmazási reláció, ezért $X \subseteq Y$ vagy $Y \subseteq X$ közül legalább az egyik teljesül.

Ha például $X \subseteq Y$ a helyzet, akkor $x \in X$ miatt $x \in Y$ is teljesül, azaz $x$ és $y$ mindketten benne vannak a $Y$ -ban. De ekkor az összegük és a szorzatuk is benne van $Y$ -ban – mivel $Y$ részgyűrű –, és így $S$ -ben is.

Ha $X \subseteq Y$ nem teljesül, akkor teljesül $Y \subseteq X$ , és ekkor a fentivel megegyező gondolatmenet alapján $x$ és $y$ összege és szorzata $X$ -ben lesz benne, és így megintcsak $S$ -ben is. Az $S$ únióhalmaz tehát valóban részgyűrű $R$ -ben.

Most nézzük a balideálokra vonatkozó állítást! Jelöljük $I$ -vel az $I$ halmazrendszerben lévő balideálok únióját. Azt kell megmutatni, hogy $I$ balideál $R$ -ben. Ez a 18.18. Definíció szerint azt jelenti, hogy egyrészt $I$ részgyűrű $R$ -ben, másrészt akármelyik $a \in I$ elemet balról megszorozva akármelyik $r \in R$ elemmel, az így kapott $r a$ szorzat szintén benne van $I$ -ben. Minthogy $I$ minden eleme részgyűrű $R$ -ben – hiszen balideál –, ezért a fentiek alapján az $I$ únióhalmaz is részgyűrű $R$ -ben. Elegendő tehát csak a baloldali szorzásra vonatkozó feltételt ellenőrizni.

Mivel $a \in I$ , és $I$ az $I$ -beli balideálok úniója, így e balideálok között biztosan létezik olyan $X$ balideál, amelynek $a$ szintén eleme. Minthogy $X$ balideál, emiatt az $r a$ szorzat is benne van $X$ -ben, és így $I$ -ben is. Emiatt $I$ valóban balideál $R$ -ben.

A jobbideálokra vonatkozó állítás értelemszerűen ugyanezzel a gondolatmenettel igazolható azzal a különbséggel, hogy ekkor az $r a$ szorzat helyett az $a r$ szorzatot kell tekinteni.

Végül a (kétoldali) ideálokra vonatkozó állítás triviálisan adódik, hiszen minden (kétoldali) ideál egyszerre bal- és jobbideál.

∎

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.

19.17. Tétel:

Legyen $R$ tetszőleges gyűrű, amelyben minden ideál végesen generált. Legyen továbbá $R$ egy tetszőleges nemüres halmazrendszer $R$ fölött, amelynek minden eleme ilyen végesen generált ideál. Ekkor az $R$ halmazrendszerben létezik maximális elem a 19.7. Definíció szerinti értelemben.

♣

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.

Bizonyítás:

Tegyük fel indirekt, hogy $R$ minden ideálja végesen generált, ám ennek ellenére az $R$ halmazrendszerben nem létezik maximális elem. Ez a 19.7. Definíció alapján azt jelenti, hogy minden $X \in R$ ideál esetén létezik $Y \in R$ ideál, amelyre teljesül az $X \subset Y$ szigorú tartalmazási reláció.

Eszerint tehát $R$ elemeiből alkotható egy olyan végtelen, ideálokból álló sorozat, amelyben minden ideál szigorúan tartalmazza a sorozatban előtte lévőt:

I_{1} \subset I_{2} \subset I_{3} \subset \dots

Képezzük ennek a végtelen sok ideálnak az únióját, és nevezzük az így kapott halmazt $U$ -nak. A 19.16. Lemma alapján ekkor $U$ is ideál az $R$ gyűrűben. Mivel $R$ minden ideálja végesen generált, így $U$ is. Léteznek tehát az $R$ gyűrűben olyan $a_{1}, a_{2}, \dots, a_{n}$ elemek, amelyek generálják az $U$ ideált, azaz:

U = (a_{1}, a_{2}, \dots, a_{n})

Mivel e generátorelemek benne vannak az $U$ únióhalmazban, ezért minden generátorelemnek benne kell lennie az $I_{1}, I_{2}, I_{3}, \dots$ ideálok közül is legalább az egyikben. Mivel ezen ideálok közül mindegyik szigorúan tartalmazza a sorozatban előtte lévőt, ezért kell lennie közöttük egy olyan $I_{k}$ ideálnak, amely már minden generátorelemet tartalmaz – hiszen azok száma véges.

Tehát egyrészt teljesül az $U \subseteq I_{k}$ tartalmazási reláció, hiszen a 19.10. Tétel miatt $U$ a legszűkebb olyan ideál, amely az $a_{1}, a_{2}, \dots, a_{n}$ generátorelemeket tartalmazza. Másrészt a fenti, ideálokból álló sorozat következő tagjára, azaz $I_{k + 1}$ -re ugye teljesül az $I_{k} \subset I_{k + 1}$ szigorú tartalmazási reláció, továbbá az $I_{k + 1} \subseteq U$ tartalmazási reláció is, hiszen $I_{k + 1}$ egyike azon ideáloknak, amelyek úniójából állítottuk elő az $U$ ideált. Ezeket összevetve az alábbit kaptuk:

U \subseteq I_{k} \subset I_{k + 1} \subseteq U

Mivel a $\subseteq$ és a $\subset$ relációk a 19.6. Tétel alapján tranzitívak, ezért ez azt jelenti, hogy végsősoron teljesül az $U \subset U$ szigorú tartalmazási reláció. Ez viszont lehetetlen, hiszen ez a 19.2. Definíció alapján azt jelentené, hogy létezik olyan $x \in U$ , amelyre $x \in / U$ , és ez ellentmond a 19.1. Definíció utáni megjegyzés 4. pontjában megfogalmazott "kizárt harmadik elvének".

Ha tehát $R$ minden ideálja végesen generált, akkor az $R$ halmazrendszernek szükségképpen kell legyen maximuma.

∎

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.

19.18. Tétel:

Legyen $R$ tetszőleges integritástartomány. Legyenek továbbá $a$ , $b$ és $d$ az $R$ tetszőleges elemei, és tegyük fel, hogy halmazegyenlőség áll fenn az $(a, b)$ és a $(d)$ ideálok között, azaz

(a, b) = (d)

Ekkor $d$ kitüntetett közös osztója $a$ -nak és $b$ -nek.

♣

Megjegyzés:

Az Olvasót eddig esetleg zavarhatta, hogy az $a$ és $b$ elemeket tartalmazó legszűkebb ideált ugyanúgy $(a, b)$ -vel jelöljük, mint $a$ és $b$ kitüntetett közös osztóját. Ez a tétel pontosan ennek az okára világít rá.

♣

Bizonyítás:

Az $a$ nyilván benne van az $(a, b)$ ideálban, ami a feltétel alapján a $(d)$ főideállal egyezik meg. Emiatt $a$ összes többszöröse is $(d)$ -ben van. Ezek viszont épp az $(a)$ főideál elemei, azaz $(a) \subseteq (d)$ , és így a 19.12. Tétel alapján teljesül a $d ∣ a$ oszthatóság. Hasonló okok miatt teljesül a $d ∣ b$ oszthatóság is, így $d$ közös osztója $a$ -nak és $b$ -nek. A 17.4. Definíció alapján azt kell még megmutatni, hogy $d$ minden közös osztónak többszöröse.

Legyen tehát $c$ egy tetszőleges közös osztó, azaz $c ∣ a$ és $c ∣ b$ . Ekkor a 19.12. Tétel miatt teljesülnek az $(a) \subseteq (c)$ és a $(b) \subseteq (c)$ tartalmazási relációk. Ez azt jelenti, hogy minden, ami az $(a)$ vagy a $(b)$ főideálok közül legalább az egyiknek eleme, az eleme egyúttal a $(c)$ főideálnak is.

Ez nyilván igaz magára $a$ -ra és $b$ -re is, azaz $a \in (c)$ és $b \in (c)$ . Minthogy az $(a, b)$ ideál a 19.11. Definíció alapján a legszűkebb olyan ideál, amely tartalmazza az $a$ és $b$ elemeket, ezért a $(c)$ főideál biztosan nem lehet nála szűkebb, azaz $(a, b) \subseteq (c)$ . A tételben szereplő $(a, b) = (d)$ feltétel miatt tehát $(d) \subseteq (c)$ teljesül, azaz a 19.12. Tétel miatt fennáll a $c ∣ d$ oszthatóság, és így $d$ valóban kitüntetett közös osztó.

∎

Mostmár könnyedén igazolhatjuk az alaptétel teljesülését minden főideálgyűrűre.

19.19. Tétel:

Minden főideálgyűrű alaptételes.

♣

Bizonyítás:

Azt kell megmutatni, hogy a 19.13. Tétel szerinti mindkét feltétel teljesül. Mivel egy $R$ főideálgyűrű minden ideálja generálható egyetlen elemmel, ezért alkalmazható a 19.17. Tétel. Eszerint bármely, főideálokból álló $R$ feletti halmazrendszernek van maximuma a 19.7. Definíció szerinti értelemben, így teljesül az 1. feltétel.

Legyen $a$ és $b$ az $R$ főideálgyűrű két tetszőleges eleme, és képezzük belőlük az $(a, b)$ ideált, ami ugye a 19.10. Tétel alapján létezik. Minthogy $R$ főideálgyűrű, ezért az $(a, b)$ ideál generálható egyetlen elemmel is. Legyen ez az elem $d$ , azaz:

(a, b) = (d)

A 19.18. Tétel alapján $d$ kitüntetett közös osztója $a$ -nak és $b$ -nek. Mivel tehát igazoltuk, hogy bármely két elemnek létezik kitüntetett közös osztója, ezért a 17.12. Tétel alapján minden felbonthatatlan elem prímtulajdonságú. Azaz teljesül a 19.13. Tétel szerinti 2. feltétel is, és így $R$ valóban alaptételes.

∎

19.8Összefoglalás

**19.10. ábra:** Az eddig megismert gyűrűosztályok térképe

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 $Z$ 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 $Z$ gyűrűt beágyazzuk a $Q$ -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 $Z$ 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.