Mallin teoria

Malliteoria on matemaattisen logiikan haara , joka tutkii muodollisten kielten ja niiden tulkintojen tai mallien välistä suhdetta . Nimimalliteorian ehdotti ensimmäisen kerran Alfred Tarski vuonna 1954 . Malliteorian pääasiallinen kehitystyö oli Tarskin, Maltsevin ja Robinsonin teoksissa .

Origins

Malliteoria on omistettu syntaksin ja semantiikan välisen perussuhteen tutkimukselle . Samaan aikaan muodollinen kieli vastaa ensimmäistä siinä ja malli vastaa toista - matemaattista rakennetta , joka mahdollistaa jonkinlaisen kuvauksen tällä kielellä. Malliteoria syntyi olemassa olevien lähestymistapojen yleistyksenä algebraan ja matemaattiseen logiikkaan liittyvien metamatemaattisten ongelmien ratkaisemiseksi . Nämä lähestymistavat itsessään ovat olleet olemassa pitkään, mutta pitkään niitä ei ole käsitelty kokonaisuutena, yhden loogis-filosofisen paradigman puitteissa . Luonnollinen esimerkki tässä yhteydessä on ongelma, joka liittyy Eukleideen viidenteen rinnakkaisten suorien postulaattiin. Vuosisatojen ajan matemaatikot eivät pystyneet todistamaan sen totuutta, kunnes 1800-luvulla Bolyai ja Lobatševski rakensivat ei-euklidisen geometrian , mikä osoitti, että rinnakkaispostulaattia ei voida todistaa eikä kumota. Malliteorian kannalta tämä tarkoittaa, että aksioomijärjestelmä ilman viidettä postulaattia mahdollistaa useita erilaisia malleja, eli tässä tapauksessa useita vaihtoehtoja geometrian toteuttamiseen.

Näin ollen alkuperäinen malliteoria kasvoi sellaisista matematiikan haaroista kuin logiikka , universaali algebra , joukkoteoria olemassa olevan tiedon yleistyksenä ja laajentamisena. Siksi malliteorian ensimmäiset tulokset ilmestyivät kauan ennen sen "virallista" ilmestymistä. Löwenheim-Skolem-lausetta ( 1915 ) pidetään ensimmäisenä tällaisena tuloksena [1] . Toinen merkittävä tulos oli Gödelin ( 1930 ) ja Maltsevin ( 1936 ) todentama kompaktisuuslause .

Klassinen ensimmäisen asteen malliteoria

Klassisen ensimmäisen asteen logiikan malliteoria on historiallisesti ensimmäinen ja kehittynein esimerkki malliteoreettisesta lähestymistavasta. Tässä mallien roolia ovat joukot , jotka edustavat muuttujien mahdollisten arvojen aluetta . Funktiosymbolit tulkitaan niitä vastaavan ariteon operaatioiksi ja predikaatit suhteiksi ( katso lisätietoja kohdasta Ensimmäisen asteen logiikka, tulkinta ).

Kompaktiteettilause

Yksi tärkeimmistä malliteorian työkaluista on Maltsevin todistama kompaktisuuslause , jonka mukaan ensimmäisen kertaluvun kaavojen joukolla on malli silloin ja vain, jos mallissa on tämän kaavojen joukon jokainen äärellinen osajoukko.

Lauseen nimi tulee siitä, että se voidaan sanoa väittämäksi Kivi-avaruuden tiiviydestä .

Kompaktiteettilauseesta seuraa, että jotkin käsitteet eivät ole ilmaistavissa ensimmäisen asteen logiikassa. Esimerkiksi äärellisyyden tai laskettavuuden käsitteitä ei voi ilmaista millään ensimmäisen kertaluvun kaavoilla tai edes niiden joukoilla: jos kaavajoukolla on mielivaltaisen suuria äärellisiä malleja, niin sillä on myös ääretön malli. Vastaavasti teorialla, jolla on ääretön malli, jonka kardinaalisuus ei ole pienempi kuin allekirjoituksen kardinaliteetti, on malleja mistä tahansa suuremmasta kardinaalisuudesta.

Kompaktiteettilausetta voidaan soveltaa klassisten teorioiden, kuten alkearitmeettisen tai laskennan , ei-standardimallien rakentamiseen .

Teoriat ja alkeisekvivalenssi

Teoria on johdettavuuden suhteen suljettu (lyhyesti sanottuna suljettu) kaavojoukko, eli sellainen joukko , että jos kaava seuraa kohdasta , niin se kuuluu joukkoon . $T$ $T$ $\varphi$ $T$ $\varphi$ $T$

