Cím: Ellentmondásos-e a matematika?
Szerző(k):  Úry László 
Füzet: 1976/május, 194 - 205. 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.

Ezt a cikket azoknak az olvasóinknak ajánljuk, akik nem sajnálják a fáradságot, hogy a matematika egy igen fontos, de fiatal ágával megismerkedjenek. Témája nem kapcsolódik szorosan a középiskolai tananyaghoz, de a benne szereplő tételek ismerete az egész matematika épületébe ad betekintést. A cikk nem könnyű olvasmány, nagy figyelmet igényel, a dolog természeténél fogva a benne szereplő fogalmak igen absztraktak. A hosszú nyári szünet alatt biztosan sok olvasónk veszi majd a fáradságot, hogy alaposan elmélyedjen a cikkben, megpróbálja a benne szereplő feladatokat megoldani. Akinek kedve van, megoldásait beküldheti a szerkesztőség címére (1443 Budapest, Postafiók 129). Ezeket a megoldásokat a cikk írója értékeli. Ha a téma megnyerte olvasóink tetszését, egy későbbi számunkban folytatjuk.
Várjuk Olvasóink hozzászólásait, megjegyzéseit.
A szerkesztőség

 

Bevezetés
 

A matematika történetében akadtak válságos időszakok, melyekben a felmerülő problémák a korabeli matematika alappilléreit érintették, s így összedőléssel fenyegették a matematika egész épületét. Például a görögöket úgy ismerjük, mint a derűs alkotás mestereit. Amikor azonban a pithagóreusok felfedezték a 2 irracionalitását ‐ vagyis azt, hogy a négyzet átlója összemérhetetlen az oldalával ‐, ezt sokáig titkolták. Ebben a tényben a világ harmóniájának megbomlását látták, és attól féltek, ha nyilvánosságra kerül, az a társadalom harmóniáját is veszélyeztetné.
Legutóbb a századfordulón bukkantak fel a matematikában olyan ellentmondások, melyek nagyon sok, eddig biztosnak és tisztázottnak érzett fogalmat tettek kérdésessé: egyáltalán mit értünk definíción, tételen, állításon? Hogyan láthatjuk be, hogy axiómáink nem tartalmaznak ellentmondást? Van-e olyan matematikai állítás, amit nem azért nem tudunk sem bizonyítani, sem cáfolni, mert ügyetlenek vagyunk, hanem mert egyáltalán nem is lehet se cáfolni, se bizonyítani? Míg az eddigi problémákat jól jellemezheti egy ilyen kérdés: "Mit jelent a -1 ?'', addig most már az volt a kérdés, mi is a matematika?
A káoszból és zűrzavarból a matematika két fiatal ága született: az axiomatikus halmazelmélet és a matematikai logika. Az első megoldási kísérlet D. Hilberttől (1862-1943) és B. Russeltől (1872-1970) származik. Nagyon sok kiváló matematikus kapcsolódott be a kutatásokba, hozott létre maradandó eredményeket. Nekünk magyaroknak sincs szégyellnivalónk, gondoljunk csak Neumann Jánosra, Kőnig Gyulára vagy a ma élők közül Péter Rózsára, Kalmár Lászlóra, Hajnal Andrásra.
Hogy jobban tudjunk a témakörben tájékozódni, a felbukkant ellentmondások közül bemutatunk kettőt, elsőnek a Russel-féle antinómiát. Halmazon akkoriban bizonyos tulajdonságú dolgok összességét értették, szerintük halmazt alkotnak a magyar ábécé betűi, a Budapesten tanuló diákok, vagy azok a dolgok, amiket Trurl mérnök gépe akkor tüntetett el, amikor Klapanciusz elhamarkodottan a Semmit csináltatta meg vele. Ha az X halmaznak az Y dolog eleme, akkor ezt így írjuk: Y∈X. Jelölje H az összes halmazok halmazát. Mivel H halmaz, így H∈H. Tehát vannak olyan halmazok, amelyek elemként tartalmazzák önmagukat, és persze olyanok is, amelyek nem. Az utóbbiakat nem tartalmazkodó halmazoknak hívjuk. Jelölje R az összes nem tartalmazkodó halmazok halmazát. Vajon R eleme-e önmagának? Ha igen, akkor R nem tartalmazkodó, tehát nem eleme önmagának. Így csak az lehet, hogy R nem tartalmazkodó halmaz, akkor viszont eleme önmagának, hiszen R az összes nem tartalmazkodó halmazt elemként tartalmazza, s így megint csak ellentmondást kapnánk. Így arra a képtelenségre jutottunk, hogy nem tudjuk megmondani pontosan, milyen elemekből áll az R halmaz.
Példánk jól mutatja, hogy precízebben meg kellene mondanunk, milyen tulajdonság alapján sorolhatunk különböző dolgokat egyetlen halmazba. Egyáltalán, pontosabban meg kellene mondanunk, mit értünk azon a szón: "tulajdonság'', és mit azon, hogy "dolog''.
Második példánk még egyszerűbb. Vajon igaz-e vagy sem a következő állítás: ,,hazudok''? Ha igaz, akkor hazudok, tehát nem mondtam igazat. Így annak, amit mondtam, épp az ellenkezője igaz, azaz nem hazudok, hanem igazat mondok. A kör ezzel bezárult, erről a nagyon egyszerű állításról képtelenek vagyunk eldönteni, igaz-e vagy hamis. Ebből mindenesetre arra következtethetünk, hogy alaposabban meg kellene vizsgálnunk, mit is értünk azon, hegy egy állítás igaz vagy hamis, és azt is, mit tekinthetünk állításnak.
Ennek a cikknek az a célja, hogy képet adjon a felvetett kérdések, ellentmondások megoldásának matematikai útjáról. Bemutassa, hogy milyen módszerekkel és fogalmakkal dolgozik a matematikai logika, a matematika önismereti tudománya.
Nagyon kevés dolgot bizonyítunk, éppen csak a legkönnyebbeket. Ezzel szemben nagyon sok új fogalommal ismerkedünk meg, amiket az áttekinthetőség kedvéért a cikk végén felsorolunk.
 

Matematikai struktúrák

 

