Lecture 9 (23.12.96)

Material of this and subsequent lectures:

• [EFT] H.D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic, 2nd ed., Springer 1994

The Lindstrom Theorems

• A logic $L = < Sent(\tau), Mean(\phi, A, z) >$ with closure conditions:
  1. Isomorphism condition
  2. Atmic formulas
  3. Closure under boolean operations
  4. Closure under existential quantification
  5. Closure under substitution of relation symbols by formulas
  6. Closure under $\Phi^#$ where $\Phi$ is a translation scheme using formulas from $Sent$.
• The compactnes property
• The Lowenheim-Skolem (L-S) Property for countable sets of formulas
• Examples of logics which are not compact: $FOL(Q_0)$ with the quantifier "there are infinitely many".
• Examples of logics without the L-S-Property: $FOL(Q_1)$ with the quantifier "there are uncountably many".

Lindstrom's Theorem (1)

Proof of the theorem

• Assume that each formula depends only on finite part of the vocabulary. It can be proved that this follows from compactness.
• Assume there is $\phi \in Sent(\tau)$ not equivalent to a first order formula.
• Use compactness again to show that there are $\tau$-structures $\cA \models \phi$ and $\cB \models \neg\phi$ such that for each n player II has a winning strategy in the FOL-game of lenth n over $\cA$ and $\cB$.
• Build `rabbit'-structure $[\cA, \cB, \cN, E_k]$ which encodes Ehrenfeucht game and define countable theory T_1 on this structure.
• Find countable non-standard model of T_1 (with respect to $\bN$) $[\cA_0, \cB_0, \cN_0, E_k]$
• Construct isomorphism between $\cA_$ and $\cB_0$ using non-standard length of the game.
• This contradicts the fact that $\cA_0 \models \phi$ and $\cB_0 \models \neg\phi$.

Lindstrom's Theorem (2)

Next lecture: Lecture 10