Teoriaa, jolla on ainakin yksi malli, kutsutaan johdonmukaiseksi, muita teorioita ristiriitaisiksi.

Teoriaa kutsutaan täydelliseksi, jos jollekin kaavalle teoria sisältää tai . Jos on algebrallinen järjestelmä, niin suljetuilla kaavoilla oleva tosi-joukko muodostaa täydellisen teorian - järjestelmän teorian , jota merkitään . $T$ $\varphi$ $\varphi$ $\lnot \varphi$ $A$ $A$ $A$ $Th(A)$

Jos algebrallisissa järjestelmissä ja samat suljetut kaavat ovat tosia, niin ja sanotaan olevan elementaarisesti ekvivalentteja. Siten ja ovat elementaarisesti ekvivalentteja, jos ja vain jos ne ovat saman täydellisen teorian malleja. $A$ $B$ $A$ $B$ $A$ $B$

Jos täydellisellä teorialla on äärellinen malli , niin teorian kaikki mallit ovat isomorfisia , erityisesti ne sisältävät saman määrän alkioita. Siksi äärellisissä algebrallisissa järjestelmissä alkeekvivalenssin ja isomorfismin käsitteet ovat samat. $T$ $A$ $T$ $A$

Alijärjestelmät ja Löwenheim-Skolem-lauseet

Algebrallista järjestelmää kutsutaan algebrallisen järjestelmän alijärjestelmäksi, jos jokaisen allekirjoitussymbolin tulkinta in on sen tulkinnan rajoitus joukkoon . Osajärjestelmää kutsutaan alkeisjärjestelmäksi mille tahansa kaavalle ja mille tahansa se pätee: jos ja vain jos . Järjestelmää kutsutaan näissä tapauksissa järjestelmän (alkeis)laajennukseksi . $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$

Alkeisosajärjestelmä vastaa alkeellisella tasolla . Teorioita, joiden malleille päinvastoin on myös totta – jokainen elementaarisesti vastaava osajärjestelmä on alkeisosajärjestelmä – kutsutaan mallin täydellisiksi. Teorian mallin täydellisyys vastaa jokaista seuraavista ominaisuuksista: $B$ $A$ $T$

mikä tahansa kaava on ekvivalentti eksistentiaalisen kaavan kanssa, $T$
mikä tahansa kaava vastaa yleiskaavaa, $T$
yhdistäminen minkä tahansa mallin kaavioon tuottaa täydellisen teorian. $T$

Jos on ei-tyhjä joukko, niin kaikista alijärjestelmistä , mukaan lukien , on pienin, jota kutsutaan generoiduksi joukoksi . Alkeisalijärjestelmille tällainen väite ei yleensä pidä paikkaansa. $X\subseteq |A|$ $A$ $X$ $X$

Teorialla sanotaan olevan termisiä Skolem-funktioita, jos jokaiselle kaavalle on olemassa termi ja kaava seuraa teoriasta . Toisin sanoen, jos on elementti, jolla kaava on tosi, niin . voidaan pitää tämän elementin . Jos teoriassa on termisiä Skolem-funktioita, se on mallina valmis. Jokaisella teorialla on laajennus , jossa on termisiä Skolem-funktioita. Tässä tapauksessa jokainen teorian malli voidaan rikastaa teorian malliksi . $T$ $\varphi (x,\;{\bar y})$ $t_{\varphi }({\bar y})$ $T$ $(\forall {\bar y})((\olemassa x)\varphi (x,\;{\bar y})\to \varphi (t_{\varphi }({\bar y}),\;{\ baari y}))$ $\varphi (x,\;{\bar y})$ $t({\bar y})$ $T$ $T^{s}$ $A$ $T$ $A^{s}$ $T^{s}$

Löwenheim-Skolem- lause "ylös" sanoo, että jos on algebrallinen kardinaalisuusjärjestelmä, joka on vähintään , niin sillä on alkeislaajennukset mille tahansa kardinaalisuudesta, joka on suurempi tai yhtä suuri kuin . $A$ $\alpha =|Th(A)|$ $A$ $\alpha$

Löwenheim-Skolem "alas" -lause: jos on algebrallinen kardinaliteettijärjestelmä ja , niin sillä on minkä tahansa kardinalisuuden alkeisalijärjestelmiä välillä ja . $A$ $\alpha$ $\beta =|Th(A)|$ $A$ $\beeta$ $\alpha$

