2

Let $C$ be a conjecture about natural numbers. Let $$S = \{n\in N: n > m \text{ where $m$ is the first number found for which $C$ is false} \} $$

Is $S$ decidable?
If $C$ is true for all natural numbers then S is an empty language which is decidable.
If $C$ is false, then m exists and $S=\{m+1, m+2, ...\}$
Let $M_k$ be a machine that accept numbers $> k$ and rejects numbers $\le k$. I don't know which $M_k$ decides $S$, but I know one of them does. Is this sufficient to prove that $S$ is decidable?

Cookie
  • 13,532
user137481
  • 2,605
  • Yes, that is enough. – André Nicolas Jul 31 '14 at 21:49
  • Your answer, and even the question, seem to presuppose that the conjecture C is such that, if it's false, then it's because of at least one counterexample $m$ and that such counterexamples can be "found". Under those presuppositions, your proof is OK. – Andreas Blass Jul 31 '14 at 21:49
  • @AndreasBlass If a conjecture is false, then we agree that it has a counterexample, although it may not be possible to find it. However, since $C$ is fixed in $S$ rather than taken as an input, we do not even need the assumption that the counterexample can be found. We know which $M_k$ decides $S$ iff we can find the first counterexample $m$. – Dávid Natingga Aug 02 '14 at 15:42
  • @DavidToth No, I do not agree that false conjectures have counterexamples. That would be true if the conjecture has the form "for all $x$, $\dots$" but not for conjectures of other forms. – Andreas Blass Aug 02 '14 at 15:47
  • @AndreasBlass I assumed $C$ was of the form $\forall$... now I understand what you meant. What about my claim that we do not need to be able to find the counterexample $m$ for $S$ to be decidable. Do you agree with it? – Dávid Natingga Aug 02 '14 at 15:56
  • 1
    @DavidToth Whether we can find the counterexample is certainly irrelevant; mathematical facts are independent of us. The argument in the question is correct, provided only that the definition of $S$ makes sense. That definition refers to the "first number found", so it presupposes some notion of "finding" and some order of "found" things so that "first" makes sense. Whether the finding can be done by us, or by some algorithm, is irrelevant, but "first number found" needs to have some meaning. – Andreas Blass Aug 02 '14 at 16:01
  • @andre Andre and Andreas, thank you both for your comments. – user137481 Aug 05 '14 at 15:36
  • In classic mathematics this proof is true, But in constructive mathematics this is not a proof for solving your problem. – Erfan Khaniki Nov 26 '15 at 20:50

0 Answers0