I am an inexperienced logician, so I may be completely missing something major in this question. I also may be misconstruing the idea of decidability. However, I was wondering if all 6 of the remaining Millennium Prize Problems are decidable in the sense of Gödel. If any of the associated theories were not decidable, wouldn't that have far-reaching applications in the world of mathematics? Thanks in advance, and I hope that my question makes sense.
$\begingroup$
$\endgroup$
4
-
6$\begingroup$ Your question does seem a little bit off, because if any such problem was proved to be independent of some mainstream axiomatic system such as ZFC, you would have definitely heard about it. As for the question is it possible that one of them is, I seem to recall that this has been extensively discussed on MO already. $\endgroup$– Thierry ZellCommented Apr 18, 2011 at 17:20
-
6$\begingroup$ +1. I voted to re-open, since the question seems quite reasonable to me, and I can imagine that additional answers might be posted about whether any of the specific problems have such a nature that one can prove something about the possiblility that they are independent. (Which is to say nothing against David's excellent current answer.) $\endgroup$– Joel David HamkinsCommented Jul 29, 2011 at 12:59
-
$\begingroup$ can someone provide the link to the duplicate question if there really is one? $\endgroup$– vznCommented Oct 19, 2012 at 5:21
-
$\begingroup$ A closely related question is my own For which Millennium Problems does undecidable -> true?. Perhaps because the latter question is more specific, it attracted no adverse comments; neither was it answered. Apparently questions in this class are generically difficult and open. $\endgroup$– John SidlesCommented Oct 11, 2013 at 20:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
There are very few results which allow us to know that a mathematical claim will be provable or disprovable within ZFC without actually proving or disproving it. To the best of my knowledge, the only exceptions are theories which have quantifier elimination. Few1 open mathematical problems which people are interested in are of this sort, and none of the Millenium problems are. So any of the Millenium problems could be independent of ZFC (except for the Poincare conjecture, because it has been proved!)
You might be particularly interested in Scott Aaronson's survey on whether or not it is likely that $P \neq NP$ is independent of ZFC.
1 Here is an example of a question which I know is decidable in ZFC, yet whether the answer is "yes" or "no" is open.
Do there exist $44$ vectors $(u_i, > v_i, w_i, x_i, y_i)$ in $\mathbb{R}^5$, each with length $1$, and with the dot product between each pair $\leq 1/2$? See Wikipedia for background.
This is the a first order question about real numbers, so it is decidable by Tarski's theorem. The analogous result for four dimensional vectors was only obtained in 2003; if you can get the answer for $5$ dimensions, it should be publishable in a good journal. I think this about as interesting a question as one can find which is definitely settleable in ZFC, yet still open. Most questions mathematicians care about are not of this form (and, in my opinion, are much more interesting).
answered Apr 18, 2011 at 17:22
-
1$\begingroup$ I was about to write a comment on the OP to this effect, but this answer is much more comprehensive, so +1. $\endgroup$ Commented Apr 18, 2011 at 17:24
-
2$\begingroup$ So the problem in $\mathbb{R}^5$ involves testing the emptiness of semi-algebraic set in 220 variables with 946 inequalities and 44 equations? Hmm... I can see why brute force will not help us here. :) $\endgroup$ Commented Apr 18, 2011 at 17:30
-
10$\begingroup$ If you know that some particular mathematical claim is provable or disprovable in ZFC, then you can find the proof/disproof by exhaustive search. Therefore the only possible obstacle to actually finding the proof/disproof is computational infeasibility. Conversely, it is easy to cook up examples of decidable mathematical claims that are infeasible to decide. For instance, is the first decimal digit of Graham's number greater than 5? en.wikipedia.org/wiki/Graham%27s_number A more interesting example is whether there exists a projective plane of order 12. $\endgroup$ Commented Apr 18, 2011 at 20:25
-
6$\begingroup$ Another example is the existence and uniqueness of the monster simple group. It's obviously decidable (check all the possible multiplication tables), but not in any feasible way, and the actual proofs involve deep ideas. $\endgroup$ Commented Apr 19, 2011 at 0:09
$\begingroup$
$\endgroup$
7
Most of the Millennium Prize Problems are individual problems, with a single yes or no answer. Decidability as a question only really makes sense in the context of a countably infinite family questions, where you can ask whether it's decidable which of those questions should be answered yes.
-
17$\begingroup$ I imagine the question meant whether they are independent of ZFC. $\endgroup$ Commented Apr 18, 2011 at 16:25
-
5$\begingroup$ I imagine that the questioner should have used the correct terminology then. $\endgroup$ Commented Apr 18, 2011 at 16:55
-
15$\begingroup$ To be fair, he said "decidable in the sense of Gödel", and Gödel referred to "formally undecidable propositions" (or rather "formal unentscheidbare Sätze") in the very title of his paper. This terminology has definitely become less standard since then, but it is still relatively common in informal usage. $\endgroup$ Commented Apr 18, 2011 at 17:08
-
6$\begingroup$ @Henry. Whether or not there exists a set whose cardinality is strictly between the cardinality of the natural numbers and the cardinality of the real numbers is also a yes-or-no question. $\endgroup$ Commented Apr 18, 2011 at 18:50
-
10$\begingroup$ @Henry and Felipe: I think the two of you are quibbling over the definition of "undecidable". As the comments above attest, there is a sense in which each of you is correct. $\endgroup$ Commented Apr 18, 2011 at 19:16