Aksiomatisoitavuus ja vakaus

Kaavojen joukkoa kutsutaan teorian aksioomijoukoksi, jos se on joukko seurauksia . Erityisesti itse on joukko aksioomia itselleen. Jos teorialla on äärellinen joukko aksioomeja, sen sanotaan olevan äärellisesti aksiomatisoitavissa. $A$ $T$ $T$ $A$ $T$ $T$

Algebrallisten järjestelmien kokoelmia kutsutaan luokiksi. Algebrallisten järjestelmien luokkaa kutsutaan aksiomatisoitaviksi, jos se on joukko jonkin teorian malleja . Tässä tapauksessa aksioomijoukkoa for kutsutaan myös aksioomien joukkoksi for . Luokka on äärellisesti aksiomatisoitavissa, jos ja vain jos sekä itse että sen komplementti ovat aksiomatisoitavissa. $K$ $T$ $T$ $K$ $K$ $K$

Teoriaa kutsutaan stabiiliksi superjärjestelmien (vastaavasti alijärjestelmien) suhteen, jos jollekin algebralliselle järjestelmälle seuraa ja (vastaavasti, ), että . Teoria on stabiili alijärjestelmien suhteen silloin ja vain, jos se on aksiomatoitavissa universaalien kaavojen avulla. Teoria on stabiili superjärjestelmien suhteen silloin ja vain, jos se on aksiomatisoitavissa eksistentiaalisten kaavojen avulla. $T$ $A$ $A\ mallit T$ $B\subseteq A$ $A\subseteq B$ $B\mallit T$ $T$ $T$

Teorian sanotaan olevan stabiili suhteessa homomorfismiin, jos mistä tahansa algebrallisesta järjestelmästä seuraa , että , jos on homomorfinen kuva . Teoria on stabiili homomorfismissa silloin ja vain, jos se on aksiomatisoitavissa positiivisilla kaavoilla (eli kaavoilla, jotka eivät sisällä implikaatiota ja negaatiota). $T$ $A$ $A\ mallit T$ $B\mallit T$ $B$ $A$ $T$

Ketjut

Ketju on joukko algebrallisia järjestelmiä, jotka on järjestetty lineaarisesti suhteella "olla alijärjestelmä". Jos ketjun elementeille täyttyy ominaisuus "olla alkeisalijärjestelmä", niin ketjua kutsutaan myös alkeisosajärjestelmäksi.

Algebrallisten järjestelmien ketjun yhdistäminen antaa uuden saman allekirjoituksen järjestelmän, joka on superjärjestelmä ketjun kaikille elementeille. Kun alkeisketju yhdistetään, tämä yhdistäminen on alkeissuperjärjestelmä ja siten kaikkien kaavojen totuus säilyy siinä.

Yhdistäessä mitä tahansa ketjuja (mukaan lukien ei-alkeisketjut) -kaavojen totuus säilyy, ja myös päinvastoin - jos kaava säilyttää totuutensa yhdistettäessä mitä tahansa ketjua, niin se vastaa jotakin -kaavaa. $\kaikki \olemassa$ $\kaikki \olemassa$

Teorioita, jotka voidaan aksiomatisoida -kaavojen avulla, kutsutaan induktiivisiksi. Chen-Los-Sushko-lauseen mukaan teoria on induktiivinen silloin ja vain, jos se on stabiili ketjujen liiton suhteen. Tärkeä esimerkki induktiivisesta teoriasta on kiinteiden ominaisuuksien kenttien teoria. $\kaikki \olemassa$ $T$

Ketjumenetelmä on yksi tärkeimmistä työkaluista haluttujen ominaisuuksien omaavien algebrallisten järjestelmien rakentamisessa.

Ultraproducts

Olkoon se kieli. on perhe algebrallisia järjestelmiä, . Algebrallisten järjestelmien suora tulo , on algebrallinen järjestelmä , jossa jokaiselle predikaattisymbolille $L$ $\{{\mathcal {A}}_{i}\}_{{i\in I}}$ ${\mathcal {A}}_{i}=\langle M_{i},\;L\rangle$ ${\mathcal {A}}_{i}$ $minä\minässä$ $\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}})

jokaiselle ;

minä\minässä

jokaiselle funktiosymbolille $f\in L$

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

ja jokaiselle vakiosymbolille $c\in L$

(c)_{i}=c.

Olkoon suodatin päälle . Määritellään suhde . Esitellään merkintä: $D$ $minä$ $\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\}.

