Syntactic implication

Definition 3..1 (Axioms)  
  1. $ p \Rightarrow (q \Rightarrow p)$ is true $ \forall p,q \in L$
  2. $ (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))$ $ \forall p,q,r \in L$
  3. $ (\neg \neg p) \Rightarrow p$ $ \forall p \in L$

Observation 3..2 (Consistent with semantic implication)  

All the axioms are tautologies.

Definition 3..3 (Modus ponens)   From $ p$ and $ p \Rightarrow q$ can deduce $ q$.

Definition 3..4 (Proof)  

Let $ S \subseteq L$ be called the set of hypotheses or premises. A proof of a conclusion $ t \in L$ from $ S$ is a finite set $ t_1,\cdots,t_n$ with $ t_n = t$ and each $ t_i$ is either

  1. an axiom
  2. a member of $ S$
  3. such that there exist $ j,k < m: t_k = (t_j \Rightarrow t_m)$

Then $ S \vdash t$ ($ S$ proves or syntactically implies $ t$). If $ \emptyset \vdash t$ then $ t$ is a theorem (written $ \vdash t$).

Theorem 3..5  

$ ( p \Rightarrow q, q \Rightarrow r ) \vdash ( p \Rightarrow r ) $

Proof. [Proof]

1 $ (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))$ Axiom 2
2 $ q \Rightarrow r $ Hypothesis
3 $ ( q \Rightarrow r ) \Rightarrow ( p \Rightarrow ( q \Rightarrow r ) ) $ Axiom 1
4 $ p \Rightarrow ( q \Rightarrow r ) $ Modus ponens on 2, 3
5 $ ( p \Rightarrow q ) \Rightarrow ( p \Rightarrow r ) $ Modus ponens on 4,1
6 $ p \Rightarrow q$ Hypothesis
7 $ p \Rightarrow r$ Modus ponens on 6,5

$ \qedsymbol$

Theorem 3..6  

$\displaystyle \vdash ( p \Rightarrow p ) $

Proof. [Proof]

1 $ p \Rightarrow ( ( p \Rightarrow p ) \Rightarrow p )
\Rightarrow ( ( p \Rightarrow ( p \Rightarrow p ) ) \Rightarrow ( p \Rightarrow p ) )$ Axiom 2
2 $ p \Rightarrow ( ( p \Rightarrow p ) \Rightarrow p )$ Axoim 1
3 $ ( p \Rightarrow ( p \Rightarrow p ) ) \Rightarrow ( p \Rightarrow p ) $ Modus ponens on 2,1
4 $ p \Rightarrow ( p \Rightarrow p )$ Axiom 1
5 $ p \Rightarrow p $ Modus ponens on 4,3
$ \qedsymbol$

Theorem 3..7 (Deduction theorem)  

Let $ S \subseteq L$, $ p,q \in L$. Then $ S \vdash ( p \Rightarrow q
)$ iff $ S \cup [p] \vdash q$.

Proof. $ S \vdash ( p \Rightarrow q
)$. Given a proof of $ p \Rightarrow q$ from S add lines

$ p$ Hypothesis
$ q$ Modus ponens

Thus proving $ q$ from $ S \cup [p]$.

$ S \cup [p] \vdash q$

Let $ t_1,t_2,...,t_n$ be a proof of $ q$ from $ S \cup [p]$. Show that $ S \vdash ( p \Rightarrow t_i )$ for every $ i$.

If $ t_i = p$ certainly $ S \vdash ( p \Rightarrow p )$ as $ \vdash ( p \Rightarrow p )$.

Otherwise if $ t_i$ is an axiom or $ t_i \in S$, write
$ t_i$ Axiom or Hypothesis
$ t_i \Rightarrow ( p \Rightarrow t_i )$ Axiom 1
$ p \Rightarrow t_i$ Modus ponens

So $ S \vdash ( p \Rightarrow t_i )$.

Otherwise $ t_i$ was got from Modus Ponens, i.e. there exist $ j$ such that $ t_j \Rightarrow t_i$. By induction on $ i$ assume $ S \vdash ( p
\Rightarrow t_j )$ and $ S \vdash ( p \Rightarrow ( t_j
\Rightarrow t_i ) )$ so write

$ ( p \Rightarrow ( t_j \Rightarrow t_i ) ) \Rightarrow ( ( p \Rightarrow t_j ) \Rightarrow ( p \Rightarrow t_i ) )$ Axiom 2
$ ( p \Rightarrow t_j ) \Rightarrow ( p \Rightarrow t_i )$ Modus ponens
$ p \Rightarrow t_i$ Modus ponens

$ \qedsymbol$

Example 3..8  

To show $ \{ p \Rightarrow q, q \Rightarrow r \} \vdash ( p \Rightarrow q
)$ show $ \{ p \Rightarrow q, q \Rightarrow r, p \} \vdash r$ using modus ponens twice.

