Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-28T03:20:42.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Hierarchies of monadic generalized quantifiers

Published online by Cambridge University Press:  12 March 2014

Kerkko Luosto
Kerkko Luosto*
Affiliation:
Department of Mathematics, P.O. Box 4 (Yliopistonkatu 5), Fin-00014, University of Helsinki, Finland E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A combinatorial criterium is given when a monadic quantifier is expressible by means of universe-independent monadic quantifiers of width n. It is proved that the corresponding hierarchy does not collapse. As an application, it is shown that the second resumption (or vectorization) of the Härtig quantifier is not definable by monadic quantifiers. The techniques rely on Ramsey theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 3 , September 2000 , pp. 1241 - 1263
Copyright
Copyright © Association for Symbolic Logic 2000

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

[C]Corredor, Luis Jaime, El reticulo de las logicas de primer orden con cuantificadores cardinales, Revista Colombiana de Matemáticas, vol. XX (1986), pp. 1–26.Google Scholar
[D]Dawar, Anuj, Generalized quantifiers and logical reducibilities, Journal of Logic and Computation, vol. 5 (1995), pp. 213–226.CrossRefGoogle Scholar
[G]Graham, R. L., Recent developments in Ramsey theory, Proceedings of the international congress of mathematicians, 1983, pp. 1555–1567.Google Scholar
[GRS]Graham, R. L., Rothschild, B. L., and Spencer, J. H., Ramsey theory, Wiley, 1980.Google Scholar
[Ha]Härtig, Klaus, Über eine Quantifikator mit zwei Wirkungsbereiche, Colloquium on the foundations of mathematics, mathematical machines and their applications (Kalmár, L., editor), 1965, pp. 31–36.Google Scholar
[HL]Hella, L. and Luosto, K., Finite generation problem and n-ary quantifiers, Quantifiers: Logics, models and computation (Krynicki, M., Mostowski, M., and Szczerba, L. W., editors), Kluwer Academic Publishers, 1995, pp. 63–104.Google Scholar
[HLV]Hella, L., Luosto, K., and Väänänen, J., The hierarchy theorem for generalized quantifiers, this Journal, vol. 61 (1996), pp. 802–817.Google Scholar
[He1]Hella, Lauri, Definability hierarchies of generalized quantifiers, Annals of Pure and Applied Logic, vol. 43 (1989), pp. 235–271.CrossRefGoogle Scholar
[He2]Hella, Lauri, Logical hierarchies in PTIME, Proceedings of 7th IEEE symposium on logicin computer science, 1992, pp. 360–368.Google Scholar
[KV]Kolaitis, P. and Väänänen, J., Generalized quantifiers and pebble games on finite structures, Annals of Pure and Applied Logic, vol. 74 (1995), pp. 23–75.CrossRefGoogle Scholar
[L1]Lindström, Per, First order predicate logic with generalized quantifiers, Theoria, vol. 32 (1966), pp. 186–195.Google Scholar
[L2]Lindström, Per, Personal communication, Via Dag Westerståhl, 1993.Google Scholar
[M]Mostowski, Andrzej, On a generalization of quantifiers, Fundamenta Mathematicae, vol. 44 (1957), pp. 12–36.CrossRefGoogle Scholar
[NV]Nešetřxil, J. and Jouko Väänänen, , Combinatorics and quantifiers, Commentationes Mathematicae Universitatis Carolinae, vol. 37 (1996), pp. 433–443.Google Scholar
[O]Otto, Martin, Generalized quantifiers for simple properties, Proceedings of 9th IEEE symposium in logic in computer science, 1994, pp. 30–39.Google Scholar
[V]Väänänen, Jouko, A hierarchy theorem for Lindström quantifiers, Logic and abstraction (Furberg, M., Wetterstrom, T., and Åberg, C., editors), Acta Philosophica Gothoburgesia, no. 1, 1986, pp. 317–323.Google Scholar
[Wa]van der Waerden, B. L., Beweis einer Baudetschen Vermutung, Nieuw Archiefvoor Wiskunde, vol. 15 (1927), pp. 212–216.Google Scholar
[We]Westerståxhl, D., Quantifiers in natural language. A survey of some recent work, Quantifiers: Logics, models and computation (Krynicki, M., Mostowski, M., and Szczerba, L. W, editors), Kluwer Academic Publishers, 1995, pp. 359–408.Google Scholar
[Wi]Witt, E., Ein kombinatorisches Satz der Elementargeometrie, Mathematische Nachrichten, vol. 6 (1951), pp. 261–262.Google Scholar