Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Detecting algebraic (in)dependence of explicitly presented functions (some applications of Nevanlinna theory to mathematical logic)


Author: R. H. Gurevič
Journal: Trans. Amer. Math. Soc. 336 (1993), 1-67
MSC: Primary 03C62; Secondary 03B30, 30D35, 32A22
DOI: https://doi.org/10.1090/S0002-9947-1993-0991961-1
MathSciNet review: 991961
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider algebraic relations between explicitly presented analytic functions with particular emphasis on Tarski's high school algebra problem.

The part not related directly to Tarski's high school algebra problem. Let $ U$ be a connected complex-analytic manifold. Denote by $ \mathcal{F}(U)$ the minimal field containing all functions meromorphic on $ U$ and closed under exponentiation $ f \mapsto {e^f}$. Let $ {f_j} \in \mathcal{F}(U)$, $ {p_j} \in \mathcal{M}(U) - \{ 0\} $ for $ 1 \leq j \leq m$, and $ {g_k} \in \mathcal{F}(U)$, $ {q_k} \in \mathcal{M}(U) - \{ 0\} $ for $ 1 \leq k \leq n$ (where $ \mathcal{M}(U)$ is the field of functions meromorphic on $ U$). Let $ {f_i} - {f_j} \notin \mathcal{H}(U)$ for $ i \ne j$ and $ {g_k} - {g_l} \notin \mathcal{H}(U)$ for $ k \ne 1$ (where $ \mathcal{H}(U)$ is the ring of functions holomorphic on $ U$). If all zeros and singularities of

$\displaystyle h = \frac{{\sum\nolimits_{j = 1}^m {{p_j}{e^{{f_j}}}} }} {{\sum\nolimits_{k = 1}^n {{q_k}{e^{{g_k}}}} }}$

are contained in an analytic subset of $ U$ then $ m = n$ and there exists a permutation $ \sigma $ of $ \{ 1, \ldots ,m\} $ such that $ h = ({p_j}/{q_{\sigma (j)}}) \cdot {e^{{f_j} - {g_{\sigma (j)}}}}$ for $ 1 \leq j \leq m$. When $ h \in \mathcal{M}(U)$, additionally $ {f_j} - {g_{\sigma (j)}} \in \mathcal{H}(U)$ for all $ j$ .

On Tarski's high school algebra problem. Consider $ L = \{ $-terms in variables and $ 1$, $ + $, $ \cdot $, $ \uparrow \} $ , where $ \uparrow :a$, $ b \mapsto {a^b}$ for positive $ a$, $ b$. Each term $ t \in L$ naturally determines a function $ \bar t$ : $ {({{\mathbf{R}}_ + })^n} \to {{\mathbf{R}}_ - }$ , where $ n$ is the number of variables involved. For $ S \subset L$ put $ \bar S = \{ \bar t\vert t \in S\} $ .

