2
$\begingroup$

Look at statements such as these:

  1. All nontrivial zeroes of the Riemann Zeta function lie on the critical line.

  2. Every even integer greater than 2 can be expressed as the sum of two primes.

  3. Every perfect number is even.

Suppose that any statement like these is proven to be undecidable or independent of ZFC. Wouldn't that be the same as proving it to be true?

Because if it's undecidable or independent we can never find a finite counterexample, so it's safe to assume that it's true.

Or does this simply mean that statements such as the above can't be undecidable or independent of ZFC? If yes, what is the exact criterion for something to be a "statement such as these"?

$\endgroup$
4
$\begingroup$

Suppose that any statement like these is proven to be undecidable or independent of ZFC. Wouldn't that be the same as proving it to be true?Because if it's undecidable or independent we can never find a finite counterexample, so it's safe to assume that it's true.

Yup!

In general, a statement of the form "there is no [thing] such that [fact]" is true if it is (a) un-disprovable from (say) ZFC,

and (b) is reasonably "simple": the "things" have to be things we can search through in an "easy" way (like natural numbers, and unlike arbitrary real numbers), and the "fact" has to be something which is "easy" to check (like "is prime," and unlike "has the property that there are infinitely many primes with that difference").

These, ultimately, turn out the be the $\Pi^0_1$ sentences - this is a notion of complexity coming from both proof theory and computability theory. Or rather, they are the sentences equivalent to some $\Pi^0_1$ sentence.

At this point it's good to see some examples:

  • The Goldbach conjecture is manifestly $\Pi^0_1$.

  • The Twin Prime Conjecture is not (so far as we know) equivalent to a $\Pi^0_1$ sentence: a "counterexample" to TPC is an $n$ such that there are no twin primes above $n$, but "there are no twin primes above $n$" is not an "easy to check" property.

  • Finally, there are really interesting situations where something that (a) doesn't look $\Pi^0_1$ and (b) isn't known to be provable is still equivalent to a $\Pi^0_1$ sentence. The Riemann hypothesis (RH) is a great example of this: it is not obviously $\Pi^0_1$ - a counterexample to RH is a complex number, and there's no easy way to search through all the complex numbers. However, it turns out that we can prove in ZFC that RH is equivalent to a certain $\Pi^0_1$ sentence - see this question - and so (in a surprising way!) has the property that, if it is un-disprovable in ZFC, it is true.


Incidentally, there's nothing too special about ZFC here. The only property of ZFC being used to show that $\Pi^0_1$ sentences not disprovable in ZFC are true, is the fact that it is $\Sigma^0_1$-complete: if $\varphi$ is a true $\Sigma^0_1$ sentence, then ZFC proves $\varphi$. Much weaker theories have this property - even theories much weaker than PA!

$\endgroup$
  • $\begingroup$ Thanks, it's nice to see that my intuition here was correct. $\endgroup$ – orlp Oct 12 '17 at 14:00
  • $\begingroup$ I don't understand one point - prove un-disprovability means prove true, but how can prove independence means prove true? $\endgroup$ – user202729 Oct 12 '17 at 14:02
  • $\begingroup$ @user202729 If it's independent, then it's undisprovable ... $\endgroup$ – Noah Schweber Oct 12 '17 at 14:03
  • $\begingroup$ Can you give some example? I find that somewhat confusing. $\endgroup$ – user202729 Oct 12 '17 at 14:05
  • 1
    $\begingroup$ @user202729 No, because when we're talking about independence etc. we need to specify a theory. What we really have (for $\varphi$ a $\Pi^0_1$ sentence) is that for $T, S$ appropriate theories, if $T$ proves that $\varphi$ is un-disprovable from $S$ then $\varphi$ is provable from $T$. But this is no issue at all: the theories in question aren't the same. (This is the same situation we're in with Godel's incompleteness theorem: when we prove that the Godel sentence is unprovable in PA, that proof is taking place in the stronger theory PA+Con(PA), so there's no contradiction.) $\endgroup$ – Noah Schweber Oct 12 '17 at 14:32

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.