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 .

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 .

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.

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.

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 .

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:

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.

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 .

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 .

Löwenheim-Skolem "alas" -lause: jos  on algebrallinen kardinaliteettijärjestelmä ja , niin sillä on minkä tahansa kardinalisuuden alkeisalijärjestelmiä välillä ja .

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.

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.

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.

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).

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.

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.

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

jokaiselle ;

jokaiselle funktiosymbolille

ja jokaiselle vakiosymbolille

Olkoon  suodatin päälle . Määritellään suhde . Esitellään merkintä:

,

Määrittelemme algebrallisen järjestelmän seuraavasti.

Asetetaan predikaattisymboli

jokaiselle funktiosymbolille

ja vakiosymboleille

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 .

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

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 . [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.

Korkeamman asteen mallien teoria

Finite Model Theory

Muistiinpanot

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

Kirjallisuus