Episode I

Alice és Bob

12. fejezet

Alice és Bob rendet tesz

Az előző fejezetben kitöröltünk mindent a fejünkből, amit az általános iskolában a számokról tanultunk, és elkezdtük felépíteni a modern kriptográfiai eljárások alapját jelentő számelméletet a semmiből. Mindössze négy egyszerű állításból indultunk ki, amelyet Peano-axiómarendszernek nevezünk, és amelyek rögzítik a pozitív egész számok és a $0$ alapvető tulajdonságait. Ezek halmazát természetes számoknak neveztük, és $N$ -nel jelöltük. Szigorúan az axiómákat használva bevezettünk az $N$ halmazon egy összeadásnak nevezett műveletet, amelyről megmutattuk, hogy – az axiómák logikai következményeként – valóban teljesíti az általános iskolában jól megszokott tulajdonságokat. De vajon mi minden következik még ebből a négy axiómából? Milyen alaptulajdonságai vannak a szorzás műveletének és mi az oka, hogy ezek valóban teljesülnek? Mik azok a relációk és hogy jön ide a "kő-papír-olló" nevű játék? Mit nevezünk rendezett halmaznak és hogyan vezethetjük be a "kisebb-nagyobb" fogalmát a természetes számok között? Ebben a fejezetben erről lesz szó...

Figyelem! Ez a fejezet erőteljesen épít a 11. fejezetben bevezetett alábbi definíciókra és tételekre, amelyekkel elkezdtük a számelmélet felépítését:

E definíciók és tételek kontextusba helyezése miatt erőteljesen ajánlott tehát elolvasni a 11. fejezetet.

A matematika igazi természete kezdett el kibontakozni az előző fejezetben. Nevezetesen: kiindulunk néhány egyszerű állításból, amelyeket igaznak fogadunk el – ez jelen példánkban a Peano-axiómarendszer négy állítása. Nem azért fogadjuk el őket igaznak, mert valamiféle abszolút igazságokat állítanak – olyan talán nem is létezik, ha belegondolunk –, hanem azért, mert ezek rögzítik a felépítendő elmélet "játékszabályait", akárcsak a sakkban. A fogalmainkat közvetlenül vagy közvetett módon az axiómákból építjük fel, és csak olyan további állításokat fogadunk el igaznak, amelyeket szigorú logikai érveléssel az axiómákra, az azok segítségével felépített fogalmakra, vagy korábban már bizonyított állításokra tudunk visszavezetni.

Ennek a tudománynak épp ez adja az erősségét is. Minden más természettudomány alapja ugyanis a kísérletezés. Akárhány kísérletet is végzünk, soha nem lehetünk teljesen biztosak egy tudományos elmélet igazságában, arra csupán megerősítést kapunk. Ha azonban akárcsak egyetlen kísérlet is megcáfolja az elméletünket, azt azonnal dobhatjuk ki a kukába. Ezzel szemben egy matematikai állítás igazsága örök érvényű. Egy bizonyított állítás igaz marad, ameddig világ a világ, arra nyugodtan lehet tovább építkezni, és nincs szükség arra, hogy azt kísérletekkel megerősítsük. A 11.5. szakaszban például a Peano-axiómarendszer segítségével bevezettük az összeadás fogalmát, a 11.6. és a 11.7. szakaszban pedig bizonyítottuk annak kommutativitását és asszociativitását. A továbbiakban tehát nyugodtan építkezhetünk ezekre a tulajdonságokra.

Építkezzünk hát tovább, és kényelmi okok miatt vezessünk be egy újabb műveletet az $N$ halmazon.

12.1A természetes számok szorzása

Képzeljük el azt a szituációt, amikor egy természetes számot önmagával sokszor kell összeadni. Jó volna valamilyen módon rövidíteni az olyan jellegű kifejezéseket, mint például ez: $a + a + a + a + a$ . Itt az $a$ természetes számot ötször adtuk össze önmagával, ami – valljuk be – eléggé kényelmetlen. Ezt elkerülendő, most bevezetünk egy "szorzásnak" nevezett műveletet, amelyet a $\cdot$ szimbólummal fogunk jelölni. A fenti kifejezést például így rövidíthetjük: $a \cdot 5$ .

A szorzás műveletével kapcsolatban azonnal rögzíthetünk két megállapodást. Először is állapodjunk meg abban, hogy mi legyen az eredmény akkor, ha valamit $0$ -val szorzunk meg. Ezt ugye a fenti értelmezés alapján egy $0$ tagú összegként foghatjuk fel. Természetes tehát, ha rögzítjük, hogy tetszőleges $a$ esetén $a \cdot 0$ eredménye $0$ legyen. A másik megállapodásunk pedig legyen az, hogy ha egy $a$ természetes számot egy $b$ természetes szám rákövetkezőjével szorozzuk meg, akkor az ennek megfelelő összegben éppen eggyel többször szerepeljen $a$ , mintha csak $b$ -vel szoroztunk volna.

Ennek megfelelően a most következő definícióval vezetjük be a szorzás műveletét.

12.1. Definíció (Természetes számok szorzása):

Az $N$ halmazon értelmezett, $\cdot$ -tal jelölt kétváltozós műveletet szorzásnak nevezzük, amennyiben teljesülnek rá a következő tulajdonságok:

Tetszőleges

a

természetes szám esetén

a \cdot 0 = 0

Amennyiben valamely

a

és

b

természetes számokra az

a \cdot b

eredménye már ismert, úgy teljesül az

a \cdot s (b) = (a \cdot b) + a

egyenlőség.

A fentiekben $0$ a nulla természetes számot, $s (x)$ az $x$ természetes szám rákövetkezőjét, a $+$ szimbólum pedig a természetes számok összeadását jelöli.

♣

Ez alapján kiszámítható bármely két természetes szám szorzata. Amennyiben például $N$ elemeit a szokásos módon, tízes számrendszerben jelöljük, akkor a $2 \cdot 3$ szorzat az alábbi lépésekben fejthető ki szigorúan a fenti definíció szerint:

2 \cdot 0 2 \cdot 1 2 \cdot 2 2 \cdot 3 = 0 = 2 \cdot s (0) = (2 \cdot 0) + 2 = 0 + 2 = 2 = 2 \cdot s (1) = (2 \cdot 1) + 2 = 2 + 2 = 4 = 2 \cdot s (2) = (2 \cdot 2) + 2 = 4 + 2 = 6

Értelmeztünk tehát egy újabb műveletet az $N$ halmazon, amelyet önkényesen "szorzásnak" neveztünk, és a $\cdot$ műveleti jellel jelöltünk. Az összeadáshoz hasonlóan vizsgáljuk hát meg, hogy ez is teljesíti-e azokat a jól megszokott tulajdonságokat, amelyeket általános iskolai tanulmányaink alapján elvárnánk tőle.

12.2A szorzás kommutativitása

Általános iskolában megtanultuk, hogy az összeadáshoz hasonlóan a szorzás esetén is felcserélhető a két tényező sorrendje. Első jogos kérdés tehát, hogy vajon a 12.1. Definícióban ismertetett szorzás művelete teljesíti-e ezt a kritériumot?

