Hostname: page-component-6bf8c574d5-mggfc Total loading time: 0 Render date: 2025-02-17T12:51:42.006Z Has data issue: false hasContentIssue false
  • English
  • Français

UNDEFINABILITY OF MULTIPLICATION IN PRESBURGER ARITHMETIC WITH SETS OF POWERS

Part of: Model theory

Published online by Cambridge University Press:  10 October 2023

CHRIS SCHULZ
CHRIS SCHULZ*
Affiliation:
DEPARTMENT OF PURE MATHEMATICS UNIVERSITY OF WATERLOO 200 UNIVERSITY AVENUE WEST WATERLOO, ON N2L 3G1, CANADA
*
E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We begin by proving that any Presburger-definable image of one or more sets of powers has zero natural density. Then, by adapting the proof of a dichotomy result on o-minimal structures by Friedman and Miller, we produce a similar dichotomy for expansions of Presburger arithmetic on the integers. Combining these two results, we obtain that the expansion of the ordered group of integers by any number of sets of powers does not define multiplication.

Keywords

definabilityPresburger arithmeticnumeration systemsmodel theoryk-automatic

MSC classification

Primary: 03C57: Effective and recursion-theoretic model theory
Secondary: 03C15: Denumerable structures
Type
Article
Information
The Journal of Symbolic Logic , First View , pp. 1 - 15
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bès, A., Undecidable extensions of Büchi arithmetic and Cobham-Semënov theorem, this Journal, vol. 62 (1997), no. 4, pp. 1280–1296.Google Scholar
Bruyère, V., Hansel, G., Michaux, C., and Villemaire, R., Logic and $p$ -recognizable sets of integers . Journées Montoises (Mons, 1992), vol. 1 (1994), pp. 191–238.Google Scholar
Cluckers, R., Presburger sets and p-minimal fields, this Journal, vol. 68 (2003), no. 1, pp. 153–162.Google Scholar
Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata . Mathematical Systems Theory, vol. 3 (1969), pp. 186–192.CrossRefGoogle Scholar
Conant, G., Multiplicative structure in stable expansions of the group of integers . Illinois Journal of Mathematics, vol. 62 (2018), nos. 1–4, pp. 341–364.CrossRefGoogle Scholar
Friedman, H. and Miller, C., Expansions of o-minimal structures by sparse sets . Fundamenta Mathematicae, vol. 167 (2001), pp. 55–64.CrossRefGoogle Scholar
Ginsburg, S. and Spanier, E. H., Semigroups, Presburger formulas, and languages . Pacific Journal of Mathematics, vol. 16 (1966), pp. 285–296.CrossRefGoogle Scholar
Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers, fifth ed., Oxford University Press, New York, 1979.Google Scholar
Hieronymi, P. and Schulz, C., A strong version of Cobham’s theorem , Stoc 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, New York, 2022, pp. 1172–1179.CrossRefGoogle Scholar
Michaux, C. and Villemaire, R., Open questions around Büchi and Presburger arithmetics , Logic: From Foundations to Applications (Staffordshire, 1993) (W. Hodges, M. Hyland, C. Steinhorn, and J. Truss, editors), Oxford University Press, New York, 1996, pp. 353–383.CrossRefGoogle Scholar
Schlickewei, H. P. and Schmidt, W. P., The number of solutions of polynomial-exponential equations . Compositio Mathematica, vol. 120 (2000), no. 2, pp. 193–225.CrossRefGoogle Scholar
Semënov, A. L., The Presburger nature of predicates that are regular in two number systems . Sibirskii Matematicheskii Zhurnal, vol. 18 (1977), no. 2, pp. 403–418.Google Scholar
Shelah, S., Classification Theory and the Number of Nonisomorphic Models, North-Holland, Amsterdam, 1978.Google Scholar
Villemaire, R., The theory of $\left\langle \boldsymbol{N},+,{V}_k,{V}_l\right\rangle$ is undecidable . Theoretical Computer Science, vol. 106 (1992), no. 2, pp. 337–349.CrossRefGoogle Scholar
Zapryagaev, A. and Pakhomov, F., Interpretations of Presburger arithmetic in itself , Logical Foundations of Computer Science (Artemov, S. and Nerode, A., editors), Springer, Cham, 2018, pp. 354–367.CrossRefGoogle Scholar