6
$\begingroup$

Just a curiosity:

Is there an assertion of which a proof (formalizable, say, in ZFC) is not known but a proof that it's not undecidable (in ZFC) is known?

Edit: after the comments, I think the actual question was

Is there an ("interesting") assertion of which neither a proof (formalizable, say, in ZFC) of it or its negation is known but a proof that it's not undecidable (in ZFC) is known?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Well, $0 = 1$ will do... There is no known proof that is formalizable in ZFC, but it is known that $ZFC \vdash \lnot(0 = 1)$, regardless of whether ZFC is consistent or not. (Since quid might scold me again for being unclear: I'm writing this because what you wrote is probably not what you meant...) $\endgroup$
    – François G. Dorais
    Commented Sep 8, 2011 at 22:20
  • 6
    $\begingroup$ See David Speyer's answer here mathoverflow.net/questions/62144/… $\endgroup$
    – Gjergji Zaimi
    Commented Sep 8, 2011 at 22:21
  • 4
    $\begingroup$ Any decidable but (so far) infeasible open problem. Such as: what is the 5th Ramsey number? (en.wikipedia.org/wiki/Ramsey_number) $\endgroup$
    – Daniel Mehkeri
    Commented Sep 8, 2011 at 22:49
  • 3
    $\begingroup$ A simple way to put your question: "Is there an assertion in ZFC which is known to be decidable but has not been decided yet." The answer is YES, see the link in Gjergji Zaimi's comment. $\endgroup$
    – GH from MO
    Commented Sep 8, 2011 at 22:49
  • 3
    $\begingroup$ In fact deciding any decidable assertion is nothing more than a computationally challenging problem: one simply needs to generate all possible proofs in ZFC and find the one which decides the assertion. $\endgroup$
    – GH from MO
    Commented Sep 8, 2011 at 23:11

3 Answers 3

Reset to default
13
$\begingroup$

If it's known that some statement $S$ is decidable in ZFC, then you can just run a computer program that enumerates all ZFC-proofs and stops when it finds a proof of $S$ or a proof of $\neg S$. By hypothesis, this algorithm is guaranteed to terminate. Therefore, the only possible obstacle separating decidable statements from decided ones is computational complexity.

In other words, the only possible instances of what you're looking for are statements that have already been proved up to a finite computation. Until they were actually proved, the Kepler Conjecture and Catalan's Conjecture were perhaps the most interesting examples of this type. I can't think of other examples of comparable interest offhand, but maybe others can.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ The odd Goldbach problem is only known for $n<10^{18}$ or $n>e^{3100}$, according to en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture. $\endgroup$
    – Kevin Ventullo
    Commented Sep 9, 2011 at 5:02
  • 4
    $\begingroup$ Another one which was of comparable interest until it was settled: Is there a simple group of order 808017424794512875886459904961710757005754368000000000 ? Clearly checkable by finite computation! $\endgroup$
    – David E Speyer
    Commented Sep 9, 2011 at 13:48
  • $\begingroup$ @Timothy: Your response elaborates on my earlier comment above. $\endgroup$
    – GH from MO
    Commented Sep 9, 2011 at 14:45
  • $\begingroup$ @GH: Sorry, I didn't see your comment until after I posted. (By the way, I had already made essentially the same comment in response to David Speyer's answer here: mathoverflow.net/questions/62144/… ) $\endgroup$
    – Timothy Chow
    Commented Sep 9, 2011 at 20:21
  • 1
    $\begingroup$ @KevinVentullo : A couple of years after you originally posted your comment, Helfgott announced a proof of Goldbach's weak conjecture. The proof seems to have been generally accepted, so that's another potential example that has "bitten the dust." $\endgroup$
    – Timothy Chow
    Commented Dec 12, 2016 at 15:32
11
$\begingroup$

It shouldn't be hard to find a large number $N$ such that no one knows a proof that $N$ is prime and no one knows a proof that $N$ is not prime. Yet the question of the primality of $N$ can't be undecidable - there is a simple (if impractical) algorithm for deciding it.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ How about a handsome tower of 2's plus 1? $\endgroup$
    – GH from MO
    Commented Sep 8, 2011 at 22:55
  • $\begingroup$ Is $2^{43112621}-1$ prime? $\endgroup$
    – Gerald Edgar
    Commented Sep 9, 2011 at 0:08
  • $\begingroup$ @Gerald: Hmm. I may be misinterpreting it, but my reading of mersenne.org/report_exponent/… is that its Lucas–Lehmer residue, independently confirmed by two people (with another failed attempt), is nonzero, therefore the number is composite, even though no explicit factor is known. $\endgroup$
    – Emil Jeřábek
    Commented Sep 9, 2011 at 10:58
  • 1
    $\begingroup$ @GHfromMO For that sort, we can make it even worse if instead of primality we ask whether the number has an even or odd number of distinct prime factors, and if we add a small amount to it to make sure that there isn't any hidden pattern involving numbers very close to powers of 2, then we could ask if 2^2^2^2^2^2^2 +35 has an even or odd number of distinct prime factors. This is decidable. But there also is likely not enough computational power in the observable universe to answer this essentially simple arithmetic question. $\endgroup$
    – JoshuaZ
    Commented Jan 25 at 3:06
7
$\begingroup$

There's tons of assertions like that in finite combinatorics. For example the Ramsey numbers R(5,5) and R(6,6) can be "straightforwardly" (i.e. given impractically large computing resources) found by direct enumeration. It's known that $43\le R(5,5) \le 49$ and $102\le R(6,6)\le 165$. But Wikipedia's article on Ramsey theory quotes Joel Spencer:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.

The article Graham's number has another interesting example.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .