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  

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