Modellelmélet

A modellelmélet a matematikai logika egyik ága , amely a formális nyelvek és értelmezéseik , illetve modelljeik kapcsolatának vizsgálatával foglalkozik . A névmodell elméletet Alfred Tarski javasolta először 1954- ben . A modellelmélet fő fejlesztése Tarski, Maltsev és Robinson munkáiban volt .

Eredet

A modellelmélet a szintaxis és a szemantika közötti alapvető kapcsolat vizsgálatának szenteli magát . Ugyanakkor a formális nyelv megfelel az elsőnek , a modell pedig a másodiknak - egy matematikai struktúra , amely lehetővé teszi ennek a nyelvnek a leírását. A modellelmélet az algebrával és a matematikai logikával kapcsolatos metamatematikai problémák megoldásának meglévő megközelítéseinek általánosításaként jelent meg . Ezek a megközelítések maguk is régóta léteznek, de sokáig nem vették őket teljes egészükben, egyetlen logikai-filozófiai paradigma keretein belül . Természetes példa ebben az összefüggésben az Euklidész ötödik párhuzamos egyenesek posztulátumához kapcsolódó probléma. A matematikusok évszázadokon át nem tudták bizonyítani ennek igazságát, mígnem a 19. században Bolyai és Lobacsevszkij felépítette a nem euklideszi geometriát , megmutatva ezzel, hogy a párhuzamos posztulátumot nem lehet sem bizonyítani, sem megcáfolni. Ez a modellelmélet szempontjából azt jelenti, hogy az ötödik posztulátum nélküli axiómarendszer többféle modellt, azaz jelen esetben több lehetőséget is megenged a geometria megvalósítására.

Így az eredeti modellelmélet a matematika olyan ágaiból nőtt ki, mint a logika , az univerzális algebra , a halmazelmélet , mint a meglévő ismeretek általánosítása és bővítése. Ezért a modellelmélet első eredményei jóval a „hivatalos” megjelenése előtt megjelentek. A Löwenheim-Skolem tétel ( 1915 ) tekinthető az első ilyen eredménynek [1] . Egy másik jelentős eredmény a tömörségi tétel volt , amelyet Gödel ( 1930 ) és Maltsev ( 1936 ) bizonyított.

Klasszikus elsőrendű modellelmélet

A klasszikus elsőrendű logika modellelmélete történelmileg a modellelméleti megközelítés első és legfejlettebb példája. A modellek szerepét itt a változók lehetséges értékeinek tartományát reprezentáló halmazok játsszák . A függvényszimbólumok a rajtuk lévő megfelelő aritás műveleteiként, a predikátumok pedig relációkként értelmeződnek (további részletekért lásd : Elsőrendű logika, értelmezés ).

Tömörségi tétel

A modellelmélet egyik legfontosabb eszköze a Maltsev által bizonyított tömörségi tétel , amely kimondja, hogy az elsőrendű képletek halmazának akkor és csak akkor van modellje, ha a modellben az adott képlethalmaz minden véges részhalmaza van.

A tétel elnevezése onnan ered, hogy egy kőtér tömörségére vonatkozó állításként fogalmazható meg .

A tömörségi tételből következik, hogy egyes fogalmak nem fejezhetők ki az elsőrendű logikában. Például a végesség vagy a megszámlálhatóság fogalma nem fejezhető ki semmilyen elsőrendű formulával, sőt halmazakkal sem: ha egy képlethalmaznak tetszőlegesen nagy véges modelljei vannak, akkor annak is van végtelen modellje. Hasonlóképpen, egy olyan elméletnek, amelynek végtelen számú modellje van, és amelynek számossága nem kisebb, mint az aláírás számossága, vannak bármilyen nagyobb számosságú modellje.

A tömörségi tétel alkalmazható klasszikus elméletek nem szabványos modelljei , például elemi aritmetika vagy számítás .

Elméletek és elemi ekvivalencia

Az elmélet a levezethetőség szempontjából zárt (röviden: zárt) formulák halmaza, vagyis olyan halmaz , hogy ha a képlet -ből következik , akkor -hoz tartozik . $T$ $T$ $\varphi$ $T$ $\varphi$ $T$

Azt az elméletet, amelynek legalább egy modellje van, konzisztensnek, a többi elméletet ellentmondásosnak nevezzük.

Egy elméletet teljesnek nevezünk, ha bármely képletre az elmélet vagy -t tartalmaz . Ha egy algebrai rendszer, akkor az igaz halmaza zárt formulákon egy teljes elméletet alkot - a rendszer elméletét , amelyet jelöl . $T$ $\varphi$ $\varphi$ $\lnem \varphi$ $A$ $A$ $A$ $Th(A)$

