Is every property of the integers provable?

Question

I've been researching provability of properties, and I came across and interesting argument which states that every property of the integers is provable, yet doesn't the incompleteness theorem tell us that this is false? The proof is:

Let $P(n)$ be a property of the integers. Let us assume that ($\forall n:P(n)$) is unprovable, therefore it is impossible to prove it false. This means that it is impossible to give a counterexample, and thus no such counterexample exists. Because no counterexample exists, the statement must be true, and is therefore provable (we just proved it), which is a contradiction.

Wouldn't this mean that all properties of the integers are provable?

Answer 1

No. The proof contains all sorts of badness. In any particularly useful definition of "provable" (i.e. provable by a consistent system with a recursively enumerable set of axioms), Godel's theorem does indeed hold. The fact that the proof doesn't address exactly what it means by "provable" is another issue altogether - and a slightly worse one is that it doesn't say what it means by "property".

Let me address two issues. The first is that what this proof actually claims is:

If $P(n)$ is unprovable, then $P(n)$ is true.

However, in order to extend this to $P(n)$ is provable, we would need to prove that $P(n)$ is unprovable, not just take it as an assumption. This proof does not suppose that we can prove $P(n)$ is unprovable - merely that it is. If we cannot prove $P(n)$ is unprovable, then we cannot prove it is true by the logic of the proof. It is actually a necessary consequence of Godel's theorem that there are statements which are unprovably unprovable (see here). The proof does nothing to fix this hole.

A much worse issue is that the proof assumes that it is "easy" to verify any counterexample. The proof is introducing another assumption in thinking that a counterexample would provably be a counterexample - really, the statement it proves is:

If $P(n)$ is unprovable, but one could construct a proof of $\neg P(n)$ for any counterexample $n$, then $P(n)$ is true.

We could consider something like the negation of Fermat's Last Theorem - in particular let $P(n)$ be the statement that there are solutions to $x^{n}+y^n=z^n$. To prove $P(n)$ was false for some specific $n$, we would need to prove that there were no solutions - and there's no formulaic way to do that. Sure, we can get away with setting $P(n)$ to statements like "this turing machine halts in $n$ steps", where we can run it for $n$ steps to verify or disprove the statement (i.e. a proof of $\neg P(n)$ exists if it is true), but this is far from every statement we might be interested in.

Answer 2

One of many good strategies for understanding what's going on in a proof (whether it's a good proof or a bad proof) is to go through it with an example. You know that the incompleteness theorem should supply examples of properties $P(n)$ such that $\forall n : P(n)$ is unprovable, so let's pick one. The example I'll use is that $P(n)$ asserts that $n$ does not code a proof of a contradiction in Peano arithmetic (PA).

So $\forall n : P(n)$ asserts that PA is consistent, and by the incompleteness theorem, we know that PA cannot prove this statement unless it is itself inconsistent. So let's see what happens when we run this example through the proof. The problem is here:

Because no counterexample exists, the statement must be true, and is therefore provable

No! Part of the lesson of all this incompleteness business is that there can be statements that are true but unprovable, such as the consistency of PA (assuming it is true)!

(we just proved it)

We didn't prove it in PA! Whenever you say that a statement is unprovable, you mean unprovable with respect to some fixed axiom system, which here is PA. This proof is not a proof in that axiom system. Instead, it's a proof in a "metatheory" that we are using to analyze properties of axiom systems such as PA.

Also, assuming that $\forall n : P(n)$ is unprovable is equivalent to assuming that PA is consistent, and as we know, PA can't prove this.

Answer 3

This is true for certain types of expression $P$, but by no means all.

For example, if the statement is of the form $\exists m>n(Q(m,n))$, then there might not be an example.

And if this $P$ is true, it still might not be provable because you can find, for each $n$ a value $m$ by trial and error, but you can't prove it by a finite proof. Indeed, this is one of the limits of proof - the finiteness. For example, the Collatz Conjecture might be true, but it might not be provable with a finite number of steps.

How do you prove that you have a counter-example to the Collatz conjecture? It might not be possible.

Answer 4

I think this is a simple counterexample: every integer represents a Turing machine and ‘halts’ is a property.

So if I understand correctly what you mean by prove and property, you're secretly trying to solve the halting problem. So in fact there is a property which is not just unprovable but worse, undecidable.