Probabilities of first-order sentences about unary functions

Author:
James F. Lynch

Journal:
Trans. Amer. Math. Soc. **287** (1985), 543-568

MSC:
Primary 03C13; Secondary 03B25, 03B48

MathSciNet review:
768725

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be any fixed positive integer and a sentence in the first-order predicate calculus of unary functions. For positive integers , an -structure is a model with universe and unary functions, and is the ratio of the number of -structures satisfying to , the number of -structures. We show that exists for all such , and its value is given by an expression consisting of integer constants and the operators , and .

**[1]**C. C. Chang and H. J. Keisler,*Model theory*, 2nd ed., North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Studies in Logic and the Foundations of Mathematics, 73. MR**0532927****[2]**K. J. Compton,*A logical approach to asymptotic combinatorics*, Adv. in Math. (submitted).**[3]**-,*An undecidable problem in finite combinatorics*, J. Symbolic Logic (submitted).**[4]**A. Ehrenfeucht,*An application of games to the completeness problem for formalized theories*, Fund. Math.**49**(1960/1961), 129–141. MR**0126370****[5]**Ronald Fagin,*Monadic generalized spectra*, Z. Math. Logik Grundlagen Math.**21**(1975), 89–96. MR**0371623****[6]**Ronald Fagin,*Probabilities on finite models*, J. Symbolic Logic**41**(1976), no. 1, 50–58. MR**0476480****[7]**William Feller,*An introduction to probability theory and its applications. Vol. I*, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0228020****[8]**Haim Gaifman,*Concerning measures in first order calculi*, Israel J. Math.**2**(1964), 1–18. MR**0175755****[9]**-,*On local and non-local properties*(to appear).**[10]**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.**[11]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[12]**Bernard Harris,*Probability distributions related to random mappings*, Ann. Math. Statist.**31**(1960), 1045–1062. MR**0119227****[13]**Leo Katz,*Probability of indecomposability of a random mapping function*, Ann. Math. Statist.**26**(1955), 512–517. MR**0070869****[14]**Martin D. Kruskal,*The expected number of components under a random mapping function*, Amer. Math. Monthly**61**(1954), 392–397. MR**0062973****[15]**James F. Lynch,*Almost sure theories*, Ann. Math. Logic**18**(1980), no. 2, 91–135. MR**578540**, 10.1016/0003-4843(80)90014-5**[16]**-,*A limit law for sentences about unary functions*, Abstracts Amer. Math. Soc.**1**(1980), 494.**[17]**James F. Lynch,*On sets of relations definable by addition*, J. Symbolic Logic**47**(1982), no. 3, 659–668. MR**666823**, 10.2307/2273595**[18]**N. Metropolis and S. Ulam,*A property of randomness of an arithmetical function*, Amer. Math. Monthly**60**(1953), 252–253. MR**0053416****[19]**J. Donald Monk,*Mathematical logic*, Springer-Verlag, New York-Heidelberg, 1976. Graduate Texts in Mathematics, No. 37. MR**0465767****[20]**Gonzalo E. Reyes,*Local definability theory*, Ann. Math. Logic**1**(1970), 95–137. MR**0274266****[21]**L. A. Shepp and S. P. Lloyd,*Ordered cycle lengths in a random permutation*, Trans. Amer. Math. Soc.**121**(1966), 340–357. MR**0195117**, 10.1090/S0002-9947-1966-0195117-8**[22]**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**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03C13,
03B25,
03B48

Retrieve articles in all journals with MSC: 03C13, 03B25, 03B48

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1985-0768725-2

Article copyright:
© Copyright 1985
American Mathematical Society