Äärellisten mallien teoria

Laskuharjoitukset

Harjoitustehtävät ovat omalla sivullaan.

Kurssikuvaus

Malliteoriassa tietyntyyppisiä matemaattisia struktuureja, malleja, tutkitaan matemaattisen logiikan välinein. Malleja ovat niin algebralliset struktuurit, kuten ryhmät, kunnat ja renkaat, kuin diskreetissä matematiikassa tutut verkot, puut ja lineaariset järjestykset. Äärelliset mallit ovat kiinnostavia diskreetin matematiikan ja tietojenkäsittelyn kannalta, minkä vuoksi äärellisten mallien teoriaa voi luonnehtia nimenomaan diskreetin matematiikan malliteoriaksi, kun taas klassinen, äärettömiä malleja tutkiva malliteoriaa on algebrallisesti suuntautuneempi.

Kurssilla tutustutaan ensin mallin käsitteeseen ja siihen, miten kahden mallin samanlaisuutta voi mitata eri tavoilla: homomorfisuudella, isomorfisuudella ja kombinatorisilla peleillä. Loogisiin käsitteisiin paneuduttaessa huomataan, että kombinatoriset pelit ovat suorassa yhteydessä logiikkaan. Malleja voi ajatella myös tietokoneohjelmien syötteinä eli relationaalisina tietokantoina; tämän idean kehittäminen johtaa deskriptiiviseen vaativuusteoriaan. Kurssin lopuksi käsitellään lyhyesti ensimmäisen kertaluvun logiikan 0-1-lakia ja yleistettyjä kvanttoreita.

Sisältö

I MALLIT

  1. Relaatiot
  2. Laskutoimitukset
  3. Aakkostot ja mallit
  4. Homomorfismi, isomorfismi

II PELIT

  1. Ehrenfeuchtin ja Fraïssén peli
  2. Helmipeli
  3. EF-pelin ja helmipelin sovelluksia

III LOGIIKAT

  1. Vakiot, muuttujat ja termit
  2. Lauseet ja kaavat
  3. Ensimmäisen kertaluvun logiikka FO ja äärellisen monen muuttujan logiikka FVL
  4. FO:n pelikarakterisointi
  5. FVL:n pelikarakterisointi
  6. Määrittelemättömyystuloksia

IV KUVAILEVAA VAATIVUUSTEORIAA

Vuoden 2008 kurssin eli Juha Kontisen versio luvun lopusta [pdf]

  1. Sanamallit ja äärellinen automaatti
  2. Monadinen toisen kertaluvun logiikka ja Büchin lause
  3. Turingin kone ja vaativuusluokat
  4. Kiintopistelogiikka
  5. PTIME:n karakterisointi

V 0-1-LAIT

VI YLEISTETYT KVANTTORIT (seminaarimuotoiset muistiinpanot [ps], [pdf])

Kurssimateriaali

Luennot kokonaisuudessaan (versio 2.1) [ps] [pdf]. Sisällyksen yhteydessä on materiaalia, joka luentojen versioon 2.1 nähden uutta tai ylimääräistä.

Oppikirjoista kurssia tukee parhaiten Ebbinghaus, Flum: Finite model theory, Springer 1995. Kirja käsittelee äärellisten mallien teoriaa selvästi laveammin kuin kurssi, ja kattaa kurssin lukujen aihepiirit täysin viimeistä lukua lukuun ottamatta. Hyvää kirjallisuutta ovat myös Immerman: Descriptive complexity, Springer 1999, ja Libkin: Elements of finite model theory, Springer 2004.

Äärellisistä malleista pidetystä tiiviskurssista on luentomoniste Väänänen: shortcourse.pdf. Verkon kautta voi saada myös luentokalvot Lauri Hellan Aix-en-Provencessa pitämästä kesäkurssista.

Logiikan ryhmä Äärellisten mallien teoria Suomessa