Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T23:11:26.699Z Has data issue: false hasContentIssue false
  • English
  • Français

CONNECTEDNESS IN STRUCTURES ON THE REAL NUMBERS: O-MINIMALITY AND UNDECIDABILITY

Part of: Computability and recursion theory Model theory Fairly general properties

Published online by Cambridge University Press:  18 February 2022

ALFRED DOLICH ,
CHRIS MILLER ,
ALEX SAVATOVSKY  and
ATHIPAT THAMRONGTHANYALAK
ALFRED DOLICH
Affiliation:
DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE KINGSBOROUGH COMMUNITY COLLEGE 2001 ORIENTAL BOULEVARD BROOKLYN, NY11235, USA and DEPARTMENT OF MATHEMATICS THE GRADUATE CENTER 365 FIFTH AVENUE ROOM 4208 NEW YORK, NY10016, USAE-mail:[email protected]
CHRIS MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS OHIO STATE UNIVERSITY 231 WEST 18TH AVENUE COLUMBUS, OH43210, USAE-mail:[email protected]
ALEX SAVATOVSKY
Affiliation:
DEPARTMENT OF MATHEMATICS AND STATISTICS UNIVERSITY OF KONSTANZ78457KONSTANZ, GERMANYCurrent address: DEPARTMENT OF MATHEMATICS, FACULTY OF NATURAL SCIENCES UNIVERSITY OF HAIFA 199 ABBA KHOUSHY AVENUE MOUNT CARMEL, HAIFA, 3498838, ISRAELE-mail:[email protected]
ATHIPAT THAMRONGTHANYALAK
Affiliation:
DEPARTMENT OF MATHEMATICS OHIO STATE UNIVERSITY 231 WEST 18TH AVENUE COLUMBUS, OH43210, USACurrent address: DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE FACULTY OF SCIENCE CHULALONGKORN UNIVERSITYBANGKOK, 10330, THAILANDE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We initiate an investigation of structures on the set of real numbers having the property that path components of definable sets are definable. All o-minimal structures on $(\mathbb {R},<)$ have the property, as do all expansions of $(\mathbb {R},+,\cdot ,\mathbb {N})$ . Our main analytic-geometric result is that any such expansion of $(\mathbb {R},<,+)$ by Boolean combinations of open sets (of any arities) either is o-minimal or defines an isomorph of $(\mathbb N,+,\cdot )$ . We also show that any given expansion of $(\mathbb {R}, <, +,\mathbb {N})$ by subsets of $\mathbb {N}^n$ (n allowed to vary) has the property if and only if it defines all arithmetic sets. Variations arise by considering connected components or quasicomponents instead of path components.

Keywords

o-minimallocally o-minimalpath componentquasicomponentundecidable

MSC classification

Primary: 03C64: Model theory of ordered structures; o-minimality
Secondary: 03D35: Undecidability and degrees of sets of sentences 54D99: None of the above, but in this section
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 3 , September 2022 , pp. 1243 - 1259
Check for updates
Copyright
© The Author(s), 2022. 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

