Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?

Solution 1:

As suggested in my comment above, I will interpret your question as asking whether the Collatz conjecture is provably equivalent to a $\Pi_1$ or $\Sigma_1$ sentence over some base theory $T$. There are a variety of issues at stake depending on the outcome of the conjecture (in the standard model).

Case 0: The Collatz conjecture is false because some Collatz sequence is periodic with a period other than $4,2,1$. In that case, the Collatz conjecture is provably equivalent to $0=1$ over any theory with enough power to encode and decode the witnessing sequence up to its first repetition (e.g. PA or I$\Sigma_1$).

Case 1: The Collatz conjecture is false because some Collatz sequence never repeats itself. In that case, the conjecture is perhaps equivalent to a $\Pi_1$ sentence. To say that the Collatz sequence starting with some standard number $n_0$ is never repeating is a $\Pi_1$ statement. In the strange scenario where the Collatz sequences that don't repeat are precisely the ones that go through $n_0$, then the Collatz conjecture is equivalent to that $\Pi_1$ statement. More generally, if there is a (standard) finite list $n_0,n_1,\dots,n_k$ such that the Collatz sequences that don't repeat are precisely those that go through one of these, then we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. Still more generally, if there is a computable sequence $n_0,n_1,\dots$ with that property, we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. However, if no such computable sequence exists then it is unlikely that we can do better than $\Sigma_2$ unless we use a non-axiomatizable base theory like the $\Pi_1$ theory of the standard model.

Case 2: The Collatz conjecture is true. In that case, the Collatz conjecture is equivalent to the statement that $g(n) = (\mu k)(C^k(n)=1)$ is a total computable function. We can then compare $g$ to various levels of the fast-growing hierarchy for a more precise analysis. For example, if $g(n)$ is bounded above by some $f_k$ where $k$ is finite, then $g$ is actually primitive recursive and the Collatz conjecture is provably true in I$\Sigma_1$ (same as PA except that induction is restricted to $\Sigma_1$ formulas). If $g(n)$ is abounded above by some $f_\alpha$ with $\alpha \lt \varepsilon_0$, then the Collatz conjecture is provably true in PA. If $g$ grows faster than that then a still stronger theory is required to prove the Collatz conjecture.