The Hierarchy Theorem for Second Order Generalized Quantifiers

Journal of Symbolic Logic 71 (1):188 - 202 (2006)
  Copy   BIBTEX

Abstract

We study definability of second order generalized quantifiers on finite structures. Our main result says that for every second order type t there exists a second order generalized quantifier of type t which is not definable in the extension of second order logic by all second order generalized quantifiers of types lower than t

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1140641168

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
The hierarchy theorem for generalized quantifiers.Lauri Hella, Kerkko Luosto & Jouko Väänänen - 1996 - Journal of Symbolic Logic 61 (3):802-817.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Relativized logspace and generalized quantifiers over finite ordered structures.Georg Gottlob - 1997 - Journal of Symbolic Logic 62 (2):545-574.
Definability of polyadic lifts of generalized quantifiers.Lauri Hella, Jouko Väänänen & Dag Westerståhl - 1997 - Journal of Logic, Language and Information 6 (3):305-335.
Generalized quantifiers and modal logic.Wiebe Van Der Hoek & Maarten De Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
Definability of Second Order Generalized Quantifiers.Juha Kontinen - 2004 - Dissertation,
Natural language, sortal reducibility and generalized quantifiers.Edward L. Keenan - 1993 - Journal of Symbolic Logic 58 (1):314-325.
Modal Ontology and Generalized Quantifiers.Peter Fritz - 2013 - Journal of Philosophical Logic 42 (4):643-678.
First order predicate logic with generalized quantifiers.Per Lindström - 1966 - Theoria 32 (3):186--195.
Quantifiers Definable by Second Order Means.M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 181--214.
A representation theorem for languages with generalized quantifiers through back-and-forth methods.Renato H. L. Pedrosa & Antonio M. A. Sette - 1988 - Studia Logica 47 (4):401 - 411.
On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.

Analytics

Added to PP
2010-08-24

Downloads
26 (#595,031)

6 months
9 (#290,637)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Dependence Logic with a Majority Quantifier.Arnaud Durand, Johannes Ebbing, Juha Kontinen & Heribert Vollmer - 2015 - Journal of Logic, Language and Information 24 (3):289-305.

Add more citations

References found in this work

On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
Definability of second order generalized quantifiers.Juha Kontinen - 2010 - Archive for Mathematical Logic 49 (3):379-398.

Add more references