A matematikusok nagyon furcsa szemüvegen át nézik a világot. Vizsgáljunk például egy népes családot. Itt a bíró egy esetleges válóperes tárgyalást, az orvos szív- és bélműködést, a szociológus jó vagy rossz lakáshelyzetet lát, mindenkit valami más érdekel. Mit láthat és mit vizsgálhat itt a matematikus? Nem sokat, csak annyit lát, hogy valaki valakinek az apja, hogy valaki megint más valakinek a házastársa. Elfelejtkezik arról, hogy a családanya szőke, kék a szeme, itt és itt dolgozik, hogy hány kiló, csupán csak viszonyokat, relációkat vizsgál: két ember egy bizonyos viszonyban áll egymással, nevezetesen férj és feleség. Ellenvetésként bárki mondhatja, hogy a matematika számokkal foglalkozik leginkább, s így a család életkorának változását épp úgy látja, mint a szociológus. Ez igaz, de később látni fogjuk, hogy a számok relációk segítségével kifejezhetők. Egy egyszerű példával megvilágítjuk, hogy ez nem is olyan távoli szemléletünktől. A labdarúgóidény végével az újságok megírják, ki lett az  első, a második, a tizedik. Ehelyett azonban teljesen elegendő lenne azt a relációt megadni, amelyik megmutatja, melyik csapat kit előzött meg.
 

Definíció:
 

Individuumtartományon elemek, dolgok bizonyos összességét értjük.
A matematikusok vizsgálódási körébe különböző individuumtartományok tartoznak. A geometriában például ez a sík pontjainak és egyeneseinek összessége, az algebrában például a valós számok.
 

Legyen A egy individuumtartomány. A-beli rendezett n-esen az A-nak n darab elemét értjük, meghatározott sorrendben. A rendezett 2-est másképpen rendezett párnak hívjuk. Ez a fogalom már ismert a koordinátageometriából, ahol a sík és a tér pontjait valós számokból álló rendezett párokkal, illetve hármasokkal írjuk le. A sík egy pontja például (14, ‐ 5), a téré pedig (1, ‐ 3, 0). Az elemek sorrendje lényeges, a (14, ‐ 5) és a ( ‐ 5, 14) pontok nem azonosak.
Az A-beli rendezett n-esek halmazát nA-val jelöljük.
 

Definíció:
 

Egy A-n értelmezett n-változós M műveleten egy olyan megfeleltetést értünk, amely nA minden eleméhez hozzárendeli A egy elemét.
 

Az M műveletet A tetszőlegesen választott n elemére alkalmazva A egy újabb elemét kapjuk. Műveletek például az összeadás és a szorzás, ha individuumtartománynak R-t, a valós számok halmazát választjuk. Nem művelet R-n az osztás, ugyanis az (x,0) párnak nem felel meg semmi. Ezen kétféleképpen is segíthetünk: vagy individuumtartománynak R-{0}-t választjuk (a valós számok halmazából elhagyva az egyetlen 0 számot), vagy x/0-t 0-nak definiáljuk. Az így kapott osztások már műveletek. Négy változós művelet R-n a min (x,y,z,u ). De művelet az is, ha egy színházban ülő emberek mindegyikéhez hozzárendeljük a hozzá legközelebb ülő, tőle különböző embert. Itt az individuumtartomány a színházban ülő emberek összessége, a szóban forgó művelet egyváltozós.
 

1. feladat. Jelölje E a ma élő, Eϑ pedig a valaha élt emberek összességét. A az a hozzárendelés, amelyik mindenkinek megfelelteti az anyját. Az E és Eϑ individuumtartományok melyikén lesz A művelet és melyiken nem?
 

Definíció:
 

Egy A-n értelmezett n-változós P reláció nA egy részhalmaza.
 

Kicsit részletesebben ez azt jelenti, hogy A minden rendezett n-eséről el tudom dönteni, hogy az adott sorrendben eleme-e P-nek vagy sem, P relációban állnak-e vagy sem. Ismert reláció például N-n, a természetes számok halmazán a "kisebb'' kétváltozós reláció. E-n, a ma élő emberek halmazán egy kétváltozós reláció az "idősebb'' vagy az a H reláció, ami azt jelenti, hogy "házastársak''.
 

Definíció:
 

Egy A-beli C konstanson A egy kitüntetett elemét értjük.
 

A "konstans'' szót gyakran a "szám'' szinonimájaként használjuk, itt azonban eredeti "állandó'' értelmében szerepel. Például c-beli konstans "a szerző édesanyja''.
 

Definíció:
 

Egy A=(A;M1,...,Mp;P1,...,Pq;C1,...,Cs) struktúra áll
 

(i)111az A nem üres individuumtartományból,
(ii)11A-n értelmezett véges sok ( p darab) M1,M2,...,Mp műveletből,
(iii)1A-n értelmezett véges sok ( q darab) P1,P2,...,Pq relációból és
(iv)1A-beli véges sok ( s darab) C1,C2,...,Cs konstansból.
 

A matematikus feladata a különböző struktúrák vizsgálata. Számára mindegy, hogy az individuumtartomány elemei számok, emberek, csavarok, vagy dugóhúzók, érdeklődése a relációk és műveletek felé fordul.
A matematikai struktúra fogalmát a legabsztraktabb, tehát legegyszerűbb formájában fogalmaztuk meg. Célunk ugyanis nem az, hogy egyes matematikai feladatokat oldjunk meg, hanem az összes lehetséges feladatok szerkezetét tanulmányozzuk. Minél kevesebb eszközt engedünk meg a feladatok megfogalmazására, annál könnyebben tudjuk szerkezetüket leírni.
 

2. feladat. Legyen G a geometria struktúrája, W pedig a vektorok struktúrája. Milyen relációkból, műveletekből és konstansokból állnak? Mi az individuumtartományuk?
 

3. feladat. Adjunk meg E-n minél több műveletet! Törekedjünk arra, hogy ezek ne legyenek légbőlkapottak! Mit mondhatunk arról a hozzárendelésről, ami minden emberhez a nevét rendeli?
 

Matematikai nyelvek felépítése

 

