Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T06:09:37.015Z Has data issue: false hasContentIssue false
  • English
  • Français

Zero-one law and definability of linear order

Published online by Cambridge University Press:  12 March 2014

Hannu Niemistö
Hannu Niemistö*
Affiliation:
Department of Mathematics and Statistics, University of Helsinki, Fi-00014 University of Helsinki, Finland, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§1. Introduction. A logic ℒ has a limit law, if the asymptotic probability of every query definable in ℒ converges. It has a 0–1-law if the probability converges to 0 or 1. The 0–1-law for first-order logic on relational vocabularies was independently found by Glebski et al. [6] and Fagin [5]. Later it has been shown for many other logics, for instance for fragments of second order logic [12], for finite variable logic [13] and for FO extended with the rigidity quantifier [3]. Lynch [14] has shown a limit law for first-order logic on vocabularies with unary functions.

We say that two formulas or two logics are almost everywhere equivalent, if they are equivalent on a class of structures whose asymptotic probability measure is one [7]. A 0–1-law is usually proved by showing that every quantifier of the logic has almost everywhere quantifier elimination, i.e., every formula with just one quantifier in front of it is almost everywhere equivalent to a quantifier-free formula. Besides proving 0–1-law, this implies that the logic is (weakly) almost everywhere equivalent to first-order logic.

The aim of this paper is to study, whether a logic with a 0–1-law can have greater expressive power than FO in the almost everywhere sense and to what extent. In particular, we are interested on the definability of linear order. Because a 0–1-law determines the almost everywhere expressive power of the sentences of the logic completely, but does not say anything about formulas explicitly, we have to assume some regularity on logics. We will therefore mostly consider extensions of first-order logic with generalized quantifiers.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 1 , March 2009 , pp. 105 - 123
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]Blass, Andreas and Gurevich, Yuri, Strong extension axioms and Shelah's zero-one law for choiceless polynomial time, this Journal, vol. 68 (2003), no. 1, pp. 65–131.Google Scholar
[2]Compton, Kevin J., Henson, C. Ward, and Shelah, Saharon, Nonconvergence, undecidability, and intractability in asymptotic problems, Annals of Pure and Applied Logic, vol. 36 (1987), no. 3, pp. 207–224.CrossRefGoogle Scholar
[3]Dawar, Anuj and Grädel, Erich, Generalized quantifiers and 0–1 laws, Logic in computer science, 1995, pp. 54–64.Google Scholar
[4]Ebbinghaus, Heinz-Dieter and Flum, Jörg, Finite model theory, second ed., Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.Google Scholar
[5]Fagin, Ronald, Probabilities on finite models, this Journal, vol. 41 (1976), no. 1, pp. 50–58.Google Scholar
[6]Glebskiĭ, Ju. V., Kogan, D. I., Liogon'kiĭ, M. I., and Talanov, V. A., Volume and fraction of satisfiability of formulas of the lower predicate calculus, Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskol SSR. Kibernetika, (1969), no. 2, pp. 17–27.Google Scholar
[7]Helia, Lauri, Kolaitis, Phokion G., and Luosto, Kerkko, Almost everywhere equivalence of logics infinite model theory, The Bulletin of Symbolic Logic, vol. 2 (1996), no. 4, pp. 422–443.CrossRefGoogle Scholar
[8]Helia, Lauri, How to define a linear order on finite models, Annals of Pure and Applied Logic, vol. 87 (1997), no. 3, pp. 241–267.CrossRefGoogle Scholar
[9]Hoeffding, Wassily, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, vol. 58 (1963), pp. 13–30.CrossRefGoogle Scholar
[10]Karp, Richard M., Probabilistic analysis of a canonical numbering algorithm for graphs, Relations between combinatorics and other parts of mathematics, Proceedings of Symposia in Pure Mathematics, XXXIV, Ohio State University, Columbus, Ohio, 1978, American Mathematical Society, Providence, R.I., 1979, pp. 365–378.Google Scholar
[11]Kaufmann, M., Counterexample to the 0–1 law for existential monadic second-order logic, 12 1987.Google Scholar
[12]Kolaitis, Phokion G. and Vardi, Moshe Y, 0-1 laws and decision problems for fragments of second-order logic, Information and Computation, vol. 87 (1990), no. 1–2, pp. 302–338.CrossRefGoogle Scholar
[13]Kolaitis, Phokion G. and Vardi, Moshe Y, Infinitary logics and 0-1 laws, Information and Computation, vol. 98 (1992), no. 2, pp. 258–294, Selections from the 1990 IEEE Symposium on Logic in Computer Science.CrossRefGoogle Scholar
[14]Lynch, James F., Probabilities of first-order sentences about unary functions, Transactions of the American Mathematical Society, vol. 287 (1985), no. 2, pp. 543–568.CrossRefGoogle Scholar