Alice és Bob számelméletet épít

11.1Mik azok az axiómák?

Minden logikai játéknak vannak bizonyos alapfogalmai és az ezekre épülő játékszabályai, amelyeket meg kell ismernünk ahhoz, hogy játszani tudjunk. Ezeket az alapfogalmakat és játékszabályokat nincs értelme kétségbe vonnunk, mivel azokat a játék megalkotója hozta létre – mondhatni önkényesen – abból a célból, hogy a játék épp olyan legyen, amilyen. Például kérdezhetnénk, hogy a sakkban a vezér miért nem tud lóugrásban lépni, csak vízszintesen, függőlegesen és átlósan? Erre nagyon egyszerű a válasz: azért mert ez a szabály. Lehetne persze az is a szabály, hogy a vezér lóugrásban is tud lépni. Minden bizonnyal az is egy nagyszerű játék lenne, de konkrétan a sakkban ez a lépés meg van tiltva.

A matematika összes területe – így például a számelmélet is – ugyanígy épül fel azzal a különbséggel, hogy itt az alapfogalmakat definícióknak, a játékszabályokat pedig axiómáknak nevezik, mert így tudományosabban hangzik. Egy matematikai elmélet axiómáiban ugyanúgy nincs értelme kételkednünk, mint a sakk játékszabályaiban. És nem azért nincs értelme, mert ezek abszolút igazságok lennének, hanem azért, mert ha valamelyik axiómát nem tekintenénk igaznak, akkor az vagy ellentmondáshoz vezetne, vagy pedig egy teljesen más elméletet kapnánk teljesen más logikai következményekkel. Lehet-e egy ilyen módosított elmélet ugyanúgy hasznos, mint az eredeti? Természetesen lehet.

Erre az egyik legszemléletesebb példát a geometriában találhatjuk. A geometria alapfogalmai közül nézzük a következő hármat: pont, egyenes, egyenesek metszése. Az, hogy ezek lényegét köznyelven hogyan lehet megfogalmazni, alapjában véve csak azért fontos, hogy valahogy el tudjuk őket képzelni. Biztos vagyok benne, hogy az Olvasónak él is valamilyen kép a fejében ezekről a fogalmakról. De mégis mi alapján képzelünk el egy egyenest vagy egy pontot épp úgy, ahogy? Habár a megszokás miatt sokan nincsenek ennek tudatában, de ezeket a képeket e geometriai fogalmak alaptulajdonságait leíró axiómák, vagy ha úgy tetszik, a geometria játékszabályai okozzák.

Az egyik ilyen axióma a geometriában az úgynevezett párhuzamossági axióma, amely a következőt mondja ki: ha van egy $e$ egyenes és egy ezen kívüli $P$ pont, akkor pontosan egy olyan $f$ egyenes létezik, amely átmegy a $P$ ponton, de nem metszi az $e$ egyenest.

És valóban: egy papírlapon kipróbálva a fenti axiómát tényleg pontosan egyféleképpen tudunk egy adott egyenessel párhuzamos másik egyenest rajzolni, amely egy adott ponton áthalad (11.1. ábra).

De vajon miért van ez így? Hogyan lehetne erre matematikai bizonyítást adni? A meglepő válasz a következő: ezt nem kell bizonyítani, ez ugyanis egy axióma. A sakkos példa analógiájával élve azért lehet egy adott egyeneshez egy adott ponton keresztül pontosan $1$ (azaz se nem több, se nem kevesebb) párhuzamos másik egyenest rajzolni, mert egész egyszerűen ez a szabály. Lehetne persze az is a szabály, hogy ne lehessen egyáltalán párhuzamost rajzolni, vagy hogy éppenséggel végtelen sok párhuzamost lehessen rajzolni. Minden bizonnyal ezek is nagyszerű geometriák lennének... Valóban így van? Nézzük is meg gyorsan egy gondolatkísérlettel!

11.2A játékszabályok megváltoztatása

Önkényesen változtassuk meg a párhuzamossági axiómát – azaz az egyik játékszabályt – a következőképpen: ha van egy $e$ egyenes, és egy ezen kívüli $P$ pont, akkor nem létezik olyan egyenes, amely átmegy a $P$ ponton, és nem metszi az $e$ egyenest. Vagy ami ennek közvetlen logikai következménye: nem léteznek párhuzamos egyenesek. Mi a gond ezzel? Első olvasatra butaságnak tűnik? Már hogyne léteznének párhuzamosok? Hiszen az előbb próbáltuk ki a papírlapon – mondhatnánk, de meglepő módon tévedünk.

Sokaknak nem tűnik fel, de az előző mondatban a "papírlap" szó kulcsfontosságú volt. Méghozzá azért, mert a papírlapra rajzolt vonalak valójában nem maguk az egyenesek, mint absztrakt geometriai objektumok, hanem azoknak csak a modelljei. Sőt az egész papírlap maga is csak egy modell. Méghozzá annak a geometriának a modellje, amelyben szerepel a párhuzamossági axióma, mint játékszabály. Nem modellje viszont ennek a nagyon furcsának tűnő másik geometriának, amelyből önkényesen kihajítottuk a párhuzamossági axiómát, és felvettünk helyette egy, a párhuzamosságot megtiltó új axiómát. Ha jobban belegondolunk, modellekre csakis nekünk embereknek van szükségünk ahhoz, hogy el tudjuk képzelni a matematikát. A matematika azonban köszöni szépen, de e nélkül is nagyon jól működik. Mi lehet hát a modellje ennek az új geometriának, és vajon hasznos-e egyáltalán?

A válasz az, hogy enélkül nem létezne hajózás, repülőzés, űrhajózás, és valószínűleg műholdakat sem tudnánk Föld körüli pályára állítani. E geometria ugyanis nem más, mint az úgynevezett gömbi geometria. Ennek egyik – de nem az egyetlen – modellje egy sík papírlap helyett egy gömbfelület. Az "egyenesek" pedig az e gömbfelületen elhelyezkedő úgynevezett főköröknek feleltethetők meg. Főkörnek nevezzük a gömbfelület és egy tetszőleges, a gömb középpontjára illeszkedő sík metszésvonalát. Ha belegondolunk, az "egyenes" fogalmának ilyen módon történő definíciója esetén valóban nem léteznek párhuzamos "egyenesek", azaz olyanok, amelyek ne metszenék egymást.

Vegyünk is a kezünkbe egy Földgömböt, hogy jobban el tudjuk képzelni a rajta elhelyezkedő főköröket. A 11.2. ábrán két ilyen főkör látható.

Mondhatnánk, hogy jó-jó, de milyen butaság már "egyeneseknek" hívni a főköröket, amikor szemmel láthatóan görbe vonalakról van szó, ráadásul még a nevükben is benne van, hogy "kör". Ez azonban pusztán fogalomalkotás kérdése, hiszen nem a neve határozza meg egy adott matematikai objektum tulajdonságait, hanem a rá kimondott axiómák. Az "egyenes" kifejezés használata mellett szól például az, hogy gömbi geometria esetén is igaz marad az a szokásos megállapítás, miszerint két pont között a legrövidebb út az őket összekötő "egyenes" mentén helyezkedik el.

Gondoljunk csak mondjuk a repülésre. Biztosan mindenki elgondolkozott már azon, hogy vajon miért tesznek akkora kerülőt Grönland felé az Európából az USA-ba tartó repülőgépek, holott mehetnének nyugat felé is, ami a térképeken látszólag rövidebb út lenne? A válasz nagyon egyszerű. Azért mert a látszat ellenére, ha a kapitány Európában Grönland felé irányítja a gép orrát, és csak egyenesen halad előre irányváltoztatás nélkül, akkor az USA nyugati partján fog kikötni. Mindenki fogjon a kezébe ismét egy Földgömböt, és azonnal látni fogja, hogy ez valóban így van.