Määrittelemme algebrallisen järjestelmän seuraavasti. ${\mathcal {A}}=\left\langle \prod _{{i\in I}}A_{i}/D,\;L\right\rangle$

Asetetaan predikaattisymboli $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,

jokaiselle funktiosymbolille $f\in L$

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

ja vakiosymboleille $c\in L$

c=c/D.

Tällä tavalla määriteltyä algebrallista järjestelmää kutsutaan suodattimen järjestelmien suodatetuksi tuotteeksi ja sitä merkitään . Jos on ultrasuodatin , niin sitä kutsutaan ultratuotteeksi , jos kaikki ovat samat ja ovat yhtä suuret , niin sitä kutsutaan ultratehoksi ja merkitään . $\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$

Ultratuotteiden tärkein ominaisuus on, että ne säilyttävät kaikki lauseet:

Elkin lause. Antaa olla kieli, olla kielen algebrallisten järjestelmien perhe ja olla ultrasuodatin . Sitten mille tahansa kielen kaavalle ja mille tahansa elementtisarjalle $L$ $\{{\mathcal {A}}_{i}\}_{{i\in I}}$ $L$ $D$ $minä$ $\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.

Myös kompaktisuuslause voidaan muotoilla seuraavasti.

Kompaktiteettilause. Jos kaavojen joukko on paikallisesti tyydyttävissä jossain luokassa , niin se on tyydytettävissä joissakin järjestelmien ultratuloissa . ${\mathbf {K}}$ ${\mathbf {K}}$ [2]

Tyypit

Kategorinen

Teorian yhtäläisyydellä, jolla on äärellinen tai laskettava allekirjoitus, sanotaan olevan kategorinen laskettavassa kardinaalisuudesta , jos kaikki sen laskettavat normaalimallit ovat isomorfisia . Kategorisuus tietyssä lukemattomassa potenssissa määritellään samalla tavalla. $T$

Korkeamman asteen mallien teoria

Finite Model Theory

Muistiinpanot

↑ Keisler G., Chen C. Malliteoria. - M.: Mir, 1977. - s. neljätoista.
↑ Ershov, 1987 , s. 117.

Kirjallisuus

Ershov Yu. L. , Palyutin E. A. Matemaattinen logiikka. - M .: Nauka, 1987. - 336 s.
Matemaattisen logiikan hakuteos. Osa 1. Mallien teoria / toim. J. Barwise. - M .: Nauka, 1982. - 392 s.
Keisler, G. J.; Chen Chun, Chen. Jatkuvien mallien teoria. - M . : Mir, 1971. - 184 s.
Keisler, G. J.; Chen Chun, Chen. Mallien teoria. - M .: Mir, 1977. - 616 s.

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNF : 119323610 GND : 4114617-7 J9U : 987007541020605171 LCCN : sh85086421 LNB : 000101674 NDL : 00567757 NKC : ph799924

Logiikka

Filosofia • Semantiikka • Syntaksi • Historia

Logiikkaryhmät

klassista logiikkaa	Aristoteelinen logiikka propositionaalinen logiikka Ensimmäisen asteen logiikka Toisen asteen logiikka korkeamman asteen logiikkaa
matemaattinen logiikka	joukko teoria Mallin teoria Lasketettavuuden teoria Todistusteoria ja konstruktiivinen matematiikka Lineaarinen logiikka muodollinen järjestelmä luonnollinen johtopäätös Sekvenssilaskenta Logiikan algebra Asiaankuuluva logiikka Deonttinen logiikka intuitionistinen logiikka Lambek-laskenta
Ei-klassinen logiikka	intuitionismi sumea logiikka Alirakennelogiikka logiikka Kuvauslogiikka Moniarvoinen logiikka Logiikka synteesi Sidontalogiikka Temporaalinen logiikka Modaalinen logiikka ( Hybridilogiikka ) episteeminen logiikka
Filosofinen logiikka	Kriittinen ajattelu epävirallista logiikkaa deduktiivinen päättely

Komponentit

Sieppaus (logiikka)
Todennäköisyys
lausunto
Vähennys / Induktio / Traduction
Todellisuus
induktiivinen päättely
päättely
boolen vakio
Totta
loogista seuraamista
Looginen muoto
Tarpeelliset ja riittävät olosuhteet
Kuvaus
Määritelmä
Korvaus
Paketti
Kiista ( Antinomia )
Synteettinen arviointi / Analyyttinen arviointi
Linkki

Luettelo loogisista symboleista