Ennek megmutatásához két segédtételre lesz szükségünk. Az első segédtétel azt mondja ki, hogy a definíció 1. pontjában szereplő esetben a tényezők felcserélhetők – azaz, hogy az $a \cdot 0$ -hoz hasonlóan a $0 \cdot a$ eredménye is $0$ lesz.

12.2. Lemma:

Az $N$ halmaz tetszőleges $a$ elemére igaz az alábbi összefüggés:

0 \cdot a = 0

Itt $0$ a nulla természetes számot jelöli.

♣

Ez ugyan magától értetődőnek tűnik, de ismételten felhívjuk a figyelmet arra, hogy mindenben kételkednünk kell, amit nem vezettünk vissza az axiómákra, az azokból alkotott definíciókra vagy korábban már bizonyított állításokra. Márpedig a $\cdot$ -tal jelölt szorzás jelenleg nem több pusztán egy általunk kreált definíciónál. A bizonyításhoz az előző fejezetben már jól bejáratott teljes indukciót alkalmazzuk, amelynek használatát a 4. Peano-axióma teszi lehetővé.

Bizonyítás:

Az $a$ -ra vonatkozó teljes indukciót alkalmazunk, azaz feltesszük, hogy valamilyen $a = n$ természetes számra az állítás igaz. Az indukciós feltétel tehát: $0 \cdot n = 0$ . Azt kell bizonyítanunk, hogy ekkor $a = s (n)$ -re is igaz lesz, azaz:

0 \cdot = a s (n) = 0

A 12.1. Definíció 2. pontja miatt:

0 \cdot s (n) = (0 \cdot n) + 0 = \dots

A 11.4. Definíció 1. pontja miatt:

\dots = 0 \cdot n = \dots

Végül pedig az indukciós feltétel miatt:

\dots = 0

Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Ezért most felborítjuk az első dominót, azaz igazoljuk, hogy az állítás igaz $a = 0$ -ra.

Ez viszont nyilvánvalóan teljesül a 12.1. Definíció 1. pontja miatt:

0 \cdot = a 0 = 0

Borul tehát az első dominó, és vele együtt a teljes dominósor, azaz minden $a$ természetes számra igaz, hogy $0 \cdot a = 0$ .

∎

A kommutativitáshoz szükséges második segédtétel lényegében azt mondja ki, hogy mi történik a 12.1. Definíció 2. pontjában szereplő képlettel, ha felcseréljük a tényezőket:

12.3. Lemma:

Az $N$ halmaz tetszőleges $a$ és $b$ elemeire igaz az alábbi összefüggés:

s (b) \cdot a = (b \cdot a) + a

Itt $s (x)$ az $x$ természetes szám rákövetkezőjét, a $+$ szimbólum pedig a természetes számok összeadását jelöli.

♣

Bizonyítás:

Az $a$ -ra vonatkozó teljes indukciót alkalmazunk, azaz feltesszük, hogy valamilyen $a = n$ természetes számra az állítás igaz. Az indukciós feltétel tehát: $s (b) \cdot n = (b \cdot n) + n$ . Azt kell bizonyítanunk, hogy ekkor $a = s (n)$ -re is igaz lesz, azaz:

s (b) \cdot s (n) = (b \cdot s (n)) + s (n)

A 12.1. Definíció 2. pontja miatt:

s (b) \cdot s (n) = (s (b) \cdot n) + s (b) = \dots

Az indukciós feltétel miatt a zárójel átírható:

\dots = (= s (b) \cdot n (b \cdot n) + n) + s (b) = \dots

A 11.10. Tétel miatt az összeadás asszociatív, ezért ezt a kifejezést átzárójelezhetjük:

\dots = (b \cdot n) + (n + s (b)) = \dots

A 11.4. Definíció 2. pontja miatt a zárójel átírható:

\dots = (b \cdot n) + = (n + s (b)) s (n + b) = \dots

A 11.8. Tétel miatt az összeadás kommutatív, ezért a jobboldali tagban szereplő $s$ függvény paramétere átírható:

\dots = (b \cdot n) + s (= n + b b + n) = \dots

Ismételten a 11.4. Definíció 2. pontja miatt:

\dots = (b \cdot n) + = s (b + n) (b + s (n)) = \dots

A 11.10. Tétel miatt az összeadás asszociatív, ezért ez a kifejezés ismételten átzárójelezhető:

\dots = ((b \cdot n) + b) + s (n) = \dots

Végül ismét a 12.1. Definíció 2. pontja miatt miatt a zárójelben lévő kifejezés átírható:

\dots = (= (b \cdot n) + b b \cdot s (n)) + s (n)

Vagyis azt kaptuk, hogy valóban $s (b) \cdot = a s (n) = (b \cdot = a s (n)) + = a s (n)$ .

Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni.

Ezért most felborítjuk az első dominót, azaz igazoljuk, hogy az állítás igaz $a = 0$ -ra, azaz:

s (b) \cdot = a 0 = (b \cdot = a 0) + = a 0

Ez viszont nyilvánvalóan teljesül, hiszen a 12.1. Definíció 1. pontja miatt:

s (b) \cdot 0 = 0 = \dots

Szintén ugyanezen ok miatt:

\dots = b \cdot 0 = \dots

Végül a 11.4. Definíció 1. pontja miatt:

\dots = (b \cdot 0) + 0

Borul tehát az első dominó, és vele együtt a teljes dominósor, azaz minden $b$ és $a$ természetes számra igaz, hogy $s (b) \cdot a = (b \cdot a) + a$ .

∎

Ezután az imént bizonyított 12.2. és 12.3. Lemma segítségével bizonyítjuk a szorzás kommutativitását:

12.4. Tétel:

A természetes számok szorzása kommutatív. Másként fogalmazva az $N$ halmaz tetszőleges $a$ és $b$ elemeire igaz az alábbi összefüggés:

a \cdot b = b \cdot a

♣

Bizonyítás:

A $b$ -re vonatkozó teljes indukciót alkalmazunk, azaz feltesszük, hogy valamilyen $b = n$ természetes számra az állítás igaz. Az indukciós feltétel tehát: $a \cdot n = n \cdot a$ . Azt kell bizonyítanunk, hogy ekkor $b = s (n)$ -re is igaz lesz, azaz:

a \cdot = b s (n) = = b s (n) \cdot a

A 12.1. Definíció 2. pontja miatt:

a \cdot s (n) = (a \cdot n) + a = \dots

Az indukciós feltétel miatt:

\dots = (n \cdot a) + a = \dots

Végül a 12.3. Lemma miatt:

\dots = s (n) \cdot a

Vagyis azt kaptuk, hogy valóban $a \cdot = b s (n) = = b s (n) \cdot a$ .

Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Az első dominót pedig már fel is borítottuk, ugyanis a 12.2. Lemma alapján az állítás igaz $b = 0$ -ra.

Borul tehát az első dominó, és vele együtt a teljes dominósor, azaz minden $a$ és $b$ számra igaz, hogy $a \cdot b = b \cdot a$ .

∎

Látható tehát, hogy a 12.1. Definíció szerinti szorzás művelete valóban kommutatív, ahogy azt az általános iskolában már megszokhattuk tőle.

