„Modellelmélet” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a r2.7.1) (Bot: következő hozzáadása: ja:モデル理論 |
|||
15. sor:
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
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]]▼
Egy modell predikátumok interpretálására szolgál. A [[Predikátumkalkulus|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) [[szemantika|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 [[Logika|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 [[Gödel teljességi tétele|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 [[direktszorzat|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 ekvivalencia osztá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 [[Los 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:'''
Az [[Injektív leképezés|injektív]] [[homomorfizmus|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, [[Szaharón Selah|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''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>n</sub> változókat tartalmazó formuláknak egy <math>\mbox{ }_{\mathfrak{p}(x_1,x_2,...,x_n)}</math> halmazáról azt mondjuk, hogy parciális típusa ''T''-nek, ha <math>\mbox{ }_{\mathfrak{p}(x_1,x_2,...,x_n)}</math> ''konzisztens'' ''T''-vel, azaz létezik ''T''-nek olyan <math>\mbox{ }_{\mathfrak{A}}</math> modellje és olyan ''A''-beli ''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>n</sub> sorozat, hogy minden <math>\mbox{ }_{\varphi\in\mathfrak{p}(x_1,x_2,...,x_n)}</math>-ra
36 ⟶ 43 sor:
# ''T'' nyelve megszámlálható,
# ''T'' konzisztens és
# minden ''m''-re ''T'' lokálisan elkerüli a <math>\mbox{ }_{\Gamma_m(x_1,...,x_{n_m})}</math> formulahalmazt, akkor létezik ''T''-nek olyan megszámlálható modellje, mely minden ''m'' természetes számra elkerüli a <math>\mbox{ }_{\Gamma_m(x_1,...,x_{n_m})}</math> 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.
▲'''Axiomatizálás:''' 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.
== Filozófiai vonatkozás ==
| |||