Gödel's Incompleteness Theorem and the complexity of arithmetic - MathOverflow

Gödel's Incompleteness Theorem and the complexity of arithmetic

2010-09-03T10:08:12Z

In How complicated can structures be? Jouko Väänänen says:

The guiding result of mathematical logic is the Incompleteness Theorem of Gödel, which says that the logical structure of number theory is so complicated that it cannot be effectively axiomatized in its entirety. In other words, the theory is non-recursive, i.e. there is no Turing machine that could tell whether a sentence of number theory is true or not.

I've never seen Gödel's Incompleteness Theorem this way: that it's a matter of the overall complexity of the structure of the natural numbers that there are facts about them that cannot be proved.

So I wonder whether I can take the quote above literally:

Can Gödel's Theorem be rigorously stated in terms of complexity?

Somehow like this: "Every system which exceeds complexity threshold X is undecidable."

Or is it just a vague paraphrase, not to be taken too seriously?

Answer by Joel David Hamkins for Gödel's Incompleteness Theorem and the complexity of arithmetic

2010-09-03T10:26:20Z

Yes, this line of thought is perfectly fine.

A set is decidable if and only if it has complexity $\Delta_1$ in the arithmetic hiearchy, which provides a way to measure the complexity of a definable set in terms of the complexity of its defining formulas. In particular, a set is decidable when both it and its complement can be characterized by an existential statement $\exists n\ \varphi(x,n)$, where $\varphi$ has only bounded quantifiers.

Thus, if you have a mathematical structure whose set of truths exceeds this level of complexity, then the theory cannot be decidable.

To show that the true theory of arithmetic has this level of complexity amounts to showing that the arithmetic hierarchy does not collapse. For every $n$, there are sets of complexity $\Sigma_n$ not arising earlier in the hierarchy. This follows inductively, starting with a universal $\Sigma_1$ set.

Tarski's theorem on the non-definability of truth goes somewhat beyond the statement you quote, since he shows that the collection of true statements of arithmetic is not only undecidable, but is not even definable---it does not appear at any finite level of the arithmetic hiearchy.

Finally, it may be worth remarking on the fact that there are two distinct uses of the word undecidable in this context. On the one hand, an assertion $\sigma$ is not decided by a theory $T$, if $T$ neither proves nor refutes $\sigma$. On the other hand, a set of numbers (or strings, or statements, etc.) is undecidable, if there is no Turing machine program that correctly computes membership in the set. The connection between the two notions is that if a (computably axiomatizable) theory $T$ is complete, then its set of theorems is decidable, since given any statement $\sigma$, we can search for a proof of $\sigma$ or a proof of $\neg\sigma$, and eventually we will find one or the other. Another way to say this is that every computably axiomatization of arithmetic must have an undecidable sentence, for otherwise arithmetic truth would be decidable, which is impossible by the halting problem (or because the arithmetic hierarchy does not collapse, or any number of other ways).

Answer by Stefan Geschke for Gödel's Incompleteness Theorem and the complexity of arithmetic

2010-09-03T10:46:47Z

I agree with your statement "Every system which exceeds complexity threshold X is undecidable".

Let us focus on the specific case where we consider the the first order theory of a fixed structure. Once the structure is complicated enough to simulate (or to express) computation, the theory becomes undecidable.

This is based on the following easy proof of a weak form of the incompleteness theorem: In the language of number theory, you can write down a formula $\varphi(x)$ such that the natural numbers satisfy $\varphi(t_n)$ for a natural number $n$ iff $n$ is the Goedel number of a Turing machine that halts on an empty tape. Here $t_n$ denotes the term for the $n$-th successor of $0$.
If the theory of the natural numbers was decidable, then you could decide the halting problem.

Answer by none for Gödel's Incompleteness Theorem and the complexity of arithmetic

2012-03-02T07:07:28Z

Hmm, nobody has mentioned Chaitin's incompleteness theorem.