De akkor miért tűnik mégis kerülőútnak a világtérképen a Grönland felé vezető útvonal? Ennek pusztán az az oka, hogy egy világtérkép a valódi gömbfelületnek csak egy sík felületre történő vetítése, amelyen a távolságok szükségszerűen torzulnak az útvonal mentén. Attól függően, hogy milyen vetítéssel készült az adott térkép, a gömbi geometriának más és más modelljét kapjuk, és ezekben az "egyenesek" modelljei is más és más görbék lesznek. Egy szokásos világtérképen például az "egyenesek" modelljei hullámszerű görbék lesznek. Biztosan sokan láttak már űrhajós filmet, ahol az irányítóközpont falára volt kivetítve az űrhajó pályája, amely a világtérképen egy ilyen hullámhoz hasonló görbeként jelent meg.

A 11.3. ábrán például a Nemzetközi Űrállomás (ISS) földfelszínre vetített pályájának két periódusát láthatjuk. Itt a dolog még annyiban bonyolódik, hogy mivel az ISS másfél óra alatt kerüli meg a Földet, amely ezidő alatt elfordul valamennyit a tengelye körül, ezért az egyes periódusok nem ugyanott végződnek a térképen, mint ahol kezdődtek. Például az $a$ pontból indulva az ISS az első keringési periódus végén a $b$, a második periódus végén pedig a $c$ pontnál lesz.

Most, hogy van már kétféle geometriánk, felmerül a kérdés, hogy melyik a jobb, melyiket használjuk? Egy ilyen kérdést feltenni önmagában nincs értelme, hiszen a válaszhoz tudnunk kell, hogy mihez akarjuk használni. Amennyiben például házat tervezünk, vagy ki akarjuk számolni, hogy mennyi festéket vegyünk egy adott falfelületre, akkor bőven elég a hagyományos síkgeometriát használnunk, hiszen ebben jóval egyszerűbb számolni. Ha viszont egy világkörüli hajóutat kell megterveznünk adott állomásokkal a Föld különböző pontjain, akkor nem árt, ha meg tudjuk mérni az állomások közti távolságokat a szükséges üzemanyagmennyiségek kiszámításához. Erre nyilvánvalóan a síkgeometria nem alkalmas, lévén hogy egy gömbfelületen fogunk hajózni.

Egyszóval a matematika mindössze eszközöket ad a kezünkbe a világ dolgainak modellezésére. Azt azonban mi döntjük el, hogy mennyire pontos modellre van szükségünk az adott feladathoz. A többi "sallangra" nem vagyunk kíváncsiak, ezért ezeket kizárjuk a vizsgálatainkból. Ezt a folyamatot nevezik absztrakciónak.

De mi köze ennek a geometriai példának a kriptográfiához? Közvetlenül természetesen az égvilágon semmi, közvetetten viszont igen fontos látni azt a mechanizmust, amely alapján egy-egy matematikai elmélet felépül. Ezekkel a példákkal remélhetőleg világossá vált, hogy mit értünk axiómák alatt, amik a kiindulópontot adják ehhez az építkezéshez – csakúgy, mint egy valódi ház alapja.

Most a 9. és 10. fejezetben megismert kriptográfiai eljárások alapjait jelentő számelmélet "játékszabályait" fogjuk rögzíteni. Ez az axiómarendszer Giuseppe Peano olasz matematikustól származik 1889-ből.

11.3A Peano-féle axiómarendszer

Az Olvasónak vélhetően van valamilyen intuitív elképzelése a számokról, azon belül is az úgynevezett természetes számokról. Ezek a pozitív egész számok és a $0$. Megjegyezzük, hogy évszázadok óta megy a hitvita arról, hogy a $0$-t is természetes számnak kell-e tekinteni vagy nem. Mi ebben a vitában az igenlők pártjára helyezkedünk – azaz természetes számnak tekintjük a $0$-t –, ennek azonban pusztán praktikussági okai vannak. Sokak fejében él egy kép valamiféle egyik irányban végtelen számegyenesről – a negatív számokkal egyelőre nem foglalkozunk –, amely a $0$-val kezdődik, és a többi természetes szám ettől jobbra helyezkedik el szép sorban, egymástól egyenlő távolságokra. Talán még összeadni és szorozni is tudunk ezen a számegyenesen, például a 9.3. szakaszban leírtakhoz hasonló módon.

