On Skolem’s exponential functions below $2^{2^{X}}$
HTML articles powered by AMS MathViewer
- by Lou van den Dries and Hilbert Levitz PDF
- Trans. Amer. Math. Soc. 286 (1984), 339-349 Request permission
Abstract:
A result of Ehrenfeucht implies that the smallest class of number-theoretic functions $f:{\mathbf {N}} \to {\mathbf {N}}$ containing the constants $0,1,2, \ldots$, the identity function $X$, and closed under addition, multiplication and $f \to {f^X}$, is well-ordered by the relation of eventual dominance. We show that its order type is ${\omega ^{{\omega ^\omega }}}$, and that for any two nonzero functions $f,g$ in the class the quotient $f(n)/g(n)$ tends to a limit in ${E^ + } \cup \{ 0,\infty \}$ as $n \to \infty$, where ${E^ + }$ is the smallest set of positive real numbers containing $1$ and closed under addition, multiplication and under the operations $x \to {x^{ - 1}},x \to {e^x}$.References
- Heinz Bachmann, Transfinite Zahlen, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 1, Springer-Verlag, Berlin-New York, 1967 (German). Zweite, neubearbeitete Auflage. MR 0219424, DOI 10.1007/978-3-642-88514-3 N. G. de Bruijn, Asymptotic methods in analysis, North-Holland, Amsterdam, 1958.
- A. Ehrenfeucht, Polynomial functions with exponentiation are well ordered, Algebra Universalis 3 (1973), 261–262. MR 332582, DOI 10.1007/BF02945125 R. Gurevič, Transcendent numbers and eventual dominance of exponential functions, Abstracts Amer. Math. Soc. 4 (1983), 310. G. H. Hardy, Orders of infinity: The ’infinitärcalcül’ of Paul du Bois-Reymond, 2nd ed., Cambridge Univ. Press, Cambridge, 1924.
- Hilbert Levitz, An initial segment of the set of polynomial functions with exponentiation, Algebra Universalis 7 (1977), no. 1, 133–136. MR 498009, DOI 10.1007/BF02485422
- Hilbert Levitz, An ordinal bound for the set of polynomial functions with exponentiation, Algebra Universalis 8 (1978), no. 2, 233–243. MR 473913, DOI 10.1007/BF02485393
- Hilbert Levitz, The Cartesian product of sets and the Hessenberg natural product of ordinals, Czechoslovak Math. J. 29(104) (1979), no. 3, 353–358. MR 536062, DOI 10.21136/CMJ.1979.101618
- Hilbert Levitz, Calculation of an order type: an application of nonstandard methods, Z. Math. Logik Grundlagen Math. 28 (1982), no. 3, 219–228. MR 668008, DOI 10.1002/malq.19820281406
- D. Richardson, Solution of the identity problem for integral exponential functions, Z. Math. Logik Grundlagen Math. 15 (1969), 333–340. MR 262068, DOI 10.1002/malq.19690152003
- Th. Skolem, An ordered set of arithmetic functions representing the least $\epsilon$-number, Norske Vid. Selsk. Forh., Trondheim 29 (1956), 54–59 (1957). MR 0083957
Additional Information
- © Copyright 1984 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 286 (1984), 339-349
- MSC: Primary 03D20; Secondary 06F05, 26A12
- DOI: https://doi.org/10.1090/S0002-9947-1984-0756043-7
- MathSciNet review: 756043