Logic Seminar
Christian Schulz
University of Illinois at Urbana Champagne
The theory of (N, +, k^N, l^N)
Abstract: Let k, l ≥ 2 be two multiplicatively independent integers. It is a well-known implication of Büchi that the expansion of (N, +) by any k-automatic relation has a decidable theory. But as shown by Bès in 1997, there exist k-automatic sets S_k such that for any l-automatic set S_l, the structure (N, +, S_k, S_l) defines multiplication. Here we show that this dichotomy does not extend to all expansions of (N, +) by k-automatic and l-automatic sets: the structure (N, +, k^N, l^N) does not have a decidable theory, nor does it define multiplication.
Tuesday February 14, 2023 at 4:00 PM in 636 SEO