Az előző részben említett műveleteknek, relációknak vannak lényeges, meghatározó jegyei. Például az összeadás kommutatív, H pedig szimmetrikus. Feladatunk nehézsége éppen abban áll, hogy ezekről a tulajdonságokról beszélni tudjunk, értelmes állításokat mondhassunk ki struktúránkban. Természetesen eddig is beszéltünk róluk, csakhogy a beszélt nyelv túlságosan sok kétértelműséget rejt magában. Első feladatunk így olyan mesterséges nyelv létrehozása, amelyik lehetőség szerint minden kétértelműséget kizár. Erre a célra nem egyetlen nyelvet, hanem nyelvek egész családját konstruáljuk meg, s ezeket matematikai nyelveknek nevezzük. Különböző struktúrabeli állításokat ezeknek a nyelveknek valamelyikén fogjuk felírni.
Először is meg kell adnunk az ilyen nyelvek ábécéjét, s azokat a szabályokat, amelyek segítségével felépíthetjük mesterséges nyelvünk mondatait, melyeket itt formuláknak hívunk. Kezdjünk hozzá a munkához!
Nézzük például a következő, az (N,+,1 ) struktúráról szóló állítást: "Tetszőleges x természetes szám nagyobb vagy egyenlő, mint 1.'' Az "x'' jel itt nem egyetlen természetes számot jelent, tetszésünk szerint akármelyik lehet, az összeset, az egészet képviseli, mintegy végigfut a természetes számokon. Nyelvünknek szüksége lesz ilyen jelekre.
(A) Nyelvünk tartalmazza az x1,x2,...,xn,... változójeleket.
Végtelen sok változójel van, s hogy meg tudjuk különböztetni őket egymástól, indexeltük őket. Esetenként más betűket is használhatunk változójeleknek, fontos csak az, hegy tudjuk, ezek változójelek. (Mindegy, hegy az "a'' betűt milyen típussal szedik ki, lényeges, hogy felismerjük, ez "a'' betű.)
Ez azonban még kevés. Struktúráink az individuumtartományon kívül műveletekből, konstansokból, relációkból állanak. Ezeknek a matematikai objektumoknak a leírására különböző jeleket vezetünk be.
(B) Nyelvünk tartalmazhat véges sok f1,f2,...,fp műveletjelet. Minden műveletjelről tudnunk kell egyben, hogy hányváltozós műveletet reprezentál. Ha például f az összeadásnak felel meg, akkor kétváltozós műveletjel. Azokat a jeleket, amelyekre a műveletjel vonatkozik, rendszerint a műveletjel után zárójelbe téve soroljuk fel. Szokás azonban a hagyományos műveletjelek esetén például f(x,y) helyett (x+y)-t írni. A műveletjelek szigorúan elkülönülnek egymástól, a + és a ⋅ nem cserélhető össze. Az érthetőség és rövidség kedvéért az fi-k helyett gyakran használunk más jeleket is műveletjelnek, de mindig tudni fogjuk, ezek itt műveletjelek.
(C) Nyelvünk tartalmazhat véges sok k1,k2...,ks konstansjelet.
A konstansjelek, a műveletjelekhez hasonlóan, nem feltétlenül a nyelv tartozékai. Lehet hogy csak néhány van belőlük, de akár teljesen el is maradhatnak. A konstansjelek írására is használunk néha más jeleket.
(D) Nyelvünk tartalmazhat véges sok r1,r2,...,rq relációjelet.
Minden relációjelhez, ugyanúgy mint a műveletjelekhez, hozzárendelünk egy számot, amely megmutatja, hegy hányváltozós relációjelről van szó. Csakúgy, mint a műveletjeleknél, a relációjel után téve zárójelben soroljuk fel azokat a jeleket amire a relációjel vonatkozik. Például ha r6 az egyenlőség relációjele, akkor kétváltozós és szokás szerint r6(x,y) helyett x=y-t írunk.
(E) Nyelvünk tartalmazza az ^ ( = és), ∨ (= vagy), → ( = ha ... akkor), ¬ (= nem), ∀ (= minden egyes), ∃ ( = van olyan) logikai jeleket.
Később ezek segítségével fogjuk felépíteni állításainkat, akkor részletezzük ezek jelentését.
 

Definíció:
 

Egy L matematikai nyelv az (A)‐(E) pontokban felsorolt jelekből és zárójelekből áll.
 

