July 06, 2007

Second-order logic and Gödel’s first incompleteness theorem (Frances)

That’s a very impressive title for a blog entry, but I promise that things will not get very complicated in what follows. For I am no logician. I’m not even a philosopher of logic. So, I don’t know much about logic. But I know just enough to be confused about something having to do with second-order logic and Gödel’s first incompleteness theorem.

Let L be the formal first-order language with a name for zero and function symbols for the successor function, addition, and multiplication (and no other non-logical symbols). So L is a pretty simple formal language. Let N be the interpretation of L that has as its domain the set of natural numbers {0, 1, 2, …} and assigns zero to the name ‘0’, addition to the function symbol ‘+’, etc. So N is the natural way to interpret L. Arithmetic is the set of sentences of L that are true under N. So, arithmetic is a set of sentences of a formal language, where each sentence is most naturally interpreted as an arithmetic truth. This will be an infinite set.

Arithmetic counts as a theory of L because it is “closed under logical consequence”, which means that any sentence of L that is entailed by the sentences in arithmetic is in arithmetic. Arithmetic contains all its logical consequences; that’s what makes it a “theory”.

Now a theory T in language L is decidable when there is an algorithm for deciding whether any given sentence of L is a theorem (member) of the theory. So a theory T in L is decidable when there is some algorithm that when fed a sentence S of L will tell you in a finite number of steps whether or not S is in T.

Roughly put, a theory T is axiomatizable just in case everything in T is a logical consequence of some nice subset of T. The nice subset of T generates, so to speak, everything in T (just like how the central Euclidean claims generate all the truths of plane geometry). The member sentences of the nice subset are axioms of T.

The subset could be infinite! But even so it has to be nice. That means: there has to be an algorithm that when fed a sentence of L will tell you in a finite number of steps whether or not the sentence is one of the axioms. That is, the set of axioms has to be decidable.

The famous consequence of Gödel’s first incompleteness theorem is that arithmetic isn’t axiomatizable. This is surprising! You’d think it wouldn’t be that hard to write down a nice set of axioms (say, the Peano axioms) for generating all the truths of arithmetic. But it can’t be done.

Now suppose we add second-order quantifiers and variables to L. Now let arithmetic* be the set of first-order and second-order sentences of L that are true under N. Arithmetic* contains everything in arithmetic plus some more arithmetic truths (the second-order ones).

The cool thing, in my opinion, is that arithmetic* is axiomatizable. You can write down one long sentence that generates, through logical consequence, everything in arithmetic*. So when you hear someone say ‘Gödel famously showed that arithmetic isn’t axiomatizable’, you should say to them ‘Wait a damn minute buddy. First-order arithmetic isn’t axiomatizable, but second-order arithmetic is’. So you can write down just one relatively simple sentence that generates all the (first-order) truths of arithmetic—-but it will generate a whole bunch of other arithmetic truths as well, the second-order ones.

I take it that not that many non-logicians and non-philosophers of logic are aware of that result. Hopefully I’m right about it and as a consequence this blog entry is worthwhile.

But now we come to my question: why is it thought to be such a big honking deal that arithmetic isn’t axiomatizable? I take it that people who know about these things think the second-order axiomatization is not terribly significant. But why?

I guess some people are allergic to second-order logic, but I don’t know anything about that issue. What if you think second-order logic is a-okay?

Is the problem connected to this: whereas there is an algorithm that when fed a first-order sentence S of L that’s logically true, will tell you in a finite number of steps that S is indeed logically true, but there is no algorithm that when fed a second-order sentence S of L that’s logically true, will tell you in a finite number of steps that S is indeed logically true? If so, why does that matter so much?


Peter Smith said...

You are, it has to be said, misusing the term "axiomatizable". It is true that there is a single sentence S (the conjunction of the second-order Peano Axioms) such that every true sentence of L2 the language of second order arithmetic -- and hence, a fortiori, every true sentence of the language L1 of first-order arithmetic -- is semantically entailed by S. But that is not enough to make arithmetic* as you call it, i.e. the set of L2 truths, axiomatizable according to the meaning of the act. For on the absolutely standard definition, that requires that the consequence relation be axiomatizable too, and a simple compactness argument shows that second-order consequence isn't axiomatizable.

Ok, you might say, that's just labels. You might say: isn't the interesting thing that there is a sentence S which semantically entails all L2 truths? Well, that is one interesting thing. But it remains the case that any attempt to capture all the L2 truths in a axiomatic formal system (i.e. where we can decide what's an axiom and what is a well-constructed proof) must fail -- by Gödel's Theorem.

For an extended discussion of this, see my Gödel book (www.godelbook.net), Chapter 22!

Richard Zach said...

The point is (and was, historically) that you somehow want to get at the standard model in a reductive way. A good way to think about it is perhaps epistemically: you don't have direct access to the standard model (at least if you don't believe in Kantian intuition, which is exactly what Frege, Russell, and the logical empiricists wanted to get rid of). So you want to reduce arithmetical truth to something more accessible--and derivability from a set of axioms is one option. Second incompleteness shows that this doesn't work. If you move to second order logic, you have completeness, but what you're reducing to is just as elusive/unknowable as what you're trying to reduce in the first place.

John Ryskamp said...

I don't think you know much about the history of set theory, especially the important recent work being done. It has importance for understanding Godel's theorems and a lot of other important twentieth-century ideas.

Here is a brief comment on some of this work:
You should do some reading in the history of set theory. You clearly don't know what's been going on in this field, and you certainly don't understand Godel's very poor understanding of the issues involved. Here is a brief comment on some of the work:

Ryskamp, John Henry, "Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas" (May 19, 2007). Available at SSRN: http://ssrn.com/abstract=897085

Richard Zach said...

I followed that link, and my understanding of the history of set theory has not improved, I think.

I did want to add that the standard reference for the view that a move to 2nd order logic does have foundational significance/payoff, is Stewart Shapiro's Foundations without Foundatinalism.

John Ryskamp said...

We are currently enjoying a renaissance in the historiography of set theory. I discuss some of the results below. Above all, do not write another word on Godel before you have read Garciadiego.

Cordially yours,
John Ryskamp

Ryskamp, John Henry, "Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas" (May 19, 2007). Available at SSRN: http://ssrn.com/abstract=897085

John Ryskamp said...

You are very presumptuous. Read Garciadiego, which is cited repeatedly in the paper. What is your problem?

Bryan Frances said...

I am sorry that I have not responded to the comments. I have been very busy with a couple papers that have been haunting me for ages, and I simply must finish them off before they finish me off.

And now that the Harry Potter book is about to be released, well, I am going to be busy with matters more important than philosophical theories.

So perhaps we should close the discussion at this point? After all, I was the confused one in need of an answer, and I think Richard Zach has pointed me in the right direction.

John Ryskamp said...

You're a moron.

Bryan Frances said...

John is right to imply that I don't know much about logic (as I insisted in the original post). I'm one of those people who blog rarely and blog only on topics I don't know too much about. I know a fair amount of other philosophy, however, and I think my lack of knowledge of logic (or metalogic) doesn't make me a moron.

Perhaps I'm a moron for liking the Harry Potter books? Sorry, that I won't admit. I finished HP7 last night and loved it. Shakespeare and Austen are for losers! ;)