NEIL W. TENNANT

tennant.9@osu.edu

If you email me, please use the header PHIL 150: [YOURNAME].

Professor
Department of Philosophy


Lecture summary © Neil Tennant, February 2004

Soundness and completeness of systems of deductive proof

We saw earlier what it was for an argument of the form

Premises; therefore Conclusion

to be deductively valid:

every interpretation that makes the Premises true makes the Conclusion true also.
This is a strict universal generalization of the form
All Fs are G
By strict here we mean that just one counterinstance would be enough to falsify it. Its truth requires that absolutely every F be a G.

Given the definition above of what validity of an argument consists in, we can see that its invalidity would consist in its being the case that

not every interpretation that makes the Premises true makes the Conclusion true also.
Classically, to say that
not every F is a G
is equivalent to saying that
some F is not a G.
So the invalidity of an argument of the form
Premises; therefore Conclusion
consists in there being some interpretation that makes the Premises true, but that does not make the Conclusion true. That is to say, the argument is invalid just in case
some interpretation that makes the Premises true makes the Conclusion false.
Such an interpretation is called a counterexample to the invalid argument in question.

So: an argument is invalid just in case it has some counterexample. And it is valid just in case it has no counterexample; or, equivalently, just in case every interpretation that makes its Premises true makes its Conclusion true also.

We can show an argument to be invalid (when it is invalid) by producing but a single counterexample. This is done by describing one imaginatively in natural language, or by constructing one abstractly in mathematical terms, or by drawing an illustrative diagram. The means are varied; but they all serve the same purpose: which is to show that in some 'logically possible' situation the Premises are true yet the Conclusion is false.

That is all well and good when there is a counterexample to be shown. But what if there is no counterexample at all? That is to say: what if the argument is valid? How do we then show this to be the case?

Here lies the crucial importance of proof. A proof is a finite piece of discourse that can be checked mechanically for its correctness, so that no step is left open to dispute or incompatible interpretations. A proof must indicate what its starting points (the Premises) are, and what its endpoint (the Conclusion) is. It must make the deductive transition from the former to the latter completely clear, by means of simple and obvious steps that preserve truth. These steps must be in accordance with basic rules of inference. There can be only finitely many rules of inference. Each rule of inference, ideally, concerns only one logical expression, such as 'not', 'or', 'and', 'only if', 'some', 'all', or 'is identical to'. These rules, and the permissible ways of combining their applications, make up what is known as a system of logical proof for the language in question. The system is deductive, not inductive.

The first requirement on any system of proof is that it must be sound: the system will provide proofs only for valid arguments. That is to say, all provable arguments are valid. This is easily guaranteed by the truth-preserving character of the basic rules of inference in the system.

The second requirement on a system of proof is harder to meet. It is the requirement that the system of proof be complete: the system must provide every valid argument with a proof.

Another way to state soundness is as follows: no invalid argument has a proof. And another way to state completeness is this: every valid argument has a proof.

Putting soundness and completeness together, we can say:

every argument has either a proof or a counterexample, but not both.
A first-order language is one in which the words "some" and "all" are used to generalize only about individuals, and not about their properties or the relations in which those individuals stand to each another. If one generalizes about properties of individuals, or about relations among individuals, then one is using a second-order language. While a second-order language has the advantage of extra expressive power, it unfortunately lacks a complete proof system. This can be proved rigorously; it is an impossibility result, not just a journalistic comment on the inadequacies of whatever proof systems for second-order might have been offered up till now. One cannot provide a complete system of proof for second-order logic.

The system of classical first-order logic, which is the deductive apparatus of modern mathematics, was invented in 1879 by the German philosopher-logician-mathematician Gottlob Frege. Frege's system was actually more ambitious and comprehensive, since it contained higher-order quantification. First-order logic was a small fragment of his overall system. He also happened to provide a (sound and) complete proof system for the fragment in question.

The completeness of the first-order system of proof was first established by Kurt Gödel, in his 1929 doctoral dissertation at the University of Vienna. Gödel did not use exactly Frege's proof system, but rather one closely related to it. A much simpler proof of completeness was later provided by Leon Henkin, in his 1949 doctoral dissertation at Princeton.

By far the most natural and elegant system of proof for first-order logic was provided by Gerhard Gentzen in 1936. You can learn about this system of so-called 'natural deduction', and read a Henkin-style completeness proof for it, in the text Natural Logic for PHIL 250: Introduction to Symbolic Logic and PHIL 650: Symbolic Logic.

Despite the fact that first-order logic is logically complete, it turns out that certain important first-order mathematical theories based on that logic, such as arithmetic, are theoretically incomplete, if consistent. That is, no matter what true Axioms one might lay down as arbitrary starting-points for proofs, there will be true sentences in the language of the theory that cannot be proved (as conclusions) from those axioms, provided that the axioms are consistent. This is the famous First Incompleteness Theorem of Gödel (1930). It is one of the most famous and profound results in the foundations of mathematics. This and related results are covered in PHIL 750: Advanced Symbolic Logic.