17
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Your main question "Can Godel ....in terms of complexity" is somewhat ambiguous: because the term complexity might be construed here either as logical (or quantifier) complexity, or as computational complexity. In the former case, as J.D. Hamkins showed, the answer to your question is "yes". In the latter case, I would presume the answer might be "no". (On the other hand, Godel's incompleteness phenomenon does hold for weak theories (bounded arithmetic), which have formal relations with computational complexity classes.) $\endgroup$
    – Iddo Tzameret
    Commented Sep 3, 2010 at 12:47
  • $\begingroup$ What kind of complexity does Väänänen mean, one might ask? (Might it be case that he has in mind a more abstract concept of complexity?) $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 3, 2010 at 12:59
  • 1
    $\begingroup$ I presume Väänänen meant computational complexity, that is, computability? In fact, it's hard for me to imagine an interesting formulation of Godel's incompleteness that doesn't involve computability: you could just say that PA is incomplete, but that seems too localized to be interesting; or there's the cocktail-party version that "arithmetic can't be axiomatized" which, taken literally, is false (just take the set of all sentences true in the structure (N, +, times)). $\endgroup$
    – John Goodrick
    Commented Sep 4, 2010 at 3:25
  • 1
    $\begingroup$ There are several meanings of complexity here. One is computational complexity, e.g. polynomial-time computation. Another is the sort of complexity measured by the arithmetical hierarchy. A third is the internal combinatorial structure of a particular model. In this informal third sense, dense linear orders have little complexity, while nonstandard models of PA have great complexity. In the quote above, I think the third sense is being alluded to. However, Väänänen does mention computational complexity in the context of finite models later in his paper. $\endgroup$
    – Carl Mummert
    Commented Sep 4, 2010 at 11:25
  • $\begingroup$ Interestingly, empty set + adjunction suffices to interpret Robinson arithmetic, which is essentially undecidable. $\endgroup$
    – user76284
    Commented Nov 15 at 20:28

3 Answers 3

Reset to default
30
$\begingroup$

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).

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How could "simulate (or express) computation" be defined rigorously? $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 3, 2010 at 11:07
  • 1
    $\begingroup$ One rigorous definition would be the following (I know that this looks almost silly, but this is a general criterion that I can come up with): There is a computable function $f$ assigning to each natural number (or description of a Turing machine, if you wish) $n$ a sentence $\psi_n$ in the language of the structure such that the structure satisfies $\psi_n$ iff the Turing machine with Goedel number $n$ halts on the empty tape. Such a function exists in case of the natural numbers, namely, let $\psi_n=\varphi(t_n)$. $\endgroup$
    – Stefan Geschke
    Commented Sep 3, 2010 at 13:11
  • 1
    $\begingroup$ Comment continued: In order to prove the existence of a function $n\mapsto\psi_n$ you would usually need to show that you can actually "simulate" computation in your structure in one way or other. $\endgroup$
    – Stefan Geschke
    Commented Sep 3, 2010 at 13:12
  • 1
    $\begingroup$ When we consider the natural numbers as an infinite directed graph, what are the properties of this graph, that enable it to simulate computation, and that other infinite graphs do not have? What are its sufficient and what are its necessary properties? (Infinitely many distinguishable (=adressable) nodes?) $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 3, 2010 at 15:40
4
$\begingroup$

Hmm, nobody has mentioned Chaitin's incompleteness theorem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice and very relevant point — but could you say at least a little more here, so that this isn’t just a link-only answer? $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Dec 8, 2023 at 12:14
  • $\begingroup$ @Peter, the user you are addressing has not been seen here since March 2012. $\endgroup$
    – Gerry Myerson
    Commented Dec 9, 2023 at 1:30
  • 1
    $\begingroup$ @GerryMyerson: oops, I’d misread the “edited” date as the “answered” date and thought this was new… $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Dec 9, 2023 at 10:12

You must log in to answer this question.

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