youproof.orgDeep Math. Human Access.
Régi könyvek könyvtári polcokon

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 00 alapvető tulajdonságait. Ezek halmazát természetes számoknak neveztük, és N\N-nel jelöltük. Szigorúan az axiómákat használva bevezettünk az N\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\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+aa+a+a+a+a. Itt az aa 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⋅5a \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 00-val szorzunk meg. Ezt ugye a fenti értelmezés alapján egy 00 tagú összegként foghatjuk fel. Természetes tehát, ha rögzítjük, hogy tetszőleges aa esetén a⋅0a \cdot 0 eredménye 00 legyen. A másik megállapodásunk pedig legyen az, hogy ha egy aa természetes számot egy bb természetes szám rákövetkezőjével szorozzuk meg, akkor az ennek megfelelő összegben éppen eggyel többször szerepeljen aa, mintha csak bb-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\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:

1.
Tetszőleges aa természetes szám esetén a⋅0=0a\cdot 0=0.
2.
Amennyiben valamely aa és bb természetes számokra az a⋅ba\cdot b eredménye már ismert, úgy teljesül az a⋅s(b)=(a⋅b)+aa\cdot s(b)=(a\cdot b) + a egyenlőség.

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

Megnézem a tudásbázisban

♣

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

2⋅0=02⋅1=2⋅s(0)=(2⋅0)+2=0+2=22⋅2=2⋅s(1)=(2⋅1)+2=2+2=42⋅3=2⋅s(2)=(2⋅2)+2=4+2=6\begin{aligned} 2 \cdot 0&=0 \\ 2 \cdot 1&=2 \cdot s(0)=(2 \cdot 0) + 2 = 0 + 2 = 2 \\ 2 \cdot 2&=2 \cdot s(1) = (2 \cdot 1) + 2=2+2=4 \\ 2 \cdot 3&=2 \cdot s(2)=(2 \cdot 2) + 2=4 + 2=6 \end{aligned}

Értelmeztünk tehát egy újabb műveletet az N\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⋅0a \cdot 0-hoz hasonlóan a 0⋅a0 \cdot a eredménye is 00 lesz.

12.2. Lemma:

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

0⋅a=00\cdot a=0

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

Megnézem a tudásbázisban

♣

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

0⋅s(n)⏟=a=00\cdot \underbrace{s(n)}_{=a}=0

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

0⋅s(n)=(0⋅n)+0=…0\cdot s(n)=(0\cdot n) + 0 = \ldots

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

…=0⋅n=…\ldots =0\cdot n = \ldots

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

…=0\ldots =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=0a=0-ra.

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

0⋅0⏟=a=00\cdot \underbrace{0}_{=a}=0

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

Megnézem a tudásbázisban

∎

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\N halmaz tetszőleges aa és bb elemeire igaz az alábbi összefüggés:

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

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

Megnézem a tudásbázisban

♣

Bizonyítás:

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

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

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

s(b)⋅s(n)=(s(b)⋅n)+s(b)=…s(b)\cdot s(n) = (s(b)\cdot n) + s(b) = \ldots

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

…=((b⋅n)+n⏟=s(b)⋅n)+s(b)=…\ldots = (\underbrace{(b\cdot n) + n}_{=s(b)\cdot n}) + s(b) = \ldots

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

…=(b⋅n)+(n+s(b))=…\ldots = (b\cdot n) + (n + s(b)) = \ldots

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

…=(b⋅n)+s(n+b)⏟=(n+s(b))=…\ldots = (b\cdot n) + \underbrace{s(n+b)}_{=(n + s(b))} = \ldots

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

…=(b⋅n)+s(b+n⏟=n+b)=…\ldots = (b\cdot n) + s(\underbrace{b+n}_{=n+b}) = \ldots

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

…=(b⋅n)+(b+s(n))⏟=s(b+n)=…\ldots = (b\cdot n) + \underbrace{(b+s(n))}_{=s(b+n)} = \ldots

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

