Definability and Regularity in Automatic Presentations of Subsystems of Arithmetic
Bakh Khoussainov, Sasha Rubin, F Stephan · ResearchSpace (University of Auckland) · 2003
This paper is devoted to the study of the relationship between regularity and definability of relations in structures presented by finite automata. An emphasis is given to relations in fragments of arithmetic, in particular in (ω,≤), (ω, S), (ω, +) and some of their variants. A relation in a structure is intrinsically regular if it is regular in every automatic presentation of the structure. All definable relations in the first order logic with finite number of parameters are intrinsically regular. We investigate questions related to whether or not intrinsically regular relations are definable. For example, on the one hand, we show that the set M2 of all even numbers in every automatic presentation of (ω,≤) is intrinsically regular (but not definable). On the other, we show that there exists an automatic presentation of (ω, S) in which the set M2 is not regular. In particular, we show that a unary relation in (ω, S) is intrinsically regular if and only if it is definable.