Löwenheim-Skolem.

Kuten olen aiemminkin kertonut, luennoin syksyllä Matemaattista logiikkaa. Kurssi käsittelee propositio- ja predikaattilogiikkaa. En ole vielä täysin varma, tuleeko kurssille lainkaan modaalilogiikkaa. Ainakaan kovin syvällisesti sitä ei tule olemaan.

Tärkein käsiteltävä logiikka on ensimmäisen kertaluvun predikaattilogiikka. (First order logic, FOL). Predikaattilogiikka koostuu nimensä mukaisesti predikaateista. Predikaatti on väitelause, jolla on jokin määrä parametreja (makuasia, pitääkö niitä olla vähintään yksi, vai sallitaanko nolla). Predikaatti on "tosi" tai "epätosi" riippuen saamastaan parameteristä. Parametri on aina termi. Termejä ovat vakiot ja muuttujat. Predikaattilogiikkaa voidaan laajentaa funktioilla, jos halutaan. Funktiolla on ariteetti, eli sen paramterien määrä. Parametriksi kelpaa mikä hyvänsä termi, ja kun funktion parametrit on annettu, funktio itsessään on termi. Esimerkiksi "x" on termi, ja jos f on funktio joka saa yhden parametrin, myös f(x) on termi. Jos g on funktio, joka saa kaksi parametriä, niin esimerkiksi g(x,f(x)) on termi. Jne.

Atominen predikaattilogiikan kaava on yksittäinen predikaatti, jonka parametreiksi on asetettu termit. Yleisemmin, kaava on joko atominen kaava, kaksi kaavaa jotka on yhdistetty loogisella operaattorilla (ja, tai, implikaatio jne), kaavan negaatio, tai kvantifioitu kaava. Kvantifioitu kaava on muotoa  "∀x A" tai  " ∃x A", missä A on jokin kaava. Tällä tavalla kvantifioidussa kaavassa muuttuja x on sidottu. Jos x ei ole sidottu, se on vapaa.

Kaava, jossa on vapaita muuttujia, voidaan ajatella totuusarvoiseksi funktioksi, jonka totuusarvo riippuu vapaiden muuttujien saamista arvoista. Tällaista kaavaa sanotaan avoimeksi, kun taas kaavaa jossa ei ole vapaita muuttujia, sanotaan suljetuksi kaavaksi. Suljettua kaavaa sanotaan myös lauseeksi.

Kaava sinällään ei kerro meille vielä yhtään mitään, se on pelkkä merkkijono. Vasta tulkinta tekee kaavasta toden tai epätoden. Tulkinta sisältää neljä välttämätöntä osaa. Ensimmäinen on määrittelyjoukko (domain), joka on se joukko johon termit aina viittaavat. Määrittelyjoukko on tavallaan se joukko josta logiikan kaava puhuu. Tämän lisäksi tarvitaan jokaista predikaattia kohden jokin relaatio määrittelyjoukon yli. Kolmanneksi, tarvitaan tulkinta funktioille, ja neljänneksi, täytyy tietää mihin määrittelyjoukon alkoihin mikäkin vakiosymboli viittaa. Tulkinta on äärellinen, jos sen määrittelyjoukko on äärellinen, ja numeroituva, jos sen määrittelyjoukko on numeroituva.

Jos tulkinta tekee kaavan todeksi, niin sanomme, että tulkinta on kaavan malli. Tämä on tavallaan päinvastainen merkitys kuin missä sanaa "malli" yleensä käytetään. Malli on siis struktuuri, joka tekee kaavan todeksi. Jos kaavalla on malli, niin kaava on toteutuva (satisfiable). Jos kaava taas on tosi kaikissa tulkinnoissa, niin kaava on validi, eli tautologia.

Hyvä. Teoria on joukko lauseita eli suljettuja kaavoja; usein tehdään myös rajaus, että teorian pitää olla suljettu loogisen seurauksen suhteen, eli jos T on teoria, ja A kuuluu T:hen, ja B on A:n looginen seuraus, niin myös B kuuluu T:hen. Tämä ei ole meidän kannaltamme juuri nyt olennaista, mutta oletamme että loogiset seuraukset ovat aina mukana teoriassa.

Teoria on toteutuva, jos on olemassa tulkinta, joka tekee kaikki teorian lauseet todeksi samanaikaisesti. Tällainen tulkinta on siis teorian malli.

Löwenheim-Skolemin teoreema sanoo, että jos ensimmäisen kertaluvun numeroituvalla teorialla on malli, sillä on myös numeroituva malli. Tästä seuraa esimerkiksi se, että ensimmäisen kertaluvun teorioilla ei voida määritellä reaalilukujen aksiomia niin, että niistä seuraisi reaalilukujen ylinumeroituvuus. Käytännössä tämä tapahtuu reaalilukujen täydellisyysaksioomassa, joka sanoo, että jokaisella reaalilukujen osajoukolla, jolla on yläraja, on myös pienin yläraja. Koska tämä vaatii käytännössä sellaisen aksiomaskeeman, jossa jokainen osajoukko mainitaan erikseen (tai sitten toisen kertaluvun teorian, jossa on sallittua kvantifioida osajoukkojen yli), kyseessä ei ole mikään varsinainen paradoksi.