…=((b⋅n)+b)+s(n)=…\ldots = ((b\cdot n) + b)+s(n) = \ldots

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

…=(b⋅s(n)⏟=(b⋅n)+b)+s(n)\ldots = (\underbrace{b\cdot s(n)}_{=(b\cdot n)+b})+s(n)

Vagyis azt kaptuk, hogy valóban s(b)⋅s(n)⏟=a=(b⋅s(n)⏟=a)+s(n)⏟=as(b)\cdot \underbrace{s(n)}_{=a} = (b\cdot \underbrace{s(n)}_{=a}) + \underbrace{s(n)}_{=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.

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

s(b)⋅0⏟=a=(b⋅0⏟=a)+0⏟=as(b)\cdot \underbrace{0}_{=a} = (b\cdot \underbrace{0}_{=a}) + \underbrace{0}_{=a}

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

s(b)⋅0=0=…s(b)\cdot 0 = 0 = \ldots

Szintén ugyanezen ok miatt:

…=b⋅0=…\ldots = b\cdot 0 = \ldots

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

…=(b⋅0)+0\ldots = (b\cdot 0) + 0

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

Megnézem a tudásbázisban

∎

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\N halmaz tetszőleges aa és bb elemeire igaz az alábbi összefüggés:

a⋅b=b⋅aa\cdot b = b\cdot a

Megnézem a tudásbázisban

♣

Bizonyítás:

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

a⋅s(n)⏟=b=s(n)⏟=b⋅aa \cdot \underbrace{s(n)}_{=b} = \underbrace{s(n)}_{=b} \cdot a

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

a⋅s(n)=(a⋅n)+a=…a\cdot s(n) = (a\cdot n) + a = \ldots

Az indukciós feltétel miatt:

…=(n⋅a)+a=…\ldots =(n\cdot a) + a= \ldots

Végül a 12.3. Lemma miatt:

…=s(n)⋅a\ldots = s(n) \cdot a

Vagyis azt kaptuk, hogy valóban a⋅s(n)⏟=b=s(n)⏟=b⋅aa \cdot \underbrace{s(n)}_{=b} = \underbrace{s(n)}_{=b} \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=0b=0-ra.

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

Megnézem a tudásbázisban

∎

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 SS halmazon. Jelöljük az egyik műveletet ∘\circ-rel, a másikat pedig ∙\bullet-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ő két kifejezést kell kiértékelnünk az SS halmaz aa, bb és cc elemeire:

a∙(b∘c)(a∙b)∘(a∙c)\begin{gathered} a\bullet (b \circ c) \\ (a\bullet b)\circ (a\bullet c) \end{gathered}

A 12.1. ábra az első kifejezés kiértékelését mutatja. Itt először a ∘\circ műveletet kell elvégezni bb-re és cc-re, majd ennek az eredményét kell össze-∙\bullet-ozni aa-val balról.

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

A második kifejezés kiértékelését mutatja a 12.2. ábra. Ebben az esetben először össze-∙\bullet-ozzuk bb-t és cc-t aa-val balról, majd az így kapott két eredményt ∘\circ-özzük össze.

Disztributív művelet kiértékelése (2. 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 aa, bb és cc elemek esetén megegyeznek.

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

Legyenek ∙\bullet és ∘\circ egy valamilyen SS halmazon értelmezett kétváltozós műveletek. Amennyiben tetszőleges SS-beli aa-ra, bb-re és cc elemekre

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

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

Amennyiben

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

teljesül, akkor azt mondjuk, hogy a ∙\bullet 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 ∙\bullet művelet disztributív a ∘\circ műveletre nézve.

Megnézem a tudásbázisban

♣

Megjegyzés:

1.
Ha a ∙\bullet 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 ∙\bullet művelet kommutativitása.
2.
A disztributivitási kapcsolat két művelet között általában nem kölcsönös. Ez azt jelenti, hogy ha a ∙\bullet 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 ∙\bullet műveletre nézve.
3.
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∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)\begin{aligned} A\cap (B\cup C) &= (A\cap B)\cup (A\cap C) \\ A\cup (B\cap C) &= (A\cup B)\cap (A\cup C) \end{aligned}

Megnézem a tudásbázisban

♣

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\N halmaz tetszőleges aa, bb és cc elemeire igazak az alábbi összefüggések:

a⋅(b+c)=(a⋅b)+(a⋅c)(a+b)⋅c=(a⋅c)+(b⋅c)\begin{aligned} a\cdot (b+c) &= (a\cdot b) + (a\cdot c) \\ (a+b)\cdot c &= (a\cdot c) + (b\cdot c) \end{aligned}

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

Megnézem a tudásbázisban

♣

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 cc-re vonatkozóan. Tegyük fel, hogy az állítás igaz valamilyen c=nc=n természetes számra. Az tehát az indukciós feltétel, hogy

a⋅(b+n)=(a⋅b)+(a⋅n)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)c=s(n)-re is igaz lesz, azaz:

