Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-22T21:29:57.504Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic probabilities of existential second-order Gödel sentences

Published online by Cambridge University Press:  12 March 2014

Leszek Pacholski  and
WiesŁaw Szwast
Leszek Pacholski
Affiliation:
Institute of Mathematics, Polish Academy of Science, Wrocław Branch, Wrocław, Poland
WiesŁaw Szwast
Affiliation:
Institute of Mathematics, Pedagogical University of Opole, Opole, Poland
Get access Rights & Permissions [Opens in a new window]

Extract

In [9] and [10] P. Kolaitis and M. Vardi proved that the 0-1 law holds for the second-order existential sentences whose first-order parts are formulas of Bernays-Schonfinkel or Ackermann prefix classes. They also provided several examples of second-order formulas for which the 0-1 law does not hold, and noticed that the classification of second-order sentences for which the 0-1 law holds resembles the classification of decidable cases of first-order prenex sentences. The only cases they have not settled are the cases of Gödel classes with and without equality.

In this paper we confirm the conjecture of Kolaitis and Vardi that the 0-1 law does not hold for the existential second-order sentences whose first-order part is in Gödel prenex form with equality. The proof we give is based on a modification of the example employed by W. Goldfarb [5] in his proof that, contrary to the Gödel claim [6], the class of Gödel prenex formulas with equality is undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 56 , Issue 2 , June 1991 , pp. 427 - 438
Copyright
Copyright © Association for Symbolic Logic 1991

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, A., Gurevich, Y., and Kozen, D., A zero-one law for logic with a fixed point operator, Information and Control, vol. 67 (1985), pp. 70–90.CrossRefGoogle Scholar
[2]Dreben, B. and Goldfarb, W. D., The decision problem: solvable classes of quantificational formulas, Addison-Wesley, Reading, Massachusetts, 1979.Google Scholar
[3]Fagin, R., Probabilities on finite models, this Journal, vol. 41 (1976), pp. 50–58.Google Scholar
[4]Glebskiĭ, Yu. V., Kogan, D. I., Liogon'kiĭ, M. I., and Talanov, V. A., Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics, vol. 5 (1969), pp. 142–154.CrossRefGoogle Scholar
[5]Goldfarb, W. D., The Gödel class with equality is unsolvable, Bulletin (New Series) of the American Mathematical Society, vol. 10 (1984), pp. 113–115.CrossRefGoogle Scholar
[6]Gödel, K., Ein Spezialfall des Entscheidungsproblems der theoretischien Logik, Ergebnisse eines Mathematischen Kolloquiums, vol. 2 (1932), pp. 27–28.Google Scholar
[7]Kaufmann, M., A counterexample to the 0-1 law for existential monadic second-order logic, CLI International Note 32, Computational Logic Inc., 12 1987.Google Scholar
[8]Kaufmann, M. and Shelah, S., On random models of finite power and monadic logic, Discrete Mathematics, vol. 54 (1985), pp. 285–293.CrossRefGoogle Scholar
[9]Kolaitis, P. G. and Vardi, M. Y., The decision problem for the probabilities of higher-order properties, Proceedings of the 19th ACM Symposium on Theory on Computing, ACM, New York, 1987, pp. 425–435.Google Scholar
[10]Kolaitis, P. G., 0-1 laws and decision problems for fragments of second-order logic, Proceedings of the 3rd Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, D. C., 1988, pp. 2–11.Google Scholar
[11]Kolaitis, P. G., 0-1 laws for infinitary logic, Proceedings of the 5th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, D. C., 1990, pp. 156–167.Google Scholar
[12]Lewis, H. R., Unsolvable classes of quantificational formulas, Addison-Wesley, Reading, Massachusetts, 1979.Google Scholar
[13]Matijasevič, Ju. V., Enumerable sets are Diophantine, Doklady Akademii Nauk SSSR, vol. 191 (1970), pp. 279–282 (Russian); English translation, Soviet Mathematics Doklady, vol. 11 (1970), pp. 554–557.Google Scholar