Friday, November 13, 20152:00 pmCUNY Logic WorkshopGC 6417

Diophantine approximation, scalar multiplication and decidability

Philipp Hieronymi

University of Illinois Urbana-Champaign

Philipp Hieronymi

It has long been known that the first order theory of the expansion (R,<,+,Z) of the ordered additive group of real numbers by just a predicate for the set of integers is decidable. Arguably due to Skolem, the result can be deduced easily from Buechi's theorem on the decidability of monadic second order theory of one successor, and was later rediscovered independently by Weispfenning and Miller. However, a consequence of Goedel's famous first incompleteness theorem states that when expanding this structure by a symbol for multiplication, the theory of the resulting structure (R,<,+,*,Z) becomes undecidable. This observation gives rise to the following natural and surprisingly still open question: How many traces of multiplication can be added to (R,<,+,Z) without making the first order theory undecidable? We will give a complete answer to this question when "traces of multiplication" is taken to mean scalar multiplication by certain irrational numbers. To make this statement precise: for b in R, let f_b: R -> R be the function that takes x to bx. I will show that the theory of (R,<,+,Z,f_b) is decidable if and only if b is quadratic. The proof rests on the observation that many of the Diophantine properties (in the sense of Diophantine approximation) of b can be coded in these structures.