a⋅(b+s(n)⏟=c)=(a⋅b)+(a⋅s(n)⏟=c)a \cdot (b+ \underbrace{s(n)}_{=c})=(a \cdot b) + (a \cdot \underbrace{s(n)}_{=c})

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

a⋅(b+s(n))=a⋅s(b+n)=…a \cdot (b+ s(n))=a \cdot s(b+n) = \ldots

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

…=(a⋅(b+n))+a=…\ldots =(a \cdot (b+n)) + a = \ldots

Az indukciós feltétel miatt:

…=((a⋅b)+(a⋅n))+a=…\ldots =((a \cdot b)+(a \cdot n)) + a = \ldots

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

…=(a⋅b)+((a⋅n)+a)=…\ldots =(a \cdot b)+((a \cdot n) + a) = \ldots

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

…=(a⋅b)+(a⋅s(n))\ldots =(a \cdot b)+(a \cdot s(n))

Vagyis azt kaptuk, hogy valóban a⋅(b+s(n)⏟=c)=(a⋅b)+(a⋅s(n)⏟=c)a \cdot (b+ \underbrace{s(n)}_{=c})=(a \cdot b) + (a \cdot \underbrace{s(n)}_{=c}).

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=0c=0 esetén, azaz:

a⋅(b+0⏟=c)=(a⋅b)+(a⋅0⏟=c)a \cdot (b+ \underbrace{0}_{=c})=(a \cdot b) + (a \cdot \underbrace{0}_{=c})

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

a⋅(b+0)=a⋅b=…a \cdot (b+ 0)=a \cdot b = \ldots

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

…=(a⋅b)+0=…\ldots = (a\cdot b) + 0 =\ldots

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

…=(a⋅b)+(a⋅0)\ldots = (a\cdot b) + (a\cdot 0)

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

Megnézem a tudásbázisban

∎

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\N halmaz tetszőleges aa, bb és cc elemeire igaz az alábbi összefüggés:

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

Megnézem a tudásbázisban

♣

Bizonyítás:

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

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

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

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

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

(a⋅b)⋅s(n)=((a⋅b)⋅n)+(a⋅b)=…(a\cdot b)\cdot s(n) = ((a\cdot b) \cdot n) + (a\cdot b)=\ldots

Az indukciós feltétel miatt:

…=(a⋅(b⋅n))+(a⋅b)=…\ldots =(a\cdot (b \cdot n)) + (a\cdot b)=\ldots

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

…=a⋅((b⋅n)+b)=…\ldots =a\cdot ((b \cdot n) + b)=\ldots

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

…=a⋅(b⋅s(n))\ldots =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=0c=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⋅b)⋅0⏟=c=0=a⋅0=a⋅(b⋅0⏟=c)(a\cdot b) \cdot \underbrace{0}_{=c} = 0 = a\cdot 0 = a \cdot (b \cdot \underbrace{0}_{=c})

Megnézem a tudásbázisban

∎

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\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\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 aa természetes szám "előrébb van" ebben a képzeletbeli sorban, mint egy bb természetes szám.

