Ugrás a tartalomhoz

Szerkesztő:Emájti/próba

A Wikipédiából, a szabad enciklopédiából

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. Minden 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 változtathatók egyik halmaza az individuumváltozók (U halmaznak, az 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”} (más jelöléssel {0,1}) halmazba képző heterogén műveletek, a logikai függvények vagy predikátumokat 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. 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. φ –t tehát a halmazelmélet alapján állítjuk. 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). Ezzel interpretáljuk a jelentést. (Egy formula modellje olyan matematikai struktúra, amely a formulát kielégíti, a nyelv esetén az r mondathalmaznak pontosan akkor van modellje, ha minden véges részének van modellje. Ha az L elsőrendű nyelv és az A struktúra típusa megegyezik, akkor A egy L-struktúra.) 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 ellenben a függvényszimbólumok és relációszimbólumok jelentése egy adott interpretáción belül nem változik. Ha egy formulára teljesül az, hogy az adott modellosztályból következik a formula, azaz minden A eleme K-ra fennáll, hogy A l= formula, akkor ez 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-ból következik E formula halmaz, és A eleme K (jele Mod(E)). Két struktúra akkor azonos, ha szerkezetük azonos (szükséges feltétele, hogy létezzen a két struktúra között egy bijekció), és csak elemeik konkrét alakjában lehetnek eltérések. Az A, B azonos struktúrák elemien ekvivalensek, ha Th(A) és Th(B) egyenlő. Egy speciális formulahalmaz parciális típusa lehet egy elméletnek, ha konzisztens vele, azaz ha az elmélet modelljében realizálható az adott speciális formula halmaz. Ha van a T elmélettel konzisztens θ formula, hogy θ φ levezethető, úgy hogy minden φ eleme az elsőrendű nyelvbeli formula halmaznak, akkor azt mondjuk, hogy T lokálisan megvalósítja ezt az elsőrendű nyelvet. 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 egy L elsőrendű nyelvben megadott T elmélet konzisztens, akkor van modellje.