Soundness and completeness

Two questions about the course system

The unit on deduction fixed the course system: Łukasiewicz's axiom schemas A1, A2 and A3 and two rules, modus ponens (MP) and the replacement of double negation (RDN), which the lesson on the four deduction techniques added after proving double negation. A deduction from a set $\Gamma$ is a finite sequence of formulas in which each one is an axiom, an element of $\Gamma$, the result of modus ponens applied to two earlier formulas or the result of RDN applied to an earlier one; $\Gamma \vdash \varphi$ means that there is a deduction from $\Gamma$ whose last formula is $\varphi$. The unit on semantics, for its part, defined in the lesson on semantic consequence and equivalence the relation $\Gamma \models \varphi$: every valuation that satisfies all the formulas of $\Gamma$ satisfies $\varphi$. Both relations are written with the same pattern, a set on the left and a formula on the right; their nature, however, is opposite. The first is syntactic and existential: it asserts that there exists a finite object, a deduction, which can be checked symbol by symbol. The second is semantic and universal: it asserts something about all valuations, which are infinitely many, and each of which gives a value to infinitely many variables.

Two questions therefore arise about the system. The first: does it deduce only what it should? The system is said to be sound if, for every set $\Gamma$ and every formula $\varphi$, $\Gamma \vdash \varphi$ implies $\Gamma \models \varphi$: what is deduced from some premises is true under every valuation that makes the premises true. The second: does it deduce everything it should? The system is said to be complete if $\Gamma \models \varphi$ implies $\Gamma \vdash \varphi$. Completeness admits three degrees, according to the sets of premises it covers:

• weak completeness: if $\models \varphi$, then $\vdash \varphi$; every tautology is a theorem;
• completeness for finite sets: if $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$, then $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$;
• strong completeness: if $\Gamma \models \varphi$, then $\Gamma \vdash \varphi$, for an arbitrary set $\Gamma$, infinite ones included.

This lesson proves soundness and the first two degrees of completeness. The third is proved in the lesson on the compactness theorem, and the reason for that division will be explained at the end of the lesson.

What should not be said

In Spanish, soundness is sometimes called “solvencia”, a calque of the English soundness; the Spanish term is “corrección”, and it is the one the course uses in Spanish. Nor should soundness be defined as the property of the system “of inferring an expression from a set of expressions”, which is derivability itself and not a property of the system. The errors of substance, however, are two others.

The first is to assert that soundness and completeness “can be inferred from each other”. They are independent properties: Łukasiewicz's system, without the rule RDN, is sound (the proof in this lesson proves it, with one case removed) and is not complete (the lesson on formal deductive systems exhibited a tautology that it does not deduce); and a system that adopted all formulas as axioms would be complete without being sound. Solved problem 2 examines both examples.

The second error is more serious, because it presents a circular argument as a proof of completeness. It says, in substance: if $\varphi \nvdash \psi$, then, by the deduction theorem, $\nvdash (\varphi \rightarrow \psi)$; “by soundness”, $\not\models (\varphi \rightarrow \psi)$; and by the semantic deduction theorem, $\varphi \not\models \psi$. Now, soundness says that what is derivable is valid, and its contrapositive, that what is not valid is not derivable:

The step of the argument goes in the other direction, from $\nvdash \chi$ to $\not\models \chi$, which is the contrapositive of $\models \chi \Rightarrow \vdash \chi$, that is, of weak completeness. If this is so, the argument assumes what it sets out to prove. It follows that completeness is not “inferred in a simple way”: it is the deepest result of the course, and its proof takes up most of this lesson. Finally, it is inaccurate to summarize completeness by saying that “all true expressions have a proof”; what has a proof is what is valid, true under every valuation, not what is true under some: the variable $v_{1}$ is true under many valuations, and it is not a theorem.