TY - GEN
T1 - A strong version of Cobham's theorem
AU - Hieronymi, Philipp
AU - Schulz, Christian
N1 - Funding Information:
The authors were partially supported by NSF grant DMS-1654725. We thank Chris Miller, Jeffrey Shallit and Erik Walsberg for helpful conversations around the topic of this paper.
Publisher Copyright:
© 2022 ACM.
PY - 2022/9/6
Y1 - 2022/9/6
N2 - Let k,g.,"≥ 2 be two multiplicatively independent integers. Cobham's famous theorem states that a set X† g.,• is both k-recognizable and g.,"-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let X† g.,•m be k-recognizable, let Y† g.,•n be g.,"-recognizable such that both X and Y are not definable in Presburger arithmetic. Then the first-order logical theory of (g.,•,+,X,Y) is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of (g.,•,+,X) is decidable.
AB - Let k,g.,"≥ 2 be two multiplicatively independent integers. Cobham's famous theorem states that a set X† g.,• is both k-recognizable and g.,"-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let X† g.,•m be k-recognizable, let Y† g.,•n be g.,"-recognizable such that both X and Y are not definable in Presburger arithmetic. Then the first-order logical theory of (g.,•,+,X,Y) is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of (g.,•,+,X) is decidable.
KW - Cobham's theorem
KW - Presburger arithmetic
KW - logical theories
KW - undecidability
UR - http://www.scopus.com/inward/record.url?scp=85132740116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132740116&partnerID=8YFLogxK
U2 - 10.1145/3519935.3519958
DO - 10.1145/3519935.3519958
M3 - Conference contribution
AN - SCOPUS:85132740116
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1172
EP - 1179
BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Leonardi, Stefano
A2 - Gupta, Anupam
PB - Association for Computing Machinery
T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Y2 - 20 June 2022 through 24 June 2022
ER -