A matematikai logika története

A logika ősrégi tudomány, története az ókorig vezethető vissza. A logikát sokáig a filozófia részének tekintették, e vonatkozásban csak a 19. század végén történt jelentős fordulat, amikor is megtörtént a logika egy jelentős szeletének (elsőrendű logikának) a matematizálása, és ezzel egy új tudományág jött létre, a matematikai logika.

A kezdetek

A logika leghíresebb ókori művelői Arisztotelész, a szillogizmus elméletének atyja és Euklidész, aki a síkgeometria axiómáit alkotta meg. Az 1700-as években történtek először kísérletek a logika matematizálására. Olyan filozófusok, matematikusok foglalkoztak a témával, mint Leibniz és Lambert, de munkásságuk még nem nevezhető áttörőnek.

A 19. század

A 19. század közepén George Boole, majd később Augustus De Morgan formalizáltak először bizonyos logikai fogalmakat a matematika, ezen belül az algebra segítségével. Munkájuk, amely olyan algebristák munkáira épült, mint például George Peacock, újraértelmezte és megreformálta a klasszikus arisztotelészi logikai axiómákat, és így létrejött a megfelelő „eszköz” a matematika alapvető fogalmainak formalizálására. Ezt már a matematikai logika közvetlen előzményének tekintjük. Boole munkáiból kiindulva alkotta meg Charles Peirce a relációk és kvantorok logikai rendszerét, amit számos újságban publikált 1870 és 1885 között. Ettől függetlenül jelentette meg munkáját Gottlob Frege a kvantifikált logikáról az 1879-ben kiadott Begriffsschrift című művében. Frege munkája ismeretlen maradt addig, amíg Russell a századforduló környékén népszerűsíteni nem kezdte. Viszont a Frege által kitalált kétdimenziós jelölés sosem terjedt el, és a korabeli szövegekben sem használták. Ernst Schröder 1890-től 1905-ig, 3 részletben publikálta Vorlesungen über die Algebra der Logik című művét. Ez a tanulmány összegzi és továbbfejleszti Boole, De Morgan, és Peirce munkáit, és átfogó képet ad a szimbolikus logikáról, ahogy azt a 19. században értelmezték.

Legfontosabb tételek

A formális logika megjelenésének köszönhetően megszülethetett a matematika főbb területeinek - mint az aritmetika, az analízis és a geometria – axiómarendszerei. Erre azért is volt szükség, mert eddig a matematikusoknak nem állt rendelkezésükre megfelelő alap, amelyre az elméleteiket építhették.

Az aritmetika a matematikának az az ága, mely a valós számok elméletével foglalkozik. Giuseppe Peano 1888-ban vezette be az aritmetika egy axiomatikus elméletét, melyben Boole és Schröder logikai rendszerét kvantorokkal egészítette ki. Peano ekkor még nem ismerte Frege munkáit. Körülbelül ugyanekkor Richard Dedekind megmutatta, hogy a természetes számok egyértelműen jellemezhetőek indukciós tulajdonságukkal. Dedekind (1888) ezzel egy olyan tulajdonságot mondott ki, amely a Peano-axiómákból hiányzik.

A 19. század közepére egyre nyilvánvalóbb lett az euklideszi geometriai axiómák hiányossága. 1826-ban Lobacsevszkij bebizonyította a párhuzamossági axióma függetlenségét, illetve matematikusok megállapították, hogy bizonyos Euklidész által kimondott tételek nem vezethetők le az axiómáiból. Többek közt azon tétel is, mi szerint egy egyenesnek legalább két pontja van. 1899-ben Hilbert egy komplett geometriai axiómarendszert alkotott, Pash (1882) régebbi munkáira alapozva. A geometria axiomatizálásának sikerén felbuzdulva, Hilbert szerette volna a matematika más területeit is axiomatizálni, mint például a valós, vagy a természetes számok elméletét. Végül ezek a problémák bizonyultak a főbb kutatási területeknek a 20. század első felében.

A 19. században nagy fejlődés történt a valós analízisben is, mint például a függvények konvergenciája, vagy a Fourier-sorok terén. Olyan matematikusok, mint például Karl Weierstrass a nem-differenciálható folytonos függvényekkel kapcsolatos tételeket bizonyított. Az olyan elgondolások, mi szerint a függvény csupán egy egyenletes grafikon, nem bizonyultak többé helytállónak. Weierstrass élen járt az analízis axiomatizálásában, melyhez a természetes számok tulajdonságait használta fel. A folytonos függvények korlátosságának modern, "ε-δ"-s tételét Bolzano és Cauchy bizonyította be 1817 és 1823 között. 1858-ban Dedekind a valós számok egy új definícióját mondja ki, a valós számok Dedekind-szeleteinek segítségével. Ez a definíció több korabeli szövegben megtalálható. Georg Cantor alkotta meg a naiv halmazelmélet alaptételeit. Korai munkáiban mondta ki a számosság tételét, és bebizonyította, hogy a valós és természetes számok halmaza különböző számosságú. A következő 20 évben több művében ír a transzfinit számokról. 1891-ben egy új bizonyítást ad közre a valós számok megszámlálhatatlanságáról, amiben azt a tételét használta fel, miszerint egy halmaz számossága nem egyezhet meg összes részhalmazai halmazának számosságával (hatványhalmaz számossága). Cantor úgy hitte, hogy minden halmaz jólrendezhető, de bizonyítania nem sikerült, így ez megoldatlan probléma maradt egészen 1895-ig.

