Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-17T17:20:35.561Z Has data issue: false hasContentIssue false
  • English
  • Français

EXPANSIONS OF THE ORDERED ADDITIVE GROUP OF REAL NUMBERS BY TWO DISCRETE SUBGROUPS

Published online by Cambridge University Press:  10 May 2016

PHILIPP HIERONYMI
PHILIPP HIERONYMI*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 1409 WEST GREEN STREET URBANA, IL 61801, USAE-mail: [email protected]: http://www.math.uiuc.edu/∼phierony
Get access Rights & Permissions [Opens in a new window]

Abstract

The theory of (ℝ, <, +, ℤ, ℤa) is decidable if a is quadratic. If a is the golden ratio, (ℝ, <, +, ℤ, ℤa) defines multiplication by a. The results are established by using the Ostrowski numeration system based on the continued fraction expansion of a to define the above structures in monadic second order logic of one successor. The converse that (ℝ, <, +, ℤ, ℤa) defines monadic second order logic of one successor, will also be established.

Keywords

ordered additive group of real numbersdecidabilityOstrowski numeration systemmonadic second order logic of one successor
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 3 , September 2016 , pp. 1007 - 1027
Copyright
Copyright © The Association for Symbolic Logic 2016 

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

REFERENCES

Ahlbach, C., Usatine, J., Frougny, C., and Pippenger, N., Efficient algorithms for Zeckendorf arithmetic . Fibonacci Quarterly, vol. 51 (2013), no. 3, pp. 249–255.Google Scholar
Boigelot, B., Brusten, J., and Bruyère, V., On the sets of real numbers recognized by finite automata in multiple bases . Logical Methods in Computer Science, vol. 6 (2010), no. 1, pp. 1–17.Google Scholar
Boigelot, B., Rassart, S., and Wolper, P., On the expressiveness of real and integer arithmetic automata (extended abstract) , Proceedings of the 25th International Colloquium on Automata, Languages and Programming (London, UK), ICALP ’98, Springer-Verlag, 1998, pp. 152–163.CrossRefGoogle Scholar
Büchi, J. R., On a decision method in restricted second order arithmetic , Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), Stanford University Press, Stanford, CA, 1962, pp. 1–11.Google Scholar
Frougny, C., Representations of numbers and finite automata . Mathematical Systems Theory, vol. 25 (1992), no. 1, pp. 37–60.Google Scholar
Hieronymi, P., Defining the set of integers in expansions of the real field by a closed discrete set . Proceedings of the American Mathematical Society, vol. 138 (2010), no. 6, pp. 2163–2168.Google Scholar
Hieronymi, P. and Terry, A. Jr., Ostrowski numeration systems, addition and finite automata, preprint, 2014.Google Scholar
Hieronymi, P. and Tychonievich, M., Interpreting the projective hierarchy in expansions of the real line . Proceedings of the American Mathematical Society, vol. 142 (2014), no. 9, pp. 3259–3267.Google Scholar
Khoussainov, B. and Nerode, A., Automata Theory and its Applications, Progress in Computer Science and Applied Logic, vol. 21, Birkhäuser Boston, Inc., Boston, MA, 2001.CrossRefGoogle 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
Ostrowski, A., Bemerkungen zur Theorie der Diophantischen Approximationen . Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 1 (1922), no. 1, pp. 77–98.CrossRefGoogle Scholar
Rockett, A. M. and Szüsz, P., Continued Fractions, World Scientific, River Edge, NJ, 1992.Google Scholar
Skolem, T., Über einige Satzfunktionen in der Arithmetik , Skrifter, Norske videnskaps-akademi i Oslo I–Mat.-naturv. klasse, vol. 7 (1931), pp. 1–28.Google Scholar
Smoryński, C., Logical Number Theory. I: An Introduction, Universitext, Springer-Verlag, Berlin, 1991.CrossRefGoogle Scholar
Villemaire, R., The theory of 〈N, +, V k , V l 〉 is undecidable . Theoretical Computer Science, vol. 106 (1992), no. 2, pp. 337–349.CrossRefGoogle Scholar
Weispfenning, V., Mixed real-integer linear quantifier elimination , Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), ACM, New York, 1999, pp. 129–136 (electronic).Google Scholar
Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas . Bulletin de la Société Royale des Sciences de Liège, vol. 41 (1972), pp. 179–182.Google Scholar