Logic – Meaning of Completeness in Propositional Logic

Question

During one of the lectures in logic, My prof proved completeness and soundness of Hilbert system of axioms or simple axiom system as in http://en.wikipedia.org/wiki/Propositional_calculus#Soundness_and_completeness_of_the_rules

But looks like neither my prof's proof nor the proof in wikipedia has any references to the axioms on which completeness is proved. I am really confused, Completeness supposed to mean any tautology can be proved just through that axiom schema and modes ponens right? Or am i missing something?

Entire proof seems to make valid statements but i dont see any connection to what it proves and how it uses of any of the assumptions.

Answer 1

You can see a full exposition of the Completeness Theorem for propositional logic in every good math log textbook, like :

• Dirk van Dalen, Logic and Structure (5th ed - 2013), 2.5 Completeness, page 38-on.

The proof system used is Natural Deduction; here is a sketch of the proof.

Lemma 2.5.1 (Soundness) If $Γ \vdash \varphi$, then $Γ \vDash \varphi$.

The proof of it needs the rules of the proof system.

Definition 2.5.2 A set $\Gamma$ of propositions is consistent if $\Gamma \nvdash \bot$ [$\bot$ is the logical constant for "the falsum, used in ND].

Let us call $Γ$ inconsistent if $Γ \vdash \bot$.

Lemma 2.5.4 If there is a valuation $v$ such that $v(\psi) = 1$ for all $\psi \in \Gamma$, then $\Gamma$ is consistent.

Lemma 2.5.5

(a) $Γ \cup \{ ¬\varphi \}$ is inconsistent iff $Γ \vdash \varphi$,

(b) $Γ \cup \{ \varphi \}$ is inconsistent iff $Γ \vdash ¬\varphi$.

For (a) : by assumption we have (see def of consistency) $\Gamma, \lnot \varphi \vdash \bot$. Now apply the (RAA) rule [i.e. if we have a derivation of $\bot$ from $\lnot \varphi$, we can infer $\varphi$, "discharging" the assumption $\lnot \varphi$] to conclude with : $\Gamma \vdash \varphi$.

Lemma 2.5.7 Each consistent set $Γ$ is contained in a maximally consistent set $Γ^*$.

Lemma 2.5.8 If $Γ$ is maximally consistent, then $Γ$ is closed under derivability (i.e. if $Γ \vdash \varphi$, then $\varphi \in Γ$).

[...]

Lemma 2.5.11 If $Γ$ is consistent, then there exists a valuation $v$ such that $v(\psi) = 1$, for all $\psi \in Γ$.

Corollary 2.5.12 $Γ \nvdash \varphi$ iff there is a valuation $v$ such that $v(\psi) = 1$ for all $\psi \in Γ$ and $v(\varphi) = 0$.

Proof $Γ \nvdash \varphi$ iff $Γ \cup \{ ¬ \varphi \}$ is consistent iff there is a valuation $v$ such that $v(\psi) = 1$ for all $\psi \in Γ \cup \{ ¬ \varphi \}$, or $v(\psi) = 1$ for all $\psi \in Γ$ and $v(\varphi) = 0$.

Theorem 2.5.13 (Completeness Theorem) $Γ \nvdash \varphi$ iff $Γ \nvDash \varphi$.

Proof if $Γ \nvdash \varphi$, then $Γ \nvDash \varphi$ by Corollary 2.5.12. The converse holds by Lemma 2.5.1.