Complete Theories - Model Theory - Cambridge III notes

1 Complete Theories

Definition 1.1 ( $T$ models a sentence). Let $T$ be an $L$ -theory, $φ$ an $L$ -sentence. Then $T ⊨ φ$ if every model of $T$ is a model of $φ$ .

Example. $\emptyset ⊨ \exists (x = x)$ .

$T_{groups} ⊨ \forall x \forall y \forall z ((x * y = e \land x * z = e) \to y = z)$ .

Definition 1.2 (Complete theory). An $L$ -theory $T$ is complete if for every $L$ -sentence $φ$ , either $T ⊨ φ$ or $T ⊨ \neg φ$ .

Example 1.3. $T_{groups}$ is not complete, as (for example) it doesn’t imply $\forall x \forall y (x + y = y + x)$ or $\neg \forall x \forall y (x + y = y + x)$ .

Definition 1.4 (Theory of $M$ ). Let $M$ be an $L$ -structure. Then the theory of $M$

{T h}_{L} (M) = {φ : φ is an L -sentence, and M ⊨ φ} .

(can be written $T h (M)$ when $L$ is clear).

Remark 1.5. ${T h}_{L} (M)$ is always complete.

Definition 1.6 (Elementarily equivalent). Two $L$ -structures are elementarily equivalent if their theories are equal.

Given $L$ -structures $M, N$ , we write $M \equiv_{L} N$ to mean ${T h}_{L} (M) = {T h}_{L} (N)$ .

Note. This is an equivalence relation on $L$ -structures.

Exercise: Let $T$ be an $L$ -theory. Then the following are equivalent:

$T$ is complete
For any $L$ -sentence $φ$ , if $T ⁄ ⊨ φ$ then $T ⊨ \neg φ$ .
Any two models of $T$ are elementarily equivalent.

Example 1.7. Let $L = \emptyset$ and $T_{sets} = {φ_{n} : n \geq 2}$ , where

φ_{n} = \exists x_{1} \dots \exists x_{n} \underset{i \neq j}{\land} x_{i} \neq x_{j} .

This forms the theory of infinite sets. Any infinite set models this, but also in this language we have that any two infinite sets are elementarily equivalent. For example,

ℕ \equiv_{L} ℝ \equiv_{L} ℚ \equiv_{L} ℂ \equiv_{L} P (ℂ) .

Question: How do we prove a theory is complete?

Theorem 1.8 (Los-Vaught test). Assuming that:

$T$ is an $L$ -theory
$T$ has no finite models
There exists some $K \geq | L | + ℵ_{0}$ such that any two models of $T$ of cardinality $κ$ are elementarily equivalent

Then

T

is complete.

Proof. Assume $T$ is not complete, i.e. there is some $L$ -sentence $σ$ such that $T \cup {σ}$ and $T \cup {\neg σ}$ are both satisfiable.

So we have $M ⊨ T \cup {σ}$ , $N ⊨ T \cup {\neg σ}$ .

From (a) we know $M, N$ are infinite. By Lowenheim-Skölem, we know we have $M^{'} ⊨ T \cup {σ}$ and $N^{'} ⊨ T \cup {\neg σ}$ with $| M^{'} | = | N^{'} | = κ$ , contradicting (b). □

Reminder: By combining Lowenheim-Skölem up and down, we get the following statement:

If an $L$ -theory $T$ has an infinite model, then it has a model of size $κ$ for every $κ \geq | L | + ℵ_{0}$ .