Christian Schulz : The theory of (N, +, k^N, l^N)

Posted by Tom Benhamou , part of the Logic Seminar.

At

Feb. 14, 2023, 4 p.m.

In

636 SEO

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.