19
$\begingroup$

According to wikipedia a theory (i.e. a set of sentences) is complete iff for every formula either it, or its negation, is provable.

On the other side, a logic is complete iff "semantically valid" and "provable" are the same.

The first notion of completeness is with what Gödel's Incompleteness result is concerned, but then I do not understand the significance given to it, or why it surprised people? Because if I read the first definition, if I can give a formula which is satisfied in one model, but not the other, then this formula and its negation could not be provable (if the logic is sound). And in general, I would expect this property more than the property that in every theory, every sentence either holds for all models (is valid), or its negation is valid.

To be more specific, Gödel's 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.

So, why did it come as a surprise? Did people really think that for every theory and a given formula, either it or its negation are semantically valid, i.e. fulfilled by every model?

$\endgroup$
  • 5
    $\begingroup$ In short, yes, they basically did. I don't know enough of the history of math to give a good answer, but I know that Hilbert firmly believed that there existed some complete, consistent theory. See, for instance, this wikipedia article. $\endgroup$ – Arthur Apr 6 '18 at 14:25
  • 4
    $\begingroup$ @StefanH Nothing of the sort. It's called the incompleteness theorem because it proves that no "reasonable" theory in the language of arithmetic can ever be complete. In particular, for example, it proves (under reasonable hypotheses) that PA is incomplete. That's a perfectly good reason to call it "the incompleteness theorem"! $\endgroup$ – Noah Schweber Apr 6 '18 at 15:22
  • 1
    $\begingroup$ "But this seems different than demanding that every formula or its negation is provable" Why? $Th(\mathcal{A})$ does indeed prove every statement or its negation, for any structure $\mathcal{A}$. In particular, TA (= $Th(\mathbb{N})$) is complete. Godel's incompleteness theorem can be thought of as saying that "TA is complicated:" in particular, all the recursively axiomatizable subtheories of TA are incomplete. $\endgroup$ – Noah Schweber Apr 6 '18 at 15:31
  • 1
    $\begingroup$ @StefanH Well, it's a computability-theoretic phrasing of it. "TA is not reasonable" and "no reasonable theory of arithmetic is complete" are of course equivalent (one of my requirements for "reasonable" is that it be true in $\mathbb{N}$), but I think the latter fits the "spirit" at the time better. More significantly, Godel's arguments can be extended to prove more: in particular, that no consistent recursive theory extending PA is complete regardless of whether it is true in $\mathbb{N}$. This is not a result about TA! $\endgroup$ – Noah Schweber Apr 6 '18 at 15:38
  • 1
    $\begingroup$ @StefanH "PA captures $\mathbb{N}$ up to isomorphism" No, it doesn't. Second-order PA does, but "PA" in this context (and almost always in logic) means first-order PA, which absolutely does not capture $\mathbb{N}$ up to isomorphism (we don't even need incompleteness to see this - the compactness theorem does it already, and in fact proves that no first order theory can ever capture any infinite structure up to isomorphism). $\endgroup$ – Noah Schweber Apr 6 '18 at 15:49
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. If I got it right, a counterexample to my statement would be to have $\mathcal A$, and as $\mbox{Th}(\mathcal A)$ is complete, when we also have some $\mathcal B$ with $\mbox{Th}(\mathcal A) \subsetneq \mbox{Th}(\mathcal B)$, i.e. the situation to have a complete theory but two models of if and a sentence satisfied by one, but not the other. Hope thats right. $\endgroup$ – StefanH Apr 6 '18 at 16:41
  • $\begingroup$ @StefanH I don't understand your comment. There is no pair of structures (in the same language) $\mathcal{A},\mathcal{B}$ with $Th(\mathcal{A})\subsetneq Th(\mathcal{B})$. Remember that complete theories have no consistent proper extensions in the same language! When you say "a counterexample to my statement," what statement do you have in mind? $\endgroup$ – Noah Schweber Apr 6 '18 at 16:42
  • 1
    $\begingroup$ @StefanH I think the key points are: (1) There certainly are complete theories. In particular, "$Th(\mathbb{N})$" is one of them (in fact, the complete theories are exactly the theories of the form $Th(\mathcal{A})$ for some structure $A$ - this is a good exercise). (2) Godel's theorem proves that a large class of theories are not complete. (3) The mere existence of nonisomorphic models of a theory does not suggest anything about whether that theory is complete or not; in particular, the existence of nonstandard models of PA doesn't suggest incompleteness of PA. (cont'd) $\endgroup$ – Noah Schweber Apr 6 '18 at 16:56
  • 1
    $\begingroup$ So the surprising-ness of GIT is a reflection of how confident (many) people were that $Th(\mathbb{N})$ did in fact belong to that "large class" mentioned previously (namely, the recursively axiomatizable theories of arithmetic which consist only of true sentences). This expectation - I think - came from two things: (a) the (very old) belief of the mathematical community that "every problem is solvable," and (b) the (very new) belief of at least a large portion of the mathematical community that mathematics could be captured by a single formal system (= reasonable first-order theory). (cont'd) $\endgroup$ – Noah Schweber Apr 6 '18 at 16:58
  • 1
    $\begingroup$ What Godel showed (philosophically speaking) was that these two beliefs are in tension with each other: to the extent that we believe mathematics can be viewed as taking place within some reasonable first-order theory we have to believe that there are mathematical problems which are unanswerable. Of course, the alternative perspective is that mathematics is not tied to a single formal theory, and this (I believe) was the perspective advocated by Godel himself. But Godel certainly revealed a tension between two foundational ideas about what mathematics is, and that tension was surprising. $\endgroup$ – Noah Schweber Apr 6 '18 at 17:00
31
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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 :

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks, but I do not understand your last remarks, if I have a formula $A$ such that neither $A$ nor $\neg A$ is provable, then why should $A$ be false? By symmetry of negation consider $B := \neg A$, then it is also a formula such that neither $B$ nor $\neg B$ is provable, but it is a true statement if $A$ is false? $\endgroup$ – StefanH Apr 6 '18 at 14:45
  • $\begingroup$ Oh, okay, got it, you do not mean the sentence itself but your quoted paragraph. $\endgroup$ – StefanH Apr 6 '18 at 14:47
  • $\begingroup$ So, has Gödel shown that in the first order case, where Gödel also holds for $\mathbb N$ with addition and multiplication, this theory has two models and sentences true in one, but not in the other (as asked in the comment above)? $\endgroup$ – StefanH Apr 6 '18 at 14:48
  • 1
    $\begingroup$ @StefanH - accordinf to our "intuition" about truth and the natural numebr system, one of $A$ and $\lnot A$ must be false. $\endgroup$ – Mauro ALLEGRANZA Apr 6 '18 at 16:00
  • $\begingroup$ Do you have any more specific reference for your last claim, any paper by Kleene? $\endgroup$ – StefanH Apr 6 '18 at 16:18
10
$\begingroup$

Godel's incompleteness proof is published in 1931. In 1931, the mathematical community's response to your question

"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?"

and comment

"Because if I read the first definition, If I can give a formula which is satisfied in one model, but not the other, then this formula, and its negation could not be provable (if the logic is sound)."

is "What's a model?"

Some mathematical logic from before the 1950s was subsequently recognized as model theoretic. But model theory wasn't a thing until Tarski and his students fleshed it out in the 1950s and 1960s.

The setting of Hilbert's extreme optimism is described in some detail in Hilbert's Philosophy of Mathematics, especially section 5, "Hilbert's Programme and Logical Positivism".


Added in edit, 20180407.

Skolem for instance did not interpret either of his Lowenheim-Skolem Theorems (the first, with AC and the second, without) in a model theoretic sense. I was first exposed to this in [G],

"From our perspective, it is obvious that the possession of set-theoretic properties, if relative to anything, is relative to the model one is using to interpret the formal system. Several writers have noted that this was perhaps not obvious to Skolem who, they claim, often interpreted the LST as demonstrating the relativity of set-theoretic notions to the axiom system itself (see, e.g., his 1929b, 293 [sic]; and 1958, 635-637)." Those references are

  • 1929b 'Uber einige Grundlagen fragen der Mathematik', Skrifrer, Vitenskapsakadernie I, 4, 1-49; reprinted in Skolem 1970, 227-273.
  • 1958 'Une relativisation des notions mathematiques fondamentales', in Colloque: nationaux du Centre National de Recherche Scientifique, Paris, 13-18; reprinted in Skolem 1970, 633-638.
  • 1970 Selected works in logic, edited by Fenstad, J.E., Oslo (Universitetsforlaget).

In short, when we say the Lowenheim-Skolem theorem is a theorem about models, we are very much putting words into Skolem's mouth. He writes as if the axioms pick out a unique model, so the study of models would be redundant. He also writes as if the existence of non-standard models of arithmetic are a defect of the underlying logical system not of the proposed model axiom systems. See

  • Skolem, "Uber die Unmoglichkeit einer vollstandigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems. Norsk Matematisk Forening, Skrifter, pages 73–82, 1933. (reprinted in Skolem 1970, 345–354.)

  • Skolem, "Uber de Nichtcharakterisierbarkeit der Zahlenreihe mittels endlich oder abzahlbar unendlich vieler Aussagen mit ausschliesslich Zahlen-variablen. Fundamenta Mathematicae, 23:150–161, 1934. (reprinted in Skolem 1970, 355–366.)

It's easy to look back in time and frame the work of others in terms that were not available and would have been alien to them. When we push the ideas and language of model theory earlier than the mid-1930s, we are guilty of doing so. And even then, once such terms become available they are not instantly available to all practitioners; it can take more than a decade for the good ideas to be communicated widely and explained clearly.

[G] George, A., "Skolem and the Lowenheim-Skolem Theorem: A Case Study of the Philosophical Significance of Mathematical Results", History and Philosophy of Logic, 6 (1985), pp. 75-89, http://www.fitelson.org/140A/george.pdf .

$\endgroup$
  • 1
    $\begingroup$ I'm still confused by the claim that there was no notion of model around 1930, though. Even if "model theory" was only recognized as a separate field later, I can't see how they could have done without some concept of structures that satisfy a particular set of axioms. How could they speak about logical validity otherwise? Which word did they use about the Klein and Poincaré models that were used in the late 1800s to show the consistency of hyperbolic geometry? $\endgroup$ – Henning Makholm Apr 7 '18 at 22:58
  • $\begingroup$ @HenningMakholm : Those were just "other geometries". In particular, they are embeddings into sneaky subsets of Euclidean geometry, so they are at least as consistent as Euclidean geometry. Beltrami is usually associated with the consistency of hyperbolic geometry, but he certainly doesn't frame it in this language -- he just shows, for example, that chunks of the pseudosphere admit hyperbolic geometry. Claims that he has shown consistency don't come until later, after that idea exists. $\endgroup$ – Eric Towers Apr 8 '18 at 1:52
  • $\begingroup$ @HenningMakholm : Perhaps I'll add some words about how, for example, Skolem interpreting the Lowenheim-Skolem Theorem as relativivity of set-theoretic notions to the axiom system, not as a model theoretic idea. $\endgroup$ – Eric Towers Apr 8 '18 at 2:05
  • $\begingroup$ @HenningMakholm : In editing in some history of Skolem on the LST, I am reminded that, for a very long time, it was widely believed that there were no non-standard models -- each set of axioms picked out a unique model. Skolem persisted in thinking this even after the LST, believing non-standard models were a defect of the underlying logical system. And he was not alone in thinking this. $\endgroup$ – Eric Towers Apr 8 '18 at 2:50
  • $\begingroup$ x @EricTowers: How could anyone have believed that "there were no non-standard models" if, as you say, they did not have a concept of "model" at all? $\endgroup$ – Henning Makholm Apr 8 '18 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.