Date: Thu, 30 Jun 2022 17:16:33 +0300 (EEST) Message-ID: <1140252373.15872.1656598593905@wiki-1.it.helsinki.fi> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_15871_545914470.1656598593905" ------=_Part_15871_545914470.1656598593905 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Finite model theory, fall 2016

# Fi= nite model theory, fall 2016

=20

Teacher: Juha Kontinen and Jonni Virtema

Scope: 10 cr

Teaching: Four hours of lectures and two hours of exerc= ises per week

Topics: Model theory studies mathematical objects, so-c= alled models, with logical tools. Both algebraic structures, like groups, r= ings 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 th= eoretical computer science; therefore one could describe finite-model theor= y as model theory for discrete mathematics. Classical model theory, on the = other hand, studies infinite models almost exclusively, and it is more alge= braically oriented.

The course starts with an introduction of the general concept of a model= and different ways of measuring the similarity of given models: homomorphi= sms, isomorphisms and combinatorial games. The close relationship between t= he games and some logical concepts is studied next. Finite models can also = be regarded as inputs to a computer programs (a finite model is practically= the same thing as a relational database), which leads to descriptive compl= exity theory. We will discuss  &n= bsp;B=C3=BCchi's Theorem relating monadic second-order logic = intimately with finite automata and regular languages. We will also discuss= Fagin's theorem characterizing the complexity class non-deterministic poly= nomial time by existential second-order logic. Time permitting, we will als= o discuss the zero-one law of first-order logic.

Prerequisites:
Introduction to Logic I&II

= =20

## News

•  The first lecture is on Mond= ay 5 September at 10-12 in room B321.
•  The exercise session on Tues= day 22nd of November is cancelled and moved to the next week.
• The last lecture of the course wil= l be on Thursday 8th December.
• The final exam will be organized o= n Wednesday 21st December at 10-14 in = room B321.
• The lecture of Monday 5.12= is cancelled.

## Course diary

Monday 5.9.2016:

Thursday 8.9.2016

• Strong homomorphisms, embeddins, isomorphisms, automorphisms, model red= uctions, submodels, ordered models. Representation theorem for finite order= ed models.

Monday 12.9.2016:

•  Partial isomorphisms,
• Terms and atomic sentences.

Thursday 15.9.2016:

• First-order sentences, and quantifier rank of a sentence.

Monday 19.9.2016:

• Infinitary logic and Fra=C3=AFss=C3=A9 system= s.

Thursday 22.9.2016:

• Ehrenfeucht=E2=80=93Fra=C3=AFss=C3=A9 game.

Monday 26.9.2016:

• Equivalence of Fra=C3=AFss=C3=A9 systems and = Ehrenfeucht=E2=80=93Fra=C3=AFss=C3=A9 games.

Thursday 29.9.2016:

•  Partial isomorphisms up to k equals logical equivalence up to qua= ntifier rank k.

Monday 3.10.2016:

• Pebble game and  partial isomorphism up to k variables.

Thursday 6.10.2016:

• Partial isomorphisms up to k variables equals logical equivalence in th= e k-variable infinitary logic,
• Basic concepts of formal language theory.

Monday 10.10.2016:

• Word models, finite automata, and invariance.

Thursday 13.10.2016:

• Any language L that is a union of equivalence classes of an invariance = that has finitely many equivalence classes if recognizable by a finite auto= maton,
• Definability of languages by logics,
• Second-order logic.

Monday 17.10.2016:

• Fragments of second-order logic,
• Every language recognized by some finite automaton is definable in mona= dic =CE=A311.

Thursday 20.10.2016:

• Simulating monadic second-order logic by first-order logic in models wi= th added structure.

Monday 31.10.2016:

• Completed the proof of B=C3=BCchi's theorem,
• Basics of Turing machines. We follow the textbook of Ebbinghaus and Flu= m (see Notes.pdf).

Thursday 3.11.2016:

• Complexity classes PTIME, NPTIME and PSPACE,
• Basics of fixed-point logics.

Monday 14 and Thursday 17.11.2016:

• Logical characterization of PTIME, PSPACE and NPTIME by IFP, PFP, and e= xistential second-order logic.

Monday 21.11.2015:

• Satisfiability, validity, and model checking problems. Decidability, un= decidability, RE, and coRE.
• Normal form for the one-variable fragment of first-order logic. Notes.

Thursday 24.11.2016:

• Normal form for the two-variable fragment of first-order logic.
• Types.

Monday 28.11.2016:

• Finite model property of the two-variable fragment of first-order logic= .

Thursday 1.12.2016:

• Asymptotic probabilities, 0-1 laws, and extension axioms.

Thursday 8.12.2016:

• 0-1 law for first-order logic and FVL.

## Final exam

The final exam will be organized o= n Wednesday 21st December at 10-14 in room B321.

## Course material

We will follow the structure of K. Luosto's lecture notes:

Luosto, =C3=84=C3=A4rellisten mallien teoria (in Finnish).

All material covered during the course can be also found in:

Ebbinghaus and Flum, Finite Model Theory.

V=C3=A4=C3=A4n=C3=A4nen, A Short Course in Finite Model Theory.

The slides of Lauri Hella's = summer course in Aix-en-Provence.

## Registration

Did you forget to register?<= /span>   What to do?

## Exercises

### Exercise classes

Group Day Time Room Instructors
1. Tuesday  14-16  B321  Juha Kontinen & Jonni Virtema<= /td>

## Course feedback

Course feedback can be given at any point during the course. Click = here.<= /p>

------=_Part_15871_545914470.1656598593905--