Two consequences of completeness

Theorem 3..16 (Compactness theorem)  

Let $ S \subseteq L$, $ t \in L: S \models t$. Then some finite $ S'
\subseteq S$ has $ S' \models t$.

Proof. If $ S \models
t$ then $ S \vdash t$. But proofs are finite so some finite $ S'
\subseteq S$ has $ S' \vdash t$. Then $ S' \models t$.

$ \qedsymbol$

Corollary 3..17 (Equivalent formulation of compactness)  

If every finite subset of $ S$ has a model, then $ S$ is consistent.

Proof. There is no finite subset of $ S$, such that $ S \vdash \bot $. So $ S
\not \vdash \bot $.

$ \qedsymbol$

Theorem 3..18 (Decidability theorem)  

There is an algorithm to determine, for any $ S \subseteq L$ and $ t \in L$ whether or not $ S \vdash t$.

Note that this is not obvious at all.

Proof. Trivial by replacing $ \vdash $ with $ \models $. To decide if $ S \models
t$ just write down a truth table.

$ \qedsymbol$

John Fremlin 2010-02-17