Ha algebrai rendszerekre és ugyanazok a zárt formulák igazak, akkor és elemi ekvivalensnek mondjuk. Így és akkor és csak akkor ekvivalensek, ha ugyanannak a teljes elméletnek a modelljei. $A$ $B$ $A$ $B$ $A$ $B$

Ha egy teljes elméletnek véges modellje van , akkor az elmélet minden modellje izomorf , különösen, mindegyikben ugyanannyi elem van. Ezért véges algebrai rendszerek esetén az elemi ekvivalencia és az izomorfizmus fogalma egybeesik. $T$ $A$ $T$ $A$

Alrendszerek és Löwenheim-Skolem tételek

Az algebrai rendszert egy algebrai rendszer alrendszerének nevezzük, ha az egyes aláírás szimbólumok értelmezése a halmazban való értelmezésének korlátozása . Egy alrendszert eleminek nevezünk, ha bármely képletre és bármelyikre teljesül: akkor és csak akkor, ha . A rendszert ezekben az esetekben a rendszer (elemi) kiterjesztésének nevezzük . $B$ $A$ $|B|\subseteq |A|$ $B$ $A$ $|B|$ $\varphi (x_{1},\;\ldots ,\;x_{n})$ $b_{1},\;\ldots ,\;b_{n}\in |B|$ $A\models \varphi (b_{1},\;\ldots ,\;b_{n})$ $B\models \varphi (b_{1},\;\ldots ,\;b_{n})$ $A$ $B$

Egy elemi alrendszer elemileg egyenértékű a -val . Azokat az elméleteket, amelyek modelljére fordítva is igaz – minden elemileg ekvivalens alrendszer elemi –, teljes modellnek nevezzük. Egy elmélet modellteljessége a következő tulajdonságok mindegyikével egyenértékű: $B$ $A$ $T$

bármely képlet ekvivalens egy egzisztenciális formulával, $T$
bármely képlet egyenértékű egy univerzális formulával, $T$
bármely modell diagramjával kombinálva egy teljes elméletet generálunk. $T$

Ha nem üres halmaz, akkor az összes alrendszer között, beleértve a -t is , ott van a legkisebb, amit generált halmaznak nevezünk . Az elemi alrendszerekre általános esetben egy ilyen állítás nem igaz. $X\subseteq |A|$ $A$ $x$ $x$

Egy elméletről azt mondjuk, hogy termikus Skolem-függvényei vannak, ha minden képlethez létezik egy tag, és a képlet az elméletből következik . Más szóval, ha van olyan elem, amelyre a képlet igaz, akkor a .-t vehetjük ennek az elemnek . Ha egy elméletnek termikus Skolem-függvényei vannak, akkor modellteljes. Minden elméletnek van egy kiterjesztése , amely termikus Skolem függvényekkel rendelkezik. Ebben az esetben az elmélet minden modellje az elmélet modelljévé gazdagítható . $T$ $\varphi (x,\;{\bar y})$ $t_{\varphi }({\bar y})$ $T$ $(\forall {\bar y})((\exists x)\varphi (x,\;{\bar y})\to \varphi (t_{\varphi }({\bar y}),\;{\ bár y}))$ $\varphi (x,\;{\bar y})$ $t({\bar y})$ $T$ $T^{s}$ $A$ $T$ $A^{s}$ $T^{s}$

A Löwenheim-Skolem „fel” tétel kimondja, hogy ha egy algebrai kardinalitási rendszer nem kisebb, mint , akkor bármely olyan kardinalitás elemi kiterjesztése van, amely nagyobb vagy egyenlő vele . $A$ $\alpha =|Th(A)|$ $A$ $\alpha$

A Löwenheim-Skolem „lefelé” tétel: ha egy és számú algebrai rendszer , akkor és között tetszőleges számosságú elemi alrendszerei vannak . $A$ $\alpha$ $\beta =|Th(A)|$ $A$ $\beta$ $\alpha$

Axiomatizálhatóság és stabilitás

A képletek halmazát egy elmélet axiómahalmazának nevezzük, ha az a következmények halmaza . Konkrétan önmaga axiómák halmaza önmagának. Ha egy elméletnek véges axiómakészlete van, akkor azt mondjuk, hogy véges axiomatizálható. $A$ $T$ $T$ $A$ $T$ $T$

Az algebrai rendszerek gyűjteményeit osztályoknak nevezzük. Az algebrai rendszerek egy osztályát axiomatizálhatónak nevezzük, ha valamely elmélet modelljeinek halmaza . Ebben az esetben a for axiómák halmazát az axiómák halmazának is nevezik . Egy osztály akkor és csak akkor véges axiomatizálható, ha maga és komplementere is axiomatizálható. $K$ $T$ $T$ $K$ $K$ $K$

