Id: arxiv/2602.06066 Url: https://arxiv.org/abs/2602.06066 Tags: math.GM Score: 0 Title: Non-Definability of Reachability in Büchi Arithmetic for a Family of Generalized Collatz Maps Domain: math.GM Source: arxiv Authors: Madhav Dhiman, Rohan Pandey Reviews: 0 Subject: math.GM Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-01 Page: https://delphi.science/r/arxiv/2602.06066 Let $q \ge 3$ and $d \ge 1$ be odd integers with $q+d$ a power of $2$. We study the generalized Collatz map $T_{q,d}$, a one-dimensional piecewise-affine map on the positive integers, and its unparameterized reachability relation $R(x,z)$, which holds when $z$ is an iterate of $x$ under $T_{q,d}$. We prove that for every such pair $(q,d)$ the relation $R$ is not first-order definable in Büchi arithmetic $\langle \mathbb{N}, +, V_q \rangle$. Equivalently, no finite automaton recognizes the base-$q$ encoding of $R$. Assuming definability of $R$, we construct a first-order formula that defines…