Azonban ne feledjük: egy matematikai objektum tulajdonságait csak és kizárólag a rá kimondott axiómák határozzák meg, nem holmi intuitív kép, ami a fejünkben van. Mivel most a természetes számokra vonatkozó axiómákat fogjuk ismertetni, ezért átmenetileg töröljünk ki mindent a fejünkből, amit ezekről az objektumokról eddig gondoltunk. Tekintsük őket pusztán "valamiknek", amelyekről ezen a ponton csak annyit tudunk, hogy egy valamilyen "összesség" vagy "sokaság" elemei. A matematikában ezt a "sokaságot" a természetes számok halmazának nevezzük, és $\mathbb{N}$-nel jelöljük. Az, hogy pontosan miként lehet ezeket a "valamiket" elképzelni, igazából ezen a ponton nem is fontos. Minket pusztán a tulajdonságaik érdekelnek, ezeket pedig kizárólag a rájuk kimondott axiómák fogják meghatározni. És mint azt hamarosan látni fogjuk, ezek pontosan összeegyeztethetők lesznek azzal az intuitív képpel, amit az imént átmenetileg kitöröltünk a fejünkből (ugye?!).

A természetes számokra vonatkozó axiómák megfogalmazásához két további fogalomra van szükségünk, ám szerencsére ezekkel már találkoztunk a 9.1. szakaszban, amelynek átismétlését erősen ajánljuk az Olvasónak. Az egyik ilyen fogalom a függvény lesz, amely tehát egy hozzárendelést valósít meg két tetszőleges halmaz – az alaphalmaz és a képhalmaz – elemei között. Mi egy olyan függvényt fogunk használni, amelynek mind az alaphalmaza, mind pedig a képhalmaza a természetes számok $\mathbb{N}$-nel jelölt halmaza lesz. A másik számunkra fontos fogalom a részhalmaz fogalma lesz, amely tehát azt fejezi ki, hogy egy szűkebb $A$ halmaz minden eleme egyben egy ennél bővebb $B$ halmaznak is eleme. Ilyenkor azt mondjuk, hogy $A$ részhalmaza $B$-nek. Erről részletesebben egy halmazelméleti gyorstalpaló keretében a 19.1. szakaszban olvashatunk majd.

Ennyi bevezető után most ismertetjük a természetes számok viselkedését meghatározó úgynevezett Peano-féle axiómarendszert. Ez lesz matematikai építményünk alapköve, az első definíció, amely néhány alapfogalmat és négy darab axiómát tartalmaz. A továbbiakban kizárólag ezeket fogadjuk el igaznak, és minden egyéb állításra szigorú matematikai bizonyítást fogunk megkövetelni. Noha a megfogalmazás első ránézésre meglehetősen technikainak fog tűnni, a definíció utáni megjegyzésben intuitív magyarázatot is fogunk adni az axiómákra, amelyből látható lesz, hogy tulajdonképpen teljesen nyilvánvaló dolgokat fogalmaznak meg. A definíciók és megjegyzések végét a ♣ karakterrel fogjuk jelölni mostantól.

Megjegyzés:

Az 1. axióma tulajdonképpen azt követeli meg, hogy minden $x$ természetes számhoz létezzen egy olyan természetes szám is, amely $x$ rákövetkezője. Ez azt jelenti, hogy bármelyik természetes számból indulunk ki, a rákövetkezésen keresztül mindig tovább tudunk lépni egy másik természetes számhoz, azaz utunk soha nem szakad meg.

A 2. axióma lényegében azt mondja ki, hogy semmilyen természetes számhoz a rákövetkezésen keresztül nem érkezhetünk meg két különböző irányból, bárhonnan is indulunk. Ez tehát megakadályozza egy, a 11.4. ábrán láthatóhoz hasonló szituáció kialakulását.