Egy elméletet akkor nevezünk stabilnak a szuperrendszerek (illetve alrendszerek) vonatkozásában, ha bármely algebrai rendszerre az következik és (illetve, ), hogy . Egy elmélet akkor és csak akkor stabil az alrendszerek tekintetében, ha univerzális képletekkel axiomatizálható. Egy elmélet akkor és csak akkor stabil a szuperrendszerek tekintetében, ha egzisztenciális formulákkal axiomatizálható. $T$ $A$ $A\ modellek T$ $B\subseteq A$ $A\subseteq B$ $B\ modellek T$ $T$ $T$

Egy elméletet akkor mondunk stabilnak a homomorfizmusok tekintetében, ha bármely algebrai rendszerből az következik , hogy , ha a homomorf képe . Egy elmélet akkor és csak akkor stabil homomorfizmusok esetén, ha pozitív képletekkel (vagyis olyan formulákkal, amelyek nem tartalmaznak implikációt és tagadást) axiomatizálhatóak. $T$ $A$ $A\ modellek T$ $B\ modellek T$ $B$ $A$ $T$

Láncok

A lánc algebrai rendszerek halmaza, lineárisan rendezve az "alrendszernek lenni" relációval. Ha a lánc elemei esetében teljesül az "elemi alrendszernek lenni" tulajdonság, akkor a láncot eleminek is nevezik.

Az algebrai rendszerek láncának egyesítése egy új, azonos aláírású rendszert ad, amely a lánc összes elemének szuperrendszere lesz. Amikor egy elemi láncot egységesítünk, ez az egyesülés elemi szuperrendszer lesz, következésképpen minden képlet igazsága megmarad benne.

Bármilyen lánc kombinálásakor (beleértve a nem elemieket is), a -képletek igazsága megmarad, és az ellenkezője is igaz - ha egy képlet bármilyen lánc kombinálásakor megőrzi igazságát, akkor ekvivalens valamilyen -képlettel. $\mindenre \létezik$ $\mindenre \létezik$

Az -képletekkel axiomatizálható elméleteket induktívnak nevezzük. A Chen-Los-Sushko tétel szerint egy elmélet akkor és csak akkor induktív, ha a láncok egyesülése szempontjából stabil. Az induktív elmélet fontos példája a rögzített karakterisztikájú mezők elmélete. $\mindenre \létezik$ $T$

A láncmódszer az egyik legfontosabb eszköz a kívánt tulajdonságokkal rendelkező algebrai rendszerek felépítéséhez.

Ultraproducts

Legyen ez a nyelv. az algebrai rendszerek családja, . Az algebrai rendszerek közvetlen szorzata , egy algebrai rendszer , ahol minden predikátum szimbólumhoz $L$ $\{{\mathcal {A}}_{i}\}_{{i\in I}}$ ${\mathcal {A}}_{i}=\langle M_{i},\;L\rangle$ ${\mathcal {A}}_{i}$ $i\in I$ $\prod _{{i\in I}}{\mathcal {A}}_{i}=\left\langle \prod _{{i\in I}}A_{i},\;L\right\rangle$ $P\in L$

\prod _{{i\in I}}{\mathcal {A}}_{i}\models P(a_{1},\;\ldots ,\;a_{{n_{P}}})\Leftrightarrow {\mathcal {A}}_{i}\models P(a_{{1i}},\;\ldots ,\;a_{{n_{P}i}})

mindegyikhez ;

i\in I

minden funkciószimbólumhoz $f\in L$

(f(a_{1},\;\ldots ,\;a_{{n_{f}}}))_{i}=f(a_{{1i}},\;\ldots ,\;a_{{ n_{f}i}})

és minden állandó szimbólumra $c\in L$

(c)_{i}=c.

Legyen egy szűrő . Határozzuk meg a kapcsolatot . Bemutatjuk a jelölést: $D$ $én$ $\prod _{{i\in I}}A_{i}$ $a\sim _{D}b\Leftrightarrow \{i\in I\mid a_{i}=b_{i}\}\in D$

a/D=\{b\mid b\sim _{D}a\}

\prod _{{i\in I}}A_{i}/D=\left\{a/D\mid a\in \prod _{{i\in I}}A_{i}\right\}.

Egy algebrai rendszert a következőképpen definiálunk. ${\mathcal {A}}=\left\langle \prod _{{i\in I}}A_{i}/D,\;L\right\rangle$

Állítsuk be a predikátum szimbólumot $P\in L$