A kétváltozós műveletekhez hasonlóan szükségünk lesz tehát egy olyan képzeletbeli dobozra, amelybe ha felül bedobunk két tetszőleges természetes számot az N\N halmazból, akkor alul kipottyan egy igen vagy egy nem válasz egy adott eldöntendő kérdésre. Például arra a kérdésre, hogy aa "előrébb van-e" a természetes számok halmazában, mint bb? Ez nagyon hasonló azokhoz a Turing-gépekhez, amelyeket a 6.6. szakaszban formális nyelvek felismeréséhez használtunk. Jelen esetben azonban a bemenet nem egy szimbólumsorozat, hanem két természetes szám, a kimenet pedig egy igen vagy egy nem válasz lesz. Ezt szemlélteti a 12.3. ábra.

Kétváltozós reláció
12.3. ábra: Kétváltozós reláció

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 RR-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 nn-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\N halmazt, és válasszunk ki belőle két tetszőleges elemet, mondjuk 11-et és 22-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)(1; 2)-vel, a másikat pedig (2;1)(2; 1)-gyel jelöljük. Az (1;2)(1; 2) és a (2;1)(2; 1) rendezett párok tehát különbözőek, mivel nem azonos a bennük szereplő elemek sorrendje. Általánosabban rendezett nn-eseknek nevezzük azokat az ehhez hasonló sorozatokat, amelyekben nem 22, hanem nn darab elem szerepel. Most fogalmazzuk meg ugyanezt a halmazok nyelvén.

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

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

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

Általánosabban legyenek A1A_1, A2A_2, ..., AnA_n tetszőleges halmazok. Ekkor ezen halmazok direkt szorzatának (vagy Descartes-szorzatának) nevezzük azt a halmazt, amely az összes olyan (a1;a2;…;an)(a_1;a_2;\ldots;a_n) alakban felírható elemet tartalmazza, amelyek esetén minden ii index esetén aia_i valamilyen AiA_i-beli elem. Ezt a halmazt így jelöljük:

A1×A2×…×AnA_1\times A_2\times \ldots \times A_n

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

Az A1×A2×⋯×AnA_1\times A_2\times \dots \times A_n direkt szorzat (a1;a2;…;an)(a_1;a_2;\ldots;a_n) elemeit rendezett nn-eseknek, adott ii index esetén pedig aia_i-t a rendezett nn-es ii-edik komponensének nevezzük.

Megnézem a tudásbázisban

♣

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

Megnézem a tudásbázisban

♣

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 ko˝\text{kő}, a papıˊr\text{papír} és az olloˊ\text{olló} szavakat tartalmazza. Jelöljük ezt a halmazt SS-sel. Ekkor a S×SS\times S halmaz az alábbi kilenc rendezett párt fogja tartalmazni: (ko˝;ko˝)(\text{kő}; \text{kő}), (ko˝;papıˊr)(\text{kő}; \text{papír}), (ko˝;olloˊ)(\text{kő}; \text{olló}), (papıˊr;ko˝)(\text{papír}; \text{kő}), (papıˊr;papıˊr)(\text{papír}; \text{papír}), (papıˊr;olloˊ)(\text{papír}; \text{olló}), (olloˊ;ko˝)(\text{olló}; \text{kő}), (olloˊ;papıˊr)(\text{olló}; \text{papír}), és (olloˊ;olloˊ)(\text{olló}; \text{olló}).

Most szigorúan a 12.9. Definíció alapján adjunk meg egy relációt az SS halmazon. Ez ugye az S×SS\times S direkt szorzat valamely részhalmaza lesz, amelyet most jelöljünk például a ≻\succ szimbólummal. Válasszuk azt a részhalmazt, amely csak a (ko˝;olloˊ)(\text{kő}; \text{olló}), (olloˊ;papıˊr)(\text{olló}; \text{papír}) és (papıˊr;ko˝)(\text{papír}; \text{kő}) 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 SS halmaz elemei között:

