Definability hierarchies of generalized quantifiers
From MaRDI portal
The author develops a general framework for proving that a quantifier is not definable in terms of n-ary quantifiers. He shows in particular that many logics existing in the literature can express a hierarchy \(Q_ 1,Q_ 2,..\). of such irreducible quantifiers. Back-and-forth techniques are applied to study the interpolation problems of certain cardinality logics.
Recommendations
Cites work
- An Ehrenfeucht game for the multivariable quantifiers of Malitz and some applications
- Axioms for abstract model theory
- Compact extensions of L(Q) (part 1a)
- Finite partially-ordered quantification
- Generalized Ehrenfeucht games
- Henkin and function quantifiers
- scientific article; zbMATH DE number 6003856 (Why is no real title available?)
- scientific article; zbMATH DE number 3941493 (Why is no real title available?)
- scientific article; zbMATH DE number 3675868 (Why is no real title available?)
- scientific article; zbMATH DE number 3399227 (Why is no real title available?)
- scientific article; zbMATH DE number 3196255 (Why is no real title available?)
- Logic with the quantifier “there exist uncountably many”
- On Extensions of Elementary Logic
- On orderings of the family of all logics
- On the expressibility hierarchy of Magidor-Malitz quantifiers
- ON THE EXPRESSIVE POWER OF THE LOGICS L(Qαn1,…,nm)
- Relative strength of Malitz quantifiers
- Stationary logic
- Vector spaces and binary quantifiers
- δ-Logics and generalized quantifiers
Cited in
(41)- Henkin and function quantifiers
- An overview of fuzzy quantifiers. I. Interpretations
- On second-order generalized quantifiers and finite structures
- Counting modulo quantifiers on finite structures
- Directions in generalized quantifier theory
- A double arity hierarchy theorem for transitive closure logic
- Arity and alternation: a proper hierarchy in higher order logics
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Finite quantifier hierarchies in relational algebras
- Rank hierarchies for generalized quantifiers
- Finite Quantification in Hierarchic Theorem Proving
- On the expressibility hierarchy of Magidor-Malitz quantifiers
- Automata Presenting Structures: A Survey of the Finite String Case
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Fixed-Point Definability and Polynomial Time
- scientific article; zbMATH DE number 4039872 (Why is no real title available?)
- scientific article; zbMATH DE number 956483 (Why is no real title available?)
- The Härtig quantifier: a survey
- The Beth-closure of ℒ(Qα) is not finitely generated
- Generalized lower and upper approximations in quantales
- On vectorizations of unary generalized quantifiers
- Finite Variable Logics in Descriptive Complexity Theory
- Generic expansions of ω-categorical structures and semantics of generalized quantifiers
- Relativized logspace and generalized quantifiers over finite ordered structures
- Hierarchies of monadic generalized quantifiers
- Interpolation for a sequent calculus of generalized quantifiers
- Capturing complexity classes with Lindström quantifiers
- Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
- The hierarchy theorem for second order generalized quantifiers
- The hierarchy theorem for generalized quantifiers
- Good-for-Game QPTL: An Alternating Hodges Semantics
- Count-free Weisfeiler-Leman and group isomorphism
- Game comonads \& generalised quantifiers
- Game comonads \& generalised quantifiers
- On the descriptive complexity of groups without abelian normal subgroups
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
- On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
- Parallel complexity of identifying groups and quasigroups via decompositions
- Vector spaces and binary quantifiers
- Definability properties and the congruence closure
This page was built for publication: Definability hierarchies of generalized quantifiers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1824614)
