Probabilities of first-order sentences about unary functions
HTML articles powered by AMS MathViewer
- by James F. Lynch PDF
- Trans. Amer. Math. Soc. 287 (1985), 543-568 Request permission
Abstract:
Let $f$ be any fixed positive integer and $\sigma$ a sentence in the first-order predicate calculus of $f$ unary functions. For positive integers $n$, an $n$-structure is a model with universe $\{ 0,1, \ldots ,n - 1\}$ and $f$ unary functions, and $\mu (n,\sigma )$ is the ratio of the number of $n$-structures satisfying $\sigma$ to ${n^{nf}}$, the number of $n$-structures. We show that ${\lim _{n \to \infty }}\mu (n,\sigma )$ exists for all such $\sigma$, and its value is given by an expression consisting of integer constants and the operators $+ , - , \cdot ,/$, and ${e^x}$.References
- C. C. Chang and H. J. Keisler, Model theory, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0532927 K. J. Compton, A logical approach to asymptotic combinatorics, Adv. in Math. (submitted). —, An undecidable problem in finite combinatorics, J. Symbolic Logic (submitted).
- A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1960/61), 129–141. MR 126370, DOI 10.4064/fm-49-2-129-141
- Ronald Fagin, Monadic generalized spectra, Z. Math. Logik Grundlagen Math. 21 (1975), 89–96. MR 371623, DOI 10.1002/malq.19750210112
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945
- William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
- Haim Gaifman, Concerning measures in first order calculi, Israel J. Math. 2 (1964), 1–18. MR 175755, DOI 10.1007/BF02759729 —, On local and non-local properties (to appear). Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kii and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics 5 (1969), 142-154.
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- Bernard Harris, Probability distributions related to random mappings, Ann. Math. Statist. 31 (1960), 1045–1062. MR 119227, DOI 10.1214/aoms/1177705677
- Leo Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26 (1955), 512–517. MR 70869, DOI 10.1214/aoms/1177728496
- Martin D. Kruskal, The expected number of components under a random mapping function, Amer. Math. Monthly 61 (1954), 392–397. MR 62973, DOI 10.2307/2307900
- James F. Lynch, Almost sure theories, Ann. Math. Logic 18 (1980), no. 2, 91–135. MR 578540, DOI 10.1016/0003-4843(80)90014-5 —, A limit law for sentences about unary functions, Abstracts Amer. Math. Soc. 1 (1980), 494.
- James F. Lynch, On sets of relations definable by addition, J. Symbolic Logic 47 (1982), no. 3, 659–668. MR 666823, DOI 10.2307/2273595
- N. Metropolis and S. Ulam, A property of randomness of an arithmetical function, Amer. Math. Monthly 60 (1953), 252–253. MR 53416, DOI 10.2307/2307436
- J. Donald Monk, Mathematical logic, Graduate Texts in Mathematics, No. 37, Springer-Verlag, New York-Heidelberg, 1976. MR 0465767
- Gonzalo E. Reyes, Local definability theory, Ann. Math. Logic 1 (1970), 95–137. MR 274266, DOI 10.1016/S0003-4843(70)80006-7
- L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340–357. MR 195117, DOI 10.1090/S0002-9947-1966-0195117-8
- S. M. Ulam, On the notion of analogy and complexity in some constructive mathematical schemata, Probability, statistical mechanics, and number theory, Adv. Math. Suppl. Stud., vol. 9, Academic Press, Orlando, FL, 1986, pp. 35–45. MR 875444
Additional Information
- © Copyright 1985 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 287 (1985), 543-568
- MSC: Primary 03C13; Secondary 03B25, 03B48
- DOI: https://doi.org/10.1090/S0002-9947-1985-0768725-2
- MathSciNet review: 768725