Probabilities on models of universal sentences

Author:
Douglas N. Hoover

Journal:
Proc. Amer. Math. Soc. **98** (1986), 294-297

MSC:
Primary 03C13; Secondary 68Q15

DOI:
https://doi.org/10.1090/S0002-9939-1986-0854036-X

MathSciNet review:
854036

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the asymptotics of conditional probabilities of first order universal sentences on finite models are the same as those of general first order sentences. This answers a question of R. Fagin.

**[1]**Ronald Fagin,*Generalized first-order spectra and polynomial-time recognizable sets*, Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973) Amer. Math. Soc., Providence, R.I., 1974, pp. 43–73. SIAM-AMS Proc., Vol. VII. MR**0371622****[2]**Ronald Fagin,*Probabilities on finite models*, J. Symbolic Logic**41**(1976), no. 1, 50–58. MR**0476480**, https://doi.org/10.2307/2272945**[3]**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*, Kybernetika (Prague)**5**(1969), 142-154.**[4]**N. D. Jones and A. L. Selman,*Turing machines and the spectra of first order formulas with equality*, Proc. 4th ACM Sympos. on Theory of Computing, 1972, pp. 157-167.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03C13,
68Q15

Retrieve articles in all journals with MSC: 03C13, 68Q15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1986-0854036-X

Keywords:
Probabilities on finite models,
conditional probabilities,
finite spectra

Article copyright:
© Copyright 1986
American Mathematical Society