First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

The study of quantification in natural language has made remarkable progress. Quantification in natural language has been investigated extensively by philosophers, logicians, and linguists. The result has been an elegant and far-reaching theory. This article presents a survey of some of the important components of this theory. The first section presents the core of the theory of generalized quantifiers. This theory explores the range of expressions of generality in natural language, and studies some of their logical properties. The second section (...) turns to issues of how quantifiers enter into scope relations. Here there is less unanimity than in the theory of generalized quantifiers. Two basic approaches, representative of the main theories in the literature, are sketched and compared. The final section turns briefly to the general question of what a quantifier is. (shrink)

Plural predication is a pervasive part of ordinary language. We can say that some people are fifty in number, are surrounding a building, come from many countries, and are classmates. These predicates can be true of some people without being true of any one of them; they are non-distributive predications. However, the apparatus of modern logic does not allow a place for them. Thomas McKay here explores the enrichment of logic with non-distributive plural predication and quantification. His book will be (...) of great interest to philosophers of language, linguists, metaphysicians, and logicians. (shrink)

There are two main routes to a concept of (generalized) quantifier. The first starts from first‐order logic, FO, and generalizes from the familiar ∀ and ∃ occurring there. The second route begins with real languages, and notes that many so‐called noun phrases, a kind of phrase which occurs abundantly in most languages, can be interpreted in a natural and uniform way using quantifiers.

Frege's invention of the predicate calculus has been the most influential event in the history of modern logic. The calculus’ place in logic is so central that many philosophers think, in fact, of it when they think of logic. This book challenges the position in contemporary logic and philosophy of language of the predicate calculus claiming that it is based on mistaken assumptions. Ben-Yami shows that the predicate calculus is different from natural language in its fundamental semantic charac.

This paper is part of a longer project on the semantics of depiction verbs and their associated relational nouns. Depiction verbs include verbs for physical acts, such as ‘draw’ (with relational noun ‘drawing’), ‘sketch’, ‘caricature’, ‘sculpt’, ‘write (about)’, and verbs for mental ones, such as ‘visualize’, ‘imagine’, and ‘fantasize’.