Why do we find Gödel's Incompleteness Theorem surprising?

Question

Gödel's First and Second Incompleteness Theorems are well-known, and usually taught by most colleges in undergrad logic courses. In my logic course I'm taking, we went over the proof of Gödel's Theorems. I'm sure everyone here knows this theorem, but let me explicitly state it to be on the same page. We use Computability and Logic by Boolos et al. Here is the exact result we proved:

Theorem. (Gödel's First Incompleteness Theorem) There is no consistent, complete, axiomatizable extension of Q.

where Q is a theory that can do minimal arithmetic, it just has +, * and 0 as its symbols along with some axioms (the set of cardinal numbers is a model of theory Q but not the set of ordinal numbers).

Having explicitly stated the mathematical result I want to question the high-level value of this theorem. I have no doubt that this result is very important for mathematics. This post does not cast doubt upon the importance of the theorem, but upon its so-called "unexpected" nature. The theorem seems highly intuitive to me for two reasons.

First, anyone who has done mathematics in axiomatic context (such as abstract algebra) would not surprise the fact that there are some statements in theories that are independent of them. The theory of groups does not prove commutativity. It also does not disprove it too. Hence, we have both noncommutative groups and abelian groups. The theory of rings does not prove or disprove commutativity, there being non-zero zero divisors, having a Euclidean division algorithm etc... I fail to see the difference between these two scenerios. Now imagine T to be a theory that can do minimal arithmetic (extends Q), is consistent and axiomatizable. Then by Gödel's first, there is a sentence phi such that T does not prove phi nor does it prove not phi. But this seems to tell me that there is an arithmetic truth, phi or not phi that is not captured by theory T. Similarly, the algebraic truth commutative or not commutative is not captured by theory G where G is the theory of groups. Why is former an unexpected, surprising, paradoxical result whereas mathematical literature has tons of situations akin to the latter? Is there a difference that I do not know of? It seems like it's fairly normal for a consistent mathematical theory to be incomplete.

The second reason comes from a more skeptical point of view. I read Gödel's philosophical texts, such as Gibbs Lecture, he seems to think that arithmetic, logic and set theory (ZF) are what is called mathematics proper so they a priori trues whereas theories like Euclidean geometry, algebra etc... are conditionally true mathematical statements (this this axioms follow this this theorems). He seems to think -- and this seems like a common belief among mathematicians -- that there is something inherent in logic, arithmetic and set theory that makes them evident in themselves that all we need is to axiomatize them. But this does not seem like a well-thought out argument to me. Cantor could say the same for naive set theory. Russel certainly thought his formalism will prove everything. Hilbert certainly thought mathematics could be made both provably consistent and complete. Moreover, it seems like axioms we choose for arithmetic profoundly impacts what models them; for example Q is modeled by cardinals but not ordinals. Similarly, some theories that axiomatize ordinals are not modeled by cardinals. So, why do we think arithmetic is this special theory that we would expect not to be incomplete? Arithmetic seems, to my humble eyes, just like another theory.

Answer 1

Perhaps "surprising" is no longer the right word; what is surprising to one person may not be surprising to another. The fundamental theorem of calculus is another result which is sometimes claimed to be "surprising" but which may not surprise everyone. So I don't want to dwell on the "surprising" part, but I want to address a few other questions from the post.

One point is that, even if the incompleteness theorem is not surprising, its proof is far from obvious - particularly the theorem as stated in the question, which requires Rosser's trick in addition to Gödel's argument. If the incompleteness theorem was as obvious as the fact that a group can be commutative or noncommutative, we might expect the proof to be simpler.

The second point is that, although it is true that (e.g.) the axioms of a group are not complete, they are easy to make complete. For example, the theory of torsion free, divisible Abelian groups is complete, consistent, and axiomatizable, as is the theory of algebraically closed fields of a fixed characteristic. The theory of real closed fields is axiomatizable, consistent, and complete, as is Tarski's axiomatization of Euclidean geometry.

So there is something different about arithmetic, compared to real closed fields or geometry. In that sense, the incompleteness theorems may not be surprising, but they are fundamental. They show that we cannot hope to attain the kind of axiomatization for arithmetic that we can obtain for the field of real numbers or for geometry.

Many of the theories in the mathematical literature describe a class of structures (all groups, all fields, all posets, etc.) and so we don't expect them to be complete. But other theories might be intended to describe a particular structure - the real line, the Euclidean plane, the natural numbers. In these cases, once we pick the signature, there is already a complete theory at hand, namely the set of all true sentences of the structure in that signature. So the question is not so much about whether a particular theory is complete (as in the penultimate paragraph of the post), but whether we could in principle write a complete ''and effective'' set of axioms for the theory of the structure and signature we are looking at. For the specific structure $\mathbb{N}$, the incompleteness theorem shows that this is impossible, but goes beyond that to show more.

Answer 2

It seems like it's fairly normal for a consistent mathematical theory to be incomplete.

Well that's true, but the main point is not really negation-incompleteness but essential negation-incompleteness, namely that there is no extension with decidable proof validity that is negation-complete. This is rather surprising at first glance, because one might think that we could simply throw in a sufficiently large decidable set of axioms to make it complete. I shan't repeat Carl's examples of decidable complete theories, nor the fact that we are frequently interested in the question of whether there is an axiomatization that generates the complete theory of some particular structure that we have in mind.

More interestingly, it shows how badly incomplete Q is, even though it is finitely axiomatized and does not have induction. A lot of people have a misconception that PA is incomplete because of induction, which requires somewhat infinitary justification, philosophically speaking. But Q only takes as axioms finitary statements about natural numbers that are essentially nothing more than basic properties of string manipulation! $ \def\nn{\mathbb{N}} \def\con{\text{Con}} $

This very fact that Q can be understood to describe finite strings is what makes its incompleteness so bad, because every useful formal system is described syntactically using finite strings, and Q is strong enough that for every useful formal system $S$ there is a sentence $\con(S)$ over Q such that $S$ is consistent iff $\nn \vDash \con(S)$, and most importantly one can easily write an explicit program that given as input any proof verifier program for $S$ will output $\con(S)$. And the rather uncomfortable consequence of the second incompleteness theorem is that no useful extension $S$ of Q can prove $\con(S)$, not just that it is incomplete but that in its incompleteness it cannot even 'prove its own consistency'. And of course the incompleteness theorem also implies that iteratively adding $\con(S)$ to $S$ will never make it able to prove the new $\con(S)$.

This is what makes $\nn$ very different from other structures, because no mathematics can be done without finite strings of symbols. We have a very concrete representation of $\nn$ in physical media that we actually utilize immensely on a daily basis (in HTTPS, compression, ...) and we rely very heavily on the theorems of PA being true when applied to the real world that way. Worse still, if it turns out that there is actually no model of PA in the real world (perhaps due to a finite universe or relativistic effects or quantum fluctuations), then we can conceivably describe the real world some other way, but the whole edifice of logic and mathematics is built on some foundations that always amount to some formal system, otherwise how do we agree on what is a valid proof of a theorem? Without $\nn$, we can't even describe precisely what are valid sentences, not to say describe what is a valid proof.

So, why do we think arithmetic is this special theory that we would expect not to be incomplete? Arithmetic seems, to my humble eyes, just like another theory.

I hope I've given you sufficient reason to consider arithmetic as special, and something that we would (as Hilbert did) like to be negation-complete, not just for completeness' sake but so that it 'proves itself consistent'. Note how Hilbert asks to find a foundational system that proves all true mathematical statements (not realizing that truth is intrinsically relative to the meta-system), which by definition needs to include proving its own consistency because its consistency is a mathematical statement too.

I read Gödel's philosophical texts, such as Gibbs Lecture, he seems to think that arithmetic, logic and set theory (ZF) are what is called mathematics proper so they a priori trues whereas theories like Euclidean geometry, algebra etc... are conditionally true mathematical statements (this this axioms follow this this theorems). He seems to think -- and this seems like a common belief among mathematicians -- that there is something inherent in logic, arithmetic and set theory that makes them evident in themselves that all we need is to axiomatize them.

Finally, while Godel had beliefs in some kind of platonic truth of ZFC set theory, such beliefs are not tenable unless one first specifies what "truth" here is supposed to mean. Without doing so, it would be pointless to discuss such notions any further. Also, modern mathematicians generally do not ascribe platonic truth to all of mathematics.