In English

Äärellisten mallien teoria

Luennot

Keväällä 2013 Ph.D. Pietro Galliani

Info

Kurssin infosivu sisältää kurssin hallinnolliset tiedot, ts. tiedot luentoajoista ja -paikoista, kokeista sekä laskuharjoituksista.

Kurssin asema opinnoissa

Kurssi on matemaattisen logiikan linjan valinnainen, ja muiden linjojen vapaasti valittava laudatur-erikoiskurssi.

Laajuus 10 op

Laskuharjoitukset

Laskuharjoitukset pitää myös Pietro Galliani.

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.0) [ps] [pdf]. Sisällyksen yhteydessä on materiaalia, joka luentojen versioon 2.0 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.

Esitiedot:

Kurssi vaatii ennen kaikkea tietyn määrän matemaattista kypsyyttä. Olisi suotavaa, että ainakin yksi kursseista Logiikka I, Algebra I tai Tietorakenteet (tkt) olisi suoritettuna.

Matematiikan laitos Äärellisten mallien teoria Suomessa Matemaattisen logiikan opetus

  Suomeksi

Finite-model Theory

Lectures

Spring 2013 PhD Pietro Galliani.

Info

See infopage of the course for various administrative information such as the lecture times and rooms.

Course Status

The course is among the alternative choices for students specializing in mathematical logic and can be included in the freely chosen courses for other students majoring in mathematics. There will be a final exam, whose date will be fixed later.

Credits: 10 points

Course Description

Model theory studies a certain type of mathematical objects, so-called models, with logical tools. Both algebraic structures, like groups, rings and fields, and objects studied in discrete mathematics, like graphs, trees and linear orderings, are examples of models. The interest in finite models is largely motivated by connections with discrete mathematics and theoretical computer science; therefore one could describe finite-model theory as model theory for discrete mathematics. Classical model theory, on the other hand, studies infinite models almost exclusively, and it is more algebraically oriented.

The course starts with the introduction of the general concept of a model and different ways of measuring the similarity of given models: homomorphisms, isomorphisms and combinatorial games. The close relationship between the games and some logical concepts is studied next. Finite models can also be regarded as inputs to a computer programme (a finite model is practically the same thing as a relational database), which leads to descriptive complexity theory. Finally, we look briefly at the zero-one-law of first-order logic and at generalized quantifiers.

Contents

I MODELS

  1. Relations
  2. Arithmetical operations
  3. Vocabularies and models
  4. Homomorphism, isomorphism
  5. Ehrenfeucht-Fraïssé-game
  6. Pebble game
  7. Applications of EF-game and pebble game

II LOGICS

  1. Constants, variables and terms
  2. Formulas and sentences
  3. First-order logic FO and finite-variable logic FVL

III GAMES

  1. Game characterization of FO
  2. Game characterization of FVL
  3. Undefinability results

IV DESCRIPTIVE COMPLEXITY THEORY

  1. Word models and finite automata
  2. Monadic second-order logic and Büchi's Theorem
  3. Turing machines and complexity classes
  4. Fixpoint logic
  5. Characterization of PTIME

V 0-1-LAWS

VI GENERALIZED QUANTIFIERS

Course material

The lecture notes will be available from this page later on. In addition, the following textbook is recommended: Ebbinghaus, Flum: Finite model theory, Springer 1995. The book contains much more material than the course and covers everything in it except for the last section. The textbooks Immerman: Descriptive complexity, Springer 1999. and Libkin: Elements of finite model theory, Springer 2004 are also recommendable.

The notes for a short course on finite models by Jouko Väänänen are available: shortcourse.pdf. You can also obtain the slides of Lauri Hella's summer course in Aix-en-Provence.

Department of Mathematics Finite model theory in Finland Teaching of mathematical logic