20. század

a 20. század elejének főbb kutatási területei a halmazelmélet és a formális logika voltak. A naiv halmazelmélet ellentmondásosságának felfedezésével (Russell, 1901) felmerült, hogy esetleg maga a matematika is összeegyeztethetetlen, ennek bizonyításával többen kísérleteztek. 1900-ban Hilbert összeállított egy híres, 23 problémából álló listát a következő századnak. Ez első kettő kontinuumhipotézissel és a számelmélet axiómarendszerének ellentmondás-mentességével foglalkozott, a tizedik pedig a diofantoszi egyenletek megoldhatóságával. Ezen problémák későbbi megoldása gyakran a matematikai logika felé mutatott, mint ahogy ezt használták Hilbert Entscheidungsproblem-jának megoldására is 1928-ban. Ez a probléma arra keresi a választ, hogy létezik-e olyan eljárás, ami egy formalizált matematikai állításról egyértelműen eldönti, hogy igaz vagy hamis.

Halmazelmélet és paradoxonok

1904-ben Ernst Zermelo adott bizonyítást arra, hogy minden halmaz jólrendezhető, ez Georg Cantornak még nem sikerült. Ebben a bizonyításban mondta ki először a kiválasztási axiómát, ami heves vitát váltott ki a matematikusok és a halmazelmélet szakértői körében. A kritikák miatt 1908-ban Zermelo egy új magyarázatot adott közre, amiben újrafogalmazza a bizonyítást, és amit kifejezetten az első bizonyítás kritizálóinak ajánlott. A második bizonyítás után a kiválasztási axióma általánosan elfogadottá vált a matematikusok körében. A kiválasztási axiómával kapcsolatos szkepticizmus azért is volt indokolt, mivel rendszeresen jelentek meg új paradoxonok a naiv halmazelmélettel kapcsolatban. 1897-ben Cesare Burali-Forti volt az első, aki egy paradoxonnal állt elő, a végtelen halmazok paradox voltát világította meg. Nem sokkal ez után fedezte fel Bertrand Russell a Russell-paradoxont 1901-ben, és Jules Richard a Richard-paradoxont 1905-ben. 1908-ban Zermelo adta az első halmazelméleti axiómarendszert. Ezeket az axiómákat, kiegészítve Abraham Fraenkel helyettesítési axiómájával, ma Zermelo–Fraenkel (ZF) halmazelméletnek hívjuk. Zermelo axiómáit egyesítették azzal az elvvel, miszerint legnagyobb számosságú halmaz nem létezik, kikerülve ezzel Russell paradoxonját. 1910-ben jelent meg , Russell és Alfred North Whitehead Principia Mathematicájának első kötete. Ez a munka a függvényelmélettel és a típuselmélettel foglalkozott, amit Russell és Whitehead azért hoztak létre, hogy elkerüljék az addig fellépő paradoxonokat. A Principia Mathematica a 20. század egyik legmeghatározóbb műve.

Formális logika

Leopold Löwenheim (1918) és Thoralf Skolem (1919) mondták ki a Löwenheim–Skolem tételt, miszerint az elsőrendű logika nem képes értelmezni a végtelen struktúrák számosságát. Skolem megmutatta, hogy ez a tétel igaz a halmazelmélet elsőrendű formalizálására, és minden olyan formalizálásra, ami megszámlálható modellel rendelkezik. Ez a meglepő tényt Skolem-paradoxonnak nevezik. Doktori disszertációjában Gödel (1929) bebizonyította teljességi tételét, amely szerint az elsőrendű logikában a szemantika és a szintaktika megegyeznek. Gödel a kompaktsági tétel bebizonyításához a komplettségi tételt használta, ezzel megmutatva az elsőrendű logika véges természetét. Ezen eredményeknek köszönhetően az elsőrendű logika a matematikusok által leggyakrabban használt logika. 1931-ben Gödel publikálta első nemteljességi tételét. Ez az eredmény szigorú szabályok közé szorította az axiomatikát, és így nem vetett jó fényt Hilbert munkájára. Megmutatta az aritmetika konzisztens bizonyításának lehetetlenségét, annak bármely formális elméletében. Hilbert sokáig nem ismerte fel a nemteljességi tétel fontosságát. Gödel bizonyítása megmutatta, hogy egy elég erős, eredményes axióma rendszer konzisztens bizonyítása nem kapható meg rendszerből magából, sem akármilyen gyengébb rendszerből. Nyitva hagyja az olyan konzisztens bizonyítások lehetőségét, melyek nem formalizálhatóak a rendszerben, amelyre vonatkoznak.

Új ágak

