Wednesday, April 6, 2022 — 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:

Event tags 

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
  1. 2022 (117)
    1. October (1)
    2. September (17)
    3. August (9)
    4. July (15)
    5. June (14)
    6. May (13)
    7. April (14)
    8. March (15)
    9. February (12)
    10. January (7)
  2. 2021 (135)
    1. December (11)
    2. November (22)
    3. October (15)
    4. September (5)
    5. August (15)
    6. July (17)
    7. June (15)
    8. May (1)
    9. April (4)
    10. March (11)
    11. February (9)
    12. January (10)
  3. 2020 (103)
  4. 2019 (199)
  5. 2018 (212)
  6. 2017 (281)
  7. 2016 (335)
  8. 2015 (211)
  9. 2014 (235)
  10. 2013 (251)
  11. 2012 (135)