# Can we decide a conjecture is decidable without knowing a conjecture is correct or false?

Can we decide a conjecture is decidable without knowing a conjecture is correct or false?

I asked this question because I assume that the millenium prize problem is already to be decidable, otherwise the mathematician would need to consider infinity numbers of cases in order to get the money or the question's logic makes it a fake question.

-
What do you mean by "infinity numbers of cases"? – Willie Wong Jun 15 '12 at 16:18
@WillieWong - If i am not mistaken, if a problem is decicible, then it only have a limited possiblity to consider – Victor Jun 15 '12 at 16:20
@Victor: What exactly do you mean by "limited possibility to consider"? Note that "decidable sets" (sets $S$ for which there is an algorithm that will tell you in finite time, given $n$ whether $n$ is in $S$ or not) can be infinite, and describing the entire set may, in principle, require you to do infinitely many things (even if you only need to do finitely many for each integer). – Arturo Magidin Jun 15 '12 at 16:51

We need to be very clear and precise, so let me flood you with a bunch of definitions.

If we are talking about "decidable" and "undecidable", we are talking about formal systems.

In a formal system, we have primitive notions (undefined terms and relations/functions among them), axioms, rules of inference, and "grammatical rules" that tell us when a sequence of symbols is a well-formed formula.

A well-formed formula $F$ is provable in the formal system if there is a finite sequence of well-formed formulas such that each term of the sequence is either an axiom, or a consequence of previous formulas in the sequence that follows from the valid rules of inference, and such that the last term of the sequence is $F$.

We say a well-formed formula $F$ is decidable in the formal system if and only if either $F$ is provable, or its negation $\neg F$ is provable. It is undecidable otherwise.

A model of a formal system is a specific interpretation of the primitive terms that makes the axioms true.

A formal system is consistent if and only if it has at least one model.

It is a theorem of first order logic that a well-formed formula $F$ is provable in an axiomatic system if and only if $F$ is true in every model of the system. In particular, $F$ is undecidable if and only if there are models of the system in which $F$ is true, and there are models of the system in which $F$ is false.

Now, notice that while "decidable" and "undecidable" and formal notions: they refer to whether or not a particular formula can be formally deduced from the axiomatic system. By contrast, "true" and "false" are semantic notions: they depend on the meaning (the model) of the terms, and not only on their formal properties (which are given by the axioms and the rules of inference).

In a sense, showing that a formula is undecidable means showing that it is neither true nor false... rather, that it's truth or falsity will depend on the interpretation we give to the terms. A classical example is the Continuum Hypothesis: there does not exist an infinite subset of $\mathbb{R}$ that is not bijectable with either $\mathbb{N}$ or with $\mathbb{R}$. Turns out this is neither true nor false, it is undecidable (assuming Set Theory itself has models): there are models of set theory where it is true, and there are models where it is false. You have one theory in which you can assume it as an axiom, and another theory where you assume its negation as an axiom (in fact, infinitely many theories, one each for what different kinds of such sets there might be).

In a sense, if you already knew whether the conjecture is "true or false" (meaning, true in every model or false in every model), then you've already proven it, it is no longer a conjecture, and it cannot be undecidable. Or else you might be talking about "true in the standard model" (some theories have a 'standard' way of interpreting the terms, such as Peano Arithmetic), or "false in the standard model". In that case, knowing this only tells you that the statement is either provable or formally undecidable. (For example, Goedel proved that there is model of Set Theory in which the Axiom of Choice is true; that showed that it was impossible to disprove the Axiom of Choice, but it did not establish whether the Axiom of Choice was provable or whether it was undecidable; Paul Cohen later showed that there is a model where the Axiom of Choice is false, and that showed that the Axiom of choice was not provable, and so it must be formally undecidable).

For the Millenium Problems, some problems are known to be decidable; others may be undecidable. In some instances, undecidability would establish truth in the standard model. To see an example of this latter situation, think about the Goldbach Conjecture:

Goldbach Conjecture. Every even integer greater than $2$ can be written as a sum of two primes.

Suppose we could show that the Goldbach Conjecture is undecidable in Peano Arithmetic. This would show that it is true in the standard model. Why? Because if there were a counterexample to the Goldbach Conjecture, this could be established in finite time by simply going over all the even numbers and checking all sums of primes smaller than them; this would mean that its falsity in the standard model would be provable, so GC cannot be both undecidable and false-in-the-standard-model. Of course, there are other ways of interpreting the meaning of "number" ("non-standard models") in which GC would be false, but in the standard model it would be true.

The Riemann Hypothesis is one such question: if the Riemann Hypothesis were false, then this could be established by exhibiting a zero and verifying it is a zero (which can be done in finite time). So if the Riemann Hypothesis is formally undecidable, then it must be true in the standard model.

I have no idea what you are going on about with "infinity number of cases"...

