Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 2085

Preprint Number 2085

Previous Next Preprint server

2085. Philipp Hieronymi, Christian Schulz
A strong version of Cobham's theorem

Submission date: 22 October 2021


Let k, ℓ ≥ 2 be two multiplicatively independent integers. Cobham's famous theorem states that a set X ⊆ ℕ is both k-recognizable and ℓ-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let X ⊆ ℕ^m be k-recognizable, let Y ⊆ ℕ^m be ℓ-recognizable such that both X and Y are not definable in Presburger arithmetic. Then the first-order logical theory of (ℕ,+,X,Y) is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of (ℕ,+,X) is decidable.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2110.11858: pdf, ps.

Last updated: November 3 2021 21:52 Please send your corrections to: