Cím: Axiómarendszerekről
Szerző(k):  Urbán János 
Füzet: 1993/október, 289 - 293. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Kezdjük egy feladattal. Egy város autóbuszhálózatát kell megtervezni a következő feltételekkel:

a)minden megállóból minden megállóba átszállás nélkül el lehessen jutni;
b)bármely két (különböző) autóbuszvonalnak pontosan egy közös megállója legyen;
c)minden autóbuszvonalon 3 megálló legyen;
d)a városban legalább 4 megálló legyen.
Meg lehet-e tervezni ezt az autóbuszhálózatot?
Jelöljük a megállókat nagybetűkkel: A,B,C,..., a vonalakat pozitív egész számokkal: 1, 2, 3, .... Ekkor ‐ némi töprengés után ‐ például a következő táblázatot állíthatjuk össze:
 
 

A táblázatban pontok jelzik, hogy a megfelelő autóbuszvonalon milyen megállók vannak. Az autóbuszvonalakról az ábrán látható vázlatos térképet rajzolhatjuk meg.
 
 

ábra
 

Kézenfekvő hasonlatnak tűnik azt mondani, hogy itt egyfajta "geometriát'' konstruáltunk. A megállók a "pontok'', az autóbuszvonalak az "egyenesek''. Ezen a "síkon'' összesen 7 "pont'' és 7 "egyenes'' van. Az így megadott "pontokból'' és "egyenesekből'' álló rendszert véges projektív síknak nevezik.
Itt 3-adrendű véges projektív síkot konstruáltunk meg. Igazolható, hogy ha adott n-hez (az egy egyenesen lévő pontok számához) van a feltételeket kielégítő véges projektív sík, akkor ezen a pontok száma is és az egyenesek száma is n(n-1)+1. Azt sejtik, hogy olyan n-ekre van véges n-edrendű projektív sík, amelyekre n-1 prímhatvány.
Végül is azt kell kérdeznünk, mit értünk azon, hogy pont, egyenes, sík? Erre kétféle választ adhatunk. Vagy bizonyos matematikai objektumokat adunk meg, ezekről állítjuk, majd igazoljuk, hogy eleget tesznek a megszokott, ismert tulajdonságoknak.
Vagy bizonyos alaptulajdonságokat, összefüggéseket ‐ röviden axiómákat ‐ sorolunk fel, és azt mondjuk, hogy mindazokat ‐ a bármiféle objektumokat ‐ pontnak, egyenesnek, síknak nevezzük, amelyek kielégítik a felsorolt axiómákat, azaz a megadott axiómarendszert.
Vizsgáljuk meg ezt a kérdést egy egyszerűbb példán, a természetes számok példáján. Először megadjuk a természetes számok aritmetikájának Peano-féle axióma-rendszerét.
Alapfogalomként használjuk a "természetes szám'', a "0'', a "rákövetkezés'' (számlálás) egyváltozós műveletet, jelöljük x rákövetkezőjét x'-vel.
Használjuk természetesen az =-et, mint logikai fogalmat is.
Az axiómák a következők:
P1. A 0 természetes szám.
P2. Ha x természetes szám, akkor x' is az.
P3. Ha x'=y', akkor x=y.
P4. Ha x természetes szám, akkor 0≠x'
P5. (A teljes indukció axiómája.) Ha a 0-ra igaz egy T tulajdonság, és abból, hogy az x természetes számra igaz T, következik, hogy x'-re is igaz a T, akkor minden természetes számra igaz a T tulajdonság.
 

Ezt az axiómarendszert még ki kell egészíteni az összeadás és a szorzás rekurzív definíciójával, hogy a természetes számok szokásos aritmetikáját fel tudjuk belőle építeni:
P6. x+0=x,x+y'=(x+y)'.
P7. x⋅0=0,x⋅y'=x⋅y+x.
 

Azt mondhatjuk ezek alapján, hogy a természetes számok halmazának és a rajta értelmezett '; +; ⋅ műveleteknek nevezünk minden olyan halmazt és a halmazon értelmezett műveleteket, amely kielégíti a felsorolt axiómákat, azaz a Peano-féle axiómarendszert. Egy ilyen halmazt a rajta értelmezett műveletekkel az axiómarendszer egy modelljének nevezzük. Lássunk egy példát a Peano axiómarendszer modelljére.
Kiindulunk az üres halmazból: ∅, ez legyen a 0. A rákövetkezés műveletét a következő módon értelmezzük: x'=x∪{x}. Így például
1=0'=0∪{0}=∅∪{∅}={∅};2=1'=1∪{1}={∅}∪{{∅}}={∅,{∅}};3=2'=2∪{2}={∅,{∅}}∪{{∅,{∅}}}={∅,{∅},{∅,{∅}}}stb.

Nem nehéz igazolni, hogy az így megadott halmaz ‐ a 0-val és a rákövetkezés műveletével ‐ eleget tesz a Peano axiómarendszernek, röviden modellje annak.
Így tehát arra a kérdésre, hogy mit értünk természetes számokon, azt a választ adhatjuk, ‐ a Peano axiómarendszer modelljét.
Milyen tulajdonságokat várunk el egy axiómarendszertől?
(1) Ellentmondástalan legyen, azaz ne lehessen bizonyítani (levezetni) az axiómákból egy állítást és a tagadását is.
(2) Teljes (kategorikus) legyen, azaz bármely olyan állítás, amely megfogalmazható az axiómarendszerben, el is dönthető, azaz vagy az állítás, vagy a tagadása bizonyítható.
(3) Bizonyos típusú axiómarendszerekkel szemben ‐ mint például a természetes számok aritmetikájának axiómarendszere vagy az elemi geometria axiómarendszere ‐ elvárás volt az is, hogy bizonyos értelemben egyértelműen jellemezze a szóban forgó területet. Az axiómarendszer bármely két modellje azonos szerkezetű legyen, algebrai terminológiával: bármely két modell izomorf legyen. Ezt a tulajdonságát egy axiómarendszernek úgy hívják, hogy az axiómarendszer monomorf.
(4) Bizonyos értelemben "gazdaságossági'', illetve esztétikai követelményt jelent az, hogy elvárjuk: az egyes axiómák függetlenek legyenek a többitől, azaz ne legyenek levezethetők belőlük. Ha egy axiómarendszerre ez tejesül, akkor azt mondjuk, hogy az axiómarendszer független.
 

Tekintsük át röviden azokat a legfontosabb eredményeket, amelyek az axióma-rendszerekkel szemben támasztott (1)‐(4) követelményekkel kapcsolatban az utóbbi évszázadban sikerült bizonyítani.
A legrégibb axiómarendszerekkel kapcsolatos probléma, a geometria Euklidesz-féle axiómarendszerében a párhuzamossági axióma függetlenségének kérdése. Annak bizonyítása, hogy a párhuzamossági axióma független a többi axiómától, Bolyai János korszakalkotó munkásságára támaszkodva először az olasz Beltraminak sikerült 1868-ban. Azóta a függetlenség kérdése sok más axiómarendszerben is kérdéses volt, így például a halmazelmélet axiómarendszerében. E téren a közelmúltban is (30 éve) lényeges, új eredmények születtek.
A monomorfizmus kérdésével kapcsolatban még a század húszas éveiben meg-született a negatív eredmény: a Löwenheim ‐ Skolem-tétel azt mondja ki, hogy minden "érdekes'' axiómarendszernek vannak nem izomorf modelljei.
A teljesség kérdésével kissé részletesebben foglalkozunk. Itt 1930-ban Gödel (akkor) fiatal és (akkor) osztrák matematikus ért el meglepő negatív eredményt. Megmutatta, hogy minden "elég kifejező'' axiómarendszer ‐ ilyen például az aritmetika Peano féle, vagy a halmazelmélet axiómarendszere ‐ nem teljes.
Gödel bizonyításának alapgondolatát a Peano axiómarendszer példáján mutatjuk be.
Először arra van szükség, hogy egészen pontosan megfogalmazzuk azt az Lp nyelvet, amin az axiómarendszer axiómáit, állításait meg lehet fogalmazni.
Szükség van változójelekre (pl.: x1,x2,...,xn,...); egy konstans jelre: 0; függvényjelekre: ' egyváltozós, + és ⋅ kétváltozós; az = relációjelre és logikai jelekre: ¬ (nem), ∧ (és), ∨ (vagy), → (ha, ... akkor), ↔ (akkor és csak akkor), ∀ (minden), ∃ (van olyan). Néhány "írásjelre'', ún. segédjelekre is szükség van: ( (kezdőzárójel), ) (végzárójel) és , (vessző).
Ezekből a jelekből ‐ pontosan rögzített szabályok alapján ‐ értelmes jelsorozatokat készíthetünk. Részben természetes számokat jelölhetnek ‐ ezek a kifejezések, részben állításokat jelölhetnek ‐ ezek a formulák. Kifejezések például: x'1;(x1+x2)⋅x3; formulák például: x1=x2,¬(x'1=0); stb.
Elvileg érdekes és a bizonyítás szempontjából lényeges, hogy ezen a nyelven az aritmetika minden állítása megfogalmazható.
Gyakorlásként érdemes az axiómákat megfogalmazni ezen a pontosan körülhatárolt nyelven.
Miután a természetes számokról szóló állításokat megfogalmaztuk, azt kell megmondanunk, mikor mondjuk egy ilyen állításról, hogy igaz. Nyilván akkor tekintjük igaznak az állítást, ha az axiómarendszer minden modelljében igaz az állítás. Ezeket az igaz állításokat az axiómarendszer tételeinek nevezzük.
Érdekes és fontos tény, hogy a tételek halmazát más módon is jellemezhetjük. Gödel még 1930-ban megmutatta, hogy megadható véges sok típusú olyan logikai alapigazság, ún. logikai axióma, és néhány egyszerű levezetési szabály, amelyekre igaz, hogy a logikai axiómákból meg a Peano axiómákból a levezetési szabályok véges sokszor történő alkalmazásával előállítható formulák halmaza megegyezik a tételek halmazával.
Ezek után már áttérhetünk Gödel nem-teljességi tétele bizonyításának alapgondolatára. Gödel egyik alapvető ötlete az volt, hogy a formulákat, kifejezéseket, levezetéseket természetes számokká kódolta. Így az olyan állítások, mint "egy jelsorozat'', "axióma'' vagy "tétel'' stb. természetes számokról szóló állításokká váltak, tehát ezek is az axiómarendszer egy-egy formulájával írhatók le. Így a rendszer bizonyos formulái kettős jelentésűek. Egyrészt egy "ártalmatlan'' számelméleti állítást jelentenek, másrészt a kódoláson át a rendszerről szóló állítás is kiolvasható belőlük.
Ezek alapján Gödelnek egy újabb szép ötlettel, az ún. átlós módszerrel sikerült olyan φ formulát konstruálni, amelynek a jelentése a következő:
 

