If Γ ⊢ A, then Γ ⊨ A

Question

I'm having a difficult time differentiating between the two proofs:

1. If Γ ⊢ A, then Γ ⊨ A

vs.

2. If ⊢ A, then ⊨ A

Here's the question:

Prove “strong soundness”: for any set of formulas, Γ, and any formula A, if Γ ⊢ A then Γ ⊨ A (i.e., if A is provable from Γ then A is a semantic consequence of Γ.)

For 2. If ⊢ A, then ⊨ A, I know that I can prove this using an inductive proof for soundness.

Here's a proof of If ⊢ A, then ⊨ A

Proof: I want to show that the axioms (below) have the property of validity. When I show that, I can conclude that every theorem (formulas that are provable from no premises at all) has the property of validity:

1. P->(Q->P) PL1
2. (P->(Q->X))->(P->Q)->(P->X)) PL2
3. (~Q->~P)->((~Q->P)->Q) PL3

Base case:

• I show that every axiom is valid.

• For 1), I assume for reductio that P->(Q->P) is invalid for some interpretation Vi

• Vi(P->(Q->P))=0, Thus, Vi(P)=1 and Vi(Q->P)=0 by the definition of conditional. Use the conditional definition again, and I get Vi(Q)=1 and Vi(P)=0

• I see a contradiction of Vi(P)=1 and Vi(P)=0

• Therefore P->(Q->P) is valid.

I would show that 2) and 3) are also valid

Induction Step:

• Inductive hypothesis: I assume that every line in a proof up to a certain point is valid. I also assume that modus ponens preserves validity when I show that I can get the consequent if I have the conditional and its antecedent.

• If I assume the inductive hypothesis, I have some formula P which I got from Q->P and Q.

• I want to show that P is a valid formula.

• By the inductive hypothesis, all prior lines are valid, therefore Q->P is and Q are valid

• Thus, for some interpretation, Vi, Vi(Q->P)=1 and Vi(Q)=1

• If Vi(Q)=1, then when we break down Vi(Q->P) with our definition of conditional, Vi(Q)=1 and Vi(P)=1 because that'll make Vi(Q->P)=1

• Therefore Vi(P)=1 which is what I wanted to show

• With this induction proof, I was able to show that If ⊢ A, then ⊨ A

My question is how would I write a proof for If Γ ⊢ A, then Γ ⊨ A? What does "strong soundness" mean?

Thank you!

Answer 1

The difference between $\vdash A$ and $\Gamma \vdash A$ is that in the latter, you are allowed to use statements in $\Gamma$ as well as the axioms in your proof of $A$. The difference between $\models A$ and $\Gamma \models A$ is that in the latter, $A$ need only be true in all interpretations that satisfy $\Gamma,$ rather than in every interpretation.

So to prove $\Gamma \models A,$ you only need to consider interpretations that satisfy $\Gamma,$ but there is a wider class of proofs to check. Everything is very similar. You need to show every axiom is true in any interpretation satisfying $\Gamma,$ but you've already shown they are true in every interpretation period, so that's done. Now that you are allowed to use statements in $\Gamma,$ you need to show that all of these are true in any interpretation satisfying $\Gamma.$ But that is an immediate consequence of what it means for an interpretation to satisfy $\Gamma$.

Finally, following the same logic as in your induction step, you need to show that modus ponens preserves the property of being true in every interpretation satisfying $\Gamma$ (i.e. if $\Gamma\models A$ and $\Gamma \models A\to B,$ then $\Gamma\models B$). I'll leave it to you to check that essentially the same proof you gave goes through under these slightly different circumstances.