Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-23T05:28:16.226Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost everywhere elimination of probability quantifiers

Published online by Cambridge University Press:  12 March 2014

H. Jerome Keisler  and
Wafik Boulos Lotfallah
H. Jerome Keisler
Affiliation:
Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison Wi 53706, USA, E-mail: [email protected]
Wafik Boulos Lotfallah
Affiliation:
Department of Mathematics, The German University in Cairo, Egypt The Department of Engineering Mathematics, Faculty of Engineering, Cairo University, Egypt, E-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like ∃≥3/4y which says that “for at least 3/4 of all y”. These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are:

1. We deal with the quantifier ∃≥ry, where y is a tuple of variables.

2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope.

3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities PR for each predicate symbol R.

4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs).

5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers.

6. We allow each PR, as well as each r in the probability quantifier (∃≥ry), to depend on the size of the universe.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 4 , December 2009 , pp. 1121 - 1142
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Chang, C. C. and Keisler, H. J., Model theory, North Holland Elsevier, 1990.Google Scholar
[2]Dawar, A. and Grädel, E., Generalized quantifiers and 0–1 laws. Proceedings of the tenth annual IEEE symposium on Logic in Computer Science, 1995, pp. 54–64.CrossRefGoogle Scholar
[3]Ebbinghaus, H-D. and Flum, J., Finite model theory, second ed., Springer-Verlag, 1999.Google Scholar
[4]Fagin, R., Probabilities on finite models, this Journal, vol. 41 (1976), pp. 17–21.Google Scholar
[5]Fagin, R., Finite model theory—a personal perspective, Theoretical Computer Science, vol. 116 (1993), pp. 3–31.CrossRefGoogle Scholar
[6]Glebskii, Y. V., Kogan, D. I., Liogonki, M.I., and Talanov, V. A., Range and degree of readability of formulas in the restricted predicate calculus, Cybernetics, vol. 5 (1969), pp. 142–154.CrossRefGoogle Scholar
[7]Hella, L., Kolaitis, P. G., and Luosto, K., Almost everywhere equivalence of logics in finite model theory, The Bulletin of Symbolic Logic, vol. 2 (1996), no. 4, pp. 422–443.CrossRefGoogle Scholar
[8]Kaila, R., On probabilistic elimination of generalized quantifiers, Random Structures and Algorithms, vol. 19 (2001), no. 1, pp. 1–36.CrossRefGoogle Scholar
[9]Kaila, R., On almost sure elimination of numerical quantifiers, Journal of Logic and Computation, vol. 13 (2003), no. 2, pp. 273–285.CrossRefGoogle Scholar
[10]Keisler, H. J., Hyperfinite model theory, Logic colloquium '76 (Gandy, R. O. and Hyland, J. M. E., editors), North Holland, 1977.Google Scholar
[11]Knyazev, V. V., Zero-one law for an extension of first-order predicate language, Kibernetika, (1990), no. 2, pp. 110–113.Google Scholar
[12]Kolaitis, P. G. and Vardi, M. Y., Infinitary logics and 0–1 laws. Information and Computation, vol. 98 (1992), pp. 258–294, special issue: selections from the fifth annual IEEE symposium on Logic in Computer Science.CrossRefGoogle Scholar
[13]Luczak, T. and Spencer, J., When does the zero-one law hold?, Journal of the American Mathematical Society, vol. 4 (1991), no. 3, pp. 451–468.CrossRefGoogle Scholar
[14]Oberschelp, W., Asymptotic 0–1 laws in combinatorics, Combinatorial theory (Jungnickel, D., editor), Lecture Notes in Mathematics, no. 969, Springer, 1982, pp. 276–292.CrossRefGoogle Scholar
[15]Shelah, S. and Spencer, J., Zero-one laws for sparse random graphs. Journal of the American Mathematical Society, vol. 1 (1988), pp. 97–115.CrossRefGoogle Scholar