Alfred Tarski nevéhez fűződnek a modellelmélet alapjai. 1935-ben kiváló matematikusok egy csoportja Nicolas Bourbaki álnéven publikálták matematikai tanulmányok egy sorozatát. Ezek a szövegek, melyek pontos, axiomatikus nyelven íródtak, szigorú keretek közé szorították a halmazelméleti tételeket. Ebben a tanulmányban jelentek meg először olyan szakszavak, mint a bijekció, injekció, vagy a szürjekció. Halmazelméleti szövegeit széles körben alkalmazták a korabeli matematikusok. A kiszámíthatóságelmélet először rekurziós tételek néven lett ismert, mert Gödel és Kleene korai munkái rekurzív függvényekre hivatkoztak. Amikor megmutatták, hogy ezek a definíciók ekvivalensek Turing munkáival (Turing-gép), világossá vált, hogy egy új fogalom, az algoritmusfogalom jött létre. 1940-ben számos eredmény született a rekurziós tételek kapcsán, melyek Stephen Cole Kleene és Emil Leon Post nevéhez fűződnek. Kleene (1943) a kiszámíthatóság egy relatív megközelítésével (melyet Turing 1939-ben sejtett meg először), és az aritmetika hierarchiájával állt elő. Kleene később a rekurziós tételt magasabb rendű függvényekre is értelmezte. Kleene és Kreisel az intuitív matematika formalizált változatát is kutatták, mely elsősorban a bizonyításelmélethez kapcsolódott.

A matematikai logika, mint alkalmazott tudomány

A 20. század utolsó negyede jelentős fordulatot hozott a matematikai logika fejlődésében. A számítógépek megjelenésével és kutatásával, az informatika fejlődésével az addig elsősorban csak a matematika saját problémáival foglalkozó, kissé filozófiai ihletettségű matematikai logika egyszeriben alkalmazott és gyakorlati tudománnyá is vált. A matematikai logikát ugyan már a számítógép megjelenése előtt is alkalmazták például a nyelvtudományban, vagy az elméleti fizikában, de az alkalmazást illetően áttörés csak a számítógépek megjelenésekor következett be. A számítógépes alkalmazások miatt az érdeklődés középpontjába került az algoritmikus szemlélet és az eldönthetőséggel kapcsolatos számos pozitív eredmény. A számítástudomány fejlődésének hatására a logika egyéb területein is újabb, gyors fejlődés indult el: ilyenek a bizonyításelmélet (kutatását elsősorban a gépi bizonyítások és a logikai programozás motiválta), a nemklasszikus logikák (kutatását a mesterséges intelligencia és a matematikai nyelvészet motiválta) és a szemantikakutatás (a programozáselmélet és a programhelyesség-bizonyítás motiválta). Létrejött egy interakció is az alkalmazások és a matematikai logika elmélete között, hiszen az egész alkalmazási folyamat visszahatott a matematikai logika belső fejlődésére is. Új logikák jöttek létre, például a dinamikus logika, nemmonoton logikák, speciális többértékű logikák, stb. Az alkalmazások és az elmélet közötti interakcióra példa az adatbázis-elmélet, ahol a logikát nagymértékben alkalmazzák, ugyanakkor az alkalmazások is elindítottak fontos elméleti logikai kutatásokat.

A hazai logikakutatásokról

A hazai logikakutatás területén nemcsak jelentős kutatókról beszélhetünk, hanem jelentős logikaiskolákról is. Elmondhatjuk, hogy ezen iskolák komoly szerepet játszottak a 20. századi logika történetében. Péter Rózsa a rekurzív függvények területén ért el fontos eredményeket. Kalmár László, aki iskolát teremtett a számítástudomány, és ezen belül is az elméleti számítástudomány terén, a logika számítástudományi alkalmazásaiban vitt úttörő szerepet. Ruzsa Imre a logika humán alkalmazásainak területén teremtett iskolát, kutatási területe elsősorban a nemklasszikus logikák, ezen belül például az intenzionális logika. Németi István és Andréka Hajnal az algebrai logikában teremtettek nemzetközi hírű iskolát, bekapcsolódtak a Tarski-csoport munkájába, és a témakör vezető kutatói közé számítanak, de fontos eredmények vannak a logika számítástudományi alkalmazásainak terén is. Makkai Mihály területe a modellelmélet, számos mély eredmény fűződik a nevéhez. A felsorolt kutatók valamennyien a logika oktatásának területén is elévülhetetlen érdemeket szereztek.

Hivatkozások

Ferenczi Miklós: Matematikai logika, Műszaki Könyvkiadó, 2002., 27-28. oldal

További információk

• Dr. Tóth László: Matematikai logika egyetemi jegyzet, Pécsi Tudományegyetem 2005.
• Kovács András: Matematikai logika egyetemi jegyzet, Debreceni Egyetem
• Mathematical Logic around the world
• Polyvalued logic Archiválva 2009. június 5-i dátummal a Wayback Machine-ben
• forall x: an introduction to formal logic, by P.D. Magnus
• A Problem Course in Mathematical Logic, by Stefan Bilaniuk