6
$\begingroup$

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.

  • 0
    @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).2012-06-15

5 Answers 5

13

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"...

  • 0
    @MartianInvader: There are known finitistic methods that decide whether the zeta function has a zero in a specific region (on or off the critical strip). That's how the hypothesis has $b$een "verified up to..." certain ranges of complex numbers. So you would be able to, finitistically, express a particular region of the complex plane contained off the critical strip and then determine that it contains a zero of the zeta function.2012-06-15
8

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".

7

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.

2

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.

  • 0
    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.2012-06-15
2

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.