A matematikai nyelvek jelölésére meghonosodott L betű az angol language = nyelv szó kezdőbetűjéből származik.
Nyelvünk állandó alkotói a változó- és logikai jelek, illetve a különböző fajta zárójelek. Így a nyelv megadásához elegendő művelet-, reláció- és konstansjeleinek a felsorolása. Ha például azt mondjuk, hogy a halmazelmélet nyelve mindössze két darab kétváltozós relációjelből áll (az = és ∈ relációjelekből); akkor ezen azt értjük, hegy a nyelv állandó alkotóin kívül mindössze ezt a két jelet tartalmazza. Bonyolultabb a természetes számok nyelve, amely egy darab egyváltozós és két darab kétváltozós műveletjelből (' a rákövetkezés ‐ azaz eggyel növelés ‐, a + és a ⋅ jelek), egy kétváltozós relációjelből (= ) és egy konstansjelből (1) áll.
 

Definíció:
 

(i) Tetszőleges xi változójel illetve tetszőleges ki konstansjel kifejezés.
(ii) Ha t1,t2,...,tn kifejezések és fin-változós műveletjel, akkor fi (t1,t2,...,tn) is kifejezés.
(iii) Csak az (i) és (ii) véges sokszori alkalmazásával kapunk kifejezést.
 

Legyen például a + két változós műveletjel. Ekkor (x+y) és ((x+y)+z) kifejezés, de  +x nem, mert nem kapható meg (i) és (ii) véges sokszori alkalmazásával. Definíciónkban éppen azt fogalmaztuk meg, amit mindenki kifejezésnek tekint, így egy helyesen felírt egyenlet mindkét oldala kifejezés lesz, ha csak a nyelvben szereplő műveletjeleket használtunk fel.
Ennyi előkészítés után pontosan definiálhatjuk, mit is értünk formulán.
 

Definíció:
 

(i) Ha t1,t2,...,tn tetszőleges kifejezések, és ri tetszőleges n-változós relációjel, akkor r1(t1,t2,...,tn)formula.
(ii) Ha φ és ψ formulák, akkor a következők is azok:
 

(a) (¬φ)  (b)(φ∨ψ)(c)(φ^ψ) és (d) (φ→ψ).
 

(iii) Ha φ formula, akkor
 

(∀xiφ) és (∃xiφ) is formula.
 

(iv) Csak az (i)‐(iii)-ban leírtak véges sokszori alkalmazásával kapunk formulát.
 

Egy formulában adott helyen fellépő xi változójel szabadon fordul elő, ha nincs benne egyetlen ∀xi(...xj...), vagy pedig egy ∃xj(...xj...) alakú részformulában sem. Például a ∀x(x+y=1)^¬(x=y) formulában x első két előfordulása nem szabad, a harmadik pedig igen. A formula szabad változóinak nevezzük azokat a változókat, amelyek valahol szabadon fordulnak elő. A formula φ(x,...,y) alakjában x,...,y mindig a formula szabad változóit jelentik. Egy formula zárt, ha nincs benne szabad változó. A zárt formulákat mondatoknak is hívjuk.
Állításaink elemi állításokból épülnek fel logikai jelek segítségével. Ilyen elemi állítások például: "az ABC háromszög derékszögű'', "x tanuló'', "x országnak y a fővárosa'', "x=y'', "x maradék nélkül osztja y-t''. Az ilyen állítások egy dolog tulajdonságát vagy több dolog kapcsolatát fejezik ki. Az ilyen kapcsolatok leírását engedi meg a formulák definíciójának (i) pontja. Az elemi állításokból logikai úton más állításokat kaphatunk, ezt fejezi ki (ii) és (iii).
Egy példán illusztráljuk, hogyan lehet egy magyar nyelven felírt állítást átfordítani valamilyen matematikai nyelvre. Legyen a nyelv a természetes számok nyelve, az állítás pedig a következő:
"Végtelen sok prímszám van''.
Szerencsénkre a prímszámok fogalmát eleve a + és ⋅ műveletek segítségével definiáltuk, így könnyű dolgunk lesz. A "végtelen sok'' kifejezés helyett pedig majd azt fogalmazzuk meg, hogy tetszőleges természetes számnál van nagyobb prím. Először az állításnak könnyen formulázható részét írjuk fel:
∀x∃y(y  prím^y>x).
Az "y>x'' részformulát könnyen fordíthatjuk: ∃z(x+z=y). Mivel természetes számokról van csak szó, ez nyilván csak akkor lehet, ha y>x. Kicsit bonyolultabb azt felírni, hogy "y prím''. Egy természetes számról akkor mondjuk, hogy prím, ha nincs más osztója, csak önmaga és az 1. Az 1 számot, ami teljesíti ezt a tulajdonságot, nem tekintjük prímnek. Így az "y prím'' definíció szerint a következő:
∀z(z|y→(z=1∨z=y))^(y≠1).
"y≠1''-t könnyen fordítjuk: ¬(y=1). Ez már formula. Végül "z|y'' pontosan akkor, ha van olyan u szám, hogy u⋅z=y. Ezt fordítva: ∃u(u⋅z=y).
Így az "y prím'' a következőnek felel meg:
∀z(∃u(u⋅z=y)→(z=1∨z=y))^¬(y=1).(1)
Összefoglalva mindezt, eredeti állításunk fordítása a következő:
∀x∃y((∀z(∃u(u⋅z=y)→(z=1∨z=y))^¬(y=1))^∃z(x+z=y)).

Világos, hogy ez a formula gyakorlati célokra vajmi kevéssé használható. Nem is kell állításainkat ilyen alakra hoznunk. Abban kell csak biztosnak lennünk, hogy azok az állítások, amelyeket használunk, egyértelműen lefordíthatók nyelvünkre, ha jön valaki, aki kételkedik ebben, annak meg tudjuk mutatni. Így az "y prím'' kifejezést bátran használhatjuk, s ha valakinek ez nem felel meg, azt mondjuk: Vedd az (1) formulát, tedd mindenütt az "y prím'' helyébe, s amit így kapsz, az már neked is megfelelő formula lesz.
Formuláinkat sosem írjuk ki teljes részletességgel, de tudjuk, hogy ezt mindig megtehetjük.
 

4. feladat. Legyen L=(!,□,×,≡,?) a természetes számok nyelve, ahol a jelek rendre a rákövetkezés, összeadás, szorzás, egyenlőség és 1 jelei. Formulái-e az L nyelvnek a következő jelsorozatok:
 

(a) ∀x∃y(x□y>z)^∃y(y□?□?≡□),
 

(b) ∀x∃y(x□?≡z)∨∃x(y×z≡x),
 

(c) ∀y∃z((x□y)∨(x□z)≡u).
 

5. feladat. Döntsük el, hogy az alábbi formulák közül melyek zártak, melyek a bennük szabadon előforduló változók! x,y,z változójelek, φ(x),ψ(x,y,z),ϰ(x,y) formulák.
 

(a) φ(x)^∀x∃yψ(x,y,z),
 

(b) ∃z(ϰ(x,z)^∀x∃yϰ(x,y)^∀x∃yφ(x)),
 

(c) ∀x∃y∀z(φ(x)→ϰ(x,y)).
 

6. feladat. Legyen N egy egyváltozós relációjel, jelentése: "nőnek lenni''. H jelentése "x és y házastársak'', H kétváltozós relációjel. A G kétváltozós relációjel, jelentése "x gyermeke y-nak'', az első változója jelenti a gyereket. Ezek segítségével írjunk fel olyan formulákat, aminek jelentése rendre a következő:
 

(a)111 x anyja y-nak,
(b)111 mindenkinek van apja és anyja,
(c)111 x és y testvérek,
(d)111 x nagyapja y-nak,
(e)111 x és y unokatestvérek,
(f)111 mindenkinek egyetlen anyja van,
(g)111 x anyósa y-nak,
(h)111 a házastársak közül az egyik férfi, a másik nő.
 

7. feladat. Legyen R(x,y) egy kétváltozós relációjel. Mit jelentenek az alábbi formulák:
 

(a)111 ∀xR(x,x)^∀x∀y(R(x,y)∨R(y,x)),
 

(b)111 ∃x(∀yR(x,y)→R(x,x)),
 

(c)111 ∀x∀y∀z((R(x,y)^R(y,z)→R(x,z)).
 

8. feladat. Legyen H a sík háromszögeinek, Á pedig a budapesti állatkert lakóinak halmaza. Adjunk meg ezeken a halmazokon relációkat, műveleteket és konstansokat. Konstruáljunk olyan nyelveket, melyek ezek leírására alkalmasak.
 

Interpretációk

 

A matematikai nyelveket azért konstruáltuk meg, hogy ezen a nyelven beszélhessünk struktúráinkról. Egyelőre még semmilyen kapcsolat sincs nyelv és struktúra közt. Ezen úgy segíthetünk, hogy egy adott struktúra műveleteinek, relációinak és konstansainak egy-egy alkalmas jelet feleltetünk meg. Az ilyen típusú megfeleltetést hívjuk interpretációnak. A pontos definíció a következő.
 

Definíció:
 

Legyen A=(A;M1,...,Mp;P1,...,Pq;C1,...,Cs) tetszőleges struktúra, L=(f1,f2,...,fp;r1,...,rq;k1,...,ks) az A leírására alkalmas tetszőleges nyelv. Nézzük azt az I megfeleltetést, amelyik az L nyelv i-edik műveletjeléhez hozzárendeli A struktúra i-edik műveletét, I(fi)=Mi; az L nyelv j-edik relációjelének megfelelteti az Aj-edik relációját, I(rj)=Pj; végül az L nyelv l-edik konstans jelének az Al-edik konstansát rendeli, I(kl)=Cl. Ha úgy soroltuk fel nyelvünk jeleit, hogy a fenti megfeleltetés n-változós műveletjelekhez (illetve relációjelekhez) éppen n-változós műveleteket (relációkat) feleltet meg, akkor az I megfeleltetést az L nyelv A-beli interpretálásának nevezzük.
 

Nem szabad összekevernünk a jeleket a nekik megfeleltetett valódi objektumokkal. A jelek csak a fejünkben, a papíron léteznek, míg a nekik megfelelő relációk, műveletek a "valóság'' egy darabján, az A struktúrán hatnak. Természetesen jeleink igen szoros kapcsolatban állnak velük, hiszen azoknak mintegy a nevei.
Képzeljük, hogy adott egy t kifejezés, amelyben az x1,x2,...,xn változójelek szerepelnek, a1,a2,...,an pedig az A individuumtartomány adott jelei. Ha a t-ben szereplő művelet- és konstansjeleket A-beli interpretáltjukra cseréljük, az xi-k helyére rendre az ai-ket írjuk, s az így keletkező műveleteket végrehajtjuk, eredményül A egy elemét kapjuk. Ezt a t kifejezés a1,a2,...,an értékelésnél kapott értékének nevezzük. A pontos definíció a következő:
 

Definíció:
 

A t(x1,x2,...,xn) kifejezés értékét az a1,a2,...,an értékelés mellett a következőképpen kapjuk meg:
 

(i)100 Ha t=xi vagy t=kj, akkor értéke ai, illetve Cj.
(ii)110 Ha t=fi(t1,t2,...,tm) és tj-k értéke rendre bj, akkor t értéke
  Mi(b1,b2,...,bm)∈A.
 

A t(x1,x2,...,xn)-értékét t[a1,a2,...,an]-nel jelöljük. A kifejezés értéke mindig a megfelelő individuumtartomány eleme. Ha például A=(N,+,⋅),L=(f1,f2),I(f1)=+ és I(f2)=⋅; végül t(x1,x2)=f1(f1(f2(x1,x2),x2),x1), akkor t[1,2]=5. Ugyanis x1 értéke 1,x2 értéke 2,f2(x1,x2) értéke 1⋅2=2,f1(f2(x1,x2),x2) értéke 2+2=4, s így t értéke 4+1=5.
Első lépésben értékeket adtunk a változójeleknek, ezek segítségével kiszámítottuk a kifejezések értékét, most pedig definiálni fogjuk a formulák értékét. Ez az érték már nem A-beli érték lesz, hanem a formula az értékelés mellett vagy igaz vagy hamis.
Legyen φ(x1,x2,...,xn) az L nyelven felírt olyan formula, melynek szabad változói x1,x2,...,xn közül kerülnek ki. Legyenek még a1,a2,...,an az A elemei. Definiálni fogjuk, hogy mikor teljesül a φ(x1,x2,...,xn) formula A-n az (a1,a2,...,an)=a→ értékelés mellett, jelben:
A⊧φ(a1,...,an)vagyA⊧φ[a→].
Ugyanezt a tényt más szavakkal is kifejezhetjük: φ[a→] igaz A-n, A modell φ[a→]-ra.
 

 Definíció:
 

(i)111 Legyen φ=ri(t1,t2,...,tm) formula, a tj-k értékei rendre b1,b2,...,bm∈Aaz[a1,a2,...,an] értékelés mellett.
A⊧φ[a→] csak akkor, ha (b1,b2,...,bm)∈Pi, vagyis a (b1,b2,...,bm)m-es Pi relációban áll.
(ii)11 A⊧(¬φ)[a→] csakkor, ha nem igaz, hogy A⊧φ[a→];
  A⊧(φ^ψ)[a→] csakkor, ha A⊧φ[a→] és A⊧ψ[a→];
 A⊧(φ∨ψ)[a→] csakkor, ha A⊧φ[a→] vagyA⊧ψ[a→];
  A⊧(φ→ψ)[a→] csakkor, ha valahányszor A⊧φ[a→], akkor egyben
 A⊧φ[a→].
(iii)1 A⊧∀xiφ[a1,a2,...,an] csakkor, ha akárhogyan is választunk egy a∈A elemet, mindig
A⊧φ[a1,a2,...,ai-1,a,ai+1,...,an];
  A⊧∃xiφ[a1,a2,...,an] csakkor, ha van olyan a∈A, hogy A⊧φ[a1,a2,...,ai-1,a,ai+1,...,an].
Legyen megint A=(N,=,+,⋅,1) és L=(≡,□,×,?). Ekkor persze I(□)=+, I(×)=⋅,I(?)=1,I(≡)==. Vajon a φ(y)=¬∃x(□(x,y)≡□(?,?)) formula milyen értékelés mellett lesz igaz és milyen értékelés mellett lesz hamis, azaz n∈N esetén mikor lesz A⊧φ(n)? Végiggondolva az értékelés definícióját, rögtön látszik, hogy az a kérdés, van-e olyan m, hogy n+m=2. Mivel n és m természetes számok, ez csak n=m=1 esetben fordulhat elő. Ha tehát n>1, akkor semmilyen m természetes számra nem teljesül a □(x,y)=□(?,?) formula az (n,m) értékelés mellett, tehát ekkor A⊧φ(n). Ha viszont n=1, akkor a fenti formula igaz lesz az (1,1) értékelés mellett, tehát A nem modell φ(1) re. Így például A⊧∃yφ(y),deA⊭∀yφ(y).
Példánk azt is mutatja, hogy ha φ tartalmaz szabad változót, akkor az, hogy φ teljesül-e A-n vagy sem, ténylegesen függ az értékeléstől. Nem nehéz bizonyítani, hogy ha φ zárt, akkor tetszőleges értékelés mellett vagy teljesül vagy nem. Erre utal a következő tétel:
 

Tétel: Ha φ zárt formula, akkor A⊧φ és A⊧¬φ közül pontosan az egyik áll fenn, függetlenül az értékeléstől.
 

A matematikus úgy dolgozik, hogy a vizsgált struktúra néhány jellemző tulajdonságát, azaz a rajta igaz formulákat, állításokat kiemeli, ezeket axiómákként kezeli. Ebből következik, hogy vizsgálati körében már nemcsak az az egy struktúra áll, hanem az összes olyan struktúra, amely eleget tesz az axiómáknak.
Az alábbi definíció éppen ennek a precíz megfogalmazására szolgál.
 

Definíció:
 

Legyen Γ az L nyelven felírt formulák halmaza. Azt mondjuk, hogy A a Γ modellje, ha minden Γ-beli φ formulára A⊧φ teljesül. Jelben: A⊧Γ.
A φ formula a Γ formulahalmaz következménye, ha valahányszor egy A struktúrára A⊧Γ teljesül, akkor egyben A⊧φ. Ha φ a  Γ következménye, azt így írjuk: Γ⊧φ.
 

8. feladat. Konstruáljunk olyan A struktúrákat, ahol a következő formulák igazak, illetve hamisak! (Ez összesen hat struktúrát jelent.)
 

(a) 111 ∀x∃y∃z(P(x,y)^P(z,x));
 

(b)111 ∃x∀y(P(f(x),x)^P(y,x));
 

(c)111 ∀x∃y(G(x,y)^¬G(y,x)).
 

9. feladat. (Γ+φ) jelentse azoknak a formuláknak a halmazát, amelyeket úgy kapunk, hogy Γ formuláihoz hozzávesszük a φ formulát. Legyen φ zárt formula, s bizonyítsuk be, hogy ha (Γ+φ)⊧ψ, akkor Γ⊧φ→ψ.
 

10. feladat. Bizonyítsuk be, hogy a következő két formula tetszőleges struktúrán teljesül:
 

(a)111 (∀x1(∀x2φ))→(∀x2φ);
(b)111 ¬(φ→ψ)→(φ^¬ψ).
 

Levezetés és a teljességi tétel

 

Első pillantásra szinte lehetetlennek látszik azoknak a formuláknak a felsorolása, vagy valamilyen értelemben vett rendezése, amelyek minden olyan struktúrán teljesülnek, amely egy rögzített formulahalmazt, (axiómarendszert) kielégít. Ebben a részben a célunk egy ilyen eljárás megadása. Mint már a 10. feladatban is láttuk, vannak olyan formulák, amelyek tetszőleges struktúrán teljesülnek, ezeket logikailag igaz formuláknak nevezzük. Az igaz formulák közül néhánynak különleges és aránylag egyszerű szerkezete van.
Ezek például a következők:
 

(i)1111 φ→(ψ→φ);
 

(ii)111 (φ→(ψ→ϰ))→((φ)→ψ)→(φ→ϰ));
 

(iii)11 (¬ψ→¬φ)→((¬ψ→φ)→ψ);
 

(iv)11 ∀xiφ(xi)→φ(t), ahol t kifejezés,
 

(v)111 ∀xi(φ→ψ(xi))→(φ→∀xiψ(xi)) ahol φ-ben nem fordul elő szabadon xi.
 

Nem nehéz meggyőződnünk arról, hogy az (i) ‐(v) formulák mindegyike teljesül egy tetszőleges struktúrán, azaz igazak. Az (i) ‐ (v) típusú formulákat logikai axiómáknak nevezzük. Megjegyezzük, hogy minden pontban végtelen sok formulát soroltunk fel, így végtelen sok logikai axiómánk van, de ezek csak véges sok típusba tartoznak.
Olyan eljárásokat keresünk, melyek segítségével igaz formulákból újra igaz formulához jutunk. Ilyen eljárásokat mindenki jól ismer, aki matematikával foglalkozik, bizonyítási vagy következtetési szabályoknak hívjuk őket. Sok ilyet fel lehetne sorolni, de nekünk kettő is elegendő lesz. Az első a modus ponens, magyar nevén a leválasztási szabály. Ha két formulánk φ és  φ→ψ alakú, akkor a leválasztási szabály segítségével megkaphatjuk a ψ formulát. A másik az általánosítási szabály. Ha φ(xi) egy formula, akkor ennek a szabálynak a segítségével a ∀xiφ(xi) formulát kapjuk meg.
 

Definíció:
 

Legyen adva formuláknak egy Γ halmaza. Γ-ból történő levezetésnek nevezzük formulák egy véges φ1,φ2,...,φn sorozatát, ha mindegyikük vagy logikai axióma, vagy Γ eleme, vagy egy, illetve két, megelőző formulából származik az általánosító, illetve a leválasztó szabály segítségével. Egy φ formula levezethető Γ-ból, vagy más szóval a Γ tétele, ha van olyan φ1,φ2,...,φn levezetés Γ-ból, hogy φ=φn. Jelben Γ⊢φ. φ-t tautológiának nevezzük, ha levezethető az üres halmazból, azaz ⊢φ.
 

Definíciónkban a bizonyítás jól ismert fogalmát definiáltuk, tétel itt is pontosan az, ami bizonyos előfeltevésekből, axiómákból logikai szabályok segítségével megkapható. Egyszerű példa levezetésre a következő:
{φ,∀x1φ→ψ}⊢∀x1ψ.

A levezetés:φ1=φ      Γ elemeφ2=∀x1φφ1-ből általánosítássalφ3=∀x1φ→ψΓ elemeφ4=ψφ2 és φ3-ból leválasztássalφ5=∀x1ψφ4-ből általánosítással.   

 

A Γ-ból levezethető formulák szoros kapcsolatban állnak a Γ következményeivel. Aránylag könnyű annak a kimutatása, hogy ha φ és φ→ψ következményei Γ-nak, akkor egyben ψ is, és ha φ(xi) következménye Γ-nak, akkor egyben ∀xiφ(xi) is. Összevetve ezt azzal a ténnyel, hogy a logikai axiómák minden struktúrán teljesülnek, a következő tételt kapjuk:
 

Tétel: Ha Γ⊢φ, akkor egyben Γ⊧φ.
 

Természetszerűleg merül fel az a kérdés, hogy vajon fordítva nem igaz-e az állítás. A válaszadást segíti elő a következő definíció.
 

Definíció:
 

Γ konzisztens, ha van modellje, azaz ha van olyan A struktúra, hogy A⊧Γ. Γ ellentmondástalan, ha nem vezethető le belőle φ^¬φ alakú formula.
(A "konzisztens'' szó magyarra fordítva azt jelenti ugyan, hogy "ellentmondástalan'', de két teljesen különböző dolgot jelent a matematikában!!)
Például minden olyan Γ axiómarendszer, amelyiknek van modellje, ellentmondástalan. Ha ugyanis Γ⊢φ^¬φ, akkor erre a modellre az előző tétel szerint A⊧φ^¬φ, azaz A⊧φ és A⊧¬φ. De jól tudjuk, hogy ez utóbbi kettő közül legfeljebb az egyik teljesülhet. Ezért az üres axiómarendszer, amelyik így csak (!) a logikai axiómákból áll, ellentmondástalan, hiszen tetszőleges struktúra modell rá. Világos, hogy csak ellentmondástalan Γ-nak lehet modellje.
 

Tétel: Ha Γ ellentmondástalan, akkor van modellje, tehát konzisztens.. Ezzel ekvivalens, hogy ha φ a Γ következménye (Γ⊧φ), akkor egyben le is vezethető Γ-ból (Γ⊢φ), a levezetés és a következmény azonos fogalmak.
 

A fenti tételt Kurt Gödel német matematikus bizonyította be először 1930-ban, és Gödel-féle teljességi tétel néven ismert. (A bizonyítás igen nehéz és bonyolult.) A másik, a fenti tétellel ekvivalens megfogalmazás a következő:
 

Tétel: Ha φ nem vezethető le Γ-ból, akkor Γ-nak van olyan A modellje is, hogy még A⊧¬φ.
 

11. feladat. Bizonyítsuk be, hogy az utolsó két tétel állításai ekvivalensek!
 

Egy rövid táblázatban foglaltuk össze eddigi fogalmainkat. Gödel teljességi tétele szerint az egy sorban álló fogalmak azonosak:
 

Γ  ellentmondástalan     Γ  konzisztensΓ-ból levezethető  φ,Γ⊢φ Γ-ból következik  φ,Γ⊧φφ  tautológia,  ⊢φφ  igaz,  ⊧φ   

 

Lassan a végére jutottunk azoknak a pozitív eredményeknek, amelyek igazolják, hogy a matematikai nyelv és struktúra fogalmát jól definiáltuk. Ki tudtuk mutatni, hogy axiómarendszerünk hűen tükrözi összes modellünket. Ezen a kijelentésen azt értjük, hogy ha Γ konzisztens, akkor Γ következményei és a Γ-ból levezethető formulák megegyeznek. De ezen belül egyes konkrét modellek viselkedése nagyon különböző lehet, ugyanannak a Γ axiómarendszernek egyes modelljében ez vagy az a formula igaz vagy hamis lehet. Az ilyen állításokat Γ-tól függetlennek nevezzük. Egy Γ formula éppen akkor független Γ-tól, ha {Γ,q} és {Γ,¬q} egyaránt ellentmondástalan. Hogy vannak független állítások, az egyáltalán nem nyilvánvaló.
 

A természetes számok és a Gödel-féle nem-teljességi tétel

 

A matematika egyik leggyakrabban használt axiómarendszerét mutatjuk be, a természetes számok axiómarendszerét. A természetes számok tulajdonságait először Peano próbálta megfogalmazni. A matematikai logika, s különösen annak formalizmusa sokat köszönhet az ő tevékenységének. Az itt közölt T axiómarendszer a Peano-féle rendszer megfelelő változata.
A természetes számok nyelve egy darab egy változós, két darab kétváltozós műveletjelet tartalmaz: ezek a ' (a rákövetkezés jele), illetve a + és a ⋅ jelek, (amelyek az összeadás, és szorzás szokásos jelei). Csupán technikai okokból nem az egy, hanem a nulla számot tekintjük a legkisebb természetes számnak. Nyelvünk egyetlen konstansjele így a 0. Egyetlen kétváltozós relációjelünk az egyenlőség = jele. Tehát L=(',+,⋅,=,0).
Axiómáink, tehát T elemei a következők:
 

