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.