Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

140 Views Asked by At

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee (\textsf{ZFC} \vdash \neg\sigma)$, without providing a proof of $\textsf{ZFC} \vdash \sigma$ or a proof of $\textsf{ZFC} \vdash \neg\sigma$?

Of course this is not true for all statements $\sigma$, because $\textsf{ZFC}$ is not even complete (if it is consistent), but maybe this could be true for some specific $\sigma$.

More in general (if $\textsf{ZFC}$ is consistent ;) ), let $\Gamma$ be a set of axioms, and suppose we know that $T(\Gamma)$, the theory of $\Gamma$, is incomplete (and thus consistent). Is it possible that there exists some statement $\sigma$ such that we can show that $(\Gamma \vdash \sigma) \vee (\Gamma \vdash \neg \sigma)$ without proving $\Gamma \vdash \sigma$ nor $\Gamma \vdash \neg \sigma$?


I started to think about this some time ago in the specific case of $\textsf{P}$ vs $\textsf{NP}$. Maybe we are struggling to find a proof of $\textsf{P}=\textsf{NP}$ or of $\textsf{P} \neq \textsf{NP}$, when such a proof doesn't actually exist in $\textsf{ZFC}$. Thus it would be nice to be able to prove at least that an answer does exist. But maybe this is not possible.

Note that a somewhat "dual" result has already been proven:

Theorem (Hartmanis-Hopcroft). There exists a Turing machine $M$ that halts on every input, such that relative to the oracle $L(M)$, neither $\textsf{P}=\textsf{NP}$ nor $\textsf{P} \neq \textsf{NP}$ is provable in $\textsf{ZF}$, assuming $\textsf{ZF}$ is consistent.

You can find more about this in the paper Is $\textsf{P}$ Versus $\textsf{NP}$ Formally Independent? by Scott Aaronson (http://www.scottaaronson.com/papers/pnp.pdf).

1

There are 1 best solutions below

0
On

To continue steven taschuk's suggestion :

Let $N$ be some very big number, from which noone knows whether it is a prime number or not (for example the $33$-th Fermat-number).

If $N$ is prime or composite, in both cases there is a proof for this statement, but the result is unknown.

This can be applied to any decidable question whose answer is unknwon.