Most nézzünk meg egy rendkívül fontos kapcsolatot a 11.4. Definíció szerinti összeadás és a 12.1. Definíció szerinti szorzás műveletek között. Ez a tulajdonság szintén jól ismert az általános iskolából, most viszont vizsgáljuk meg, hogy tulajdonképpen miért is van ez így.

12.3Az összeadás és a szorzás kapcsolata

Biztosan sokan emlékeznek még általános iskolából az úgynevezett "zárójelfelbontási szabályra". Tegyük fel, hogy van két darab kétváltozós műveletünk egy valamilyen $S$ halmazon. Jelöljük az egyik műveletet $\circ$ -rel, a másikat pedig $∙$ -tal. Szándékosan választottam két semleges szimbólumot annak érdekében, hogy nehogy véletlenül bárki bármilyen konkrét műveletekre asszociáljon. Tegyük fel, hogy a következő kifejezést kell kiértékelnünk az $S$ halmaz $a$ , $b$ és $c$ elemeire:

a ∙ (b \circ c) (a ∙ b) \circ (a ∙ c)

**12.1. ábra:** Disztributív művelet kiértékelése (1. változat)

**12.2. ábra:** Disztributív művelet kiértékelése (2. változat)

Látható, hogy a két kiértékelés teljesen máshogyan történik, így igen meglepő lenne, ha ugyanazt az eredményt adnák. Az alábbi definíció arról a különleges esetről szól, amikor két művelet esetén e kiértékelések tetszőleges $a$ , $b$ és $c$ elemek esetén megegyeznek.

12.5. Definíció (Disztributív művelet):

Legyenek $∙$ és $\circ$ egy valamilyen $S$ halmazon értelmezett kétváltozós műveletek. Amennyiben tetszőleges $S$ -beli $a$ -ra, $b$ -re és $c$ elemekre

a ∙ (b \circ c) = (a ∙ b) \circ (a ∙ c)

teljesül, akkor azt mondjuk, hogy a $∙$ művelet baldisztributív a $\circ$ műveletre nézve.

Amennyiben

(b \circ c) ∙ a = (b ∙ a) \circ (c ∙ a)

teljesül, akkor azt mondjuk, hogy a $∙$ művelet jobbdisztributív a $\circ$ műveletre nézve.

Amennyiben mindkét azonosság egyszerre teljesül, akkor egyszerűen azt mondjuk, hogy a $∙$ művelet disztributív a $\circ$ műveletre nézve.

♣

Megjegyzés:

Ha a

∙

művelet kommutatív, akkor nyilván teljesül a kétoldali disztributivitás. Az állítás megfordítása azonban nem feltétlenül igaz, azaz a kétoldali disztributivitásból nem következik a

∙

művelet kommutativitása.

A disztributivitási kapcsolat két művelet között általában nem kölcsönös. Ez azt jelenti, hogy ha a

∙

művelet disztributív a

\circ

műveletre nézve, abból még nem következik, hogy a

\circ

művelet is disztributív a

∙

műveletre nézve.

Léteznek olyan kétműveletes algebrai struktúrák, amelyekben a műveletek közötti kölcsönös disztributivitás is teljesül. Ilyen például a 19.3. Definícióban szereplő

\cap

szimbólummal jelölt halmazok közötti metszetképzés, és a

\cup

szimbólummal jelölt halmazok közötti unióképzés nevű műveletek. Ezek esetén ugyanis mindkét alábbi azonosság teljesül:

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

♣

Most nézzük meg, hogy disztributivitási szempontból mit tudunk elmondani a 11.4. Definíció szerinti összeadás és a 12.1. Definíció szerinti szorzás műveletekről.

12.6. Tétel:

Az $N$ halmaz tetszőleges $a$ , $b$ és $c$ elemeire igazak az alábbi összefüggések:

a \cdot (b + c) (a + b) \cdot c = (a \cdot b) + (a \cdot c) = (a \cdot c) + (b \cdot c)

Másként fogalmazva a $\cdot$ szimbólummal jelölt szorzás disztributív a $+$ szimbólummal jelölt összeadásra nézve.

♣

Bizonyítás:

Először is megjegyezzük, hogy elegendő csak a baloldali disztributivitást bizonyítani tekintve, hogy a szorzás a 12.4. Tétel miatt kommutatív.

Teljes indukciót alkalmazunk $c$ -re vonatkozóan. Tegyük fel, hogy az állítás igaz valamilyen $c = n$ természetes számra. Az tehát az indukciós feltétel, hogy

a \cdot (b + n) = (a \cdot b) + (a \cdot n)

Azt kell bizonyítanunk, hogy ebben az esetben az állítás $c = s (n)$ -re is igaz lesz, azaz:

a \cdot (b + = c s (n)) = (a \cdot b) + (a \cdot = c s (n))

A 11.4. Definíció 2. pontja miatt:

a \cdot (b + s (n)) = a \cdot s (b + n) = \dots

A 12.1. Definíció 2. pontja miatt:

\dots = (a \cdot (b + n)) + a = \dots

Az indukciós feltétel miatt:

\dots = ((a \cdot b) + (a \cdot n)) + a = \dots

Tekintve, hogy a 11.10. Tétel miatt az összeadás asszociatív, ezért:

\dots = (a \cdot b) + ((a \cdot n) + a) = \dots

Végül ismét a 12.1. Definíció 2. pontja miatt:

\dots = (a \cdot b) + (a \cdot s (n))

Vagyis azt kaptuk, hogy valóban $a \cdot (b + = c s (n)) = (a \cdot b) + (a \cdot = c s (n))$ .

Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Most felborítjuk az első dominót, tehát igazoljuk, hogy az állítás igaz $c = 0$ esetén, azaz:

a \cdot (b + = c 0) = (a \cdot b) + (a \cdot = c 0)

A 11.4. Definíció 1. pontja miatt:

a \cdot (b + 0) = a \cdot b = \dots

Ismételten a 11.4. Definíció 1. pontja miatt:

\dots = (a \cdot b) + 0 = \dots

Végül a 12.1. Definíció 1. pontja miatt:

\dots = (a \cdot b) + (a \cdot 0)

Borul tehát az első dominó, és vele együtt a teljes dominósor, azaz minden $a$ , $b$ és $c$ számra igaz, hogy $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ .

∎

Mostantól tehát nyugodtan alkalmazhatjuk az általános iskolából már jól ismert zárójelfelbontási szabályt, mivel a 11.1. Definíció szerinti Peano-axiómarendszer segítségével bevezetett mindkét műveletünk teljesíti ezt a követelményt is.

12.4A szorzás asszociativitása

Most vizsgáljuk meg, hogy az összeadáshoz hasonlóan vajon a szorzás is asszociatív-e.

12.7. Tétel:

A természetes számok szorzása asszociatív. Másként fogalmazva az $N$ halmaz tetszőleges $a$ , $b$ és $c$ elemeire igaz az alábbi összefüggés:

(a \cdot b) \cdot c = a \cdot (b \cdot c)

♣

Bizonyítás:

Teljes indukciót alkalmazunk $c$ -re vonatkozóan. Indukciós feltételként feltételezzük, hogy valamilyen $c = n$ -re a tétel már teljesül, azaz:

(a \cdot b) \cdot n = a \cdot (b \cdot n)