{\mathcal {A}}\models P(a_{1},\;\ldots ,\;a_{{n_{P}}})\Leftrightarrow \{i\mid {\mathcal {A}}_{i }\models P(a_{{1_{i}}},\;\ldots ,\;a_{{n_{P}i}})\}\in D,

minden funkciószimbólumhoz $f\in L$

f(a_{1}/D,\;\ldots ,\;a_{{n_{f}}}/D)=f(a_{1},\;\ldots ,\;a_{n})/D

és az állandó szimbólumokhoz $c\in L$

c=c/D.

Az így definiált algebrai rendszert a szűrő a rendszerek szűrt szorzatának nevezi , és jelöli . Ha egy ultraszűrő , akkor ultraterméknek nevezzük , ha minden egybeesik és egyenlő , akkor ultrateljesítménynek nevezzük és jelöljük . $\mathcal{A}$ ${\mathcal {A}}_{i}$ $D$ $\prod _{{i\in I}}{\mathcal {A}}_{i}/D$ $D$ $\prod _{{i\in I}}{\mathcal {A}}_{i}/D$ ${\mathcal {A}}_{i}$ $\mathcal{A}$ $\prod _{{i\in I}}{\mathcal {A}}_{i}/D$ $\mathcal{A}$ ${\mathcal {A}}^{I}/D$

Az ultratermékek fő tulajdonsága, hogy megőrzik az összes mondatot:

Elk tétele. Legyen egy nyelv, legyen a nyelv algebrai rendszereinek családja , és legyen ultraszűrő a felett . Ezután bármely nyelvi képlethez és bármely elemsorozathoz $L$ $\{{\mathcal {A}}_{i}\}_{{i\in I}}$ $L$ $D$ $én$ $\varphi (\overline {x})$ $L$ ${\overline {a}}$ $\prod _{{i\in I}}A_{i}$

\prod _{{i\in I}}{\mathcal {A}}_{i}/D\models \varphi (\overline {a}/D)\Leftrightarrow \{i\in I\mid {\mathcal {A}}_{i}\models \varphi (\overline {a}_{i})\}\in D.

A tömörségi tétel a következőképpen is megfogalmazható.

A tömörségi tétel. Ha egy képlethalmaz lokálisan kielégíthető valamelyik osztályban , akkor kielégíthető a -ból származó rendszerek néhány ultratermékében . ${\mathbf {K}}$ ${\mathbf {K}}$ [2]

Típusok

Kategorikus

A véges vagy megszámlálható aláírású egyenlőséggel rendelkező elméletet kategorikusnak mondjuk megszámlálható számosságban , ha minden megszámlálható normál modellje izomorf . A kategorikusságot egy adott megszámlálhatatlan hatványban hasonlóképpen határozzuk meg. $T$

A magasabb rendű modellek elmélete

Véges modellelmélet

Jegyzetek

↑ Keisler G., Chen C. Modellelmélet . — M.: Mir, 1977. — p. tizennégy.
↑ Ershov, 1987 , p. 117.

Irodalom

Ershov Yu. L. , Paljutyin E. A. Matematikai logika. — M .: Nauka, 1987. — 336 p.
Útmutató a matematikai logikáról. 1. rész. Modellek elmélete / szerk. J. Barwise. — M .: Nauka, 1982. — 392 p.
Keisler, G. J.; Chen Chun, Chen. Folyamatos modellek elmélete. - M . : Mir, 1971. - 184 p.
Keisler, G. J.; Chen Chun, Chen. A modellek elmélete. — M .: Mir, 1977. — 616 p.

Szótárak és enciklopédiák

Bibliográfiai katalógusokban
BNF : 119323610 GND : 4114617-7 J9U : 987007541020605171 LCCN : sh85086421 LNB : 000101674 NDL : 00567757 NKC : ph799924

Logikák

Filozófia • Szemantika • Szintaxis • Történelem

Logikai csoportok

klasszikus logika	Arisztotelészi logika propozíciós logika Elsőrendű logika Másodrendű logika magasabb rendű logika
matematikai logika	halmazelmélet Modellelmélet Kiszámíthatóság elmélet Bizonyításelmélet és konstruktív matematika Lineáris logika formális rendszer természetes következtetés Sorozatszámítás Logikai algebra Releváns logika Deontikus logika intuicionista logika Lambek kalkulus
Nem klasszikus logika	intuicionizmus zavaros logika Szubstrukturális logika logika Leírás logika Többértékű logika Logikai szintézis Kötési logika Időbeli logika Modális logika ( Hibrid logika ) episztemikus logika
Filozófiai logika	Kritikus gondolkodás informális logika deduktív érvelés

Alkatrészek

Logikai szimbólumok listája