How does one show $\Sigma \vdash p$ then $\Sigma \models p$ in propositional logic

logicpropositional-calculus

I was going through these notesand wanted to understand proposition 2.2.2 on page 20. Which is:

If $\Sigma \vdash p$ then $\Sigma \models p$

I understand what it says but the proof eludes me completely because I do not understand how to connect truth/semantics (i.e. mapping to 0 or 1 according to how we label the atoms with a truth function $t:A \to \{0,1 \}$ and (syntactic) provability. The only thing the text says is:

This should be clear from earlier facts that we stated and which the reader was asked to verify.

However, I have no idea how this suppose to be true at all. Anyone has any ideas how this is done? Why is this suppose to be trivial/obvious? What am I missing/not connecting from what I should know so far?

My difficulty is understanding how we actually come up with a model (i.e. a truth assignment) given only that a formal proof $p_1, \dots, p_n$ exists. The only relationship between truth and provability that we know is that the axioms are tautologies (so any truth assignment to them makes them true, always for any entry in the truth table). Being in $\Sigma$ only means you are in that set but nothing else…essentially, I assume we have to be able construct a truth function but thats not clear.

Best Answer

This property is called soundness. You don't need to construct a particular valuation, you need to show that $p$ is true in any valuation that satisfies $\Sigma$ (i.e. any valuation such that all the sentences of $\Sigma$ are true).

You can prove it by induction on the length of the proof. $p$ is the last line of a proof from $\Sigma.$ It is either

  1. An axiom instance.
  2. A sentence in $\Sigma.$
  3. An inference from modus ponens applied two previous lines.

You need to show that $\Sigma\models p.$

  1. If $p$ is an axiom, then it is valid, so true in all truth valuations, regardless if they satisfy $\Sigma$. (This assumes you have proven all the axioms are valid previously. If not, do it, it's just a matter of checking their truth tables.)
  2. It is obvious that if $p\in\Sigma$ then $\Sigma \models p.$ In any valuation where all sentences in $\Sigma$ are true, $p$ is true, because $p$ is a sentence in $\Sigma.$
  3. If we have inferred $p$ from previous lines of the proof $p'$ and $p'\to p,$ we may assume by the induction hypothesis that $\Sigma \models p'$ and $\Sigma \models p'\to p.$ Now let $v$ be any valuation satisfying $\Sigma.$ Then since $\Sigma \models p'$ and $\Sigma\models p,$ we have $v(p')=v(p'\to p)=1.$ Using the truth tables for $\to,$ this implies $v(p)=1.$ Thus, since $v$ was an arbitrary valuation satisfying $\Sigma,$ we have $\Sigma \models p.$
Related Question