(i) We describe the algebraic structure of $ \bar \Lambda $ and $ \bar{\mathcal{L}}$ , where $ \Lambda = \{ t \in L\vert$ if $ u \uparrow v$ occurs as a subterm of $ t$ then either $ u$ is a variable or $ u$ contains no variables at all, and $ \mathcal{L} = \{ t \in L\vert$ if $ u \uparrow v$ occurs as a subterm of $ t$ then $ u \in \Lambda \} $. Of these, $ \bar \Lambda $ is a free semiring with respect to addition and multiplication but $ \bar{\mathcal{L}}$ is free only as a semigroup with respect to addition. A function $ \bar t \in \bar S$ is called $ + $-prime in $ \bar S$ if $ \bar t \ne \bar u + \bar v$ for all $ u$, $ v \in S$ and is called multiplicatively prime in $ \bar S$ if $ \bar t = \bar u \cdot \bar v \Rightarrow \bar u = 1$ or $ \bar v = 1$ for $ u$, $ v \in S$. A function is called $ ( + , \cdot )$-prime in $ \bar S$ if it is both $ + $-prime and multiplicatively prime in $ \bar S$. A function in $ \bar \Lambda $ is said to have content $ 1$ if it is not divisible by constants in $ {\mathbf{N}} - \{ 1\} $ or by $ \ne 1\ ( + , \cdot )$-primes of $ \bar \Lambda $ . The product of functions of content $ 1$ has content $ 1$ . Let $ P$ be the multiplicative subsemigroup of $ \bar \Lambda $ of functions of content $ 1$ . Then $ \bar{\mathcal{L}}$ as a semiring is isomorphic to the semigroup semiring $ \bar \Lambda ({ \oplus _f}{P_f})$, where each $ {P_f}$ is a copy of $ P$ and $ f$ ranges over the $ \ne 1\; + $-primes of $ \bar{\mathcal{L}}$.

(ii) We prove that if $ t$, $ u \in \mathcal{L}$ and $ {{\mathbf{R}}_ + } \vdash t = u$ (i.e., if $ \bar t = \bar u$) then Tarski's "high school algebra" identities $ \vdash t = u$. This result covers a conjecture of C. W. Henson and L. A. Rubel. (Note: this result does not generalize to arbitrary $ t$, $ u \in L$ . Moreover, the equational theory of $ ({{\mathbf{R}}_ + };\;1, + , \cdot , \uparrow )$ is not finitely axiomatizable.


References [Enhancements On Off] (What's this?)

  • [1] P. S. Aleksandrov, Introduction to homological dimension theory, Izdat. "Nauka", Moscow, 1975. (Russian) MR 58# 24234. MR 0515285 (58:24234a)
  • [2] P. S. Aleksandrov and B. A. Pasynkov, Introduction to dimension theory, Izdat. "Nauka", Moscow, 1973. (Russian) MR 51 #1776. MR 0365524 (51:1776)
  • [3] V. I. Arnold, Supplementary chapters of the theory of ordinary differential equations, Moscow, 1978. (Russian); English transl. in Geometrical methods in the theory of ordinary differential equations, Springer-Verlag, 1983. MR 526218 (80i:34001)
  • [4] G. Birkhoff, Lattice theory, 3rd ed., Amer. Math. Soc., Providence, R. I., 1967. MR 0227053 (37:2638)
  • [5] M. Boshernitzan, An extension of Hardy's class $ L$ of "orders of infinity", J. Analyse Math. 39 (1981), 235-255. MR 632463 (82m:26002)
  • [6] -, New "orders of infinity", J. Anal. Math. 41 (1982), 130-167. MR 687948 (85b:26002)
  • [7] B. I. Dahn, Fine structure of the integral exponential functions below $ {2^{{2^x}}}$ , Trans. Amer. Math. Soc. 297 (1986), 707-716. MR 854094 (87j:26005)
  • [8] L. van den Dries, Exponential rings, exponential polynomials and exponential functions, Pacific J. Math. 113 (1984), 51-66. MR 745594 (85j:13040)
  • [9] -, A generalization of Tarski-Seidenberg theorem, and some nondefinability results, Bull. Amer. Math. Soc. (N. S.) 15 (1986), 189-193. MR 854552 (88b:03048)
  • [10] -, Restricted theory of elementary functions, J. Symbolic Logic (to appear).
  • [11] L. van den Dries and H. Levitz, On Skolem's exponential functions below $ {2^{{2^x}}}$ , Trans. Amer. Math. Soc. 286 (1984), 339-349. MR 756043 (86g:03068)
  • [12] A. Ehrenfeucht, Polynomial functions with exponentiation are well ordered, Algebra Universalis 3 (1973), 261-349. MR 0332582 (48:10908)
  • [13] R. Godement, Topologie algébrique et théorie des faisceaux, Hermann, Paris, 1958. MR 0102797 (21:1583)
  • [14] R. C. Gunning and H. Rossi, Analytic functions of several complex variables, Prentice-Hall, Englewood Cliffs, N. J., 1965. MR 0180696 (31:4927)
  • [15] R. Gurevič, The equational theory of positive numbers with exponentiation is not finitely axiomatizable, Ann. Pure Appl. Logic (to appear). MR 1076248 (92h:03039)
  • [16] D. Handelman, Deciding eventual positivity of polynomials, Ergodic Theory Dynamical Systems 6 (1986), 57-79. MR 837976 (87m:26013)
  • [17] W. K. Hayman, Meromorphic functions, Clarendon Press, Oxford, 1964. MR 0164038 (29:1337)
  • [18] L. Henkin, The logic of equality, Amer. Math. Monthly 84 (1977), 597-612. MR 0472649 (57:12345)
  • [19] C. W. Henson and L. A. Rubel, Some applications of Nevanlinna theory to mathematical logic: identities of exponential functions, Trans. Amer. Math. Soc. 282 (1984), 1-32. MR 728700 (85h:03015)
  • [20] E. Hewitt and K. A. Ross, Abstract harmonic analysis, vols. 1, 2, Springer-Verlag, 1963, 1970. MR 0262773 (41:7378)
  • [21] G. Hiromi and M. Ozawa, On the existence of analytic mappings between two ultrahyperelliptic surfaces, Kōdai Math. Sem. Rep. 17 (1965), 281-306. MR 0188429 (32:5867)
  • [22] L. Hörmander, An introduction to complex analysis in several variables, Van Nostrand, Princeton, N.J., 1966. MR 0203075 (34:2933)
  • [23] W. Hurewicz and H. Wallman, Dimension theory, 2nd ed., Princeton Univ. Press, Princeton, N. J., 1948. MR 0006493 (3:312b)
  • [24] I. Kaplansky, An introduction to differential algebra, Hermann, Paris, 1957. MR 0093654 (20:177)
  • [25] K. Kuratowski and A. Mostowski, Set theory, North-Holland, Amsterdam, 1967. MR 0229526 (37:5100)
  • [26] S. Lang, Algebra, Addison-Wesley, 1965. MR 0197234 (33:5416)
  • [27] S. Lefschetz, On locally connected and related sets, Ann. of Math. (2) 35 (1934), 118-129. MR 1503148
  • [28] B. M. Levitan and V. V. Zhikov, Almost periodic functions and differential equations, Moscow University, 1978; English transl., Cambridge Univ. Press, 1982. MR 509035 (80d:42010)
  • [29] H. Levitz, An ordinal bound for the set of polynomial functions with exponentiation, Algebra Universalis 8 (1978), 223-243. MR 473913 (81f:04003)
  • [30] A. Macintyre, Notes on exponentiation, Lecture notes, University of Illinois at Urbana-Champaign (unpublished).
  • [31] C. B. Morrey, The analytic embedding of abstract real-analytic manifolds, Ann. of Math. (2) 68 (1958), 159-201. MR 0099060 (20:5504)
  • [32] J. T. Schwartz and M. Sharir, Motion planning and related geometric algorithms, Proc. Internat. Congr. Math. (Berkeley, 1986), pp. 1594-1611. MR 934358 (89h:68150)
  • [33] B. V. Shabat, Introduction to complex analysis. II, Moscow, 1985. (Russian) MR 831938 (88b:32001)
  • [34] P. H. Slessenger, Ph.D. Thesis, Leeds University, Leeds, 1984.
  • [35] E. Spanier, Algebraic topology, McGraw-Hill, New York, 1966. MR 0210112 (35:1007)
  • [36] A. J. Wilkie, On exponentiation--a solution to Tarski's high school algebra problem, Oxford, 1980 (manuscript).

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03C62, 03B30, 30D35, 32A22

Retrieve articles in all journals with MSC: 03C62, 03B30, 30D35, 32A22


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1993-0991961-1
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society