15
$\begingroup$

Goedel's incompleteness tells us that any system containing Robinson arithmetic is incomplete. OTOH, Presburger Arithmetic, which contains only the successor and addition, is complete. I'm pretty sure that I have read that it possible to define a complete arithmetic with only sucessor and multiplication axioms. So, this raises the question about what is special about the combination of addition and multiplication.

In reviewing the proof of Goedel's theorem, I thought I had located the key point: the $\beta$-function involves both addition and mutliplication. Without that, we cannot get to the primitive recursive functions, which means we cannot arithmetize syntax, so you cannot form the Goedel sentence, and there is nothing that says it cannot be proved. This isn't a 100% satisfying, but it makes a certain amount of sense.

But then I learned that there are self-verifying theories which can arithmetize syntax despite being much weaker than Robinson arithmetic. So that cannot be right.

Is there, then a simple explanation of why the combination of addition and multiplication is necessary for incompleteness to kick in?

$\endgroup$
2
  • $\begingroup$ I didn't think I would ever say this, and I don't know whether it's right, but this question could be a better fit over at math overflow $\endgroup$
    – Arthur
    Sep 23, 2017 at 7:18
  • 2
    $\begingroup$ Noah's answer already identifies "finite sequences" as the key. Any system that can perform basic reasoning about finite sequences will necessarily be incomplete. But I wish to point out that your question is based on a misconception (that I too once had) that it is due to some special interaction between addition and multiplication, or at least due to the number theoretic structure of the naturals. That is really quite false! See this post that explains why computability is the key. Note that the theory of concatenation is weak but incomplete. $\endgroup$
    – user21820
    Mar 27, 2018 at 15:40

1 Answer 1

13
$\begingroup$

Looking back at this question I'm quite dissatisfied with my original answer: it wasn't wrong, but it missed some important content. I believe this new version is much better.


The end of your post focuses on the second incompleteness theorem, but you open with the first, so let me split this question into two parts:

  1. How much arithmetic do we in fact need for the first incompleteness theorem?

  2. How much arithmetic do we in fact need for the second incompleteness theorem?

Briefly, the answer is this:

Only the simplest properties of addition and multiplication are needed for the first incompleteness theorem. However, the second incompleteness theorem is more complicated.

To get into the right spirit, we need to realize that these are different theorems: although the usual treatment of GFIT yields GSIT as a corollary, there's no reason to believe that that usual treatment is optimal in terms of axiomatic overhead, and hence no reason to believe that GFIT and GSIT each require the same amount of arithmetic. In fact, GSIT is much more "expensive," while GFIT uses only the very basic additive/multiplicative structure of $\mathbb{N}$ (and consequently is much better understood).


First, GFIT. Here's a more-or-less optimal version:

Suppose $T$ is a computably axiomatizable and consistent theory in the language $\{0,1,+,\cdot,<\}$ such that the following is provable in $T$:

  • Each true quantifier-free sentence.

  • For each $n\in\mathbb{N}$, the sentence $$\lambda_n\equiv\forall x(\underline{n}<x\vee \bigvee_{i\le n}x=\underline{i}),$$ where "$\underline{k}$" is the numeral corresponding to $k$.

Then $T$ is incomplete.

If we like we can use the relational version, replacing each operation with its graph - this matches Willard's approach, we just have to add "single-valuedness" axioms, at least for tuples of numerals.

In snappier jargon, Robinson's arithmetic $R$ is essentially incomplete; usually the better-known $Q$ is mentioned here, but it's overkill. There is still more to be said on exactly how optimal this is - see e.g. Section $4$ of this paper of Beklemishev. However, I would confidently say that this is optimal phrasing amongst "natural" theories.

So as you expected the very bare minimum of arithmetic is enough for at least one Godelian phenomenon to occur, and consequently for GFIT we have a very snappy characterization of what "enough arithmetic" is: more or less, we need addition, multiplication, and "discreteness," and that's it. We don't even need that addition is commutative, or that there is no largest number, or that $<$ is a linear order, or etc.! (Note however that we can't drop that second bulletpoint above since $Th(\mathbb{R};0,1,+,\cdot,<)$ is computable.)


For GSIT, on the other hand, per Willard things are much messier.

For any Godel-y argument to apply we need to be able to code sequences appropriately and prove basic facts about the (image within the theory of the) coding apparatus, and the meaning of "basic facts" varies between GFIT and GSIT. For GFIT, it's basically enough for computable functions to be representable; for GSIT, the manipulations we need to perform are much more intricate and don't lead (as yet) to a snappy characterization. In particular, GFIT doesn't need addition and multiplication to be always defined, just defined on each specific pair of actual natural numbers, while by contrast dropping totality was exactly what opens the door for Willard's self-verifying theories.

To see why GSIT plausibly requires more axiomatic power, recall its proof: from a putative proof of "I am consistent," we extract a proof of the Godel-Rosser sentence $\sigma$ by arguing within the theory that the failure of $\sigma$ (namely, a proof of $\sigma$ shorter than any disproof of $\sigma$) would entail a contradiction in our theory. But this hides a totality assumption! Specifically, we would need to argue within the theory that we can "search through all possible proofs of a given length in finite time," and while this may appear trivial at first it's really not.

If we have a proof of $\sigma$ of length $m$ shorter than any disproof of $\sigma$, the corresponding disproof of $\sigma$ would naively have length something like $\sum_{i<m} i2^i$ since for each $i$ we need to check each of the exponential-in-$i$-many possible disproofs of $\sigma$ of length $i$). We can do somewhat better, but we're never going to be able (per Willard) to get around the issue that the exhaustive proof p' of $\neg\sigma$ which we get from a putative proof p of $\sigma$ with no shorter disproof of $\sigma$ will in general have to be much longer than $\sigma$, so our theory can't prove that we can actually get p' from p without appropriate totality assumptions.

I think this paper of Willard - though technical - is well worth your time, since it really dives into some of the fine points of exactly what needs to break for what else to break. Visser's Another look at the second incompleteness theorem is also quite good; and, while not directly related, Visser's delightfully-titled paper Oracle bites theory discusses another situation where an "obvious" result about proof construction breaks down since we can't prove the necessary totality principle.

(And although it's orthogonal to your question, we can also ask what basic properties of the underlying logical system are necessary. This isn't something I know much about, but see here.)

1Dan Willard: Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles, Journal of Symbolic Logic 66 (2):536-596 (2001). DOI: 10.2307/2695030, JSTOR, author's website

$\endgroup$
5
  • $\begingroup$ Out of curiosity, why the downvote? $\endgroup$ Mar 21, 2020 at 15:03
  • $\begingroup$ People downvote for the oddest reasons. If it makes you happy, I can rescind my upvote and then vote again... :P $\endgroup$
    – Asaf Karagila
    Mar 21, 2020 at 15:17
  • $\begingroup$ @AsafKaragila Oh, I know, I just always hold out hope that it's a content-ful downvote. (This is weird stuff, and if there's a point where someone thinks I'm talking nonsense I'm happy to explain more.) $\endgroup$ Mar 21, 2020 at 15:18
  • $\begingroup$ in the second bullet point is the big conjunction supposed to be a big disjunction? $\endgroup$
    – D.R.
    Nov 26, 2022 at 19:24
  • $\begingroup$ @D.R. Whoops, good catch - fixed (and I've taken the opportunity to remove a redundant sentence as well)! $\endgroup$ Nov 26, 2022 at 21:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .