Algebra Seminar

Wednesday, April 6, 2022 1:00 pm - 1:00 pm EDT

Christian Schulz, University of Illinois at Urbana-Champaign

"A strong version of Cobham’s theorem"

An equivalent statement of the Cobham-Semënov theorem is as follows: let k, l ≥ 2 be multiplicatively independent integers; let X ⊆ N^m be k-automatic, and let Y ⊆ N^n be l-automatic, such that X and Y are not definable in (N, +). Then the expansion of the structure (N, +, X) by the set Y is nontrivial, i.e. Y is not definable in (N, +, X). We show a strengthening of this: under the same assumptions, the structure (N, +, X, Y) has an undecidable theory. This also strengthens a 1997 result by Alexis Bès, who showed that (N, +, X, Y) has an undecidable theory under the additional assumption that (N, +, X) defines every k-automatic set.

This seminar will be held jointly online and in person: