50

Let me set up a strawman:

One might entertain the following criticism of Godel's incompleteness theorem: why did we ever expect completeness for the theory of PA or ZF in the first place? Sure, one can devise complete theories semantically (taking all the statements that hold in some fixed model), but one has usually discovered something special (e.g. elimination of quantifiers) when a naturally framed theory just turns out complete.

Now perhaps one could defend Godel's theorem as follows:

By Godel, the theory of the standard natural numbers has no recursive axiomization, but equally remarkably PA has no recursive non-standard models (Tennenbaum's theorem). That means that the incompleteness of arithmetic has a deeper character than, say, the incompleteness of group theory -- there exhibiting groups with distinct first-order properties easily suffices.

My question:

Does there exist any sort of converse to Godel's incompleteness theorem. A converse might say that when one has incompleteness and also some reasonable side condition (I'm suggesting but not committed to "there exists only one recursive model"), then there must exist some self-reference mechanism causing the incompleteness? Or stronger perhaps, the theory must offer an interpretation of some sufficiently strong theory of arithmetic?

Sled
  • 103
David Feldman
  • 17,466
  • 6
    The phrase 'causes the incompleteness' is problematic. One way to show that ZFC is incomplete is to use forcing to show that ZFC does not prove CH nor its negation. This is much closer to incompleteness for the theory of groups than Gödel's argument. Furthermore, it is hard to imagine how the independence of CH might be caused by some syntactic self-reference mechanism. – François G. Dorais Oct 22 '11 at 12:48
  • 2
    On the other hand, if you restrict to $\Pi_1$ statements, then I believe the answer is yes since you can encode $\Pi_1$ facts into Con($T$). See http://mathoverflow.net/questions/67214/ This is probably the limit since Con($T$) is a $\Pi_1$ statement for any axiomatizable theory $T$. – François G. Dorais Oct 22 '11 at 12:53
  • 4
    For every undecidable set $X$, there are theories whose decision problem is of the same Turing degree as $X$. Hence one cannot expect that there is a single undecidable problem that lies behind all undecidable theories. – David Harris Oct 22 '11 at 14:13
  • 9
    I like your question, but the motivation seems far-fetched to me. Just to recall the obvious: we believed (or we hoped) that PA and ZF were complete, because Euclidean Geometry is complete (once corrected for the gaps in Euclid's text relative to the real), and was felt to be complete well before it was formally proved by Tarski, and that Eucildean Geometry has been a strong ideal of what a mathematical theory should be. When we felt strong enough to do with mathematics at large what Euclid did with geometry (that is, after Cantor and Frege), we tried... and we failed. We are still crying... – Joël Oct 22 '11 at 15:11
  • 8
    Godel's second incompleteness theorem states that a theory $T$ does not prove its consistency assuming that (1) $T$ is consistent, (2) (the set of Godel codes of) $T$ is recursively enumerable, (3) $T$ contains a large part of the Peano axiom system. Now (1) is obviously needed and (2), (3) are necessary even to formulate the claim, i.e., Con(T), so in this sense, Godel's second incompleteness theorem has a converse. – Péter Komjáth Oct 22 '11 at 20:02
  • 2
    Do you want to show something of the form:

    Let $T$ be a recursively enumerable, consistent theory which cannot be extended to any consistent, complete, recursively enumerable theory. Then $T$ has XYZ properties.

     – Will Sawin Oct 23 '11 at 18:59
  • 2
    The question also mentions Tennenbaum's theorem. If ZFC has models at all, none of them are recursive. What about: are there recursively axiomatised theories which are incomplete, and which have exactly one recursive model, but which do not encode enough arithmetic? – Daniel Mehkeri Oct 23 '11 at 19:13
  • @Daniel: Dense linear orderings without endpoints would do! (And much more...) I guess "exactly one recursive model" is slightly ambiguous. – François G. Dorais Oct 23 '11 at 19:55
  • @François: the theory of dense linear orderings without endpoints is complete isn't it? – Daniel Mehkeri Oct 23 '11 at 22:29
  • 5
    Gödel’s incompleteness theorem holds for all recursively axiomatized extensions of Robinson’s arithmetic Q, nevertheless Q (and some stronger theories, such as IOpen + the Bézout property) has nonstandard recursive models. – Emil Jeřábek Oct 24 '11 at 10:16
  • 2
    You write "By Godel, PA has no recursive axiomizations". But the Peano axioms are a recursive set. You may have meant, as also Will Sawin has suggested, "PA has no recursive completion". (Reference: Tarski-Mostowski-Robinson, Undecidable theories.) – Goldstern Oct 24 '11 at 11:38
  • @Daniel: Yes, I misread your question. – François G. Dorais Oct 24 '11 at 17:43
  • 1
    Thank you goldstern for catching my slip -- but I fixed it another way, acceptably I hope? – David Feldman Oct 25 '11 at 07:13
  • You may want to check sequential theories defined by Pavel Pudlak. Also have a look at these slides by Albert Visser: http://www.bbk.ac.uk/philosophy/our-research/ppp/MiniCourseVisser2.pdf There are interpretability versions of Godel's theorem that might be helpful in what you are looking for. – Kaveh Jan 22 '13 at 19:24
  • See Lawvere's Theorem for the minimal conditions necessary for setting up a self-referential paradox: http://www.mat.ub.edu/EMIS/journals/TAC/reprints/articles/15/tr15.pdf – Mark Gomer Aug 22 '13 at 22:13

2 Answers2

2

I will attempt to answer the first question, which I think is more philosophy than math. Consider the integers. We have strong intuitions about the integers being a very definite set of things, which we all have access to. Furthermore, if we accept a naive second order axiomization, the integers are the only thing this axiomization describes. This should survive formalization: after all we only want to describe this one model that Peano arithmetic seems to describe perfectly.

Obviously what I said above is only intuition, and is in fact hopeless. But I am willing to use second order theories to save arithmetical consistency. Of course, this has a price: describing models is hard, logic on second order theories loses a lot of nice features, but if you are willing to sacrifice an entire branch of mathematics in your worldview, you can somewhat avoid having to consider weird models of the integers.

Watson Ladd
  • 2,419
  • 13
  • 19
  • 1
    Sorry, I'm a bit confused over what the connection is - do you take the fact that $\mathbb{N}$ has a categorical second-order description to be evidence for, or against, a converse to Goedel? – Noah Schweber Jun 23 '13 at 02:27
  • 2
    Oh, I see: you're addressing the question "Why did we ever expect completeness?" Nevermind. – Noah Schweber Jun 23 '13 at 05:31
-3

A theory containing the axiom of arithmetics without the multiplication operator is complete. In some sense, a recursive theory containing the axiom of arithmetics (with the multiplication operator) may be considered as the minimum that is required for incompleteness. You ask whether any incomplete theory with one recursive model has to have self-reference property. Well it seems that we can embed this theory into the recursive theory of PA. Recursive theory that contains PA with PM as its inference rule is the minimum required for achieving incompleteness.

Yonatan
  • 1
  • 4
    Wrong - theories far weaker than (or incomparable with) $PA$ have the incompleteness property. Also, it's not specifically multiplication that's the culprit; the theory of arithmetic with just multiplication is also decidable. It's the expressive power afforded by the combination of + and $\times$. The problem is, it's hard to tell exactly how much power is needed; hence the question. – Noah Schweber Aug 23 '13 at 01:37
  • Also, what do you mean by "embeds"? – Noah Schweber Aug 23 '13 at 05:34