Lecture 10 (30.12.96)

Material of this and subsequent lectures:

[EFT] H.D. Ebbinghaus, J. Flum, Finite Model Theory, Springer 1994, Chapter 5

Proof of Buchi's Theorem

Repetition on regular languages.
Invariant equivalence relations (on string languages).
Examples of invariant equivalence relations.
Invariant equivalence relations of finite index.
k-equivalence induced by EF-games for FOL are invariant and of finite index.
k-equivalence induced by EF-games for MSOL are invariant and of finite index.
to prove that they are of finite index we show that there are up to FOL (MSOL)-equivalence, only finitely many formulas of a given quantifier rank (and a fixed set of free variables).
If a language L is the union of equivalence classes of an invariant equivalence relation of finite index then L is regular.
If L is MSOL definable then it is the union of equivalence classes of an invariant equivalence relation of finite index.
Exercise: Prove the analogue theorem for FOL definable languages.