Logic Seminar
Friday, February 12, 2021 - 3:00pm
Zoom
Let $k,l>1$ be two multiplicatively independent integers. Cobham’s famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable. We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the theory of $(N, <,+, X, Y)$ is undecidable.
This is joint work with Christian Schulz.