Logical Undefinability of the Generalized Collatz Transition Relation in Büchi Arithmetic

Madhav Dhiman, Rohan Pandey

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…