A 3. axióma kimondja egy és csakis egy olyan speciális természetes szám létezését, amely nem rákövetkezője semmilyen más természetes számnak sem. Ezzel lényegében két nagyon fontos dolgot kapunk. Egyrészt megtudjuk, hogy a "számegyenes" valóban egy egyik irányban végtelen egyenes, amely elkezdődik valahol. Másrészt pedig tulajdonképpen ez az axióma biztosítja, hogy természetes számok egyáltalán léteznek. A másik három axióma ugyanis a szigorúan vett matematikai logika szerint abban az esetben is teljesülne, ha az $\mathbb{N}$ halmaz történetesen üres lenne. Például furcsamód a "minden ismert egyszarvú fehér" állítás igaz. Az persze más kérdés, hogy a "minden" ebben a példában épp nulla darabot jelent, de ettől még az állítás igaz. Akárcsak az az állítás, miszerint "minden ismert egyszarvú fekete". Általánosságban is elmondható, hogy egy üres halmaz elemeire vonatkozó bármilyen univerzális állítás szintén igaz. Furcsa dolog ez a logika...

Végül a 4. axióma biztosítja, hogy a $0$-ból kiindulva a rákövetkezésen keresztül minden természetes számhoz eljutunk. Azaz nem léteznek a számegyenestől elszigetelt természetes számok, és így nem alakulhat ki olyan szituáció, mint amilyen 11.5. ábrán látható.

Ezen kívül a 4. axióma teszi lehetővé az úgynevezett teljes indukciós bizonyításokat. Lényegét tekintve arról van szó, hogy ha egy állítás igaz $0$-ra – amely alapján őt az axiómában említett $P$ halmazba helyeztük –, továbbá az állítás igazsága a rákövetkezésen keresztül öröklődik, akkor igaz lesz minden természetes számra. Ez jól szemléltethető egy valamelyik irányban végtelen dominósorral, amelyről belátjuk, hogy amennyiben valamelyik dominót felborítjuk – ezt indukciós feltételnek nevezzük –, akkor az fel fogja borítani a soron következő dominót is – ezt indukciós lépésnek nevezzük. Ezek után nincs más dolgunk, mint egy laza mozdulattal felborítani az első dominót, és élvezni a – végtelen hosszú – műsort.

♣

Első ránézésre ez egy igencsak szegényesre sikerült axiómarendszer. Azonban lényegében ebből a négy axiómából következik minden, amit a természetes számokról tudunk. Most vizsgáljuk meg, hogy mennyire sokmindent vagyunk képesek felépíteni ebből a mindössze négy darab axiómából.

11.4A matematikai bizonyítás fogalma

Az olyan állításokat, amelyek nem axiómák, hanem azoknak valamilyen logikai következményei, tételeknek nevezzük. Ahhoz, hogy egy matematikai állítást tételnek nevezhessünk, bizonyítást kell adnunk rá. Ennek során az állítást szigorú logikai érveléssel vissza kell vezetnünk vagy magukra az axiómákra, vagy pedig korábban már bizonyított tételekre.

Példaként ebben a szakaszban megfogalmazzuk első tételünket, és megnézzük, hogyan történik egy bizonyítás. Ez a tétel egy teljesen magától értetődő állításnak fog tűnni. Azonban ne feledjük, hogy mivel valóban kitöröltünk mindent a fejünkből a természetes számokkal kapcsolatban – ugye?! –, ezért most kizárólag a 11.1. Definícióban szereplő négy axiómára szorítkozhatunk majd.

A tételek végét – a definíciókhoz és megjegyzésekhez hasonlóan – a ♣, a bizonyítások végét pedig a ∎ karakterrel fogjuk jelölni.

Látható, hogy a természetes számok végtelensége egyáltalán nem magától értetődő, amennyiben kizárólag a Peano-axiómarendszer négy darab állítására támaszkodhatunk az érvelésben. Ez a példa jól tükrözi, hogy milyen körültekintően kell eljárni egy logikai érvelés során.

