Definition 5..32 (Logical axioms)  

Three old ones, two for $ =$ and two for $ \forall$.

  1. $ p \Rightarrow (q \Rightarrow p)$ for any formulae $ p,q$.

  2. $ (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow q))$ for any formulae $ p,q,r$.

  3. $ (\neg \neg p) \Rightarrow p$ for any formula $ p$.

  4. $ (\forall x)(x = x)$ for any variable $ x$.

  5. $ (\forall x,y)((x=y) \Rightarrow (p \Rightarrow p[y/x]))$ where $ x,y$ variables, $ p$ a formula in which $ y$ does not occur bound.

  6. $ ((\forall x)p) \Rightarrow p[t/x]$ where $ x$ is a variable, $ p$ a formula, $ t$ a term with no free variable occurring that is bound in $ p$.

  7. $ ((\forall x)(p \Rightarrow q)) \Rightarrow (p \Rightarrow (\forall x)q)$ where $ x$ is a variable, $ p,q$ formulae with $ x$ not occurring free in $ p$.

Definition 5..33 (Rules of deduction, modus ponens and generalization)  

Modus ponens. From $ p$, $ p \Rightarrow q$ deduce $ q$.

Generalization. From $ p$ deduce $ (\forall x) p$ as long as $ x$ does not occur in any of the premises used to prove $ p$.

Definition 5..34 (Proof)  

For $ S \subseteq L$ and $ p \in L$ a proof of $ p$ from $ S$ consists of a finite sequence of lines each of which is a logical axiom or a member of $ S$ or is obtained from earlier lines by a deduction rule.

Write $ S \vdash p$ if there is a proof of $ p$ from $ S$.

Observation 5..35  

If we allowed $ \emptyset$ to be an $ L$-structure we would have a contradiction.

Theorem 5..36 (Deduction theorem)  

Let $ S \subseteq L$ and $ p,q \in L$. Then $ S \vdash ( p \Rightarrow q
)$ iff $ S \cup \{ p \} \vdash q$.

Proof. If $ S \vdash ( p \Rightarrow q
)$ then have by modus ponens $ S \cup \{ p \} \vdash q$.

If $ S \cup \{ p \} \vdash q$ then as in the first chapter we show that for each line in $ r$ in a proof of $ q$ from $ S \cup \{ p \}$ in fact $ S \vdash (p \Rightarrow r)$.

We do this inductively. The only new case is if we have used generalization. So in proof of $ q$ from $ S \cup \{ p \}$ we have

$\displaystyle r $

$\displaystyle (\forall x)r $

and we know that $ S \vdash (p \Rightarrow r)$.

Note that the proof of $ r$ from $ S \cup \{ p \}$ did not use a free $ x$ in any hypothesis, so also our proof of $ p \Rightarrow r$ from $ S$ did not use one. Therefore we can deduce $ S \vdash ((\forall x)(p
\Rightarrow r))$ by generalization.

If $ x$ is not free in $ p$: deduce $ S \vdash (p \Rightarrow ((\forall
x)r))$ by the seventh axiom. Otherwise $ x$ is free in $ p$. So in our proof of $ (\forall x)r$ from $ S \cup \{ p \}$ cannot have used $ p$ (as generalization was used). So $ S \vdash ((\forall x)r)$ so $ S \vdash (p \Rightarrow ((\forall
x)r))$ by the first axiom and modus ponens.

$ \qedsymbol$

Theorem 5..37 (Soundness theorem)  

$ S$ is a set of sentences, and $ p$ a sentence. Then $ S \vdash p$ implies $ S \models p$.

Proof. Given a model of $ S$, $ p$ holds in this model by induction on the lines in the proof.

$ \qedsymbol$

Theorem 5..38 (Model Existence Lemma or Completeness Theorem)  

Let $ S$ be a consistent set of sentences. Then $ S$ has a model.

Definition 5..39 (Witness)  

A witness for $ (\exists x) p$ is $ p[t/x]$ for a closed term $ t$.

Proof. Have $ S$ in language $ L = L(\Omega, \Pi)$. Extend $ S$ to maximal consistent $ S_1 \subseteq L$ by Zorn's lemma.

