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.
Best Answer
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.