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...
Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?
22
$\begingroup$
logic
recreational-mathematics
computability
-
1The Collatz Conjecture can be written as a conjunction: (A) every Collatz sequence is bounded, and (B) the only Collatz orbit is $(1,4,2)$. Neither part is known to be true or false. But it seems like (B) is in $\Pi_1$, since it can be written as $\forall{n,k}.(C^{(k)}(n)=n)\rightarrow(n=1\vee n=2\vee n=4)$. – 2012-01-18
-
0@mjqxxxx: That looks right to me - (A) is definitely the tricky part, though, and it doesn't look to have an easy $\Pi_1$ formulation. I saw a slightly-sketchy looking paper on the web that seemed to say that questions about similar sequences were $\Pi^0_2$-complete and I seem to recall results along those lines about 'multi-Collatz' sequences with more than one iterable function (maybe from John Conway?), so I suspect there may not be any known answer for this. – 2012-01-18
-
2@mjqxxx: if we try to check (B) according to your last recipe, and if we are by accident on a divergent trajectory - isn't the result whether we are on an orbit or on a divergent trajectory not depending on the *answer* whether the current trajectory is in fact divergent? – 2012-01-18
-
0The usual statement is $\Pi_2$, but since the Collatz conjecture is a sentence it is equivalent to either $0=1$ or $0=0$... (Assuming we're working in the standard model. If you're asking whether the conjecture is provably equivalent to a $\Pi_1$ or $\Sigma_1$ sentence over PA or ZFC, that's a different matter.) – 2012-07-31
-
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