I'm thinking of the Collatz Conjecture and I'm wondering if we will ever know if it's true. If it's true, is there necessarily a proof that can prove it's true? This is more of a general question too: If something is true, does there exist a logically valid proof to prove it's true?

Also, if this is true and there is necessarily a proof for every true conjecture, how can we prove that?

  • 1
    $\begingroup$ Without any restrictions, yes, there is always a proof. But proofs depend on what you assume to be true. So, if you restrict what you assume is true, then sometimes there is no proof. Sometimes there is proof both of the assertion and also of its negation. It can also happen that the length of the proof is significantly larger than the length of the assertion. $\endgroup$ – conditionalMethod Oct 23 '19 at 1:44
  • $\begingroup$ @conditionalMethod You should write an answer, instead of attempting to answer the question through a comment. $\endgroup$ – Morgan Rodgers Oct 23 '19 at 6:35

Gödel's incompleteness theorem shows that there exist true statements that cannot be proved.

But more specifically we can say that there are some true statements very similar to the Collatz Conjecture that cannot be proved.

Turing showed that that there are some computer programs that never halt, but for which it cannot be proved that they never halt. Conway showed that functions like Collatz's (in which one of a number of simple arithmetic functions is applied to a number depending on which numbers it divides by) can be used to simulate arbitrary computer programs. By combining these results we can show that there are some conjectures which are like the Collatz Conjecture, just involving different functions than $n\mapsto 3n+1$ and $n\mapsto n/2$, which are true but cannot be proved.

For all we know, the Collatz Conjecture itself could also be one of these undecidable statements.

  • $\begingroup$ If the collatz conjecture can't be proved, is it fair to say that there's no fundamental reason we couldn't find a counterexample, but essentially none of the infinitely many numbers that exist had the necessary properties? We just didn't get lucky with an infinite number of lottery tickets? If so that is very confusing to think about. $\endgroup$ – TigerGold Oct 24 '19 at 1:26
  • $\begingroup$ also, if you can show that any conjecture is undecidable or unproveable, doesn't that mean that it's true because if it wasn't you could find a counterexample? And doesn't this prove that it's true thus contradicting the fact that it can't be proven? Thus, isn't it contradictory to prove that a conjecture is undecidable? $\endgroup$ – TigerGold Oct 24 '19 at 1:42
  • $\begingroup$ @TigerGold You're right that if it's undecidable then it's true. This means that a proof of its undecidability would give a proof of its truth. But this doesn't mean that it can't be undecidable. What it means is that if it is undecidable then we will never be able to prove that it's undecidable. $\endgroup$ – Oscar Cunningham Oct 24 '19 at 6:31

By Godel's incompleteness theorem, if a formal axiomatic system capable of modeling arithmetic is consistent (i.e. free from contradictions), then there will exist statements that are true but whose truthfulness cannot be proven. Such statements are known as Godel statements.

So to answer your question... no, if a statement in mathematics is true, this does not necessarily mean there exists a proof to show it (of course, this assumes that mathematics is consistent, and that certainly appears to be the case). Hence, if the Collatz Conjecture was a Godel statement, then we would not be able to prove it - even if it was true.

Note that we could remedy this predicament by expanding the axioms of our system, but this would inevitably lead to another set of Godel statements that could not be proven.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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