Then $ S_1$ is complete (that is for any $ p \in L$ either $ S_1 \cup
\{ p \}$ is consistent or $ S_1 \cup \{ \neg p \}$ consistent. For each $ ((\exists x)p) \in S$ add a new constant $ c$ to the language to form $ L_1 = L(\Omega \cup C_1, \Pi)$ and add the sentence $ p[c/x]$ to $ S_1$ to form $ T_1$.

Then $ T_1$ is consistent. $ T_1$ has witnesses for $ S_1$.

Now extend $ T_n$ to a complete $ S_{n+1}$ and continue inductively.

Let $ \bar{S} = \cup _{n=1}^\infty S_n$ in language $ \bar{L} = L(\Omega \cup C_1 \cup C_2 \cup \cdots, \Pi)$.

Claim. $ \bar{S}$ consistent. Proof of claim. Suppose $ \bar{S} \vdash \bot $. Then some finite $ S' \subseteq \bar{S}$ has $ S' \vdash \bot $ whence some $ S_n
\vdash \bot $. Contradiction.

Claim. $ \bar{S}$ complete. Proof of claim. For any sentence $ p \in \bar{L}$ have $ p
\in L_n$ for some $ n$ as $ p$ mentions only finitely many symbols. But $ S_{n+1}$ complete in language $ L_n$ so $ S_{n+1} \vdash p$ or $ S_{n+1} \vdash (\neg p)$. But $ \bar{S} \supseteq S$. Done.

Claim. $ \bar{S}$ has witnesses. Proof of claim. Basically the same as for consistency.

For closed terms $ s,t \in \bar{L}$ say $ s \sim t$ if $ \bar{S} \vdash
(s = t)$, clearly an equivalence relation. Write $ [t]$ for equivalence class of $ t$.

Let $ A = \{ [t]: t$    a closed term of $ \bar{L} \}$.

For each $ f \in \Omega(\bar{L})$ with arity $ n$ and $ t_1,\cdots,t_n$ closed terms, set $ f_A([t_1],\cdots,[t_n])=[f(t_1,\cdots,t_n)]$. (Clearly well defined.)

For each $ \phi \in \Pi(\bar{L})$ with arity $ n$ and $ t_1,\cdots,t_n$ closed terms, set $ \phi_A([t_1],\cdots,[t_n])=\{ ([t_1],\cdots,[t_n]) \in A^n: \bar{S} \vdash \phi(t_1,\cdots,t_n) \}$. (Clearly well defined.)

To show that $ A$ is a model for $ S$ we will show that for any sentence $ p \in I$ we have $ p_A = 1$ iff $ \bar{S} \vdash p$. This is an easy induction.

  1. $ s = t$. $ \bar{S} \vdash
(s = t)$ iff $ s \sim t$ iff $ s_A = t_A$ iff $ [s] = [t]$ iff $ (s = t)_A = 1$.

  2. $ \phi(t_1,\cdots,t_n)$ similarly.

  3. $ \bot $. $ \bar{S} \not \vdash \bot $ and $ \bot _A = 0$.

  4. $ (p \Rightarrow q)$. $ \bar{S} \vdash (p \Rightarrow q)$ iff $ \bar{S} \vdash p$ and $ \bar{S} \not \vdash q$ (as $ \bar{S}$ is complete). By induction hypothesis $ p_A = 0$ or $ q_A = 1$ iff $ (p \Rightarrow q)_A = 1$.

  5. $ (\exists x) p$. $ \bar{S} \vdash (\exists x)p$ iff $ \bar{S} \vdash p[t/x]$ or some closed term $ t$, so $ p[t/x]_A = 1$ by induction hypothesis, equivalently $ (\exists x) p$ holds in $ A$ (since $ A$ is the set of all closed terms quotiented).

$ \qedsymbol$

Corollary 5..40 (Adequacy theorem)  

Let $ S$ be a theory and $ p$ a sentence. Then $ S \models p$ implies $ S \vdash p$.

Proof. If $ S \models p$ then $ S \cup \{\neg p\} \models \bot $ implies $ S \cup \{ \neg p\} \vdash \bot $. So by the deduction theorem $ S
\vdash (\neg \neg p)$ so $ S \vdash p$.

$ \qedsymbol$

Theorem 5..41 (Gödel's Completeness Theorem, the completeness theorem of first order logic)  

$ S$ a theory, $ p$ a sentence. Then $ S \vdash p$ iff $ S \models p$.

Proof. By adequacy and soundness.

$ \qedsymbol$

Corollary 5..42 (Compactness theorem)  

$ S$ a theory. If every finite subset of $ S$ has a model then so does $ S$.

Proof. Trivial if we replace ``has a model'' with ``is consistent''.

$ \qedsymbol$

Corollary 5..43 (Upward Löwenheim-Skolem theorem)  

Let $ S$ be a theory with an infinite model. Then $ S$ has an uncountable model.

Proof. Add to the language uncountably many new constants, say $ \{c_i\}_{i \in I}$. Let $ S' = S \cup \{ \neg (c_i = c_j): i, j \in I, i \ne j \}$.

We want a model for $ S'$. But every finite $ F \subset S'$ certainly has a model since $ F$ only mentions finitely many of the $ c_i$. So by compactness the infinite model for $ S'$ exists, and it is also a model for $ S$.

$ \qedsymbol$

Observation 5..44  

The same trick of adding constants $ c_1,\cdots$ shows that no set of sentences (in the language of groups, for example) can axiomatize (i.e. have as a model) the class of finite groups.

In other words, ``finiteness is not a first order property''. Equivalently any theory that has arbitrarily large finite models must have an infinite model (called ``overspill'').

Corollary 5..45 (Downward Löwenheim-Skolem theorem)  

Let $ S$ be a consistent theory in a countable language (that is $ \Omega, \Pi$ countable). Then $ S$ has a countable model.

Proof. The model constructed in the proof of the model existence lemma was maximal and countable.

$ \qedsymbol$

John Fremlin 2010-02-17