ko˝≻olloˊolloˊ≻papıˊrpapıˊr≻ko˝\begin{aligned} \text{kő} &\succ \text{olló} \\ \text{olló} &\succ \text{papír} \\ \text{papír} &\succ \text{kő} \end{aligned}

Vegyük észre, hogy amennyiben a ≻\succ 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\N halmazon, amelynek a segítségével sorba fogjuk tudni rendezni N\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 SS halmaz és egy ezen a halmazon értelmezett RR reláció. Ha SS minden aa elemére teljesül, hogy aRaaRa, akkor azt mondjuk, hogy az RR reláció reflexív.

Megnézem a tudásbázisban

♣

Például a 12.5. szakaszban a kő-papír-olló játékkal kapcsolatban definiált ≻\succ reláció nyilvánvalóan nem reflexív, hiszen ha a két játékos ugyanazt mutatja – legyen az akár ko˝\text{kő}, akár papıˊr\text{papír}, akár olloˊ\text{olló} –, 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 SS halmaz és egy ezen a halmazon értelmezett RR reláció, valamint tegyük fel, hogy aa és bb az SS halmaz tetszőleges, de egymástól különböző elemei – azaz a≠ba\neq b. Ha minden ilyen esetben aRbaRb és bRabRa közül legfeljebb az egyik teljesül, akkor azt mondjuk, hogy az RR reláció antiszimmetrikus.

Megnézem a tudásbázisban

♣

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=ba=b.

Megjegyezzük azonban, hogy visszafelé nem feltétlenül igaz, hogy a=ba=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.

Megnézem a tudásbázisban

♣

A már említett ≻\succ 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 SS halmaz és egy ezen a halmazon értelmezett RR reláció, valamint tegyük fel, hogy aa, bb és cc az SS halmaz tetszőleges elemei. Ha minden ilyen esetben aRbaRb és bRcbRc együttes teljesülése esetén aRcaRc is teljesül, akkor azt mondjuk, hogy az RR reláció tranzitív.

Megnézem a tudásbázisban

♣

A ≻\succ reláció nem tranzitív, hiszen például papıˊr≻ko˝\text{papír} \succ \text{kő} és ko˝≻olloˊ\text{kő} \succ \text{olló} teljesül, de papıˊr≻olloˊ\text{papír} \succ \text{olló} 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 SS halmaz és egy ezen a halmazon értelmezett RR reláció, valamint tegyük fel, hogy aa és bb az SS halmaz tetszőleges elemei. Ha minden ilyen esetben aRbaRb és bRabRa közül legalább az egyik teljesül, akkor azt mondjuk, hogy az RR reláció trichotóm.

Megnézem a tudásbázisban

♣

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

Most bevezetünk egy olyan fogalmat, amely a ≻\succ 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 SS halmaz, és egy rajta értelmezett RR reláció. Amennyiben RR egyszerre reflexív, antiszimmetrikus és tranzitív, úgy az RR relációt SS feletti részbenrendezésnek hívjuk, és azt mondjuk, hogy a SS egy részbenrendezett halmaz az RR relációval.

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

Megnézem a tudásbázisban

♣

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 SS 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≤ba\leq b kifejezést egyszerűen csak interpretáljuk úgy, hogy "aa legfeljebb annyiadik elem a sorban, mint bb".

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

  1. Reflexivitás: Tetszőleges elem "legfeljebb annyiadik a sorban", mint önmaga.
  2. Antiszimmetria: Ha az aa elem "legfeljebb annyiadik a sorban", mint a bb elem, és a bb elem is "legfeljebb annyiadik a sorban", mint az aa elem, akkor a két elem megegyezik.
  3. Tranzitivitás: Ha az aa elem "legfeljebb annyiadik a sorban", mint a bb elem, amely pedig "legfeljebb annyiadik a sorban", mint a cc elem, akkor az aa elem "legfeljebb annyiadik a sorban", mint a cc elem.
  4. 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\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\N halmaz tetszőleges aa és bb elemeihez létezik olyan kk szintén N\N-beli elem, amelyre teljesül, hogy a+k=ba+k=b, akkor azt mondjuk, hogy a≤ba\leq b. Kiolvasva: "aa legfeljebb bb" vagy "bb legalább aa". A ≤\leq relációt a természetes számok rendezésének nevezzük.

