With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?
Solution 1:
Did people really thought that for every theory and a given formula, either it or its negation are semantically valid, i.e. fulfilled by every model?
(Emphasis added). No, of course not. It's easy to make theories that are obviously incomplete.
But the content of Gödel's incompleteness theorem is not just that "there are some theories that are incomplete", but that every reasonable axiomatization of basic arithmetic will be one of the incomplete theories.
Many mathematicians in the beginning of the 20th century did expect that there would be some way to present a foundation of mathematics in a way that would (at least in principle) resolve every question we could pose about it. The feeling was that it was just a matter of figuring out how to do that, and there was a general feeling of making progress towards the goal.
Then along came Gödel and proved that it cannot be done -- not even for basic arithmetic.
Solution 2:
EDIT: I've added here some of the facts from the discussion between me and the OP in the comments below the question. These doesn't address the actual OP - "why was Godel's theorem surprising?" - but I think they clear up some relevant confusions.
Godel proves (essentially) that any recursively axiomatizable theory which is true of $\mathbb{N}$ is incomplete; in particular, that under reasonable hypotheses the specific theory PA is incomplete. (Note that TA by definition is complete - see below - but by the compactness theorem does not pin down $\mathbb{N}$ up to isomorphism.) Note that this is equivalent to the statement that the true theory of arithmetic TA is not recursively axiomatizable, so it's expressible without ever using the word "incomplete." However, the computability-theoretic interpretation above doesn't really capture the spirit of the theorem at the time.
Also, focusing on TA causes us to miss an important extension of the theorem: that no complete consistent theory extending PA is recursively axiomatizable! This merely involves a simple tweak to the proof, but it's fundamentally about PA rather than about TA (and incidentally PA here can be replaced with a vastly weaker theory).
You write:
To be more specific, Gödels result in its original formulation is concerned with Peano arithmetic, but it also holds in some form of first order theory of the natural numbers with multiplication and addition as primitive notions, and for this we know that the natural numbers are not the only model.
But this isn't true in the way you want it to be. The proof that the first order theory of the natural numbers (call this "TA" for "true arithmetic") has models not isomorphic to the standard model is via the compactness theorem. However, these models do satisfy all the same sentences that $\mathbb{N}$ does! That is, they are not isomorphic to, but they are elementarily equivalent to, the standard model $\mathbb{N}$.
The key point here is that TA is a complete theory. Specifically, we define TA as $\{\theta: \mathbb{N}\models\theta\}$, that is, the set of first-order sentences true in $\mathbb{N}$. This is complete because for any sentence $\eta$, either $\mathbb{N}\models \eta$ (in which case $\eta\in$ TA) or $\mathbb{N}\models\neg\eta$ (in which case $\neg\eta\in$ TA). More generally, for any structure $\mathcal{A}$ the set $Th(\mathcal{A})=\{\theta: \mathcal{A}\models\theta\}$ is a complete theory. Note that we are not claiming that $Th(\mathcal{A})$ characterizes $\mathcal{A}$ up to isomorphism! A consequence of compactness is that elementary equivalence - that is, agreement on all first-order sentences - is strictly weaker than isomorphism, and so having lots of models in no way suggests incompleteness (e.g. DLO has lots of nonisomorphic models, but is complete). Thus, producing nonisomorphic models does not show that a theory is incomplete.
The above explains why existing results didn't immediately imply the incompleteness theorem. But, why couldn't existing techniques give a quick proof?
Well, the problem is that there were really only two techniques for building models: one could either prove the existence of a model via compactness, or one could find a structure "in nature" (or cook one up by hand) and prove that it was a model of the desired theory.
The compactness theorem is unhelpful for showing that PA is incomplete:
To show that PA is incomplete, it's enough to find a model $M$ of PA and a sentence $\varphi$ such that $M\models\varphi$ but $\varphi$ isn't in TA.
Once you've picked an appropriate $\varphi$, you can do this via the compactness theorem applied to PA + $\varphi$ ...
if you know that PA + $\varphi$ is finitely satisfiable! By the completeness theorem, you know that PA + $\varphi$ is finitely satisfiable iff PA + $\varphi$ is consistent (trivially "finitely consistent" and "consistent" mean the same thing), so all you need to do is ...
... pick some sentence $\varphi$ not in TA (= false in $\mathbb{N}$) such that PA + $\varphi$ is consistent.
Aaaaand we've gone in a circle!
Another option would be to first find a nonstandard model $M$ of PA and then show that $M$ is not elementarily equivalent to $\mathbb{N}$ by explicitly finding a sentence which they disagree about. This type of argument is extremely useful in cases where the theory being studied has lots of easily-describable models. However, $\mathbb{N}$ is the only easily-describable model of PA in a precise sense! While this wasn't known at the time, it does mean that the failure of attempts to explicitly find nonstandard models of PA not elementarily equivalent to $\mathbb{N}$ is not surprising.
The point is that there was no concrete evidence for PA being incomplete at the time, at least from the model-theoretic side.
Solution 3:
It may be useful to point out that there are (at least) two purposes for which axiomatic theories are created and, as a result, two sorts of theories, for which we may have very different expectations. One situation, known since the time of Euclid, is that we have a particular mathematical structure (plane geometry, or the natural numbers, or the complex numbers, etc.) whose properties we want to organize in a systematic way. So we take a few (easily understood and accepted) properties as axioms and deduce the rest. The second situation, which seems to have arisen only in the 19th and 20th centuries, is that we have numerous structures in which we have observed some similarities, and we summarize the similarities by axioms that apply to all those structures. A major example would be the axioms for groups, which are designed to apply equally well to integers with the operation of addition, permutations with composition, sets with symmetric difference, and many other structures.
For axiom systems of the second sort, it would be silly to expect completeness. The axioms were designed to apply to many different structures, so any aspects in which those structures differ would be undecidable on the basis of the axioms. For example, it would be silly to expect the axioms of group theory to prove or refute the commutative law, because the axioms were designed to apply to commutative examples (addition of integers) and non-commutative examples (composition of permutations).
For axiom systems of the first sort, though, the expectations were quite different. Since the axioms were intended to describe one particular structure, one would want to deduce, from the axioms, all the properties of that structure. Any meaningful statement $A$ about that structure would be true or false, so one would expect to deduce $A$ or to deduce $\neg A$, whichever is true in the intended structure. If the axioms failed to produce such deductions, then one could reasonably say that they were deficient, that the person putting together the axiomatic system had omitted some information that ought to be there.
Until Gödel's theorem appeared, such expectations were quite reasonable for axiomatic systems of the first sort, like PA or Principia Mathematica (the one system explicitly named in the title of Gödel's paper) or ZFC. And it seems to have been almost universally accepted that, even if the known axiomatic systems were incomplete, the situation could be corrected by adding more axioms in some reasonable way. That is, we should be able to give an axiomatic foundation for all the mathematical facts about, say, the natural numbers and real numbers, or about plane geometry, etc. Part of Gödel's great achievement was to show that such expectations cannot be met, in the case of arithmetic or in the case of set theory, if the axiom system is to be reasonable, i.e., if we want to be able to tell, without divine inspiration, what is and what is not an axiom.
Solution 4:
Because in the 30s, that was the context of Gödel's results, when the questions was firstly posed, the "expectations" were different.
See the first modern textbook of mathematical logic, with the first clear definition of waht we now call meta-mathematical problems :
- David Hilbert & Wilhelm Ackermann, Principles of Mathematical Logic, English transl. (1950) of the 2nd German ed. 1937, page 42:
Let us now consider the question of completeness. The completeness of an axiom system may be defined in two ways. First, it may be taken to mean that all the true formulas of a certain domain which is characterized by content can be proved from the set of axioms. However, the concept of completeness may also be more strictly formulated, so that an axiom system is termed complete only if a contradiction always arises when there is added to the axioms a formula not previously provable from them.
Applied to predicate calculus, the first question was solved (in the positive) by Gödel Completeness Theorem:
Any universally valid formula of the predicate calculus is provable.
But the question can be asked also about a system with non-logical axioms. And this is the aim of Gödel's 1931 Incompleteness Theorem :
If to the Peano axioms we add the logic of Principia mathematica (with the natural numbers as the individuals) together with the axiom of choice (for all types), we obtain a formal system $S$, for which the following theorems hold:
I. The system $S$ is not complete [entscheidungsdefinit] ; that is, it contains propositions [sentences] $A$ (and we can in fact exhibit such propositions) for which neither $A$ nor $\lnot A$ is provable.
But to say that we can exhibit a sentence $A$ of the system $S$ (corresponding to Peano's arithmetic) such that neither $A$ nor $\lnot A$ is provable in $S$, means that it is not true
"that all the true formulas of a certain domain which is characterized by content [in this case : the domain $\mathbb N$] can be proved from the set of axioms."
The existence of non-standard model for arithmetic was proved by Th. Skolem in 1933.
It seems that only around 1950 was firstly noted (by S.C. Kleene into his Introduction to Metamathematics (1952), page 430) that the existence of nonstandard models of the usual axioms of elementary number theory was derivable by juxtaposing Gödel's completeness theorem and his incompleteness theorem.