Feladatunk megmutatni, hogy ekkor $c = s (n)$ -re is teljesül, azaz:

(a \cdot b) \cdot s (n) = a \cdot (b \cdot s (n))

A 12.1. Definíció 2. pontja miatt:

(a \cdot b) \cdot s (n) = ((a \cdot b) \cdot n) + (a \cdot b) = \dots

Az indukciós feltétel miatt:

\dots = (a \cdot (b \cdot n)) + (a \cdot b) = \dots

Tekintve, hogy a 12.6. Tétel miatt a szorzás disztributív az összeadásra nézve, ezért:

\dots = a \cdot ((b \cdot n) + b) = \dots

Végül ismételten a 12.1. Definíció 2. pontja miatt:

\dots = a \cdot (b \cdot s (n))

A dominósor tehát felállítva, most elborítjuk az első dominót, azaz belátjuk, hogy $c = 0$ -ra a tétel igaz. Ez viszont nyilvánvalóan teljesül a 12.1. Definíció 1. pontjának háromszori alkalmazásával:

(a \cdot b) \cdot = c 0 = 0 = a \cdot 0 = a \cdot (b \cdot = c 0)

∎

Ezzel megmutattuk, hogy a 11.1. Definíció szerinti Peano-axiómarendszer segítségével bevezetett mindkét műveletünk az elvárt módon viselkedik. A fejezet további részében az $N$ halmazban fogunk egy kicsit rendetrakni. Ez szükséges lesz ugyanis ahhoz az absztrakcióhoz, amelyet a cikksorozat következő fejezetében fogunk majd meglépni, és amelynek a segítségével nemcsak összeadni és szorozni, hanem kivonni is fogunk tudni.

12.5Kő-papír-olló

A 11.1. Definíció szerinti Peano-axiómarendszerrel definiált $N$ halmaz jelenleg nem több csupán egy "zsáknál", amelyben ott csücsül a végtelen sok természetes szám. E számkör kibővítéséhez azonban szükségünk lesz egy olyan fogalomra, amelynek a segítségével ezeket az objektumokat valamilyen módon sorba tudjuk állítani. Szeretnénk olyan kijelentéseket tenni, miszerint egy $a$ természetes szám "előrébb van" ebben a képzeletbeli sorban, mint egy $b$ természetes szám.

Az ábrán látható doboz választ ad egy valamilyen eldöntendő kérdésre a két felül bedobott természetes szám közötti kapcsolatról. Az ilyen dobozokat kétváltozós relációknak nevezzük. A példában szereplő relációt önkényesen $R$ -rel jelöltünk, de választhattunk volna bármilyen más szimbólumot is. Most nézzük meg, hogyan tudjuk precízen megfogalmazni, hogy pontosan mit is nevezünk kétváltozós relációnak.

Ennek megértéséhez fontos először tisztázni az úgynevezett rendezett pár – vagy általánosan az úgynevezett rendezett $n$ -es – fogalmát. Emlékezzünk vissza, hogy egy kétváltozós műveletet egy olyan függvényként definiáltunk, amely az adott művelet alaphalmazából származó elemekből alkotott összes létező ún. rendezett párhoz hozzárendel egy-egy elemet szintén ebből az alaphalmazból. Vegyük például a már jól ismert $N$ halmazt, és válasszunk ki belőle két tetszőleges elemet, mondjuk $1$ -et és $2$ -t. Ebből a két elemből kétféleképpen tudunk egy rendezett párt alkotni, mivel nem mindegy, hogy melyik hol foglal helyet ebben a párban – ezért hívjuk rendezett párnak. Az egyik ilyen párt $(1; 2)$ -vel, a másikat pedig $(2; 1)$ -gyel jelöljük. Az $(1; 2)$ és a $(2; 1)$ rendezett párok tehát különbözőek, mivel nem azonos a bennük szereplő elemek sorrendje. Általánosabban rendezett $n$ -eseknek nevezzük azokat az ehhez hasonló sorozatokat, amelyekben nem $2$ , hanem $n$ darab elem szerepel. Most fogalmazzuk meg ugyanezt a halmazok nyelvén.

12.8. Definíció (Halmazok direkt szorzata):

Legyenek $A$ és $B$ tetszőleges halmazok. Ekkor az $A$ és $B$ halmazok direkt szorzatának (vagy Descartes-szorzatának) nevezzük azt a halmazt, amely az összes olyan $(a; b)$ alakban felírható elemet tartalmazza, amelyek esetén $a$ valamilyen $A$ -beli, $b$ pedig valamilyen $B$ -beli elem. Ezt a halmazt $A \times B$ -vel jelöljük (ejtsd: " $A$ kereszt $B$ "). Speciálisan ha a két halmaz azonos, akkor $A \times A$ helyett az $A^{2}$ jelölést is használhatjuk.

Az $A \times B$ direkt szorzat $(a; b)$ elemeit rendezett pároknak, $a$ -t a rendezett pár első, $b$ -t pedig a rendezett pár második komponensének nevezzük.

Általánosabban legyenek $A_{1}$ , $A_{2}$ , ..., $A_{n}$ tetszőleges halmazok. Ekkor ezen halmazok direkt szorzatának (vagy Descartes-szorzatának) nevezzük azt a halmazt, amely az összes olyan $(a_{1}; a_{2}; \dots; a_{n})$ alakban felírható elemet tartalmazza, amelyek esetén minden $i$ index esetén $a_{i}$ valamilyen $A_{i}$ -beli elem. Ezt a halmazt így jelöljük:

A_{1} \times A_{2} \times \dots \times A_{n}

Speciálisan ha a direkt szorzatban szereplő halmazok azonosak, akkor az $A^{n}$ jelölést is használhatjuk.

Az $A_{1} \times A_{2} \times \dots \times A_{n}$ direkt szorzat $(a_{1}; a_{2}; \dots; a_{n})$ elemeit rendezett $n$ -eseknek, adott $i$ index esetén pedig $a_{i}$ -t a rendezett $n$ -es $i$ -edik komponensének nevezzük.

♣

Ennek a definíciónak a birtokában mostmár precízen megfogalmazhatjuk, hogy mit is értünk kétváltozós reláció alatt.

12.9. Definíció (Kétváltozós reláció):

Ha $S$ egy tetszőleges halmaz, akkor az $S \times S$ direkt szorzat egy valamilyen $R$ részhalmazát az $S$ halmazon értelmezett kétváltozós relációnak nevezzük. Ha $a$ és $b$ a $S$ halmaz két tetszőleges – nem feltétlenül különböző – eleme, és az $(a; b)$ rendezett pár benne van az $R$ halmazban, akkor azt mondjuk, hogy $a$ és $b$ között fennáll az $R$ -reláció. Ezt így jelöljük: $a R b$ .

♣

Annak érdekében, hogy az Olvasó ne vesszen el az imént bevezetett absztrakciókban, most egy egyszerű példát fogunk mutatni: lemodellezzük a mindenki által jól ismert kő-papír-olló játékot. A játék abból áll, hogy két játékos egyszerre mutat egy kézmozdulatot, amely vagy a kő, vagy a papír, vagy az olló szavakat jelképezi. A játék szabályai szerint a kő "üti" az ollót (kicsorbítja azt), az olló "üti" a papírt (elvágja azt), a papír pedig "üti" a követ (betakarja azt). Ha mindkét játékos ugyanazt a kézmozdulatot mutatja, akkor döntetlen lesz a játék végeredménye, minden más esetben az a játékos nyer, akinek a kézmozdulata a fenti értelemben "üti" a másik játékos kézmozdulatát. Ez a játék kiválóan modellezhető egy kétváltozós reláció segítségével.

Ez a reláció egy olyan halmazon van értelmezve, amely a $k \overset{o}{˝}$ , a $pap \overset{ı}{ˊ} r$ és az $oll \overset{o}{ˊ}$ szavakat tartalmazza. Jelöljük ezt a halmazt $S$ -sel. Ekkor a $S \times S$ halmaz az alábbi kilenc rendezett párt fogja tartalmazni: $(k \overset{o}{˝}; k \overset{o}{˝})$ , $(k \overset{o}{˝}; pap \overset{ı}{ˊ} r)$ , $(k \overset{o}{˝}; oll \overset{o}{ˊ})$ , $(pap \overset{ı}{ˊ} r; k \overset{o}{˝})$ , $(pap \overset{ı}{ˊ} r; pap \overset{ı}{ˊ} r)$ , $(pap \overset{ı}{ˊ} r; oll \overset{o}{ˊ})$ , $(oll \overset{o}{ˊ}; k \overset{o}{˝})$ , $(oll \overset{o}{ˊ}; pap \overset{ı}{ˊ} r)$ , és $(oll \overset{o}{ˊ}; oll \overset{o}{ˊ})$ .

Most szigorúan a 12.9. Definíció alapján adjunk meg egy relációt az $S$ halmazon. Ez ugye az $S \times S$ direkt szorzat valamely részhalmaza lesz, amelyet most jelöljünk például a $≻$ szimbólummal. Válasszuk azt a részhalmazt, amely csak a $(k \overset{o}{˝}; oll \overset{o}{ˊ})$ , $(oll \overset{o}{ˊ}; pap \overset{ı}{ˊ} r)$ és $(pap \overset{ı}{ˊ} r; k \overset{o}{˝})$ rendezett párokat tartalmazza az összes lehetséges rendezett pár közül. A 12.9. Definícióban szereplő jelöléssel ez épp az alábbi relációk fennállását jelenti az $S$ halmaz elemei között:

k \overset{o}{˝} oll \overset{o}{ˊ} pap \overset{ı}{ˊ} r ≻ oll \overset{o}{ˊ} ≻ pap \overset{ı}{ˊ} r ≻ k \overset{o}{˝}

Vegyük észre, hogy amennyiben a $≻$ szimbólumot az "üti" jelentéssel ruházzuk fel, úgy az imént épp a matematikai leírását adtuk meg a kő-papír-olló játék ütési szabályainak.

12.6Rendezési relációk

Amikor egy végtelen halmazon értelmezünk valamilyen relációt, akkor természetesen nem tudjuk megtenni, hogy a 12.5. szakaszban bemutatott módon felsoroljuk az összes olyan párt, amelyek relációban állnak egymással. Ilyen esetekben praktikusabb inkább valamilyen szabályt megadni arra vonatkozóan, hogy mikor tekintünk két elemet egymással relációban állónak, és mikor nem.

Ebben a szakaszban bevezetünk egy olyan relációt az $N$ halmazon, amelynek a segítségével sorba fogjuk tudni rendezni $N$ elemeit – azaz a természetes számokat. Előbb azonban vizsgáljuk meg, hogy pontosan mit értünk rendezési reláció alatt. Ehhez az adott relációnak meg kell felelnie néhány speciális kritériumnak, amelyeket a most következő definíciókban egyenként ismertetünk. Az első ilyen kritérium például azt követeli meg, hogy bármely elem relációban álljon önmagával.

12.10. Definíció (Reflexív reláció):

Legyen adott egy $S$ halmaz és egy ezen a halmazon értelmezett $R$ reláció. Ha $S$ minden $a$ elemére teljesül, hogy $a R a$ , akkor azt mondjuk, hogy az $R$ reláció reflexív.

♣

Például a 12.5. szakaszban a kő-papír-olló játékkal kapcsolatban definiált $≻$ reláció nyilvánvalóan nem reflexív, hiszen ha a két játékos ugyanazt mutatja – legyen az akár $k \overset{o}{˝}$ , akár $pap \overset{ı}{ˊ} r$ , akár $oll \overset{o}{ˊ}$ –, az eredmény döntetlen lesz, tehát egyik sem "üti" a másikat.

A második definíció azt követeli meg egy relációtól, hogy két különböző elem esetén a közöttük lévő reláció iránya egyértelmű legyen – amennyiben persze egyáltalán relációban állnak egymással.

12.11. Definíció (Antiszimmetrikus reláció):

Legyen adott egy $S$ halmaz és egy ezen a halmazon értelmezett $R$ reláció, valamint tegyük fel, hogy $a$ és $b$ az $S$ halmaz tetszőleges, de egymástól különböző elemei – azaz $a \neq = b$ . Ha minden ilyen esetben $a R b$ és $b R a$ közül legfeljebb az egyik teljesül, akkor azt mondjuk, hogy az $R$ reláció antiszimmetrikus.

♣

Megjegyzés:

Ezzel ekvivalens megfogalmazás: ha egy antiszimmetrikus reláció mindkét irányban fennáll két elem között, akkor a két elem azonos, azaz $a = b$ .

Megjegyezzük azonban, hogy visszafelé nem feltétlenül igaz, hogy $a = b$ esetén bármelyik irányban is fennáll a reláció. Ezt a 12.10. Definícióban szereplő reflexivitási tulajdonság hivatott biztosítani.

♣

A már említett $≻$ reláció antiszimmetrikus, hiszen ha a két játékos különbözőt mutat, akkor biztosan nem fognak mindketten nyerni.

A harmadik definíció azt követeli meg egy relációtól, hogy az elempárok azon tulajdonsága, miszerint egymással relációban állnak, "láncszerűen" öröklődjön. Például: ha én "magasabb vagyok" az apámnál, apám pedig "magasabb" az anyámnál, akkor én "magasabb vagyok" az anyámnál.

12.12. Definíció (Tranzitív reláció):

Legyen adott egy $S$ halmaz és egy ezen a halmazon értelmezett $R$ reláció, valamint tegyük fel, hogy $a$ , $b$ és $c$ az $S$ halmaz tetszőleges elemei. Ha minden ilyen esetben $a R b$ és $b R c$ együttes teljesülése esetén $a R c$ is teljesül, akkor azt mondjuk, hogy az $R$ reláció tranzitív.

♣

A $≻$ reláció nem tranzitív, hiszen például $pap \overset{ı}{ˊ} r ≻ k \overset{o}{˝}$ és $k \overset{o}{˝} ≻ oll \overset{o}{ˊ}$ teljesül, de $pap \overset{ı}{ˊ} r ≻ oll \overset{o}{ˊ}$ nem.

Végül a negyedik definíció azt követeli meg egy relációtól, hogy két tetszőleges elemet kiválasztva azok mindenképpen legyenek egymással "összehasonlíthatók" az adott reláció segítségével.