Ha ezen kívül k≠0k\neq 0 is teljesül, akkor azt mondjuk, hogy a<ba\lt b. Kiolvasva: "aa kisebb bb" vagy "bb nagyobb aa".

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

Megnézem a tudásbázisban

♣

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\N halmaz tetszőleges aa elemére teljesül, hogy a≤aa\leq a.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tekintve, hogy a 11.4. Definíció 1. pontja szerint tetszőleges aa-ra teljesül, hogy a+0=aa+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≤aa\leq a tetszőleges aa esetén teljesül.

Megnézem a tudásbázisban

∎

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\N halmaz tetszőleges aa, bb és cc elemére teljesül, hogy a≤ba\leq b és b≤cb\leq c együttes fennállása esetén a≤ca\leq c is fennáll.

Megnézem a tudásbázisban

♣

Bizonyítás:

Ha a≤ba\leq b, akkor a 12.15. Definíció miatt létezik olyan természetes szám, amelyet aa-hoz adva bb-t kapunk. Jelöljük ezt a természetes számot k1k_1-gyel, így tehát azt kapjuk, hogy a+k1=ba+k_1=b.

Ugyanezen okok miatt ha b≤cb\leq c, akkor létezik olyan természetes szám is, amelyet bb-hez adva cc-t kapunk. Jelöljük ezt a természetes számot k2k_2-vel, így tehát azt kapjuk, hogy b+k2=cb+k_2=c.

Az első egyenlet baloldalát a második egyenletbe bb helyére behelyettesítve azt kapjuk, hogy (a+k1)⏟=b+k2=c\underbrace{(a+k_1)}_{=b} + 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+(k1+k2)=ca+(k_1+k_2)=c.

Létezik tehát olyan természetes szám is, amelyet aa-hoz adva cc-t kapunk – nevezetesen k1+k2k_1+k_2. A 12.15. Definíció miatt ez épp azt jelenti, hogy a≤ca\leq c.

Megnézem a tudásbázisban

∎

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 aa, bb és cc természetes számok esetén ha a+c=b+ca+c = b+c, akkor a=ba=b.

Megnézem a tudásbázisban

♣

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=nc=n-re, akkor teljesülni fog c=s(n)c=s(n)-re is. Meg kell tehát mutatnunk, hogy ha a+n=b+na+n = b+n-ből a=ba=b következik, akkor a+s(n)=b+s(n)a+s(n) = b+s(n)-ből is a=ba=b következik.

Az a+s(n)=b+s(n)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)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+na+n=b+n. Az indukciós feltétel szerint viszont az állítás teljesül nn-re, ezért ebből a=ba=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+0a+0=b+0-ból a=ba=b következik. Ez viszont nyilvánvalóan teljesül, hiszen az egyenlet mindkét oldalát egyszerűsíthetjük 00-val a 11.4. Definíció 1. pontja miatt.

Megnézem a tudásbázisban

∎

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 00 lehet a természetes számok között.

12.19. Lemma:

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

Megnézem a tudásbázisban

♣

Bizonyítás:

Tegyük fel, hogy nem igaz az állítás, azaz a+b=0a+b=0, de aa és bb közül legalább az egyik nem 00. 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≠0b\neq 0. Vizsgáljuk meg, hogy egy ilyen galád feltételezésnek milyen képtelen logikai következményei lennének.

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

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

a+s(n)⏟=b=0a+\underbrace{s(n)}_{=b}=0

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

s(a+n)=0s(a+n)=0

Vagyis azt kaptuk, hogy az a+na+n rákövetkezője 0. Ez azonban lehetetlen, hiszen a 11.1. Definíció 3. pontja szerint a 00 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.

Megnézem a tudásbázisban

∎

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.