Theorem 3..9 (Soundness theorem)  

Let $ S \subseteq L$, $ t \in L$ then $ S \vdash t$ implies $ S \models
t$.

Proof. Given a valuation $ v$ that is a model for $ S$, i.e. $ v(s) = 1 \forall
s \in S$ we want $ v(t) = 1$.

Certainly axioms (are tautologies) and elements of $ S$ are true. Also modus ponens: if $ v(p)=1$ and $ v(p \Rightarrow q)=1$ then $ v(q)=1$. So $ v(p)=1$ for all $ p$ in a proof of $ t$ from $ S$.

$ \qedsymbol$

Definition 3..10  

$ S \subseteq L$ is inconsistent if $ S \vdash \bot $. Otherwise it is consistent.

Definition 3..11 (Deductively closed)  

A set $ S \subseteq L$ is deductively closed if it contains all its consequences. If $ S \vdash p$ then $ p \in S$.

Theorem 3..12 ($ S$ consistent implies it has a model)  

Let $ S \subseteq L$ be consistent. Then $ S$ has a model.

Proof. Key idea: the theorem fails if both $ p$ and $ \neg p $ are in $ S$. So try to extend $ S$ keeping it consistent to swallow up one of $ p$ or $ \neg p $ for each $ p \in L$.

Claim. For any consistent $ S \subseteq L$ and any $ p \in L$ at least one of $ S \cup \{ p \}$ and $ S \cup \{ \neg p \}$ is consistent.

Proof of claim. Suppose $ S \cup \{ p \}$ is inconsistent. Then $ p
\vdash \bot $. So $ S \vdash (p \Rightarrow \bot )$ so $ S$ and $ S \cup \{ \neg p \}$ prove the same things so $ S \cup \{ \neg p \}$ is consistent.

$ L$ is countable. Let $ t_1,t_2,t_3,\cdots$ be an ordering of $ L$. Let $ S_0 = S$. Let $ S_{n+1}$ be $ S_n \cup \{t_n\}$ or $ S_n \cup \{
\neg t_n\}$ choosing one which is consistent. Let $ \bar{S} = \cup _{n \ge 1} S_n$. Then for each $ p \in L$ at least one of $ p \in \bar{S}$ or $ \neg p \in \bar{S}$. $ \bar{S}$ is consistent because proofs are finite. Also $ \bar{S}$ deductively closed. If $ p \notin S$ then $ S$ does not prove $ p$ (as $ \neg p \in S$).

Define $ v \colon L \mapsto \{ 0,1 \}: v(p) = \begin{cases}1&\text{if
$p \in S$}\\ 0&\text{otherwise}\end{cases}$. $ v$ is a valuation. Proof. $ v(\bot )=0$. If $ v(p)=1,v(q)=0$ then $ p \in \bar{S}$, $ q \notin \bar{S}$. So $ (p \Rightarrow q) \notin \bar{S}$ so $ v(p \Rightarrow q) = 0$. If $ v(q)=1$ then $ q \vdash (p \Rightarrow q)$ so $ (p \Rightarrow q) \in \bar{S}$ so $ v(p \Rightarrow q)=1$. If $ v(p)=0$ then $ p \notin \bar{S}$ so $ \neg p \in \bar{S}$. Enough to show $ \neg p \Rightarrow (p \Rightarrow q)$. That is, $ (p,\neg p) \vdash q$.

$ p \Rightarrow \bot $ Hypothesis
$ \bot \Rightarrow \neg \neg q$ Axiom 1
$ (\neg \neg q) \Rightarrow q$ Axiom 3

So $ v(p \Rightarrow q)=1$. So $ v$ is a valuation. So there is a model for $ S$.

$ \qedsymbol$

Observation 3..13  

Previous theorem used fact that $ P$ is countable (so that $ L$ is countable) but this is not necessary by Zorn's lemma (next chapter).

Corollary 3..14 (Adequacy theorem)  

Let $ S \subseteq L$, $ t \in L$. Then $ S \models
t$ implies $ S \vdash t$.

Proof. If $ S \models
t$ then $ S \cup (\neg t) \models \bot $ (has no model) so $ S
\cup (\neg t) \vdash \bot $ (is inconsistent). $ S \vdash ((\neg t) \Rightarrow \bot )$ by deduction theorem. $ S
\vdash (\neg \neg t)$. So $ S \vdash t$ by axiom.

$ \qedsymbol$

Theorem 3..15 (Completeness theorem for propositional logic)  

Let $ S \subseteq L$, $ t \in L$. Then $ S \models
t$ iff $ S \vdash t$.

Proof. Adequacy and soundness theorems.

$ \qedsymbol$



Subsections
John Fremlin 2010-02-17