What does completeness mean 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.

Answer 2

I'm not sure I follow what you're asking, but the confusing may be in the fact that the propositional calculus is sound and complete with respect to any truth assignment. You could think of a truth assignment $A$ as a list of axioms: some number of statements which are claimed to be true (or false.) Then we can semantically deduce an infinite set of truths $A_e$, using the rules like "$\phi \wedge \psi$ is true if and only if $\phi$ is true and $\psi$ is true." And we can syntactically deduce an infinite set of truths $A_y$ using the proof rules, e.g. "$\phi,\psi\vdash \phi \wedge \psi$".

The point of the soundness and completeness theorems is exactly that $A_e=A_y$-completely regardless of the initial choice of axioms $A$! So these are theorems about a method of deduction, rather than about any particular axiom system.

Another possible point of confusion about these theorems is that it seems like we give the exact same set of semantic rules as syntactic rules, so that it seems almost obvious that deductions via the two sets of rules can only lead the same place. The point is that deductions via the semantic rules need not proceed via finitely many sequential applications of the rules, so the main content of the completeness theorem is that one doesn't need any infinite proofs to get all the consequences of $A$. This is no longer necessarily the case in other logical systems! So the existence of these theorems enshrines propositional logic as a beautiful elementary case in which everything works out as well as one could possibly hope.