Proofs

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

$$r$$

$$(\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$