Modellelmélet

A modellelmélet a matematikai logika egyik legfontosabb ága a rekurzióelmélet mellett. A modellelmélet terminológiája a halmazelmélet és az univerzális algebra általánosításán alapul. A formális nyelven megadott állításokat formuláknak nevezik, a formulák egy tetszőleges halmazát pedig (formális) elméleteknek. A formulák, illetve elméletek a megfelelő kontextusba helyezve kapnak jelentést; modellelméleti szempontból az ilyen kontextusok a struktúrák. Tehát a struktúra mintegy „értelmet ad” a formuláknak.

Fontos, hogy különbséget kell tennünk véges és végtelen modellelmélet között, mivel az egyik véges struktúrákra koncentrál, lényegesen eltér a problémák tanulmányozásában és az alkalmazott technikákban. Ezek a jelsorozatok a struktúrák bizonyos tulajdonságait írják le, nem magukat a struktúrákat. A modellelmélet lényegében a struktúrák, és formulák közti kapcsolatokat vizsgálja (a legtermészetesebb ilyen kapcsolat, hogy adott formula, formulahalmaz mely struktúrákban igaz); eközben az olyan klasszikus struktúrák tudományát általánosítja, mint például a csoportok vagy a gráfok.

A modellelméletben konzisztensnek nevezzük az olyan formális elméleteket (nyelveket), melyekhez található a nyelv axiómáit teljesítő struktúra. Ha az L elsőrendű nyelv és az A struktúra típusa megegyezik, akkor röviden azt mondjuk, hogy A egy L-struktúra.

A magyarországi modellelméleti kutatások fontos előzmények után Makkai Mihály, későbbiekben pedig Sági Gábor munkássága és világra szóló eredményei révén teljesedtek ki.

Alapfogalmak

A modellelméletben az elsőrendű nyelveket, ahogy a formális nyelveket általában, logikai formulák (állítások), betűsorozatok halmazaként definiáljuk. Legyen A egy nem üres halmaz, és elemei (a1 a2 a3). Elemeiből véges sorozatok generálhatóak. Az összes ilyen sorozat halmaza legyen az U univerzum. Ahol nincs kikötve, hogy az összes sorozat szerepeljen benne, azoknak a halmazoknak a halmaza értelemszerűen az univerzum hatványhalmaza lesz. Ezek a formális nyelvek. Gyakorlati problémák szempontjából fontosabb a generatív nyelvek osztályának használata; generatív nyelvek azok a nyelvek, amelyekre igaz, hogy van olyan nyelvtan, ami éppen az ő elemeiket generálja. Tehát minden generatív formális nyelv esetén, adva van egy betűkészlet és a hozzájuk tartozó szabályok egy halmaza (a nyelv szintaxisa), mely megadja, hogy a betűket milyen sorrendben lehet és kell összerakni.