12.13. Definíció (Trichotóm reláció):

Legyen adott egy $S$ halmaz és egy ezen a halmazon értelmezett $R$ reláció, valamint tegyük fel, hogy $a$ és $b$ az $S$ halmaz tetszőleges elemei. Ha minden ilyen esetben $a R b$ és $b R a$ közül legalább az egyik teljesül, akkor azt mondjuk, hogy az $R$ reláció trichotóm.

♣

A trichotómia sem teljesül a $≻$ reláció ugyanazon okok miatt, mint a reflexivitás.

Most bevezetünk egy olyan fogalmat, amely a $≻$ relációval ellentétben ezeket a tulajdonságokat egyesíti, majd megmutatjuk az elnevezés jogosságát.

12.14. Definíció (Rendezett halmaz):

Tegyük fel, hogy adott egy $S$ halmaz, és egy rajta értelmezett $R$ reláció. Amennyiben $R$ egyszerre reflexív, antiszimmetrikus és tranzitív, úgy az $R$ relációt $S$ feletti részbenrendezésnek hívjuk, és azt mondjuk, hogy a $S$ egy részbenrendezett halmaz az $R$ relációval.

Az $R$ relációt teljes rendezésnek (vagy egyszerűen csak rendezésnek) nevezzük $S$ felett, ha a fentieken kívül a trichotómia is teljesül rá. Ilyenkor azt mondjuk, hogy a $S$ egy teljesen rendezett (vagy egyszerűen csak rendezett) halmaz az $R$ relációval.

♣

Minket jelenleg csak a teljes rendezések, és ennek megfelelően a rendezett halmazok érdekelnek, részbenrendezett halmazokkal a 19.3. szakaszban fogunk bővebben foglalkozni. Vizsgáljuk meg tehát, hogy miért nevezhetünk jogosan "rendezésnek" egy olyan relációt, amely teljesíti a 12.14. Definícióban szereplő mind a négy kritériumot.

Tegyük fel, hogy van egy valamilyen $S$ halmazon értelmezett rendezési reláció, amelyet a $\leq$ szimbólummal jelölünk. Ne társítsunk most semmilyen számokkal kapcsolatos jelentést ehhez a szimbólumhoz, az $a \leq b$ kifejezést egyszerűen csak interpretáljuk úgy, hogy " $a$ legfeljebb annyiadik elem a sorban, mint $b$ ".

Ezek után a 12.14. Definícióban szereplő négy kritériumot így is olvashatjuk:

Reflexivitás: Tetszőleges elem "legfeljebb annyiadik a sorban", mint önmaga.
Antiszimmetria: Ha az $a$ elem "legfeljebb annyiadik a sorban", mint a $b$ elem, és a $b$ elem is "legfeljebb annyiadik a sorban", mint az $a$ elem, akkor a két elem megegyezik.
Tranzitivitás: Ha az $a$ elem "legfeljebb annyiadik a sorban", mint a $b$ elem, amely pedig "legfeljebb annyiadik a sorban", mint a $c$ elem, akkor az $a$ elem "legfeljebb annyiadik a sorban", mint a $c$ elem.
Trichotómia: Bármely két elemről el lehet dönteni, hogy melyikük van "legfeljebb annyiadik helyen a sorban", mint a másik.

Ha végiggondoljuk, akkor pontosan ez az, amit elvárunk egy olyan relációtól, amelynek a segítségével egy egyértelmű sorrendet szeretnénk felállítani egy halmaz elemei között.

12.7A természetes számok rendezési relációja

Most nézzük meg, hogyan tudunk egy olyan relációt megadni a természetes számok $N$ halmazán, amely megfelel a 12.14. Definícióban szereplő követelményeknek.

12.15. Definíció (A természetes számok rendezése):

Amennyiben az $N$ halmaz tetszőleges $a$ és $b$ elemeihez létezik olyan $k$ szintén $N$ -beli elem, amelyre teljesül, hogy $a + k = b$ , akkor azt mondjuk, hogy $a \leq b$ . Kiolvasva: " $a$ legfeljebb $b$ " vagy " $b$ legalább $a$ ". A $\leq$ relációt a természetes számok rendezésének nevezzük.

Ha ezen kívül $k \neq = 0$ is teljesül, akkor azt mondjuk, hogy $a < b$ . Kiolvasva: " $a$ kisebb $b$ " vagy " $b$ nagyobb $a$ ".

Fordított irányú relációk esetén értelemszerűen használhatjuk a $\geq$ vagy a $>$ szimbólumokat is.

♣

Látható, hogy ennek az új fogalomnak a bevezetéséhez közvetett módon kizárólag a 11.1. Definícióban ismertetett Peano-axiómarendszert, közvetlenül pedig az ez alapján értelmezett összeadás nevű műveletet használtuk. Ezt szem előtt tartva tehát egyelőre semmit nem mondhatunk még erről a most bevezetett relációról, kiváltképpen azt nem, hogy ez valóban egy rendezési reláció lenne. Ezt ugyanis először bizonyítani kell.

Ehhez a 12.14. Definíció alapján be kell látnunk, hogy a $\leq$ reláció reflexív, antiszimmetrikus és tranzitív, továbbá a trichotómia is teljesül. Nézzük is az elsőt.

12.16. Tétel:

A 12.15. Definíció szerinti $\leq$ reláció reflexív, azaz az $N$ halmaz tetszőleges $a$ elemére teljesül, hogy $a \leq a$ .

♣

Bizonyítás:

Tekintve, hogy a 11.4. Definíció 1. pontja szerint tetszőleges $a$ -ra teljesül, hogy $a + 0 = a$ , ezért nyilvánvalóan létezik olyan természetes szám – nevezetesen a nulla természetes szám –, amelyet hozzáadva bármihez azt a bármit kapjuk eredményül. Így tehát $a \leq a$ tetszőleges $a$ esetén teljesül.

∎

A tranzitivitás hasonlóan egyszerűen adódik.

12.17. Tétel:

A 12.15. Definíció szerinti $\leq$ reláció tranzitív, azaz az $N$ halmaz tetszőleges $a$ , $b$ és $c$ elemére teljesül, hogy $a \leq b$ és $b \leq c$ együttes fennállása esetén $a \leq c$ is fennáll.

♣

Bizonyítás:

Ha $a \leq b$ , akkor a 12.15. Definíció miatt létezik olyan természetes szám, amelyet $a$ -hoz adva $b$ -t kapunk. Jelöljük ezt a természetes számot $k_{1}$ -gyel, így tehát azt kapjuk, hogy $a + k_{1} = b$ .

Ugyanezen okok miatt ha $b \leq c$ , akkor létezik olyan természetes szám is, amelyet $b$ -hez adva $c$ -t kapunk. Jelöljük ezt a természetes számot $k_{2}$ -vel, így tehát azt kapjuk, hogy $b + k_{2} = c$ .

Az első egyenlet baloldalát a második egyenletbe $b$ helyére behelyettesítve azt kapjuk, hogy $= b (a + k_{1}) + k_{2} = c$ . Tekintve, hogy a 11.10. Tétel miatt az összeadás asszociatív, ezért ez a kifejezés átzárójelezhető: $a + (k_{1} + k_{2}) = c$ .

