The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t. This was proved for unary similarity types by Per Lindström [17] with (...) a counting argument. We extend his method to arbitrary similarity types. (shrink)

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always (...) true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and (...) extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k−1)-ary fragment of partial fixed point logic by all (2k−1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, (...) we show that an extension is possible when we close this logic under congruence. (shrink)

We prove that if ℵα is uncountable and regular, then the Beth-closure of Lωω(Qα) is not a sublogic of L∞ω(Qn), where Qn is the class of all n-ary generalized quantifiers. In particular, B(Lωω(Qα)) is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set Q of Lindstrom quantifiers such that B(Lωω(Qα)) ≤ Lωω(Q).

A combinatorial criterium is given when a monadic quantifier is expressible by means of universe-independent monadic quantifiers of width n. It is proved that the corresponding hierarchy does not collapse. As an application, it is shown that the second resumption (or vectorization) of the Hartig quantifier is not definable by monadic quantifiers. The techniques rely on Ramsey theory.

Fix a cardinal κ. We can ask the question: what kind of a logic L is needed to characterize all models of cardinality κ up to isomorphism by their L-theories? In other words: for which logics L it is true that if any models A and B of cardinality κ satisfy the same L-theory then they are isomorphic?It is always possible to characterize models of cardinality κ by their Lκ+,κ+-theories, but we are interested in finding a “small” logic L, i.e., (...) the sentences of L are hereditarily of smaller cardinality than κ. For any cardinal κ it is independent of ZFC whether any such small definable logic L exists. If it exists it can be second order logic for κ=ω and fourth order logic or certain infinitary second order logic Lκ,ω source for uncountable κ. All models of cardinality κ can always be characterized by their theories in a small logic with generalized quantifiers, but the logic may be not definable in the language of set theory. Our work continues and extends the work of Ajtai [Miklos Ajtai, Isomorphism and higher order equivalence, Ann. Math. Logic 16 181–203]. (shrink)

This paper introduces a new Ehrenfeucht‐Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai‐Fagin game to the case when there are several alternating (coloring) moves played in different models. The game allows Duplicator to delay her choices of the models till (practically) the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in (...) Ehrenfeucht‐Fraïssé type games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game (in a sense) solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type .We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.

We introduce a natural class of quantifiersTh containing all monadic type quantifiers, all quantifiers for linear orders, quantifiers for isomorphism, Ramsey type quantifiers, and plenty more, showing that no sublogic ofL ωω (Th) or countably compact regular sublogic ofL ∞ω (Th), properly extendingL ωω , satisfies the uniform reduction property for quotients. As a consequence, none of these logics satisfies eitherΔ-interpolation or Beth's definability theorem when closed under relativizations. We also show the failure of both properties for any sublogic ofL (...) ∞ω (Th) in which Chang's quantifier or some cardinality quantifierQ α, with α≧1, is definable. (shrink)

Vectorization of a class of structures is a natural notion in finite model theory. Roughly speaking, vectorizations allow tuples to be treated similarly to elements of structures. The importance of vectorizations is highlighted by the fact that if the complexity class PTIME corresponds to a logic with reasonable syntax, then it corresponds to a logic generated via vectorizations by a single generalized quantifier (Dawar in J Log Comput 5(2):213–226, 1995). It is somewhat surprising, then, that there have been few systematic (...) studies of the expressive power of vectorizations of various quantifiers. In the present paper, we consider the simplest case: the cardinality quantifiers C S. We show that, in general, the expressive power of the vectorized quantifier logic $${{\rm FO}(\{{\mathsf C}_S^{(n)}\, | \, n \in \mathbb{Z}_+\})}$$ is much greater than the expressive power of the non-vectorized logic FO(C S ). (shrink)

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

We give a condensed survey of recent research on generalized quantifiers in logic, linguistics and computer science, under the following headings: Logical definability and expressive power, Polyadic quantifiers and linguistic definability, Weak semantics and axiomatizability, Computational semantics, Quantifiers in dynamic settings, Quantifiers and modal logic, Proof theory of generalized quantifiers.

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in Ehrenfeucht-Fraïssé type (...) games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (shrink)