Logical Undefinability of the Generalized Collatz Transition Relation in Büchi Arithmetic
Let $q$ be an odd prime and let $d$ be an odd integer. We show that the arbitrary-step transition relation of the generalized Collatz map $T_{q,d}$ is not first-order definable in Base-2 Büchi Arithmetic ($BA_2$). We do this by demonstrating that if the transition relation were definable, the exponential set $P_q = \{q^y : y \in...