Does Godel's Incompleteness theorem only prove that some self referential sentences are unprovable?

Question

It shows that the sentences of the form $\forall x, \neg Dem(x,sub(n,y,n))$ are true but unprovable, where $y$ is the Godel number mapped to the symbol $Y$ in arithmetic language, and $n$ is the Godel number of the sentence $\forall x, \neg Dem(x, sub(Y,y,Y))$

Suppose for some $y$, the sentence $\forall x, \neg Dem(x,sub(n,y,n))$ has the Godel number 1000. Then following is a true but unprovable property of the number 1000:

"The number 1000 can never be at the end of a sequence of natural numbers $x_{k}, k=1,2,3,....n$, such that every $x_{k}$ is either a Godel number of an axiom or of a sentence logically deducible from the axioms."

Properties like this, however, are a very narrow class of the properties of natural numbers. Is this even an arithmetic property? I'm asking this because this property does not involve operations of arithmetic like addition, multiplication. Instead, it involves decoding the number to a language of symbols and using rules of logical deduction. Arithmetic properties are something like '$\forall x, 10x\neq 5, x\in Z$'

Even if this is accepted as an arithmetic property, it is a very narrow class of arithmetic properties. These properties are also dependent on the map that we use for the one-to-one correspondence between integers and symbols (there are multiple maps possible). Does the Incompleteness theorem say anything about non- self referential properties of numbers?

Answer 1

The first incompleteness theorem states that certain theories, under certain conditions, are incomplete.

To prove that something is incomplete, you need to provide a witness of that. But of course, if the example of incompleteness is something like the Goldbach Conjecture, or the Riemann Hypothesis, what would be the example once you add those statements to your theory? The proof needs to be robust.

Well, Gödel's proof is generic, it uses the fact that theories with certain properties can encode certain statement, and this is how the witness is produced. By creating these "self-referential statements". The second incompleteness theorem is slightly deeper, and it talks about a theory not being able to verify its own consistency, which is arguably a more interesting example.

But if your goal is to prove incompleteness, you need to be able to do it in a generic, constructive way. And since we decide, socially, what are "meaningful statements", it's hard to do that with "meaningful statements".

Some people fall into the trap of thinking that incompleteness is only with regards to "meaningless self-referential statements and consistency statements", but if we take a gander at set theory, we see this is very much not true. And while it is admittedly harder to find independence in the natural numbers, it is still not impossible. (And arguably, consistency statements are meaningful mathematical statement.)

Answer 2

Properties like this, however, are a very narrow class of the properties of natural numbers. Is this even an arithmetic property?

Yes, this is achieved via Gödel's encoding.

Does the Incompleteness theorem say anything about non- self referential properties of numbers?

What would be your definition of "self referential properties of numbers"? The most striking example of an unprovable sentence is given by Gödel's second theorem : let $F$ be your system, the sentence $Cons(F)$ which states that $F$ is consistent, eg $Cons(F) := \neg Dem("0 = 1")$, is not provable by $F$.

Answer 3

There are many true statements of arithmetic which are unprovable in the first-order arithmetic, and some of them have nothing to do with self-reference. One example is the Hydra game.

A hydra is a rooted, finite tree. The leafs of the tree are called the heads of the hydra. A round in the Hydra game consists in choosing a head of the hydra and removing it, then moving one step closer to the root, taking a copy of the subtree and attaching a copy of it at that node (see the link for an example.) The Hydra game ends when the tree is empty.

You win the Hydra game if you cut the hydra down in a finite number of moves. One can show not only that you can win the Hydra game for any tree, but that no matter in which order you choose to cut of the heads, you will always win the Hydra game. That is, the Hydra game is impossible to lose.

The idea is to associate every play of the Hydra game to a strictly descending sequence of ordinals, which terminates in the empty set if and only if the game terminates. Since a strictly descending sequence of ordinals always terminates, this shows that the Hydra game always terminates.

This statement is unprovable in first-order arithmetic. The reason is that it's equivalent to the statement the ordinal $\varepsilon_0$ is well-ordered, a statement that can used to show that first-order arithmetic is consistent (this result is known as Gentzen's consistency proof). By Gödel's incompleteness theorem, it cannot be implied by the axioms of first-order arithmetic.

Answer 4

As others have said, the very distinction you're trying to draw is fuzzy to the point of meaninglessness, and there are very natural examples of undecidable (with respect to any of the usual theories) sentences. However, there's a very nice fact which hasn't been mentioned yet and I think puts the final nail in the coffin:

For every "reasonable" theory $T$, there is a Diophantine equation $\mathcal{E}_T$ such that $\mathcal{E}_T$ has no solutions but $T$ cannot prove that $\mathcal{E}_T$ has no solutions.

It's hard to get more concrete and arithmetic than Diophantine equations!

Here as usual "reasonable" means "computably axiomatizable, consistent, and extending $Q$" (although even that is overkill: we can replace "extending $Q$" with "interpreting $R$" or even weaker hypotheses - see here, Section $4$). The result above is a more-or-less immediate consequence of the proof of the MRDP theorem: basically, we can assign to $T$ a Diophantine equation $\mathcal{E}_T$ such that putative solutions to $\mathcal{E}_T$ correspond to putative contradictions in $T$. Of course, the $\mathcal{E}_T$s so produced are truly god-awful, but they are honest-to-goodness Diophantine equations