Department of

February 2019 March 2019 April 2019 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 1 2 1 2 3 4 5 6 3 4 5 6 7 8 9 3 4 5 6 7 8 9 7 8 9 10 11 12 13 10 11 12 13 14 15 16 10 11 12 13 14 15 16 14 15 16 17 18 19 20 17 18 19 20 21 22 23 17 18 19 20 21 22 23 21 22 23 24 25 26 27 24 25 26 27 28 24 25 26 27 28 29 30 28 29 30 31

Friday, March 15, 2019

**Abstract:** This talk concerns the intricate boundary between decidable and undecidable of expansions of Presburger artithmetic, i.e., the structure $(\mathbb{N}, +)$. For a natural number $p \ge 2$, let $p^{\mathbb{N}}$ denote the set of powers of $p$, and let $V_p$ be a predicate that allows us to access the full base-$p$ expansion of a natural number. It is known that the expansion $(\mathbb{N}, +, V_p)$ of Presburger arithmetic retains decidability, but $(\mathbb{N}, +, V_p, q^{\mathbb{N}})$, for $q$ multiplicatively independent from $p$, has an undecidable theory. In this talk, I present a proof that the reduct $(\mathbb{N}, +, p^{\mathbb{N}}, q^{\mathbb{N}})$ also has an undecidable theory, specifically in the case $p = 2$, $q = 3$. I conclude with a note on how the proof extends to other structures, as well as some discussion of directions for further research.