A natural axiomatization of Büchi Arithmetic
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.28408
curl -X POST /api/v1/records/arxiv/2605.28408/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.28408/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'