-
@Victor: You really need to be a bit less trigger happy. I posted this answer about a minute ago, it would take longer than a minute to read it (let alone think about it), and yet you've already "disaccepted" Henning Makholm's answer and "accepted" this one. Why not wait a while and see what you get, and take the time to read the answer before enthusiastically clicking on the check mark? – Arturo Magidin Jun 15 '12 at 16:43
To arturo magidin: for infinity number of cases, i mean, for example, if there exist infinity of prime but prime does not exist in a special pattern – Victor Jun 15 '12 at 16:43
@Victor: I still don't understand. What makes you think that one needs to examine "infinity number of cases" to establish that something occurs or does not occur infinitely often? We can prove that "$n$ is a prime" is true infinitely often without having to examine each number one at a time; we can prove that "$n$, $n+2$, and $n+4$ are all prime" is true only for finitely many values of $n$ (in fact, for just one) without having to examine an infinite number of cases. Paul Cohen solved the Hilbert problem relating to the Continuum Hypothesis by showing that CH is undecidable. – Arturo Magidin Jun 15 '12 at 16:46
Thanks for this write-up, Arturo, I learned some things from it. I don't understand how the argument applies to the Riemann hypothesis, however - isn't it possible that that the Riemann hypothesis is false, but all its zeros are undefinable complex numbers? – MartianInvader Jun 15 '12 at 20:30
@MartianInvader: I don't understand what you mean by "undefinable complex number". There's the notion of computable, of course, but you don't have to compute the entire number in order to establish that it lies off the critical line, nor that it is a zero. As I understand it, the Riemann hypothesis is definitely in the class of "Formally undecidable implies true in the standard model." – Arturo Magidin Jun 15 '12 at 20:37

There are many families of problems where we can prove once and for all that every problem in the family is in principle decidable (say, in Peano arithmetic), but where it is also easy to produce instances where the actual answer is completely unknown and no feasible way to produce an answer is known.

One example would be problems of the shape:

Does (insert large number here) have a factor between (insert large number here) and (insert large number here).

It is easy to generate a concrete unsolved instance of this by computer -- just program it to generate a random RSA key pair, forget the private part, and select a random but plausible interval for the factor to fit into.

A different example:

Is there a proof of P=NP which can be encoded as a proof script for proof-checking system $X$ that is at most 2 gigabytes in length?

Again it is easy to show that either PA proves "yes, such a proof exists" or PA proves "no, there is no such proof".

-

Here is a genuine example from the mathematical literature. There are many other examples of this type.

Is every odd integer greater than $5$ representable as a sum of $3$ primes?

It was proved by Vinogradov that every sufficiently large odd integer is so representable. It is now known that in fact every odd integer greater than $10^{43000}$ is representable. So the original question has turned out to be decidable. We just don't know what the answer is.

-

There are a few relatively restricted areas of mathematics that are known to be decidable, e.g. Presburger arithmetic. But most conjectures are not known to be decidable. As far as I know, none of the Millenium Prize questions (except for the Poincaré conjecture which has already been proven) are known to be decidable. This does not in any way make them "fake". If anything, it adds to the challenge: in trying to solve the conjecture, you are attempting to do something that may or may not be possible.

-
To robert isreal: Isn't that one mst prove or disprove the conjecture in order to get the reward? – Victor Jun 15 '12 at 16:30
The fake question in my sense is that fake question is the type "i am 3 years old kid, am i a boy" such question, so can it be prove that no one could get the reward? – Victor Jun 15 '12 at 16:32
Proving that one of the conjectures is independent of ZFC would almost certainly count as a solution to the problem. The rules for the prizes do not speak about "proving the conjecture", but about a "complete mathematical solution", for which an independence proof would certainly qualify. – Henning Makholm Jun 15 '12 at 16:47
Of course it's also entirely possible that the statement that the conjecture is independent of ZFC is itself independent of ZFC. In the case of the Riemann hypothesis, if it's false it is provably false (a finite calculation would verify the existence of a zero off the critical line), so a proof that RH is independent of ZFC would be a proof of RH. – Robert Israel Jun 15 '12 at 17:33

Here's another perspective on a related question: a problem where we can prove that an 'answer' in some sense exists but we can also prove that we can't find the answer.

A graph is a set of vertices and a set of edges between those vertices - for instance, the vertices might be 'Hollywood actors' with an edge between any two actors who have appeared in a movie together, or the vertices might be 'US cities with more than 100,000 people', with an edge between any two cities within 500 miles of each other.

One graph is a minor of another if, essentially, you can tag some of the vertices in the larger graph matching the vertices of the smaller graph and 'draw edges' between them matching the edges of the smaller graph - in essence, it's like a subgraph (though there are obviously some minor technical details).

And finally, we say a collection of graphs is minor-closed if every graph that's in the collection also brings along all of its minors. For instance, the set of planar graphs (the ones that can be drawn in the plane without any of their edges crossing) is minor-closed this way; any subgraph, or any contraction of a subgraph, is still planar.

Now, the Robinson-Seymour theorem says that any minor-closed set of graphs can be defined by a small set of graphs that aren't in it, the so-called 'forbidden minors'; any graph that has one of these forbidden minors as a minor isn't in the collection, and all graphs that don't have any of the forbidden minors are in the collection. For instance, for the planar graphs there are two forbidden minors: $K_5$ (a graph with five vertices, and edges between every pair of vertices) and $K_{3,3}$ (a graph with three 'red' nodes and three 'blue' nodes, and every possible edge from one color to the other).

So, we know that for any collection of graphs we give, there's some set of forbidden minors defining those graphs; in this sense we have a 'yes' answer to the problem. But that doesn't mean that we can actually find the set of forbidden minors; in fact, even though that set is known to exist, it's also known that there can't be any procedure for finding them; any algorithm for taking (a description of) a set of graphs and finding its forbidden minors could also solve the halting problem.

-