11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you trying to prove $\forall n: P(n)$? $\endgroup$ – Thomas Andrews Mar 2 '15 at 3:03
  • $\begingroup$ Yes sorry I will add that $\endgroup$ – ASKASK Mar 2 '15 at 3:03
  • $\begingroup$ Let's say we're working with the axioms of Peano Arithmetic (look them up if you haven't heard of them). Now, there are unprovable statements in it, like Goodstein's Theorem (a theorem involving exponents and base-$b$ notation), that can't be proven using PA but are still true. Also: PA can't prove that Goodstein's Theorem is unprovable. Can you see why your argument doesn't hold? $\endgroup$ – Akiva Weinberger Mar 2 '15 at 4:17
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice clean explanation. Thank you. $\endgroup$ – ASKASK Mar 2 '15 at 3:16
  • $\begingroup$ Let $P(n)$ be $0=1$ (or $0=n+1$, if you insist that it actually depend on $n$). Then $\forall n\,P(n)$ is unprovable, and for any counterexample $n$, we can construct a proof of $\neg P(n)$, yet $P(n)$ is false. What the argument actually shows is the statement “If $\forall n\,P(n)$ is not disprovable, but etc.” $\endgroup$ – Emil Jeřábek Mar 2 '15 at 15:33
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm sorry, but can you elaborate on what $\exists m>n(Q(m,n))$ mean? $\endgroup$ – ASKASK Mar 2 '15 at 3:08
  • 2
    $\begingroup$ Given some proposition $Q$ with two free variables, that means that $P(n)$ means "there exists an $m$ bigger than $n$ such that $Q(m,n)$ is true," The point is that having an $n$ for which this is false is not easily determined. @ASKASK $\endgroup$ – Thomas Andrews Mar 2 '15 at 3:10
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.