Most bevezetünk egy általános iskolából is jól ismert műveletet a természetes számok között. Ennek a műveletnek a konstrukciójához szintén a Peano-axiómarendszert fogjuk csak használni.

11.5Művelet bevezetése az $\mathbb{N}$ halmazon

Először is tisztázzuk, hogy pontosan mit értünk művelet alatt. Minket most speciálisan az olyan műveletek érdekelnek, amelyeknek két bemenetük van, de az alábbi definíció általánosítható lenne tetszőleges számú bemenetre is.

Az általános iskolában ezt olyan képzeletbeli gépekkel szokták szemléltetni, amelyeknek a tetején kettő, az alján pedig egy lyuk van. Ha a $S$ halmaz két tetszőleges $a$ és $b$ elemét beledobjuk a gép tetején lévő lyukakba, akkor a gép alján kipottyan az eredmény, amely szintén a $S$ halmaz eleme kell legyen (11.6. ábra).

Egy műveletnél tehát meg kell mondanunk azt is, hogy milyen halmazon értelmezzük. Fontos, hogy a művelet "ne vezessen ki" ebből a halmazból. Ez alapján például a szokásos összeadás a páratlan számok halmazán nem művelet, mivel például a $3+5$ eredménye nem páratlan, azaz nem eleme az alaphalmaznak. A páros számok halmazán azonban az összeadás már művelet, hiszen páros számok összege is páros.

Most definiáljuk, hogy mit értünk összeadás – mint művelet – alatt a 11.3. szakaszban bemutatott $\mathbb{N}$ halmazon, azaz a természetes számok között. Ne feledjük, hogy mivel kitöröltünk a fejünkből mindent – ugye?! –, amit a természetes számokról tudni véltünk, ezért csak a Peano-axiómarendszert használhatjuk ennek az új fogalomnak a bevezetésére.

Ez a definíció tehát két dolgot mond. Egyrészt tetszőleges természetes számhoz $0$-t adva az eredmény nem változik. Másrészt pedig azt, hogyha egy tetszőleges $a$ természetes számhoz egy szintén tetszőleges $b$ természetes szám rákövetkezőjét adjuk hozzá, akkor az eredmény megegyezik annak az összegnek a rákövetkezőjével, mintha $a$-hoz csak $b$-t adtunk volna hozzá. Figyeljük meg, hogy semmi mást nem használtunk fel ehhez a definícióhoz, csak a Peano-axiómarendszerben ismertetett alapfogalmakat.

Értelmeztünk tehát egy műveletet az $\mathbb{N}$ halmazon, amelyet önkényesen "összeadásnak" neveztünk, és a $+$ műveleti jellel jelöltünk. Vizsgáljuk hát meg, hogy ez valóban teljesíti-e azokat a jól megszokott tulajdonságokat, amelyeket általános iskolai tanulmányaink alapján elvárnánk tőle.

11.6Az összeadás kommutativitása

Általános iskolában megtanultuk, hogy teljesen mindegy, milyen sorrendben adunk össze két számot, ugyanazt az eredményt kell kapnunk. Megköveteljük tehát, hogy az összeadásban a tagok sorrendje felcserélhető legyen. Ezt a műveleti tulajdonságot fogalmazza meg általánosságban a most következő definíció.

Első jogos kérdés tehát, hogy vajon a természetes számok összeadása teljesíti-e ezt a kritériumot? Most meg fogjuk mutatni, hogy igen, méghozzá a 11.1. Definícióban szereplő Peano-axiómarendszer logikai következményeként. Ehhez először egy úgynevezett segédtételt – tudományosabb nevén lemmát – fogunk bizonyítani. Egy lemma semmiben sem különbözik egy sima tételtől. Ezzel az elnevezéssel pusztán azt szeretnénk jelezni, hogy egy olyan állításról van szó, amelynek önmagában nincs jelentősége, viszont felhasználjuk más tételek – jelen esetben például a kommutativitás – bizonyításához. Nézzük is meg ezt a segédtételt.

