What problems can one encode in Generalised Collatz Problem? The Generalised Collatz Problem asks if, given the modulus $m$ and rational coefficients $a_0,\dots,a_{m-1}$ and $b_0,\dots,b_{m-1}$ such that the transformation $T(n) := a_{n \bmod m} n + b_{n \bmod m}$ maps positive integers to positive integers, for any initial point $n_0$ there exist $i$ such that $T^i(n_0) = 1$. 
Apparently (see link), this problem is undecidable and moreover $\Pi_2^0$-complete. From the perspective of a working mathematician with a nodding acquaintance with logic, how big is $\Pi_2^0$ actually? In particualar, which recognisable conjectures/theorems fall into this class? Is Fermat's last theorem there? How about $abc$ conjecture? Do any statements from outside number theory/set theory/logic qualify?
 A: $\Pi^0_2$ is a designation in the arithmetical hierarchy. Roughly speaking, a sentence is $\Pi^0_2$ if it has the form $$\forall x_1,...,x_n\in X\exists y_1,...,y_k\in Y(P(x_1,...,x_n,y_1,...,y_k))$$ where $X$ and $Y$ are "nice" countable sets (e.g. $\mathbb{N}$ or $\mathbb{Q}$) and $P$ is a "computable" property. 


*

*Note that this is a property of the sentence as a syntactic object; while the usual statement of a conjecture may be at one complexity level, we may subsequently prove its equivalence with a principle at a lower complexity level. In particular, as soon as we prove a conjecture we lower its "essential complexity" substantially. :P


Many common sentences in number theory are $\Pi^0_2$ or simpler:


*

*Fermat's last theorem is $\Pi^0_1$: it says that for all $a,b,c,n\in\mathbb{N}$ we have $n>2\rightarrow a^n+b^n\not=c^n$, and that latter property is computable in the appropriate sense. Similarly, "ZFC is consistent" asserts the non-existence of a proof of a contradiction from ZFC, and hence is $\Pi^0_1$ (we can effectively check whether something is in fact a proof of a contradiction from ZFC). Perhaps surprisingly, the Riemann hypothesis is equivalent to a $\Pi^0_1$ sentence. 


*

*$\Pi^0_1$ principles have a special property: their undisprovability in a reasonably strong system implies their truth - or, perhaps less mysteriously, any reasonably strong system is $\Sigma^0_1$ complete since a true $\Sigma^0_1$ fact can be established by simply presenting and analyzing an example.


*Going up one level, we hit infinity principles. For example, the twin prime conjecture meanwhile is $\Pi^0_2$, since being a twin prime pair is computable and TPC says "for all $n$ there is a twin prime pair $>n$." Similarly, the infinitude of Sophie Germaine primes is $\Pi^0_2$. 

*But there are also natural statements beyond level $2$ - for example, the ABC conjecture. The first obvious issue is the apparent quantification over reals (the "$\epsilon$"), but that's ignorable: we can restrict attention to rational $\epsilon$s. Now the ABC conjecture has the form "For every rational $\epsilon$ there are only finitely many "bad triples,"" where being a bad triple is a computable property. "Only finitely many" has the form "$\exists \forall$," and so this formulation of the ABC conjecture is in fact $\Pi^0_3$ - a priori, too complicated! I do not know if the ABC conjecture has a known $\Pi^0_2$ reformulation.

What about really high-complexity principles?
Well, notice the superscript "$0$" which we haven't really touched so far. That refers to the type being quantified over (whereas the lower subscript refers to the number of "homogeneous blocks" of quantifiers, and the $\Pi$ vs. $\Sigma$ indicates whether the outermost quantifier is $\forall$ or $\exists$). Higher superscripts reflect quantification over higher types - e.g. the continuum hypothesis can be written as "There is a well-order of the reals with the countable predecessory property," which opens with an existential quantifier at "level $2$" (informally the levels go: $0$ = naturals, $1$ = reals, $2$ = sets of reals, ...) followed by what amount to quantifiers over lower types, which is to say that CH can be expressed in a $\Sigma^2_1$ way.
As we climb up these hierarchies one major question which emerges is when/how we can remove hypotheses from proofs: for example, could the axiom of choice be necessary to prove the Riemann hypothesis? Positive results along these lines are called absoluteness theorems, with one of the most important being Shoenfield's absoluteness theorem which implies that neither Choice nor CH (or their negations) can be essential to the proof of any $\Pi^1_2$ sentence (in particular, they're not going to be needed for the Riemann hypothesis).
