Proof of Soundness Lemma

1k Views Asked by At

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$

We are given the hint to use "induction on the length of the gamma proof".

Since $\Gamma \vdash \phi$, there is a sequence $s= \langle\phi_1,\dots,\phi_n\rangle$ is a gamma proof and $\phi_n = \phi$.

By the construction of a gamma proof, all $\phi_i$ of $s$ must at least be one of:

(a) $\phi_i$ is in $\Gamma$
(b) $\phi_i$ is a logical axiom
(c) there are $j_1$ and $j_2$ less than $i$ such that $\phi_{j_2} =(\phi_{j_1}\to \phi_i)$

How do we use induction on length of the gamma proof to reach that $\bar{\nu}(\phi)=T$?

Can we argue that since $\phi= \phi_n$ must satisfy at least one of (a),(b),(c)?

If $\phi_n$ satisfies (a) then it's in $\Gamma$ by definition so it is true. If it satisfies (b) then it is a logical axiom and is thus a tautology so it's true. If it satisfies (c), then what?

1

There are 1 best solutions below

1
On

I can only give you a proof sketch since you did not tell us which axioms you have in your system.

Lemma (Soundness)

$Γ \vdash ϕ ⇒ Γ \vDash ϕ$

Proof Sketch: Let $Γ⊢ϕ$. We need to show that $Γ \vDash ϕ$, that is, that for any truth assignment $ν$ such that $ν(ψ)=1$ for all $ψ∈Γ$ then $ν(ϕ)=1$. By definition of $Γ⊢ϕ$, there is a derivation $D$ with conclusion $ϕ$ and hypothesis in $\Gamma$ where every line is either:

  1. an axiom;
  2. an element of $\Gamma$ or
  3. follows from previous lines by Modus Ponens

We proceed by induction on the lenght of the proof:

(basis) We consider the case where the derivation $D$ is atomic. We have two cases:

  • $ϕ \in Γ$. Then it is easy to see that $Γ \vDash ϕ$.

  • $ϕ$ is an axiom. Then we need to show that every axiom of our system is valid. This can be done by reductio ad absurdum: suppose that Axiom so-and-so is not valid, then derive a contradiction. This shows that $\phi$ is valid, therefore $Γ \vDash ϕ$.

(Inductive Case) Induction Hypothesis: if $\frac{D}{\phi}$ and $\frac{D'}{\phi \to \psi}$ are derivations with its hypothesis contained in $\Gamma$ and $\Gamma'$ then $Γ \vDash ϕ$ and $Γ' \vDash \phi \to \psi$. We need to show that if

$$\frac{\frac{D}{\phi} \frac{D'}{\phi \to \psi}}{\psi} \tag{$D$*}$$

is a derivation with its hypothesis contained in $\Gamma \cup \Gamma'$ then $Γ, \Gamma' \vDash \psi$. Consider ($D$*). Now by the IH for any truth assignment $ν$ such that $ν(\xi)=1$ for all $\xi∈Γ\cup \Gamma'$ then $ν(ϕ)=1$ and $ν(ϕ \to \psi)=1$. Then by the interpretation of the connectives, $ν(\psi)=1$ and $Γ, \Gamma' \vDash \psi$.

In other words, the above step shows that our inference rules are "truth preservative", that is, for every derivation $Γ⊢ϕ$ we have that $Γ \vDash ϕ$. Since we have established that our property holds for every atomic derivation too, this suffices to show that if $Γ \vdash ϕ$ then $Γ \vDash ϕ$.