Ennek bizonyítására mutatunk egy remek példát a teljes indukció alkalmazására, amelyet ugye a 4. Peano-axióma tesz lehetővé.

Az imént bizonyított segédtételt fogjuk felhasználni az összeadás kommutativitásának bizonyításához. Ezt két lépésben fogjuk megtenni ismét a teljes indukciót alkalmazva. Egyrészt bizonyítjuk, hogy ha tetszőleges $a$ természetes számra valamilyen $n$ esetén teljesül, hogy $a+n=n+a$, akkor teljesülni fog $a+s(n)=s(n)+a$ is, azaz felállítjuk a dominósort. Másrészt felborítjuk az első dominót, azaz bizonyítjuk, hogy konkrétan $n=0$ esetén valóban teljesül a kommutativitás. Kezdjük ez utóbbival.

Most tehát rendelkezésünkre áll a 11.6. Lemma és a 11.7. Lemma. Ezek segítségével már igazolni tudjuk az összeadás kommutativitását:

Látható tehát, hogy a természetes számok összeadása valóban kommutatív, ahogy azt az általános iskolában már megszokhattuk tőle. Ez azonban csak és kizárólag a 11.1. Definícióban szereplő Peano-axiómarendszer logikai következménye, nem pedig holmi fejünkben élő intuitív kép miatt van ez így. Ennek bizonyításához két segédtételen keresztül vezetett az út, azaz kicsit sem mondható magától értetődőnek. A továbbiakban azonban egészen nyugodtan felhasználhatjuk majd ezt a tulajdonságot, hiszen az megnyugtató bizonyosságot nyert.

Most nézzük meg az összeadás egy másik nagyon fontos tulajdonságát, amely szintén jól ismert az általános iskolából.

11.7Az összeadás asszociativitása

Az összeadást egy kétváltozós műveletként definiáltuk, de mi van akkor, ha nem kettő, hanem három – vagy akár ennél több – természetes számot szeretnénk összeadni? Nagyon jó lenne, ha nem kéne újabb és újabb kettőnél többváltozós műveletet bevezetni a tagok számától függően. Tegyük fel például, hogy az $a+b+c$ összeget kell kiszámítani. Hogyan fogjunk hozzá? Két lehetőségünk is van.

Megtehetjük, hogy először kiszámoljuk az első kettő természetes szám összegét, és ennek eredményéhez adjuk hozzá a harmadikat. Ezt mutatja a 11.7. ábra.

Vagy megtehetjük azt is, hogy először kiszámoljuk a második és a harmadik természetes szám összegét, és ennek eredményét adjuk hozzá az elsőhöz. Ezt mutatja a 11.8. ábra.

Általános iskolában megtanultuk, hogy teljesen mindegy, melyik lehetőséget választjuk, ugyanazt az eredményt kell kapnunk. Megköveteljük tehát, hogy a kettőnél több tagot tartalmazó kifejezések tetszőlegesen "átzárójelezhetőek" legyenek. Ezt a műveleti tulajdonságot fogalmazza meg általánosságban a most következő definíció.

Kérdésünk tehát, hogy vajon a természetes számok összeadása teljesíti-e ezt a kritériumot is? Most megmutatjuk, hogy igen, méghozzá ugyancsak a 11.1. Definícióban szereplő Peano-axiómarendszer logikai következményeként.

Látható tehát, hogy a természetes számok összeadása azon kívül, hogy kommutatív, teljesíti az asszociativitást is, ahogy azt az általános iskolában már megszokhattuk tőle.

Megjegyezzük ugyanakkor, hogy a fentiekben a kommutativitást csak kéttagú, míg az asszociativitást csak háromtagú összegekre bizonyítottuk. Nem jelent túl nagy kihívást azonban annak igazolása sem, hogy tetszőleges számú tagból álló összegek is hasonló tulajdonságokkal rendelkeznek. Sőt, általánosságban érvényes az alábbi állítás.