"A φ formula nem bizonyítható.''
 

Most már látható, hogy ez a φ állítás nem dönthető el az axiómarendszerben. Hiszen tegyük fel, hogy φ bizonyítható. Ekkor φ igaz, de ez azt jelenti, hogy φ nem bizonyítható, tehát ellentmondásra jutottunk.
Tegyük fel, hogy a ¬φ formula bizonyítható. Ekkor ¬φ igaz, tehát φ hamis, azaz φ bizonyítható, ami ismét ellentmondás.
A φ formula által megfogalmazott állítás tehát nem dönthető el az axiómarendszerben, azaz az axiómarendszer nem teljes. Természetesen a bizonyításban fel kell használni azt a feltételt, hogy az axiómarendszer ellentmondásmentes. (A logika eszközeivel könnyen belátható, hogy egy ellentmondásos axiómarendszerben bármely állítás és annak tagadása is "bizonyítható'', tehát az axiómarendszer használhatatlan.)
 

Gödel tételének ismertté válása után hamarosan kiderült, hogy azokban az axiómarendszerekben, amelyekre a tétel érvényes, magát az illető axiómarendszer ellentmondástalanságát is meg lehet fogalmazni, de nem lehet bizonyítani. Ennek következményeként adódott, hogy a szóban forgó axiómarendszerek ellentmondástalanságának bizonyítása elég reménytelen eset. Például a Peano axiómarendszer ellentmondástalanságát az 1930-as években Gentzennek sikerült igazolni, de a bizonyításban elég erős halmazelméleti eszközöket használt. Lényegében azt mondhatjuk, feltételezte, hogy a halmazelmélet ellentmondástalan. Magának a halmazelméletnek az ellentmondástalanságát ‐ ma úgy tűnik ‐ reménytelen bizonyítani.
Az axiómarendszerekkel kapcsolatos elméleti vizsgálatok "melléktermékeként'' több, ma már önálló, fontos matematikai tudományág is született. Ilyen például az algoritmuselmélet, amely a szabatosan definiált "kiszámíthatóság'' fogalmának tulajdonságait vizsgálja.
Befejezésként egy erről a területről származó, viszonylag friss eredményt is érdemes elmondani.
Még Hilbert, 1900-ban fogalmazta meg a következő kérdést: van-e olyan algoritmus, amely bármely egész-együtthatós akárhány-változós polinomról eldönti, hogy van-e egész gyöke.
A nemleges választ több előzetes, lényeges eredményre támaszkodva 1972-ben Matijaszevics fiatal orosz matematikus adta meg. Matijaszevics módszerének mintegy "melléktermékeként'' kiderült az a meglepő eredmény, hogy van olyan egész-együtthatós polinom, amelynek a pozitív egész helyeken vett helyettesítési értékeinek halmaza azonos a prímszámok halmazával. Igaz, ez a polinom 26-változós és 25-ödfokú, tehát a gyakorlat számára nem használható. (l. J. I. Manyin: Bevezetés a kiszámíthatóság matematikai elméletébe, Műszaki Kiadó, 1986. 77. oldal.)