Graduate studies at Western
Studia Logica 62 (3):315-340 (1999)
|Abstract||We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see ) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo ) to the framework of finite structures, we define the concept of a meager quantifier. We show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence closed (Theorem 4.9). We prove the failure of the full congruence closure property for logics which extend first-order logic by means of meager quantifiers, arbitrary monadic quantifiers, and the Härtig quantifier (Theorem 6.1).|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Oleg Pikhurko & Oleg Verbitsky (2005). Descriptive Complexity of Finite Structures: Saving the Quantifier Rank. Journal of Symbolic Logic 70 (2):419-450.
H. Jerome Keisler & Wafik Boulos Lotfallah (2004). First Order Quantifiers in Monadic Second Order Logic. Journal of Symbolic Logic 69 (1):118-136.
Lauri Hella, Jouko Väänänen & Dag Westerståhl (1997). Definability of Polyadic Lifts of Generalized Quantifiers. Journal of Logic, Language and Information 6 (3):305-335.
Ross Willard (2000). A Finite Basis Theorem for Residually Finite, Congruence Meet-Semidistributive Varieties. Journal of Symbolic Logic 65 (1):187-200.
Kerkko Luosto (2000). Hierarchies of Monadic Generalized Quantifiers. Journal of Symbolic Logic 65 (3):1241-1263.
Jouko Väänänen (1997). Unary Quantifiers on Finite Models. Journal of Logic, Language and Information 6 (3):275-304.
Juha Kontinen (2006). The Hierarchy Theorem for Second Order Generalized Quantifiers. Journal of Symbolic Logic 71 (1):188 - 202.
Saharon Shelah & Mor Doron (2005). A Dichotomy in Classifying Quantifiers for Finite Models. Journal of Symbolic Logic 70 (4):1297 - 1324.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. 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.
Lauri Hella, Kerkko Luosto & Jouko Väänänen (1996). The Hierarchy Theorem for Generalized Quantifiers. Journal of Symbolic Logic 61 (3):802-817.
Added to index2009-01-28
Total downloads4 ( #189,291 of 739,404 )
Recent downloads (6 months)1 ( #61,680 of 739,404 )
How can I increase my downloads?