uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Lindström quantifiers and higher-order notions on finite structures
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
1999 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The expressive power of first-order logic is very limited on finite structures. One important way to obtain stronger logics is to add Lindström quantifiers, and another is to add higher-order quantification. We investigate two different ways of combing the two approaches. We define second-order generalised quantifiers by adapting the definition of Lindström quantifiers to a second-order setting. We also introduce existential and universal higher-order quantification where the objects quantified over are Lindström quantifiers rather than relations or higher-order relations.

Second-order generalized quantifiers are generally very expressive, but they can be sensitive to the underlying logic. We construct quantifiers which do not increase the expressive power of fist-order logic, but which dramatically increase the power of some modest extensions of it. For some combinations of syntactic types and classes of finite structures, almost any countable logic is equivalent to a uniformly obtained sublogic of first-order logic with a quantifier of the given type. We show this for any type on the class of ordered structures, and for any non-monadic type on all structures. It alsoholds for monadic types with arity at most n on structures of arity, at most 2n-1. For all types it holds for structures with at most binary relations. The latter is shown by introducing a second-order bijective game, and proving that there is an effcient strategy for one of the players. The stategy is then used to define the desired quantifier.

First-order logic extended with quantification over Lindström quantifiers is decidable on finite structures, and contains an arity hierarchy. The existential fragment ΣQ1 includes inflationary fixed point logic extended with the ability to express that two defined structures are non-isomorphic, and is included in Σ11 with the same extension. We show that ΣQ1 is equivalent to the latter on rigid structures, and to the former on monadic structures, but neither equivalence holds in general. The fragment ΣQn+1, allowing n+1 alternating levels of quantifiers, is included in the n-th level of the exponential hierarchy, and is equivalent to it on rigid structures.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 1999. , 115 p.
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 15
Keyword [en]
Mathematics, Finite model theory, generalized quantifiers, higher-order quantifiers and operators, bijective Ehrenfeucht-Fraïssé games, quantifying over quantifiers, isomorphism quantifiers
Keyword [sv]
National Category
Research subject
Mathematical Logic
URN: urn:nbn:se:uu:diva-1218ISBN: 91-506-1389-8OAI: oai:DiVA.org:uu-1218DiVA: diva2:160775
Public defence
2000-01-14, Room 247, Building 2, Polacksbacken, Uppsala University, Uppsala, 13:15
Available from: 1999-12-24 Created: 1999-12-24Bibliographically approved

Open Access in DiVA

No full text

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 131 hits
ReferencesLink to record
Permanent link

Direct link