{"id":"arxiv/2605.28408","url":"https://arxiv.org/abs/2605.28408","tags":["math.LO"],"score":0,"title":"A natural axiomatization of Büchi Arithmetic","domain":"math.LO","source":"arxiv","authors":["Konstantin Kovalyov"],"reviews":0,"subject":"math.LO","summary":"We investigate Büchi Arithmetic $\\mathsf{BA}_k$ -- the elementary theory of the natural numbers equipped with addition and the function mapping a number $x$ to the greatest power of $k$ dividing $x$. $\\mathsf{BA}_k$ is known to be decidable and to enjoy a few important properties, in particular, a first-order structure is automatic iff it is interpretable in $\\mathsf{BA}_k$. We propose a natural axiomatization of this theory based on a comprehension schema restricted to bounded formulas, interpreting natural numbers as finite (multi)sets of powers of $k$ via their base-$k$ expansions. The…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-27","reactions":{}}