Aschenbrenner, M. and Thamrongthanyalak, A., Michael’s selection theorem in a semilinear context . Advances in Geometry, vol. 15 (2015), no. 3, pp. 293–313.CrossRefGoogle Scholar
Chang, C. C. and Keisler, H. J., Model Theory, third ed., Studies in Logic and the Foundations of Mathematics, 73, North-Holland Publishing Co., Amsterdam, 1990.Google Scholar
Dolich, A., Miller, C., and Steinhorn, C., Structures having o-minimal open core . Transactions of the American Mathematical Society, vol. 362 (2010), no. 3, pp. 1371–1411.CrossRefGoogle Scholar
Dougherty, R. and Miller, C., Definable Boolean combinations of open sets are Boolean combinations of open definable sets . Illinois Journal of Mathematics, vol. 45 (2001), no. 4, pp. 1347–1350.CrossRefGoogle Scholar
van den Dries, L., Tame Topology and O-Minimal Structures, London Mathematical Society Lecture Note Series, 248, Cambridge University Press, Cambridge, 1998.CrossRefGoogle Scholar
van den Dries, L. and Miller, C., Geometric categories and o-minimal structures . Duke Mathematical Journal, vol. 84 (1996), no. 2, pp. 497–540.CrossRefGoogle Scholar
Fornasiero, A., Definably connected nonconnected sets . Mathematical Logic Quarterly, vol. 58 (2012), no. 1–2, pp. 125–126.CrossRefGoogle Scholar
Friedman, H. and Miller, C., Expansions of o-minimal structures by sparse sets . Fundamenta Mathematicae, vol. 167 (2001), no. 1, pp. 55–64.CrossRefGoogle Scholar
Friedman, H. and Miller, C., Expansions of o-minimal structures by fast sequences , this Journal vol. 70 (2005), no. 2, pp. 410–418.Google Scholar
Kawakami, T., Takeuchi, K., Tanaka, H., and Tsuboi, A., Locally o-minimal structures . Journal of the Mathematical Society of Japan, vol. 64 (2012), no. 3, pp. 783–797.CrossRefGoogle Scholar
Lafferriere, G. and Miller, C., Uniform Reachability Algorithms, Proceedings of the Hybrid Systems: Computation and Control. 3rd International Workshop, HSCC2000, Pittsburgh, PA, USA, March 23–25, 2000, Springer, Berlin, 2000, pp. 215–228.Google Scholar
Miller, C., Expansions of dense linear orders with the intermediate value property , this Journal vol. 66 (2001), no. 4, pp. 1783–1790.Google Scholar
Miller, C., Tameness in expansions of the real field , Logic Colloquium ’01, Lecture Notes in Logic, vol. 20, Association for Symbolic Logic, Urbana, IL, 2005, pp. 281–316.CrossRefGoogle Scholar
Miller, C., Expansions of o-minimal structures on the real field by trajectories of linear vector fields . Proceedings of the American Mathematical Society, vol. 139 (2011), no. 1, pp. 319–330.CrossRefGoogle Scholar
Miller, C. and Thamrongthanyalak, A., Component-closed expansions of the real line (preliminary report) , Structures algébriques ordonnées, Équipe de Logique Mathématique, Université Paris Diderot, Paris, 2018.Google Scholar
Miller, C. and Thamrongthanyalak, A., D-minimal expansions of the real field have the zero set property . Proceedings of the American Mathematical Society, vol. 146 (2018), no. 12, pp. 5169–5179.CrossRefGoogle Scholar
Miller, C. and Tyne, J., Expansions of o-minimal structures by iteration sequences . Notre Dame Journal of Formal Logic, vol. 47 (2006), no. 1, pp. 93–99.CrossRefGoogle Scholar
Munkres, J. R., Topology: A First Course, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1975.Google Scholar
Pillay, A., First order topological structures and theories , this Journal vol. 52 (1987), no. 3, pp. 763–778.Google Scholar
Robinson, J., Definability and decision problems in arithmetic , this Journal vol. 14 (1949), pp. 98–114.Google Scholar
Savatovsky, A., Structure theorems for d-minimal expansions of the real additive ordered group and some consequences, Ph.D. thesis, University of Konstanz, 2020.Google Scholar
Sokantika, S. and Thamrongthanyalak, A., Definable continuous selections of set-valued maps in o-minimal expansions of the real field . Bulletin of the Polish Academy of Sciences Mathematics, vol. 65 (2017), no. 2, pp. 97–105.CrossRefGoogle Scholar
Thamrongthanyalak, A., Dimensional coincidence does not imply measure-theoretic tameness . Fundamenta Mathematicae, vol. 242 (2018), no. 1, pp. 103–107.CrossRefGoogle Scholar
Thamrongthanyalak, A., Michael’s selection theorem in d-minimal expansions of the real field . Proceedings of the American Mathematical Society, vol. 147 (2019), no. 3, pp. 1059–1071.CrossRefGoogle Scholar
Tychonievich, M. A., Tameness results for expansions of the real field by groups, Ph.D. thesis, The Ohio State University, 2013.Google Scholar