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?