Létezik tehát olyan természetes szám is, amelyet $a$ -hoz adva $c$ -t kapunk – nevezetesen $k_{1} + k_{2}$ . A 12.15. Definíció miatt ez épp azt jelenti, hogy $a \leq c$ .

∎

Az antiszimmetria igazolásához először két segédtételre lesz szükségünk. Ezek közül az első egy olyan állítás, amely a későbbiekben is hasznos lesz.

12.18. Lemma:

Tetszőleges $a$ , $b$ és $c$ természetes számok esetén ha $a + c = b + c$ , akkor $a = b$ .

♣

Ne feledjük, hogy csak a már rendelkezésünkre álló fogalmakra és tételekre, valamint az axiómákra hivatkozhatunk. Tekintve, hogy "kivonás" egyelőre nem létezik, más úton kell bizonyítanunk a fenti állítást.

Bizonyítás:

A már jól ismert teljes indukciót alkalmazzuk. Először is megmutatjuk, hogy ha az állítás teljesül valamilyen $c = n$ -re, akkor teljesülni fog $c = s (n)$ -re is. Meg kell tehát mutatnunk, hogy ha $a + n = b + n$ -ből $a = b$ következik, akkor $a + s (n) = b + s (n)$ -ből is $a = b$ következik.

Az $a + s (n) = b + s (n)$ egyenlet mindkét oldalát a 11.4. Definíció 2. pontja miatt átírhatjuk így: $s (a + n) = s (b + n)$ . Mármost a 11.1. Definíció 2. pontja kimondja, hogy ha két természetes szám rákövetkezője megegyezik, akkor maga a két természetes szám is megegyezik. Ebből tehát az következik, hogy $a + n = b + n$ . Az indukciós feltétel szerint viszont az állítás teljesül $n$ -re, ezért ebből $a = b$ következik.

A dominósort felállítottuk, nincs más hátra, mint felborítani az első dominót, azaz megmutatni, hogy $a + 0 = b + 0$ -ból $a = b$ következik. Ez viszont nyilvánvalóan teljesül, hiszen az egyenlet mindkét oldalát egyszerűsíthetjük $0$ -val a 11.4. Definíció 1. pontja miatt.

∎

Az antiszimmetria igazolásához szükséges második segédtétel azt mondja ki, hogy mi az az egyetlen eset, amikor egy összeg eredménye $0$ lehet a természetes számok között.

12.19. Lemma:

A természetes számok körében ha $a + b = 0$ , akkor $a = 0$ és $b = 0$ .

♣

Bizonyítás:

Tegyük fel, hogy nem igaz az állítás, azaz $a + b = 0$ , de $a$ és $b$ közül legalább az egyik nem $0$ . Tekintve, hogy a 11.8. Tétel alapján az összeadás kommutatív, ezért mindegy, hogy melyiket választjuk, a másikkal ugyanez a gondolatmenet végigjátszható. Legyen például most $b \neq = 0$ . Vizsgáljuk meg, hogy egy ilyen galád feltételezésnek milyen képtelen logikai következményei lennének.

Ha $b \neq = 0$ , akkor a 11.1. Definíció 3. pontja miatt létezik olyan természetes szám, amelynek épp $b$ a rákövetkezője, hiszen egyedül a $0$ nem rákövetkezője semminek. Jelöljük ezt a természetes számot $n$ -nel, amelyre tehát igaz, hogy $s (n) = b$ .

Az $a + b = 0$ kifejezést tehát így is írhatjuk:

a + = b s (n) = 0

Ez a 11.4. Definíció 2. pontja miatt így írható fel:

s (a + n) = 0

Vagyis azt kaptuk, hogy az $a + n$ rákövetkezője 0. Ez azonban lehetetlen, hiszen a 11.1. Definíció 3. pontja szerint a $0$ nem rákövetkezője semminek.

Ha tehát a lemma állításának hamisságát továbbra is tartani szeretnénk, akkor hamisnak kellene tekintenünk 3. Peano-axiómát is. Megfordítva: ha 3. Peano-axiómát igaznak fogadjuk el – márpedig annak fogadjuk el –, akkor a lemma állítása is szükségképpen igaz kell legyen.

∎

Megjegyzés:

A bizonyítás során egy indirekt bizonyításnak (reductio ad absurdum) nevezett módszert alkalmaztunk. Ez az érvelés egy olyan formája, melynek során az érvelő a vita kedvéért elfogad egy állítást, megmutatja, hogy valamilyen képtelenség következik belőle, és ebből arra jut, hogy az állítás mégse volt igaz. Ilyenkor tehát nem magát az állítást igazoljuk, hanem megmutatjuk, hogy miért nem lehet hamis.

♣

A 12.18. és a 12.19. Lemma felhasználásával mostmár igazolhatjuk, hogy a $\leq$ reláció antiszimmetrikus.

12.20. Tétel:

A 12.15. Definíció szerinti $\leq$ reláció antiszimmetrikus, azaz az $N$ halmaz tetszőleges $a$ és $b$ elemére teljesül, hogy $a \leq b$ és $b \leq a$ együttes fennállása esetén szükségképpen $a = b$ .

♣

Bizonyítás:

Ugyanezen okok miatt ha $b \leq a$ , akkor létezik olyan természetes szám is, amelyet $b$ -hez adva $a$ -t kapunk. Jelöljük ezt a természetes számot $k_{2}$ -vel, így tehát azt kapjuk, hogy $b + k_{2} = a$ .

Az első egyenlet baloldalát a második egyenletbe $b$ helyére behelyettesítve azt kapjuk, hogy $= b (a + k_{1}) + k_{2} = a$ . Tekintve, hogy a 11.10. Tétel miatt az összeadás asszociatív, ezért ez a kifejezés átzárójelezhető: $a + (k_{1} + k_{2}) = c$ .

A 11.4. Definíció 1. pontja miatt az egyenlet jobboldalához hozzáadhatunk $0$ -t: $a + (k_{1} + k_{2}) = a + 0$ . Az egyenlet mindkét oldala egyszerűsíthető $a$ -val a 12.18. Lemma miatt, azaz $k_{1} + k_{2} = 0$ . Ebből viszont a 12.19. Lemma miatt az következik, hogy $k_{1} = 0$ és $k_{2} = 0$ .

Helyettesítsük vissza mondjuk $k_{1}$ -et az egyik kiindulási egyenletünkbe: $a + = k_{1} 0 = b$ . Ennek az egyenletnek a baloldala a 11.4. Definíció 1. pontja miatt $0$ -val egyszerűsíthető, azaz $a = b$ .

∎

Már csak a trichotómia igazolása van hátra. Ez az alábbi segédállításból fog következni.

12.21. Lemma:

Tetszőleges $a$ és $b$ természetes számok esetén az $a \leq b$ reláció akkor és csak akkor teljesül, ha az $s (a) \leq s (b)$ reláció is teljesül.

♣

Bizonyítás:

Mivel ez egy "akkor és csak akkor" típusú állítás, ezért mindkét irányú következtetést igazolni kell.

