Proving a statement is true by proving it is undecidable.

747 Views Asked by At

https://www.youtube.com/watch?v=O4ndIDcDSGc

I was watching this numberphile video in which Professor Du Sautoy mentions that if the Riemann hypothesis is undecidable, it must be true.

Let's say we wanted to prove whether the statement A = 5 is true.

Our systems of axioms is this: A is a prime number, A is greater than 4, A is less than 8

The statement A = 5 is consistent with these axioms; however, the statement A = 7 is also consistent with these axioms.

Consequently, within this system of axioms, A = 5 is both provably true and false, and is consequently undecidable.

Does its undecidability also imply that it is true, or is my analogy substantially different than what Professor Du Sautoy is talking about.

Please try to explain this in simple language. I am an undergraduate non-math major.

2

There are 2 best solutions below

12
On BEST ANSWER

The phenomenon that a statement is true if it is undecidable occurs for statements that can be disproved by counterexamples. A statement of the form “$A(x)$ for all $x\in X$”, where $A(x)$ is some statement about $x$ and $X$ is some infinite set, can be disproved by showing that it is false for a single $x\in X$. By contrast, it cannot be proved by proving that it is true in individual cases, since there are infinitely many cases to consider.

If it is false, there is a counterexample, and the counterexample can be used to disprove it, so it cannot be undecidable; whereas if it is true, there are infinitely many examples of it being true, but they cannot be used to prove it, so it may still be undecidable. Thus, since it is compatible with undecidability that it is true but incompatible that it is false, undecidability implies that it is true.

The Riemann hypothesis is a statement of this form, namely that the Riemann zeta function is non-zero for all complex numbers that are neither negative even integers nor have real part $\frac12$.

Your example is not of this form. You have showed that it is compatible with the assumptions that the statement be true or false (which is different from it being “both provably true and false”), and thus that it is undecidable. But it doesn’t follow in this case that it is true, since in this case the statement being false does not provide a way to disprove it.

0
On

Following the logic above, why haven't we just proved that the problem is decidable?

If it's undecidable it cannot be false. Therefore it is true, and decidable. Hence we have a contradiction, and the statement cannot be undecidable to start with?

I guess that the implication "True -> Decidable" is incorrect, but why?