Az elsőrendű nyelv egy változtatható és egy nem változtatható részből áll. A matematikai logikának azonban egyik alapfeltevése, hogy egy adott, rögzített név egyszer s mindenkorra vagy nyílt, vagy zárt. ∑t jelenti azoknak a halmazoknak az unióját, amelyek a függvényjelek, a relációjelek, és az elsőrendű logika jelei halmazának uniója, ahol t az a struktúra, mely a hasonlósági típust jelenti. K(t) tehát a hasonló típusú kifejezések halmaza, F(t) pedig a hasonló típusú formulák halmaza (ennek részhalmazai az elméletek). Nyílt formula valami (F(t) eleme) akkor, ha nem tartalmaz kvantort, és szabad változóinak halmaza nagyobb mint nulla (egész szám). A nyílt formulák lehetnek prímformulák és lehetnek diszjunktív normál formulák. Prímformulák akkor, ha még negáció jelet sem tartalmaznak, (azaz nem tagadjuk őket) és nem köthetőek össze „vagy” jellel, valamint diszjunktív normálok azok a prímformulák, amelyeket (vagy tagadásukat) összeköti a „vagy” jel. Zárt formula egy formula akkor, ha a szabad változóinak halmaza nulla. Az ítéletlogika elsődlegesen abban különbözik a kijelentés logika más ágaitól, s azért nevezzük nulladrendűnek, mert nem használ változókat, csak zárt nyelvi formulákkal foglalkozik. Az eldönthető zárt mondatokat ítéleteknek vagy nulladrendű kijelentéseknek, az eldönthető nyílt mondatokat predikátumoknak szokás nevezni. A változtathatók egyik halmaza az individuumváltozók (az U univerzum elemeinek reprezentációi) másik halmaza a nem-logikai változók (ezek a függvényszimbólumok és a relációszimbólumok). Tehát az elsőrendű nyelvek olyan formális nyelvek, melyekben lehetőség van az individuumváltozók kvantifikálására, és a nem változtatható rész tartalmazza a kvantorokat. A változtathatónál meg kell adni a függvényszimbólumok (az U halmazon értelmezett homogén műveletek jelölői) neveit, a relációszimbólumok (az U halmazon értelmezett, de az („igaz”, „hamis”) halmazba képező heterogén műveletek, a logikai függvények (predikátumok, más néven szabad változók jelölői) neveit, és azt, hogy ezek hány változósak. Ezt legkönnyebben úgy tehetjük meg, hogy felveszünk egy függvényt, mely az előbbi szimbólumok diszjunkt halmazainak unióján van értelmezve és értékei természetes számok. Ha egy φ formula egy t típusú pl (U uinerzum) struktúra feletti értékelése igaz, akkor φ igaz U halmazon, vagy másképpen az U modellje a φ formulának. Az ilyen függvények és a függvényszimbólumok halmaza az elsőrendű nyelv típusai, azaz az elsőrendű nyelv x1, x2, …, xn változósorozatát tartalmazó φ adott formulaosztályai.

A típusok különböző mellékfeltételeknek tesz eleget. v (x, y, v0,…vn-1) egy elsőrendű formula, ahol ’n’ a véges sok paraméterhalmazt jelöli. Az elsőrendű nyelvek kifejezései, a terminusok és a formulák véges szimbólumsorozatok, melyeknek önmagukban nincs jelentésük. Azáltal lesz csak jelentésük, ha megfelelő környezetben használjuk őket; az ilyen környezet matematikai szempontból, az elsőrendű struktúra (vagy elsőrendű modell). Ha tehát az L elsőrendű nyelv és az A modell (struktúra) típusa megegyezik, akkor A egy L-modell (struktúra), azaz A egy elsőrendű modell (struktúra). Sági Gábor: Válogatott fejezetek a modellelméletből és határterületeiből pdf. Dokumentuma leírja, hogy vannak olyan modellelmélészek, akik lényegesnek tartják, hogy megkülönböztessék a modell és a struktúra fogalmát. Bővebben: Matematikai struktúra. Mi ezt most a pdf-hez igazodva nem tartjuk lényegesnek megelégszünk azzal, hogy egy formula modellje egy olyan matematikai struktúra, amely a formulát kielégíti. Tehát összegezve: a megfelelő környezet megadásával interpretálhatjuk a terminusokat és a formulákat. A terminus és a formula fogalmának bemutatásával a (Wikipédia alapkifejezés) cikke foglalkozik.

Két formula azonos jelentésű, azaz ekvivalens, ha minden, a közös nyelvüknek megfelelő A struktúrában és minden A feletti értékelésben egyszerre igazak, vagy hamisak. Az A feletti értékelés azt jelenti, hogy az A modellhez tartozó V változók halmazának minden eleme felvesz egy értéket. Az individuumváltozók az adott interpretáción belül is többféle dolgot jelenthetnek. Ezzel ellentétben a függvényszimbólumok és relációszimbólumok jelentése egy adott interpretáción belül nem változik.

A modellelmélet főbb tételei

Egy modell predikátumok interpretálására szolgál. A predikátumok elsőrendű nyelvben vannak értelmezve, ami annyit jelent, hogy egy absztrakciós szinttel felette vannak a nulladrendű formuláknak, azaz lehetséges bennük a kvantifikáció. Ezért bevezetjük az interpretálandó nyelvbe a változók fogalmát. A változók egyik halmaza az individuumváltozók (az U univerzum elemeinek reprezentációi) másik halmaza a nem-logikai változók (ezek a függvényszimbólumok és a relációszimbólumok). Egy elsőrendű nyelvű elmélete azon formulák halmaza, amelyek igazak. A modell (struktúra) pedig áll egy alaphalmazból és rajta értelmezett függvényszimbólumokból, relációszimbólumokból és konstansokból.

Minden elmélet (az elméletek részhalmazai F(t)-nek) szemantikai következményei egy „fi eleme F(t)” formulának akkor és csak akkor, ha a formula levezethető az elméletből. Ha egy elméletből levezethető egy formula és annak negáltja is, akkor az elmélet inkonzisztens, azaz ellentmondásos. Ha az elméletben nincs ilyen formula, akkor az elméletnek van modellje, azaz konzisztens. Ha az elmélet minden véges részének van modellje, akkor az elméletnek is van. Az igazság tétel szerint, ha egy L elsőrendű nyelvben megadott T elméletnek (zárt formulák halmazának) van modellje, akkor konzisztens. Ez nyilvánvaló, hiszen a modellben minden T-ből levezethető állításnak igaznak kell lennie, márpedig a modellen nem teljesülhet egyszerre egy zárt formula és tagadása. A teljességi tétel az igazság tétel megfordítása. Ha tehát egy elsőrendű elméletben egy tetszőleges mondat minden modellben igaz, akkor a formalizált axiomatikus-deduktív elméletek levezethetőség kritériumának megfelel, vagyis bizonyítható. Magasabb rendű vagy végtelen logikák esetében akadály, hogy általában nem teljesek. Gödel teljességi tétele

Ha egy formulára teljesül az, minden A (modell) eleme K modellosztályra fennáll, hogy ha A modellje a formulának, akkor ez a megállapítás a K modellosztály elmélete. (jele Th(k)). A modellek elméletei formulahalmazok. K akkor modellosztálya E formulahalmaznak, ha minden A-ra fennáll, hogy A modellje az E formuláknak, és A eleme K (jele Mod(E)).

Az ultraszorzat nem más, mint egy direktszorzattal kapott I hatványhalmazán végzett szűrés (melynek az üres halmaz nem eleme és nem is üres, ha két halmaz eleme, akkor a metszetük is eleme, illetve ha egy elemének van komplementere, akkor azzal az elemmel és komplementerrel képzett halmaz is eleme) illetve egy kikötés, miszerint minden alaphalmazbeli részhalmaz az eleme (ekkor pontvéges), vagy annak komplementere az eleme. Ekkor az alaphalmaz ultraszorzatáról beszélünk. Ha az ultraszűrő végesmetszet tulajdonságú, akkor létezik egy őt tartalmazó legkisebb szűrő, valamint minden szűrő kiterjed egy ultraszűrővé. A szűréssel ekvivalenciaosztályokat képezünk, ugyanis a szimmetria és a reflexivitás nyilvánvaló, de még a tranzitívitás is megvan: kiválasztunk két nyelvet, melyek elemei az ultraszűrőnek, a metszetük is az lesz, és mivel amaz részhalmaza lesz egy olyan kibővített nyelvnek, amiben egy harmadik formula egyenlő az előző két nyelv egy-egy formulájával, ezért a felszálló tulajdonság miatt eleme lesz ez a nyelv is az ultrafilternek. Az ekvivalencia reláció miatt az ultraszorzatok megőrzik az elsőrendű igazságot. Mindez fontos lesz azokban a tételekben, amelyek a reguláris ultraszűrőkön révén elvezetnek a kompaktsági tételhez, mely révén pedig az axiomatizálhatóságról tudunk meg valamit.

Két modell elemien ekvivalens, ha a leírás szintjén megkülönböztethetetlenek, azaz ugyanazokat az állításokat teszik igazzá. Ezeknek a modell típusoknak egy részhalmaza az, amikor két struktúra izomorf is; ekkor a két struktúra között van egy bijekció. Ugyanakkor, ha két végtelen struktúra elemien ekvivalens, akkor nem biztos, hogy izomorfak. Ha ugyanis egy T elméletnek van végtelen modellje, és K az elméletnél nagyobb egyenlő számosság, akkor biztos van K számosságú modellje is, ez Lowenheim-Skolem tétel felszálló ága. Ugyanis a végesmetszet tulajdonságból következik, hogy van egy F ultraszűrő A felett. Mivel F K-reguláris ultraszűrő, ekkor azzal a függvénnyel kapott halmazon, ami a K számosságú indexhalmazt egy tetszőleges A struktúrába képezi elvégezve az F K-reguláris ultraszűrőt egy ultraszorzatot kapunk mely számossága egyenlő lesz azzal, ha csak direktszorzatot végeztünk volna. A Los-lemma miatt a direktszorzat számosságával egyenlő lesz egy az ultraszorzattal kapott struktúrával elemien ekvivalens B struktúra is, aminek lesz pontosan egy X K-számosságú részhalmaza. Ez a Löwenheim-Skolem tétel leszálló ága miatt benne lesz B egy K számosságú elemi részében. Így lesz A-val egy elemien ekvivalens, de vele nem izomorf B struktúra. Azaz egy végtelen struktúrát nem lehet elsőrendben igazságértékeléssel egyértelműen azonosítani.

Akkor mondjuk egy ultraszűrőre, hogy K-reguláris, ha egy részhalmaza K számosságú és pontvéges, azaz az alaphalmazbeli elemeknek a halmaza az eleme. A kompaktsági tétel azt mondja ki, hogy ha egy formulahalmaz minden véges részének van modellje, akkor e modellek egy alkalmas ultraszorzata modellje a formulahalmaznak. Ha ugyanis e formulahalmaz egyenlő számosságú (ezért izomorf) az alaphalmazzal, akkor az alaphalmazon végzett ultraszorzat pontvéges E részhalmaza is izomorf lesz vele és az alaphalmazzal. A bijekciót leíró függvény véges lesz E pontvégessége miatt. Azaz egy végtelen formulahalmazt úgy kenünk szét az I alaphalmazon, hogy minden koordinátára véges sok formula jut. Ez a véges halmaz tehát teljesül egy A struktúrán. Mivel tetszőleges formulára teljesül, ezért A struktúrán is teljesül az egész formulahalmaz, majd a Los-lemma révén A egy ultraszorzatán is teljesül a formulahalmaz.

Az axiomatizálhatósághoz az vezet el, hogy belátjuk, hogy egy K struktúra akkor és csak akkor axiomatizálható, ha K zárt az elemi ekvivalenciára és az ultraszorzatra, valamint, továbbá K komplementuma zárt az ultraszorzatra. A Łos-lemma miatt nyilvánvaló, hogy ha K axiomatizálható, akkor zárt az ultraszorzatra, illetve az is triviális, hogy az elemi ekvivalenciára is. Az is triviális, hogy K részhalmaza azoknak a struktúráknak, melyek modelljei a formulahalmaznak, azt kell igazolni, hogy ez fordítva is így van, azaz hogy egy végtelen formula halmaznak a modellje K-ban van. Tegyük fel, hogy van egy elemi modellje K-nak, melyben teljesül egy adott véges formulahalmaz, ekkora K komplementuma meg az axiomatizációban szereplő formulák tagadásának konjunkcióját axiomatizálja. Azaz az adott formulahalmaz minden véges részének van modellje, (és mivel az így kapott modell elemienekvivalens egy K-ban lévő végtelen számosságú A modellel), ezért ez a kompaktsági tétel miatt azzal jár, hogy ennek az egész végtelen igaz formulhalmaznak, melyek A elméletei, van modelljük K-ban.

Axiomatizálás: Tehát elmondhatjuk, hogy struktúrák egy osztálya akkor és csak akkor axiomatizálható, ha zárt az elemi ekvivalenciára és az ultraszorzatra, és végesen axiomatizálható ha komplementere is zárt.

Az injektív homomorfizmusokat beágyazásoknak nevezzük. Azt mondjuk, hogy az A struktúra elemien beágyazható B-be, ha van olyan f : A → B beágyazás, melynek értékkészlete elemi rész B-ben. A pontosan akkor ágyazható (elemien) B-be, ha A izomorf B egy (elemi) részstruktúrájával. B’ elemi része B-nek, ha része, és egy tetszőleges változósorozatról szóló állításra fennáll, hogy ha teljesül B’-ben akkor és csak akkor teljesül B-ben is. Minden struktúra elemien beágyazható minden ultrahatványába (diagonális beágyazás).

A Löwenheim-Skolem tétel felszálló ága miatt megállapíthatjuk, hogy két elemien ekvivalens struktúra univerzumaik számosságában eltérhet. Ugyanakkor mégis van köztük hasonlóság; két modell pontosan akkor elemien ekvivalens, ha vannak omega hosszú izomorf ultraláncaik (Frayne), vagy izomorf ultrahatványaik. Ez utóbbit Keisler először, Selah pedig a kontinuum hipotézis nélkül igazolta. Ezeket nem igazoljuk csak az előbbihez vezető ultraláncokról szóló tételt. Azt mondjuk, hogy A K-univerzális, ha minden A-val elemien ekvivalens és K-nál kisebb számosságú struktúra elemien beágyazható A-ba. Ha van egy F K-reguláris ultraszűrő egy K-nál kisebb számosságú formulahalmaz modelljének direktszorzata felett, akkor az így kapott ultrahatvány K+ univerzális. Ha van egy elemi beágyazás A-ból B-be, akkor van olyan diagonális beágyazás B-ből A K+ univerzális ultrahatványába, mely diagonális beágyazás eleme az előbbi elemi beágyazás értékkészlete. A feladat az, hogy B nyelvén a leképezéssel kapott képek tulajdonságainak elsőrendben meg kell egyeznie az eredeti elemek tulajdonságaival. Ez összesen annyi formula, mint a diagonális beágyazással kapott halmaz számossága. Ha F egy ultraszűrő, amely legalább annyira reguláris, mint ahány formulát szétosztunk az alaphalmaz koordinátáin, akkor a kompaktsági tétel miatt szét tudjuk úgy osztani a formulákat, hogy minden koordinátára csak véges sok formula jusson. Tehát B úgy ágyazható elemien egy ultrahatványba, hogy elég B egy véges részét jól reprezentálni, de persze egy-egy véges részen belüli elem képe függ a többi figyelembe vett elemtől is. Frayne tétele ezt felhasználva bizonyítja be az elemien ekvivalens modellek közti hasonlóságot.

Parciális típus: (Típus (modellelmélet)) Legyen T elmélet egy L elsőrendű nyelvben. A legfeljebb csak az x₁, x₂, …, x_n változókat tartalmazó formuláknak egy ${\mbox{ }}_{{\mathfrak {p}}(x_{1},x_{2},...,x_{n})}$ halmazáról azt mondjuk, hogy parciális típusa T-nek, ha ${\mbox{ }}_{{\mathfrak {p}}(x_{1},x_{2},...,x_{n})}$ konzisztens T-vel, azaz létezik T-nek olyan ${\mbox{ }}_{\mathfrak {A}}$ modellje és olyan A-beli a₁, a₂, …, a_n sorozat, hogy minden ${\mbox{ }}_{\varphi \in {\mathfrak {p}}(x_{1},x_{2},...,x_{n})}$-ra

${\mathfrak {A}}\models \varphi [a_{1},a_{2},...,a_{n}]$.

Típuselkerülési tétel: (Típuselkerülési tétel) A teljes típust ki nem elégítő modelleket keresünk. Legyen T elsőrendű nyelv elmélete, minden m természetes számra ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmaz T nyelvén. Ha

1. T nyelve megszámlálható,
2. T konzisztens és
3. minden m-re T lokálisan elkerüli a ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmazt, akkor létezik T-nek olyan megszámlálható modellje, mely minden m természetes számra elkerüli a ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmazt.

Robinson tétele alapján, ha T egy teljes elmélet az L = L1 ∩ L2 nyelven és ha T1 és T2 a T konzisztens bővítései az L1 és L2 nyelven, akkor T1 U T2 konzisztens.

Filozófiai vonatkozás

A modellelmélet szerepe a filozófiában

Tarski, aki Gödel, Löwenheim és Skolem mellett atyja a modellelméletnek az igazság azon definiálásával - miszerint egy halmaz elemi kijelentései igazak, ha a metanyelvi jelentésük megegyezik a kijelentésük T-séma beli alakjával - a matematikai logikát elkötelezte a matematika filozófia arisztotelészi hagyományának továbbvitele mellett. A modellelmélet módszertani alapja az axiomatikus-deduktív módszer (melynek axiómái rekurzívan felsorolhatók), és Gödel teljességi és nemteljességi tételeit (Gödel-tétel (egyértelműsítő lap)) is az ezekre a módszerekre épülő formalizmusokra fogalmazta meg. Így a modellelmélet elválaszthatatlan sarokkövévé vált a 20. században Wittgenstein nyomán kibontakozó analitikus nyelvfilozófiának.

Ellenben a matematika filozófia igazságelméleti kérdését nem tekinthetjük lezártnak. Vannak filozófusok, pl. Strawson, akik ezt vitatják. (A Wikipédia Igazságelméletek cikke). A modellelmélet viszont, mint a matematikai logika egyik legjelentősebb ága azonban nemhogy lezárta volna a filozófiának ezt a kérdéskörét, hanem újbóli kérdéseket vetett fel. Ilyen módon a matematika filozófiára is kihatott. Putnam megfogalmazása szerint a matematika Gödel nemteljességi tétele után a lehetőségek és lehetetlenségek tudománya, ugyanis azzal, hogy konzisztens és modellezhető, tekinthetjük a tőle kissé eltérő axiomatizálású elméletek összes lehetséges modelljének esetét. A matematika szerepének vizsgálata, a definiálhatóság, a bizonyítás mibenléte további, és a korábbi kérdésekkel azonos fajsúlyú, nyitott kapukat hagy maga mögött. Ezek a kérdések egész világnézeti képünkre hatással vannak, mert azok a fogalmak, amiket idáig intuíció útján próbáltunk megragadni, a modellelmélet révén logikus úton próbáljuk összehangolni. És bizony egész nem várt eredmények születnek, melyeket intuícióink képtelenek lettek volna megragadni; (modellelméleti kérdések).

Elimináció

Felmerült továbbá egy kérdés, hogy a valóságot leíró elméletekben mennyire vagyunk elköteleződve a matematikai entitások felé. Penelope Maddy volt az, aki cáfolta azt, hogy ontológiailag elkötelezettek lennénk a tudomány számára nélkülözhetetlen entitásokkal szemben (Quine-Putnam féle nélkülözhetetlenségi argumentum alapján definiált), ugyanis lehetnek egy tudományos elmélet jelentéssel bíró entitásai közt olyan idealisztikus elemek, amelyek elősegítik azt, hogy a kérdéses állításokból empirikusan ellenőrizhető állításokat vezessünk le. Több példa is van erre. Tehát ebből következik, hogy ha egy tudományos elmélet vizsgálatánál a jelentéssel bíró entitásokkal szemben a konfirmáció elősegítésének kérdését vizsgáljuk, csak ezt tartsuk szem előtt és ne tartsunk kizárólagos jelentőséget az eliminálhatatlan entitásoknak. Mi több a matematikai entitások eliminálhatóak (Field), a Craig-tétel megfelelő alkalmazásával, mely kimondja, hogy amennyiben egy axiomatizálható T elmélet szókészletének nem logikai része egy A és egy B részre osztható, akkor létezik egy axiomatizálható T* elmélet, amelynek nem logikai szókészlete csak B, és T* tételei azok és csak azok a tételek, amelyek T-ben, csak a B szókészletet használva levezethetők. Ellenben szükségszerűen meg kell hagynunk a formális rendszereket, amelyeket maga Field sem óhajtott eltávolítani, és mint formális rendszert, meghagyta a matematikát. Pl. a Peano-axiomákkal definiált formális struktúrákat nem eliminálhatjuk. Field tehát eliminálta a matematikai entitásokat a fizikából, amennyiben matematikai entitás alatt azt értjük, amik arra szolgálnak, hogy a különböző matematikai struktúrákat definiáló formális nyelv individuumváltozóinak jelölői legyenek. Szabó Máté Quine- Putnam nélkülözhetetlenségi argumentum TDK-jában rámutatott arra, hogy a matematikai entitások sehogy sem férnek össze azzal, hogy érzetminőségek nélkülözhetetlenségi fogalmát rájuk is alkalmazzuk, márpedig pont az érzetminőségek nélkülözhetetlensége a Craig-tételnek úgymond kivétel részét képezi.

Források

• Sági Gábor: Válogatott fejezetek a modellelméletből és határterületeiből
• Andai Attila: Az elsőrendű logika néhány tétele