This question already has an answer here:

I'm reasoning like this: (I don't have enough math education)

Suppose that the Collatz Conjecture is undecidable. This means, the Collatz conjecture cannot be proved to be true or false. This means,

$A)$ No one can never prove that the Collatz conjecture is correct.

$B)$ No one can never prove that the Collatz conjecture is false. This implies that, no one can never find a counter-example for the Collatz Conjecture.

Then, I can write, (with non-standard notation)

$$\color{red}{\text{undecidability}= A \cup B}$$

But, here I confused. Because,

The claim "No one can never find a counter-example for the Collatz Conjecture" implies that : the counterexample does not exist.

Otherwise, if there exist a counter-example, it is mathematically possible to establish the existence of that sample. It is irrelevant that mathematics cannot afford it. Because, saying "We don't have mathematical tools, "saying "Not mathematically possible," is definitely different from each other. So, we can deduce that the Collatz conjecture is "correct", not undecidable. Because, the claim $"B"$ implies us, the counterexample does not exist. And this contradicts very harshly with the claim $A.$

My problem is, I can't think of $A$ and $B$ together. Where am I making mistakes in my reasoning?


marked as duplicate by samerivertwice, Yanior Weg, Matthew Daly, ThorWittich, AlexR Oct 19 at 13:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ See this question. $\endgroup$ – Fabio Somenzi Aug 26 at 22:11
  • 7
    $\begingroup$ It's not so clear that, even if someone handed you a counterexample, you would be able to verify that it is indeed a counterexample - if it enters a cycle, okay, you can verify that, but if it diverges to infinity, who knows! There is a subtle logic question here though: it's perfectly possible for a question in which you could verify any counterexample to be undecidable - even with the understanding that this would mean that it must be "true" (...with the caveat that this mostly exposes how we can't really model the "truth" with nice sets fo axioms...) $\endgroup$ – Milo Brandt Aug 26 at 22:47
  • $\begingroup$ @Milo - why not make your comment an answer? I think it fits very well. $\endgroup$ – Gottfried Helms Aug 27 at 0:01
  • $\begingroup$ The thing is that if its undecidable you cannot prove wether a counterexample exist or not. A counterexample can exist however as bizarre as it sounds. It might also not exist and always reach $2$-$1$ cycle but still be undecidable. If its undecidable we still cannot prove the former with traditional mathematics. $\endgroup$ – Natural Number Guy Aug 27 at 12:20
  • 4
    $\begingroup$ Your reasoning is almost correct, and in fact applies in some cases (e.g. the Goldbach conjecture), but the statement has to be easier : it has to be the case that given a counterexample, you can prove that it is so (for Goldbach this is easy : if you have a counterexample, a listing of all smaller prime numbers and proof that two of them don't sum to the counterexample amounts to a proof that it's a counterexample). It's not so clear that the Collatz conjecture has this property. Statements for which this easily applies are called $\Sigma_1$ (in Peano arithmetic) $\endgroup$ – Max Aug 27 at 19:40

But, here I am stuck. Because, the claim "No one can never find a counter-example for the Collatz Conjecture" implies that : the counterexample does not exist.
Because otherwise, if there is a counter-example, it is mathematically possible to establish the existence of that sample.

Well, it may be, you find some number which looks like a counterexample (and even might be), - but you cannot prove that it is one: because there is no mathematical tool (known yet) to state this analytically (or by mathematical induction). Thus to prove it you are (currently) left with running the iteration "to infinity" - but which would not come to an end ever. (Just take one number in the $5x+1$ iteration which does not fall down to one of the known cycles in, say, 1000 iterations: as long as we have no formula we cannot say whether its orbit goes to infinity or not)

The conclusion in your first sentence is not convincing; the conclusion "does not exist" does not follow based on current state of math.

You might be interested in this handling of the question in mathoverflow (2018)

  • $\begingroup$ Not sure why this got downvoted, it seems correct. $\endgroup$ – Noah Schweber Sep 7 at 21:15

This post essentially appears to be concerned with the relationship between the statements:-

(1) The Collatz Conjecture is undecidable

(2) No counterexample can ever be found

(3) There is no counterexample

(4) The Collatz Conjecture is true

Arguably the main difficulty in justifying the chain of reasoning from (1) to (4) is whether (3) would follow from (2) since an inability to find something (for whatever reason) does not prove that it does not exist.

This line of reasoning helps me to reconcile your A) and B). Does it help you?


One need to define a context to work in where is possible to establish what is a statement, a proposition, a theory, a formula ecc.. till the notion of undecidability. Once a language is fixed we can build syntactic formulas and we can give them some sense. In a theory T (poorly speaking a list of axioms) makes sense to speak about what is provable and what not and when we say that is impossible to prove A, and is impossible to prove notA this simply means that the list of axioms we are using are not sufficiently strong.

As Gödel’s theorems show, the PA theory is incomplete, that means is there a formula that is undecidable but it is true in a Model of PA( a world in which all axioms of PA are true). So it is possible that Collatz is true but undecidable.

Is very hard to explain this for me because I’m not English and I ‘m sorry if my explanation is not clean.


Not the answer you're looking for? Browse other questions tagged or ask your own question.