Unary quantifiers on finite models


Authors
Jouko A Vaananen
University of Helsinki
Abstract
In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers.
Keywords definability   generalized   quantifiers
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1008209019899
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,669
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Game-Based Notions of Locality Over Finite Models.Marcelo Arenas, Pablo Barceló & Leonid Libkin - 2008 - Annals of Pure and Applied Logic 152 (1):3-30.

Add more citations

Similar books and articles

Beyond the Frege Boundary.Edward L. Keenan - 1992 - Linguistics and Philosophy 15 (2):199 - 221.
Scope Dominance with Monotone Quantifiers Over Finite Domains.Gilad Ben-Avi & Yoad Winter - 2004 - Journal of Logic, Language and Information 13 (4):385-402.
A Dichotomy in Classifying Quantifiers for Finite Models.Saharon Shelah & Mor Doron - 2005 - Journal of Symbolic Logic 70 (4):1297 - 1324.
Scope Dominance with Upward Monotone Quantifiers.Alon Altman, Ya'Acov Peterzil & Yoad Winter - 2005 - Journal of Logic, Language and Information 14 (4):445-455.
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.

Analytics

Added to PP index
2009-01-28

Total views
45 ( #165,521 of 2,327,693 )

Recent downloads (6 months)
2 ( #721,351 of 2,327,693 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature