Gradu-aiheita logiikasta

Stationaariset joukot

Joukko C numeroituvia ordinaaleja on CUB jos se on rajottamaton (sisältää mielivaltaisen suuria numeroituvia ordinaaleja) ja suljettu (sisältää jokaisen numeroituvan ordinaalin jota kohden C:stä löytyy suppeneva jono). Joukot jotka sisältävät CUB joukon muodostavat mielenkiintoisen filtterin, mutta tämä ei ole ultrafiltteri. On joukkoja jotka eivät sisällä CUB joukkoa ja komplementtikaan ei sisällä CUB joukkoa. Tällaisia joukkoja kutsutaan stationaarisiksi. Gradussa on tarkoitus tutkia stationaaristen joukkojen perusominaisuuksia. Sopivia kursseja: Joukko-opin alkeet, aksiomaattinen joukko-oppi.

Logiikkaa Java:lla

Laitoksella laaditaan Java-appletteja matematiikan opetuksen ja tutkimuksen tueksi. Logiikka on eräs kohde. Gradussa on tarkoitus perehtyä matemaattisesti sovittuun osaan tätä projektia sekä laatia algoritmi ja vastaava Java-ohjelma projektin osaksi. Sopivia kursseja: Logiikka I, matemaattinen logiikka.

Melkein vapaat ryhmät

Abelin ryhmä on melkein vapaa, jos sen jokainen pienempää mahtavuutta oleva aliryhmä on vapaa. Gradussa konstruoidaan aluksi epävapaa melkein vapaa ryhmä. Kysymystä, miten lähellä vapautta voi melkein vapaa ryhmä olla, on tutkittu mm. Helsingissä. Sopivia kursseja: Matemaattinen logiikka, joukko-opin alkeet, malliteoria.

Vahvat ideaalit

Äärettömällä kardinaalilla on osajoukkoja, jotka ovat äärettömiä, mutta joukko-opilliselta kannalta "pieniä". Niitä tutkitaan erilaisten ideaalien avulla. Tyypillinen pieni joukko on seuraajaordinaalien joukko tai yleisemmin ns. ei-stationaarinen joukko. Ideaali on vahva, jos sen alkioita voidaan yhdistellä tietyillä operaatioilla menemättä ulos ideaalista. Esimerkki tällaisesta on ideaali jonka komplementissa on sigma-suljettu tiheä osajoukko. Sopivia kursseja: Joukko-opin alkeet, aksiomaattinen joukko-oppi.

Spesiaalit puut

Ajatellaan puuta, jonka korkeus on ylinumeroituva, mutta jossa ei ole ylinumeroituvaa oksaa. Souslin- ja Aronszajn-puut ovat tällaisia. Puuta sanotaan spesiaaliksi, jos siitä voidaan määritellä kasvava kuvaus rationaalilukujen järjestettyyn joukkon. Spesiaalit puut ovat mielenkiintoisia, koska niin sanotusta Martinin aksioomasta seuraa, että kaikki mahtavuutta aleph_1 olevat puut, joissa ei ole ylinumeroituvaa oksaa, ovat spesiaaleja. Gradussa on tarkoitus tutkia spesiaalien puiden perusominaisuuksia ja todistaa Todorcevicin tulos: jos ei-spesiaalissa puussa on määritelty funktio f siten että f(t)< t kaikilla t (paitsi jos t on juuri), niin on olemassa ei-spesiaali alipuu, jossa f on vakio. Sopivia kursseja: Joukko-opin alkeet, aksiomaattinen joukko-oppi.

Kvanttoreiden eliminointi reaalilukujen aritmetiikassa

Alfred Tarskin kuuluisan tuloksen mukaan reaalilukujen kunta sallii kvanttoreiden eliminoinnin. Tämä tarkoittaa sitä, että jokainen predikaattilogiikan kaava on reaalilukujen kunnassa ekvivalentti kvanttorittoman kaavan kanssa. Tällä tuloksella on sovellutuksia ja yhtymäkohtia logiikan ulkopuolellakin analyyttisestä geometriasta tietokantojen teoriaan. Logiikan sisällä se merkitsi ns. geometrisen malliteorian alkua. Lause voidaan todistaa suoraan analyyttisillä menetelmillä tai malliteoreettisesti erikoistapauksena yleisemmistä tuloksista. Sopivia kursseja: Matemaattinen logiikka, malliteoria.

Ehrenfeucht-Fraisse peli

Tätä peliä pelataan kahden pelaajan kesken, joista toinen (ns. duplicator) yrittää osoittaa, että annetut kaksi mallia ovat isomofiset. Vastapelaaja (ns. spoiler) yrittää puolestaan osoittaa, että mallit ovat ei-isomorfiset. Ehrenfeucht-Fraisse peli on tehokas väline kautta logiikan. Sitä voi käyttää myös tietokantakielien tehokkuuden mittaamiseen. Sopivia kursseja: Matemaattinen logiikka, Logiikka I, malliteoria, Äärellisten mallien teoria.

Yleistetty kvanttori "Useimmille x"

Predikaattilogiikassa voidaan sanoa "(on olemassa x)A(x)" ja "(kaikille x)A(x)", mutta ei "(useimmille x)A(x)". Kyseessä on ns. yleistetty kvanttori. Yleistettyjen kvanttoreiden logiikka voi poiketa huomattavastikin tavallisten kvanttoreiden "on olemassa" ja "kaikille" logiikasta. Aiemmin yleistettyjä kvanttoreita tutkittiin äärettömillä malleilla. Viime aikoina kiinnostus on kohdistunut äärellisiin malleihin ja sovellutuksiin tietokantojen teoriassa ja luonnollisen kielen semantiikassa. Sopivia kursseja: Matemaattinen logiikka, malliteoria, Äärellisten mallien teoria.

Implisiittinen määriteltävyys

Matematiikassa esiintyy usein tilanne jossa yksi käsite määrää yksikäsitteisesti toisen. Esimerkiksi reaalifunktio määrää nollakohtiensa joukon, tason osajoukko määrää projektionsa kummallakin koordinaattiakselilla, jne. Sanomme, että predikaattilogiikan lause F, jossa esiintyy vain predikaattisymbolit P ja R, määrittelee predikaattisymbolin R implisiittisesti, jos missä tahansa kahdessa F:n mallissa, joissa universumi ja P:n tulkinta ovat samat, on myös R:n tulkinta sama. Eräs predikaattilogiikan klassisia perustuloksia on Beth:in määriteltävyyslause, joka sanoo, että jos tällainen F määrittelee R:n implisiittisesti, niin on olemassa kaava G(x), jossa R ei esiinny lainkaan, siten että kaikissa F:n malleissa pätee (kaikille x)(G(x)<==>R(x)). Tämä tulos on perusta yleisemmälle käsitteiden välisiä; suhteita koskevalle tutkimukselle. Sopivia kursseja: Matemaattinen logiikka, malliteoria.

Sähköpostiosoite:

WWW-sivu: http://www.math.helsinki.fi/logic/people/jouko.vaananen/