RUS  ENG
Full version
SEMINARS

Seminars "Proof Theory" and "Logic Online Seminar"
May 23, 2022 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + online


Interpretations of Büchi arithmetics in themselves

A. A. Zapryagaev

National Research University "Higher School of Economics", Moscow



Abstract: Büchi arithmetic BA$_k,\ k \geq 2,$ is the elementary theory of the natural numbers with equality, addition and the function $V_k (x)$ which returns the largest power of 2 dividing $x$. These arithmetics represent finite automata in the following sense: sets of natural numbers definable in BA$_k$ are exactly those accepted by some finite automaton when expressed in $k$-ary digits. We study interpretations of Büchi arithmetics in themselves. For Presburger arithmetic (theory of natural numbers with addition), it was previously proven by the author and F. Pakhomov that every self-interpretation is definably isomorphic to the identical interpretation.


© Steklov Math. Inst. of RAS, 2024