22
$\begingroup$

Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be equivalent to a $\Sigma_1$ or $\Pi_1$ statement? It's obvious that it can be expressed in the second level of the hierarchy, as $\forall n\exists k . C^{(k)}(n) = 1$ (and I believe functional composition is $\Delta_0$, so the fact that we're using a slightly extended language here should be moot; we can encode the computational path involved in computing $C^{(k)}(n)$ as a finite sequence of integers and thus as a single integer by appropriate coding), but there doesn't seem to be any obvious way of expressing it as a first-level statement...

  • 0
    @StevenStadnicki I don't know if this will help but I find this the simplest form of the conjecture to work with. You can write the conjecture $f(x)=3x+2^{v_2(x)}$ and the conjecture is \forall x\in\mathbb{N_{>0}}\exists n:f^n(x)\in\langle2\rangle where $\langle2\rangle=\{1,2,4,8,16,32,\ldots\}$2017-09-10

3 Answers 3

8

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.

  • 0
    Sorry... I misread your statement slightly and actually I need a better understanding of "computable sequence" to interpret your answer fully, but what I can tell you is that any set of numbers whose termination status is equivalent to $n_0$ but do not pass through $n_0$ is of comparable density in the integers to the set that do converge and the elements among that set are well-ordered by \omega^{<\omega} in the same way as the convergent numbers are.2018-08-30
0

I've never dealt much with the question of divergent trajectories (condition (A) in mjqxxx's comment), but the question of existence of orbits (condition (B)) can be translated into a question, whether finite sets $\small E_N $ of N integer parameters $\small \left $ where $\small A,B,\ldots,H>0 $ admit a rational solution of a related system of linear equations.
(Note: that parameters are used as exponents in the "Syracuse"-formulation of the Collatz-problem: $\small x_{k+1}=(3x_k +1)/2^A $ where $\small x_k $ is odd and A is such, that also $\small x_{k+1} $ is odd).

If we denote the number of the above parameters as N and their sum as S then N and S must be in a (not exact, but tight) relation, for instance $\small 1.5 N < S< 2N $ so the values of the parameters for any set $\small E_N $ are upper-bounded.

Moreover, the number of parameters, which equal 1 versus that which exceed 1 is related by the fact, that the 1 -parameters represent rising and >1-parameters represent falling steps in the "Syracuse"-notation

Then the question of the existence of nontrivial cycles of any specified length N can be solved by enumeration and the check of solutions: "has the solution integer value?" of the associated linear equation which has the form $\small x={Q(A,B,C,...,H) \over 2^S-3^N}$ where $\small Q(\ldots) $ is a linear composition of powers of 3 and 2 with exponents made from the parameters A,B,...,H. The amount of computation for each N is then limited by the number of combinatorical choices to satisfy the mentioned limitations for the set of N parameters . This is a kind of problem which can be solved by a supertask-machine because it is subfactorial for each N .

(I've done a related discussion about the existence of cycles in that "Syracuse"-view of the problem and the relation to the linear equation myself, but a more professional discussion of this point of view and the description of the equation (and for some specific types of cycles of a complete system of linear equations) is done for instance by John Simons 2007, one example online here or even better here in an updated joint article with Benne de Weger 2010, which I just found here)

-3

See http://matwbn.icm.edu.pl/ksiazki/aa/aa91/aa9146.pdf "A binomial representation of the 3x + 1 problem" by Maurice Margenstern and Yuri Matiyasevich.

  • 3
    Seconding what Carl said here, it looks like they have a different way of formulating the Collatz problem for any individual number $n$ as a $\Sigma_1$ statement, but the standard means for encoding the sequence of Collatz iterates already gave that; there's still the external universal quantifier of 'this holds true for all numbers' that their paper doesn't seem to do anything to change. (Unfortunately, the quantifier bounds in their statements that 'this is true if there exist numbers $w, t, \ldots$' go the wrong way)2012-04-20