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 .
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 .
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 ).
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 .
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.
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 .
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).
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.
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]
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.
![]() | ||||
---|---|---|---|---|
|
Logiikka | |||||||||
---|---|---|---|---|---|---|---|---|---|
Filosofia • Semantiikka • Syntaksi • Historia | |||||||||
Logiikkaryhmät |
| ||||||||
Komponentit |
| ||||||||
Luettelo loogisista symboleista |