We cannot rule out that the Collatz-conjecture cannot be proven. But we also cannot rule out that it is false and we cannot prove this in the case the sequence diverges for some start-number.

Is there a provable semi-decidable statement equivalent to the Collatz-conjecture ?


There is at present no $\Sigma^0_1$ (= provably true if true) or $\Pi^0_1$ (= provably false if false) sentence which is known to be equivalent$^1$ to the Collatz conjecture.

Note that checking whether a sentence is $\Sigma^0_1$, or $\Pi^0_1$, is decidable: it's a purely syntactic property. The issue is the "equivalent" bit.

$^1$Equivalence of sentences isn't a meaningful notion without specifying a "base theory:" two sentences $p,q$ are equivalent over $T$ if $T$ proves $p\leftrightarrow q$. The naive "theory-free" definition of equivalence - "$p$ is equivalent to $q$ if $p\leftrightarrow q$ is true" - leads to all true statements being equivalent and all false statements being equivalent. When we replace "true" with "provable," we get something more interesting, but then we have to specify a theory: provable in what system?

I haven't specified a base theory above. However, there is no reasonable $T$ over which the Collatz conjecture is known to be equivalent to a $\Sigma^0_1$ or $\Pi^0_1$ sentence. If you like, take $T$ to be ZFC.


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.