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:
- Zoom link: https://us02web.zoom.us/j/82276870182?pwd=Y1IyYkV5a0ozZWRRQ2dDM0JUT2Q4dz09
- MC 5417