Logic Seminar

Philipp Hieronymi University of Illinois at Urbana--Champaign
A strong version of Cobham’s theorem

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.