Megnézem a tudásbázisban

♣

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\N halmaz tetszőleges aa és bb elemére teljesül, hogy a≤ba\leq b és b≤ab\leq a együttes fennállása esetén szükségképpen a=ba=b.

Megnézem a tudásbázisban

♣

Bizonyítás:

Ha a≤ba\leq b, akkor a 12.15. Definíció miatt létezik olyan természetes szám, amelyet aa-hoz adva bb-t kapunk. Jelöljük ezt a természetes számot k1k_1-gyel, így tehát azt kapjuk, hogy a+k1=ba+k_1=b.

Ugyanezen okok miatt ha b≤ab\leq a, akkor létezik olyan természetes szám is, amelyet bb-hez adva aa-t kapunk. Jelöljük ezt a természetes számot k2k_2-vel, így tehát azt kapjuk, hogy b+k2=ab+k_2=a.

Az első egyenlet baloldalát a második egyenletbe bb helyére behelyettesítve azt kapjuk, hogy (a+k1)⏟=b+k2=a\underbrace{(a+k_1)}_{=b} + 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+(k1+k2)=ca+(k_1+k_2)=c.

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

Helyettesítsük vissza mondjuk k1k_1-et az egyik kiindulási egyenletünkbe: a+0⏟=k1=ba+\underbrace{0}_{=k_1}=b. Ennek az egyenletnek a baloldala a 11.4. Definíció 1. pontja miatt 00-val egyszerűsíthető, azaz a=ba=b.

Megnézem a tudásbázisban

∎

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 aa és bb természetes számok esetén az a≤ba\leq b reláció akkor és csak akkor teljesül, ha az s(a)≤s(b)s(a)\leq s(b) reláció is teljesül.

Megnézem a tudásbázisban

♣

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≤ba\leq b, akkor ez a 12.15. Definíció miatt azt jelenti, hogy létezik nn, amelyre a+n=ba+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)s(a+n)=s(b). Ekkor viszont a 11.4. Definíció 2. pontja miatt s(a)+n=s(b)s(a)+n=s(b) is igaz. Ez viszont szintén a 12.15. Definíció miatt épp azt jelenti, hogy s(a)≤s(b)s(a)\leq s(b).

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

Megnézem a tudásbázisban

∎

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\N halmaz tetszőleges aa és bb elemére teljesül, hogy az a≤ba\leq b és b≤ab\leq a relációk közül legalább az egyik fennáll.

Megnézem a tudásbázisban

♣

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\N halmazban léteznek olyan galád aa és bb természetes számok, amelyek között egyik irányban sem áll fenn a ≤\leq reláció, azaz a≰ba\nleq b és b≰ab\nleq a.

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

Ha viszont egyikük sem 00, 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 a1a_1-gyel és b1b_1-gyel, amelyekre tehát teljesül, hogy s(a1)=as(a_1)=a és s(b1)=bs(b_1)=b.

Mármost ha aa és bb 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 a1≰b1a_1\nleq b_1 és b1≰a1b_1\nleq a_1.

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

Kapunk tehát két végtelen sorozatot, amely sorozatokban sehol nem szerepel a 00, és a 12.4. ábrán látható rákövetkezőségi viszonyok állnak fenn közöttük:

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

Ez viszont lehetetlen, hiszen a 11.1. Definíció 4. pontja kimondja, hogy a 00-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≤ba\leq b és a b≤ab\leq a relációk közül legalább az egyiknek teljesülnie kell tetszőleges aa és bb esetén, máskülönben ellentmondásba kerülnénk a 4. Peano-axiómával.

Megnézem a tudásbázisban

∎

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\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\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\N halmazán nem művelet, mivel bizonyos esetekben kivezet belőle. Például nincs olyan természetes szám, amely a 2−52-5 különbségképzés eredménye lenne, a −3-3 ugyanis nem természetes szám, holott a 22 és az 55 is az.

Kinőttük tehát az N\N halmazt, ezért a következő fejezetekben át fogunk térni egy N\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\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.