𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On second-order generalized quantifiers and finite structures

✍ Scribed by Anders Andersson

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
255 KB
Volume
115
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the expressive power of second-order generalized quantiÿers on ÿnite structures, especially with respect to the types of the quantiÿers. We show that on ÿnite structures with at most binary relations, there are very powerful second-order generalized quantiÿers, even of the simplest possible type. More precisely, if a logic L is countable and satisÿes some weak closure conditions, then there is a generalized second-order quantiÿer Q which is monadic, unary and simple (i.e. of the same type as monadic second-order ∃), and a uniformly obtained sublogic of FO(Q) which is equivalent to L. We show some other results of the above kind, relating other classes of quantiÿers to other classes of structures. For example, if the quantiÿers are of the simplest non-monadic type, then the result extends to ÿnite structures of any arity. We further show that there are second-order generalized quantiÿers which do not increase expressive power of ÿrst-order logic but do increase the power signiÿcantly when added to stronger logics.

📜 SIMILAR VOLUMES

Characterizing Second Order Logic with F
Characterizing Second Order Logic with First Order Quantifiers
✍ David Harel 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB

CHARACTERIZING SECOND ORDER LOGIC WITH FIRST ORDER QU-4NTIFIERX by DAVID HAREL in Cambridge, Massachusets (U.S.A.) l) ') The author is indebted to W. J. WALKOE, A. R. MEYER, A. SHAMIR and a rcfeiee for comments on previous versions.

Convergence Laws for Very Sparse Random
Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers
✍ Risto Kaila 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB 👁 1 views

We prove convergence laws for logics of the form L ω ∞ω (Q), where Q is a properly chosen collection of generalized quantifiers, on very sparse finite random structures. We also study probabilistic collapsing of the logics L k ∞ω (Q), where Q is a collection of generalized quantifiers and k ∈ N+, un