3
$\begingroup$

Are there undecidable problems for which a single truth exists?

For example, the question about parallels is not decidable from Euclid axioms. But multiple answers are valid and give different kinds of geometries. That kind of proposition is not what I am talking about.

I know it's going to be a bit philosophical and maybe it doesn't have its place here but I would like an answer from a mathematical point of view.

So a bad example of what I am talking about : "is there a God?" this problem is undecidable however there is certainly only a single valid answer.

So I am not asking whether there is a God or not. I am asking if there are, in the field of mathematics, such questions known as undecidable, which only have a single valid answer (that will always remain a mystery, consequently).

$\endgroup$

2 Answers 2

4
$\begingroup$

There are many undecidable statements about the integers, but most people (including me) believe that the integers truly exist.

So any statement about the integers is either true or false, even if it is undecidable.

$\endgroup$
4
  • $\begingroup$ Any other area of mathematics where such problems exists? Or is it harder to have a belief about it as strong as the "belief" integers exists? $\endgroup$
    – davcha
    Oct 25, 2014 at 15:25
  • $\begingroup$ @davcha: I chose the integers (I really meant the natural numbers) partly because the first undecidability theorems by Godel were about the natural numbers. Also, most people accept the integers. Even Kronecker, the skeptic of many kinds of numbers, wrote "God made the integers; all else is the work of man." Other areas have undecidability theorems, but the natural numbers are easier to understand. $\endgroup$ Oct 25, 2014 at 16:32
  • $\begingroup$ If you were reading in a science-fiction or fantasy book the story of a guy who had such an undecidable problem in the field of maths applied to physics as an ultimate last chance solution. Whether or not he got lucky in the end, would you think that makes sense or not? $\endgroup$
    – davcha
    Oct 26, 2014 at 13:15
  • $\begingroup$ @davcha: Such a situation would be hard to construct and harder to make believable. For one thing, "undecidability" depends on the exact axioms used. Some statements are undecidable in Peano arithmetic but are decidable in the usual first-order arithmetic. Part of Gödel's contribution was to show that any first-order system including arithmetic where it is computable to find whether or not a statement is an axiom has some undecidable statements. But which statements depend very much on the particular axioms. $\endgroup$ Oct 26, 2014 at 17:40
1
$\begingroup$

The answer to your question depends on what exactly you mean by "question", "decidability" and "only a single valid answer".

A question in the sense of computability theory is usually identified with the set of its yes-instances. E.g. the question "which natural numbers have the property P?" is identified with the set of natural numbers having the property P. Such a question (i.e. set of yes-instances) is then called decidable if there is an algorithm which given an (encoding of an) arbitrary instance decides in a finite amount of time whether this instance belongs to the set of yes-instances. In the example, the algorithm would receive a natural number n as input and decide in a finite amount of time whether the number n belongs to the set of yes-instances of the question P, i.e., whether n has the property P.

In this sense of decidability there are no undecidable questions with a "single valid answer": if there is only one answer, it is independent of the input. Hence the trivial algorithm which simply ignores its input and outputs "yes" (or "no", depending on what the valid answer is) serves to give a decision procedure for the question.

We might not know which of the two possible algorithms is correct, but the question is still decidable in the technical sense.

$\endgroup$

You must log in to answer this question.

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