(T1) ∀x∀y∀z(x=y→(x=z→y=z))
(T2) ∀x∀y(x=y→x'=y')
(T3) ∀x¬(0=x')
(T4) ∀x∀y(x'=y'→x=y)
(T5) ∀x(x+0=x)
(T6) ∀x∀y(x+y'=(x+y)') (T7) ∀x(x⋅0=0)
(T8) ∀x∀y(x⋅y'=(x⋅y)+x)
(T9) φ(0)→(∀x(φ(x)→(x'))→∀xφ(x)).
 

A (T1)-(T8) axiómák az összeadás, szorzás és rákövetkezés jól ismert tulajdonságait formalizálják. A (T9) pontban nem egy axiómát adtunk meg, hanem végtelen sokat, a φ(x) formula minden lehetséges választására egyet-egyet. Az ilyen típusú axiómákat axiómasémának hívjuk. Az axiómasémákra a matematika minden területén szükség van. Már a logikai axiómák felsorolásakor használtuk őket.
A (T9) axiómaséma a teljes indukció átfogalmazása. Szokásos megfogalmazásban ez így hangzik:
,,Legyen K a természetes számok egyik tulajdonsága. Tegyük fel, hogy a nulla rendelkezik ezzel a tulajdonsággal és valahányszor egy természetes szám rendelkezik vele, akkor a rákövetkezője is. Ekkor valamennyi természetes szám rendelkezik a K tulajdonsággal''.
 

A problémát ebben a megfogalmazásban az okozza, mit értünk tulajdonságon. Mint mindenütt, itt is ez egy szabad változójú φ(x) formulát jelent. Egy n természetes szám rendelkezik a tulajdonsággal, ha ez a  φ[n] igaz, különben nem. Ezek után könnyen adódik a teljes indukció fenti, formalizált alakja.
A (T1)-(T9) pontokban felsorolt axiómák együtt adják a természetes számok T axiómarendszerét. Ahhoz, hogy tényleg jogunk legyen ezt a rendszert a természetes számok axiómarendszerének nevezni, meg kell mutatni, hogy a T segítségével fel tudjuk építeni az elemi aritmetikát: be tudjuk látni az összeadás és szorzás szokásos összefüggéseit, definiálhatjuk a különbséget stb. Ezt valóban meg lehet tenni, de mivel arra törekedtünk, hogy a lehető legkevesebb axiómát kelljen kimondanunk, ez nagyon soká tartana, és nem is ez a célunk.
Megemlítjük azonban a T axiómarendszerre vonatkozó nagyon fontos tételt, amit még egyetlen más bonyolultabb rendszerre sem sikerült bebizonyítani.
 

Tétel: (Gentzen, 1936). A természetes számok T axiómarendszerere ellentmondástalan.
Hogy megértsük ennek a tételnek a fontosságát, a modellelmélet még egy tételét említjük meg. Csak olyan axiómarendszerekre szorítkozunk, amelyekben véges sok lépésben el tudjuk dönteni egy tetszőleges formuláról, hogy axióma-e vagy sem. Ez az elvárás meglepőnek tűnhet, de sajnos vannak olyan dolgok, amiknek létezéséről tudunk, de a dolgot mégsem tudjuk teljes egészében megragadni. Így lehetséges, hogy valaki úgy adja meg az axiómákat, hogy nem tudjuk eldönteni, mi axióma és mi nem.
Másodszor feltesszük, hogy axiómarendszerünkben felépíthető a természetes számok aritmetikája. Világos, hogy ezekkel a tulajdonságokkal a matematikában használatos axiómarendszerek többsége rendelkezik. Az említett két tulajdonságnak eleget tevő axiómarendszert erősnek hívjuk. Ezekről szól a Gödel-féle nemteljességi tétel:
 

Tétel: Legyen Γ az L nyelven felírt ellentmondástalan, erős axiómarendszer. Ekkor van az L nyelvnek olyan (Cons Γ)-val jelölt formulája, ami azt fejezi ki, hagy a rendszer ellentmondástalan, de ez a formula független Γ-tól, tehát sem (Cons Γ), sem a tagadása nem vezethető le Γ-ból.
A tétel tehát rögtön példát is mutat egy független állításra minden erős axiómarendszerben. Ráadásul ezt az állítást nagyon is szeretnénk eldönteni, hiszen éppen azt fejezi ki, hogy a rendszer ellentmondástalan.
Ezzel befejeztük a matematikai logika egyik legfontosabb részterületének egy ugyancsak vázlatos és rövidre fogott áttekintését. A matematikai logika a matematika egyik határterülete, sok vonatkozásban kapcsolódik a logikához és a filozófiához. A kérdés iránt érdeklődők magyarul is sok érdekes könyvhöz juthatnak.
 

A cikkben előforduló jelölések és rövidítések

 

A       a struktúra individuumtartománya
A     tetszőleges struktúra A tetszőleges eleme
ai   A  tetszőleges eleme
   nA   A  rendezett  n-eseinek halmaza
a→   nA  egy eleme
A⊧Γ   A  modell a  Γ-ra
A⊧φ   A  modell a  φ-re tetszőleges értékelésnél
A⊧φ[a→]A  modell a  φ-re az  a→  értékelés mellett
Ci     tetszőleges konstans
E     a ma élő emberek összessége
Ev     a valaha élt emberek összessége
fi     műveletjel
G     a geometria struktúrája
H   "házastársaknak lenni''
I     interpretáció
i,j,l     indexek
k1     konstansjel
L     matematikai nyelv
Mi     művelet
Pj     reláció
p     a struktúra műveleteinek száma
rj     relációjel
q     a struktúra relációinak a száma
s     a struktúra konstansainak a száma
t     kifejezések rövidítése
T     a Peano-féle axiómarendszer
xi     változójel
y,z     változójelek
W     a vektorok struktúrája
Γ     formulák halmaza, axiómarendszer
Γ⊢φ   Γ-ból levezethető
{Γ,+φ}   Γ  formulái és a  φ  formula
'    a rákövetkezés jele
^     és
∨     vagy
¬     nem
→     ha, ... akkor
∀     minden egyes (az ún. univerzális kvantor)
∃     van olyan (az ún. egzisztenciális kvantor)
csakkor    akkor és csak akkor.  

 

A cikkben szereplő fogalmak és tételek

 


A-beli konstans      individuumtartományA-beli rendezett  n-esigaz formulaA-n értelmezett reláció  interpretáció  axiómarendszer    kifejezés  axiómaséma    konstansjel  általánosító szabály    konzisztens  ellentmondástalan    következmény  elsőrendű nyelv    leválasztási szabály  erős axiómarendszer    levezetés  értékelés    logikai axióma  formula    logikai jel  Gentzen tétele    matematikai logika  Gödel teljességi tétele    matematikai nyelv  Gödel nem-teljességi tétele    modell  mondat    rendezett pár  modus ponens    Russel-féle antinomia  művelet    struktúra  nyelv    szabad változó  Peano-féle axiómarendszer    tétel  reláció    tautológia  relációjel    változójel  rendezett  n-es    zárt formula  

 

Ajánlott irodalom:
 

Kalmár L.: A matematika alapjai II. ‐ Szeged, Egyetemi jegyzet.
Klaus, G.: Bevezetés a formális logikába ‐ Bp., Gondolat, 1963.
W. V. O. Quine: A logika módszerei ‐ Bp., Akadémia, 1968.
Ruzsa I.‐Urbán J.: Matematikai logika, a Világnézeti nevelésünk természettudományos alapjai IV. kötetében.
Varga T.: Matematikai logika (kezdőknek) ‐ Bp., Tankönyvkiadó, I. 1962., II. 1966.