Ha $a \leq b$ , akkor ez a 12.15. Definíció miatt azt jelenti, hogy létezik $n$ , amelyre $a + n = b$ . Ám ekkor nyilvánvalóan az egyenlet két oldalának rákövetkezője is azonos, azaz $s (a + n) = s (b)$ . Ekkor viszont a 11.4. Definíció 2. pontja miatt $s (a) + n = s (b)$ is igaz. Ez viszont szintén a 12.15. Definíció miatt épp azt jelenti, hogy $s (a) \leq s (b)$ .

Megfordítva: Ha $s (a) \leq s (b)$ , akkor a 12.15. Definíció miatt létezik $n$ , amelyre $s (a) + n = s (b)$ . Ám ekkor a 11.4. Definíció 2. pontja miatt $s (a + n) = s (b)$ is igaz, amiből a 11.1. Definíció 2. pontja miatt $a + n = b$ következik. Ez pedig a 12.15. Definíció miatt épp azt jelenti, hogy $a \leq b$ .

∎

Ebből már következik a $\leq$ reláció trichotómiája, ezért most ezt mondjuk ki.

12.22. Tétel:

A 12.15. Definíció szerinti $\leq$ reláció trichotóm, azaz az $N$ halmaz tetszőleges $a$ és $b$ elemére teljesül, hogy az $a \leq b$ és $b \leq a$ relációk közül legalább az egyik fennáll.

♣

Bizonyítás:

Indirekt bizonyítást fogunk alkalmazni, azaz nem közvetlenül a tételt bizonyítjuk, hanem megmutatjuk, miért nem lehet hamis. Tegyük fel ezért, hogy nem igaz a tétel, vagyis hogy az $N$ halmazban léteznek olyan galád $a$ és $b$ természetes számok, amelyek között egyik irányban sem áll fenn a $\leq$ reláció, azaz $a ≰ b$ és $b ≰ a$ .

Ebből az következik, hogy egyikük sem lehet $0$ , hiszen ha például $a = 0$ lenne, akkor a 12.15. Definíció miatt $= a 0 \leq b$ teljesülne, ugyanis létezne olyan természetes szám, amelyet $a = 0$ -hoz adva $b$ -t kapnánk, nevezetesen $b$ , hiszen $0 + b = b$ . Ha meg $b = 0$ lenne, akkor pedig ugyanezen okok miatt $= b 0 \leq a$ teljesülne, ugyanis $0 + a = a$ .

Ha viszont egyikük sem $0$ , akkor a 11.1. Definíció 3. pontja miatt mindkettőhöz létezik egy-egy olyan természetes szám, amelyeknek épp ők a rákövetkezői. Jelöljük ezt a két természetes számot $a_{1}$ -gyel és $b_{1}$ -gyel, amelyekre tehát teljesül, hogy $s (a_{1}) = a$ és $s (b_{1}) = b$ .

Mármost ha $a$ és $b$ között nem teljesül a $\leq$ reláció egyik irányban sem, akkor a 12.21. Lemma miatt utóbbiak között sem fog – azaz $a_{1} ≰ b_{1}$ és $b_{1} ≰ a_{1}$ .

De ekkor ugyanezen gondolatmenet alapján léteznie kell egy $a_{2}$ és egy $b_{2}$ természetes számnak is, amelyek rákövetkezői épp az $a_{1}$ és $b_{1}$ természetes számok, és amelyek közül szintén egyik sem $0$ . És így tovább, ezt a gondolatmenetet a végtelenségig folytathatjuk, mindig találunk újabb és újabb nem $0$ természetes számokat, amelyek rákövetkezői épp az előző lépésben megtalált természetes számok.

**12.4. ábra:** Végtelen leszálló sorozatok

Ez viszont lehetetlen, hiszen a 11.1. Definíció 4. pontja kimondja, hogy a $0$ -ból kiindulva a rákövetkezési függvény mentén az összes természetes számhoz el kell jutnunk előbb-utóbb. Márpedig egy ilyen útvonalon az ábrán lévő két sorozat tagjai biztosan nem lennének benne.

Ebből viszont az következik, hogy az $a \leq b$ és a $b \leq a$ relációk közül legalább az egyiknek teljesülnie kell tetszőleges $a$ és $b$ esetén, máskülönben ellentmondásba kerülnénk a 4. Peano-axiómával.

∎

A $\leq$ reláció tehát teljesíti mindazon követelményeket, amelyeket a 12.14. Definíció megkövetel tőle. Ezért mostmár nyugodtan kijelenthetjük, hogy a 12.15. Definícióban jogosan neveztük ezt a relációt rendezésnek, és jogosan nevezhetjük az $N$ halmazt rendezett halmaznak.

12.8Hol tartunk most?

Ezen a ponton álljunk meg egy pillanatra, és szedjük össze, hogy jelenleg hol tartunk a számelmélet felépítésében, amit ugye a semmiből kezdtünk el az előző fejezetben.

A 11.1. Definícióban megfogalmaztuk a Peano-axiómarendszer négy állítását, amelyek bevezetik a természetes számok $N$ -nel jelölt halmazát. Ezen a halmazon a 11.4. Definícióban értelmeztünk egy "összeadás", a 12.1. Definícióban pedig egy "szorzás" nevű műveletet. Végül a 11.8., a 11.10., a 12.4., a 12.7. és a 12.6. Tételekben bizonyítottuk, hogy e két művelet engedelmeskedik az általános iskolából már jól ismert számolási szabályoknak.

A négy alapművelet közül tehát a két legfontosabb, az összeadás és a szorzás már többé-kevésbé rendelkezésünkre áll. A "kivonás" azonban sajnos a 11.3. Definíció alapján a természetes számok $N$ halmazán nem művelet, mivel bizonyos esetekben kivezet belőle. Például nincs olyan természetes szám, amely a $2 - 5$ különbségképzés eredménye lenne, a $- 3$ ugyanis nem természetes szám, holott a $2$ és az $5$ is az.

Kinőttük tehát az $N$ halmazt, ezért a következő fejezetekben át fogunk térni egy $N$ -nél bővebb számkörbe, amelyben már gond nélkül fogunk tudni kivonást is végezni. Sajnos azonban osztásról általánosságban még itt sem fogunk tudni beszélni, legalábbis nem a megszokott értelemben. Cserébe viszont elkezdhetünk majd végre ismerkedni azokkal a különleges számokkal – az úgynevezett prímszámokkal –, amelyek alapvető szerepet játszanak a kriptográfiai eljárásokban, és úgy általában az egész számelméletben.

A számkör bővítésének előkészítése érdekében a 12.15. Definícióban bevezettünk egy relációt az $N$ halmazon, amelyről az indirekt bizonyítás módszerét bemutatva igazoltuk, hogy az egy teljes rendezést valósít meg a természetes számok között.

A következő fejezetben kilépünk a természetes számok köréből egy sokkal előnyösebb algebrai tulajdonságokkal bíró számkörbe. Ennek keretében bemutatjuk azt az absztrakciós utat, amelyet az emberiség hajnalán őseinknek is meg kellett tenniük, és ezzel párhuzamosan megismerkedünk néhány további absztrakt algebrai fogalommal. Ezek segítségével általánosabb módon tudjuk majd tárgyalni azokat a számelméleti összefüggéseket, amelyek végül a prímszámok elméletén keresztül elvezetnek minket napjaink biztonságos kommunikációjának alapjaihoz.