Topics Logic

Question Hello. This is a question for the philosophers of mathematics or the logicians. I have heard that first order logic is complete, and that second order logic is incomplete. The completeness of first order logic I have seen characterized as the fact that every true proposition (in the semantic sense) is also provable (in the syntactic sense). I've also heard that the completeness at stake in both cases is not the same, but it has never been clear to me in what they differ. Supposedly second order logic, having more expressive power, has enough resources to express arithmetic and thus the first incompleteness theorem applies to it, but that theorem says of such systems that they are incomplete. But I also have heard some people (or maybe I have misheard them) discussing such incompleteness in the same terms, that is, as saying that not every true theorem of such systems is provable, though the converse is true (they are sound). I am no logician, so I would appreciate firstly, if someone can point out any mistakes in my question, and secondly if someone could clarify the different senses of completeness. Thanks a lot.

Accepted:
January 28, 2010

Comments

Any good textbook that covers second-order logic should in fact clearly answer your question. Here, though, is a summary answer.

An inference in the formal language L from the set of premisses A to the conclusion C is valid if every interpretation of L (that respects the meaning of the logical operators) which makes all the members of A true makes C true too.

A deductive proof system S for sentences in the formal language L is complete if, for every valid inference from a set of premisses A to the conclusion C there is deduction in the system from (some of) the premisses in A to the conclusion C.

If L is a first-order language, then there is a deductive system S1 which is complete in the sense defined ("first-order logic", meaning any standard deductive system for first-order logic, is complete). If L is a second-order language, with the second-order quantifiers constrained to run over all the subsets of the domain, then there is no deductive system S2 which is complete in the same sense (any properly axiomatized system of second-order deductions will fail to warrant some valid inferences: a "second-order logic" meaning a deductive system for second-order logic must be incomplete).

There is no shift in the meaning of "complete" between the cases here. First-order logic (meaning a standard deductive system for first-order logic) is complete; and no second-order logic (meaning no properly axiomatized system for second-order deductions) is complete in the same sense.

Nor in fact do we need to appeal to Gödel's theorem to show that there is no complete deductive system for second-order logic in the sense defined.

A deductive proof can only invoke a finite number of premisses (proofs are finite objects). So if, for every valid L-inference there is a corresponding deductive proof in a system S, valid L-inferences can only depend on a finite number of premisses.

But [Result N] some valid second-order inferences essentially depend on an infinite number of premisses: so there can't be a complete proof system for second-order logic.

(Proof of Result N. The classic example is this. Take the axioms of second-order Peano Arithmetic and add the infinite number of further premisses that R is a number and R isn't 0, R isn't 1, R isn't 2, R isn't 3, etc. etc. That infinity of premisses entails a contradition (since second-order Peano Arithmetic tells us that 0, 1, 2, etc. are all the numbers, so the rogue number R is ruled out). But any finite number of those premisses is consistent (exercise!).)

Postscript: You are right that, if you define completeness in terms of capturing all logical truths, rather than all valid inferences, then that simple argument against the completeness of second-order logic won't work and going via Gödel's Theorem is the way to proceed. But I'd say that you shouldn't define completeness that way! Logic is primarily about what follows from what, after all!