Linguists and philosophers of language have shown increasing interest in the expressions that refer to quantifiers: determiners like ‘every’ and ‘many’, in addition to determiner phrases like ‘some king’ and ‘no cat’. This thesis addresses several puzzles where the way we understand quantifier expressions depends on features that go beyond standard truth conditional semantic meaning. One puzzle concerns the fact that it is often natural to understand ‘Every king is in the yard’ as being true if all (...) of the kings at the party are in the yard, even though the standard truth conditions predict it to be true if and only if every king in the universe is in the yard. Another puzzle emerges from the observation that ‘Every American king is in the yard’ sounds odd relative to contexts where there are no American kings, even though the standard truth conditions predict it to be trivially true. These puzzles have been widely discussed within linguistics and philosophy of language, and have implications for topics as diverse as the distinction between semantics and pragmatics and the ontological commitments of ordinary individuals. Yet few attempts have been made to incorporate discussions from the linguistics literature into the philosophical literature. This thesis argues that attending to the linguistics literature helps to address these puzzles. In particular, my solutions to these puzzles rely on notions from work on information structure, an often overlooked area of linguistics. I will use these notions to develop a new theory of the pragmatics of ordinary discourse, in the process of resolving the puzzles. In the first two chapters, I provide accessible overviews of key notions from the literature on quantifier expressions and information structure. In the third chapter, I discuss the problem of contextual domain restriction. In the fourth chapter, I consider the problems posed by empty restrictors. In the final chapter, I tackle the issue of category mistakes. (shrink)

This paper offers a unified, quantificational treatment of incomplete descriptions like ‘the table’. An incomplete quantified expression like ‘every bottle’ (as in “Every bottle is empty”) can feature in true utterances despite the fact that the world contains nonempty bottles. Positing a contextual restriction on the bottles being talked about is a straightforward solution. It is argued that the same strategy can be extended to incomplete definite descriptions across the board. ncorporating the contextual restrictions into semantics involves meeting a complex (...) array of desiderata, yet the apparently simpler pragmatic alternative faces severe problems and is therefore a nonstarter. (shrink)

Truth-theoretic deflationism holds that truth is simple, and yet that it can fulfil many useful logico-linguistic roles. Deflationism focuses on axioms for truth: there is no reduction of the notion of truth to more fundamental ones such as sets or higher-order quantifiers. In this paper I argue that the fundamental properties of reasonable, primitive truth predicates are at odds with the core tenets of classical truth-theoretic deflationism that I call fix, express, and quantify. Truth may be regarded as a broadly (...) logical, sui generis notion. However, this has little to do with the original aims of the deflationary theory of truth. (shrink)

We investigate the extension of monadic second-order logic of order with cardinality quantifiers "there exists uncountably many sets such that... " and "there exists continuum many sets such that... ". We prove that over the class of countable linear orders the two quantifiers are equivalent and can be effectively and uniformly eliminated. Weaker or partial elimination results are obtained for certain wider classes of chains. In particular, we show that over the class of ordinals the uncountability quantifier can be (...) effectively and uniformly eliminated. Our argument makes use of Shelah's composition method and Ramsey-like theorem for dense linear orders. (shrink)

We study definability in terms of monotone generalized quantifiers satisfying Isomorphism Closure, Conservativity and Extension. Among the quantifiers with the latter three properties - here called CE quantifiers - one finds the interpretations of determiner phrases in natural languages. The property of monotonicity is also linguistically ubiquitous, though some determiners like an even number of are highly non-monotone. They are nevertheless definable in terms of monotone CE quantifiers: we give a necessary and sufficient condition for such definability. We further identify (...) a stronger form of monotonicity, called smoothness, which also has linguistic relevance, and we extend our considerations to smooth quantifiers. The results lead us to propose two tentative universals concerning monotonicity and natural language quantification. The notions involved as well as our proofs are presented using a graphical representation of quantifiers in the so-called number triangle. (shrink)

Quantified expressions in natural language generally are taken to act like quantifiers in logic, which either range over entities that need to satisfy or not satisfy the predicate in order for the sentence to be true or otherwise are substitutional quantifiers. I will argue that there is a philosophically rather important class of quantified expressions in English that act quite differently, a class that includes something, nothing, and several things. In addition to expressing quantification, such expressions act (...) like nominalizations, introducing a new domain of objects that would not have been present in the semantic structure of the sentence otherwise. The entities those expressions introduce are of just the same sort as those that certain ordinary nominalizations refer to (such as John's wisdom or John's belief that S), namely they are tropes or entities related to tropes. Analysing certain quantifiers as nominalizing quantifiers will shed a new light on philosophical issues such as the status of properties and the nature of propositional attitudes. (shrink)

We prove that the logics of Magidor-Malitz and their generalization by Rubin are distinct even for PC classes. Let $M \models Q^nx_1 \cdots x_n \varphi(x_1 \cdots x_n)$ mean that there is an uncountable subset A of |M| such that for every $a_1, \ldots, a_n \in A, M \models \varphi\lbrack a_1, \ldots, a_n\rbrack$ . Theorem 1.1 (Shelah) $(\diamond_{\aleph_1})$ . For every n ∈ ω the class $K_{n + 1} = \{\langle A, R\rangle \mid \langle A, R\rangle \models \neg Q^{n + 1} (...) x_1 \cdots x_{n + 1} R(x_1, \ldots, x_{n + 1})\}$ is not an ℵ 0 -PC-class in the logic L n , obtained by closing first order logic under Q 1 , ..., Q n . I.e. for no countable L n -theory T, is K n + 1 the class of reducts of the models of T. Theorem 1.2 (Rubin) $(\diamond_{\aleph_1}).^3$ . Let $M \models Q^E x y\varphi(x, y)$ mean that there is $A \subseteq |M|$ such that $E_{A, \varphi} = \{\langle a, b \rangle \mid a, b \in A$ and $M \models \varphi\lbrack a, b\rbrack\}$ is an equivalence relation on A with uncountably many equivalence classes, and such that each equivalence class is uncountable. Let $K^E = \{\langle A, R\rangle\mid \langle A, R\rangle\models \neg Q^Exy R(x, y)\}$ . Then K E is not an ℵ 0 -PC-class in the logic gotten by closing first order logic under the set of quantifiers {Q n ∣ n ∈ ω} which were defined in Theorem 1.1. (shrink)

This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential (...) power of quantifier expressions by logical means. The classic version was developed in the 1980s, at the interface of linguistics, mathematics and philosophy. Before this volume, advances in "classic" generalized quantifier theory mainly focused on logical questions and their applications to linguistics, this volume adds a computational component, the third pillar of language use and logical activity. This book is essential reading for researchers in linguistics, philosophy, cognitive science, logic, AI, and computer science. (shrink)

Attempting to deflate ontological debates, the proponent of Quantifier Variance (QV) claims that there are multiple quantifier meanings of equal metaphysical merit. According to Hirsch—the main proponent of QV—metaphysical merit should be understood intensionally: two languages have equal merit if they allow us to express the same possibilities. I examine the notion of metaphysical merit and its purported link to intensionality. That link, I argue, should not be supported by adopting an intensional theory of semantic content. Rather, I (...) give a general strategy for supporting claims about metaphysical merit and examine whether that strategy can be used to link merit and intensionality. Though I don’t deliver a definitive verdict, the discussion provides a clearer framework for articulating and evaluating claims about metaphysical merit. (shrink)

Timothy Williamson has argued that in the debate on modal ontology, the familiar distinction between actualism and possibilism should be replaced by a distinction between positions he calls contingentism and necessitism. He has also argued in favor of necessitism, using results on quantified modal logic with plurally interpreted second-order quantifiers showing that necessitists can draw distinctions contingentists cannot draw. Some of these results are similar to well-known results on the relative expressivity of quantified modal logics with so-called inner and outer (...) quantifiers. The present paper deals with these issues in the context of quantified modal logics with generalized quantifiers. Its main aim is to establish two results for such a logic: Firstly, contingentists can draw the distinctions necessitists can draw if and only if the logic with inner quantifiers is at least as expressive as the logic with outer quantifiers, and necessitists can draw the distinctions contingentists can draw if and only if the logic with outer quantifiers is at least as expressive as the logic with inner quantifiers. Secondly, the former two items are the case if and only if all of the generalized quantifiers are first-order definable, and the latter two items are the case if and only if first-order logic with these generalized quantifiers relativizes. (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.

We present a general approach to quantified modal logics that can simulate most other approaches. The language is based on operators indexed by terms which allow to express de re modalities and to control the interaction of modalities with the first-order machinery and with non-rigid designators. The semantics is based on a primitive counterpart relation holding between n-tuples of objects inhabiting possible worlds. This allows an object to be represented by one, many, or no object in an accessible world. Moreover (...) by taking as primitive a relation between n-tuples we avoid some shortcoming of standard individual counterparts. Finally, we use cut-free labelled sequent calculi to give a proof-theoretic characterisation of the quantified extensions of each first-order definable propositional modal logic. In this way we show how to complete many axiomatically incomplete quantified modal logics. (shrink)

Quantifier variance holds that different languages can have unrestricted quantifier expressions that differ in meaning, where an expression is a “quantifier” just in case it plays the right inferential role. Several critics argued that J.H. Harris’s “collapse” argument refutes variance by showing that identity of inferential role is incompatible with meaning variance. This standard, syntactic collapse argument has generated several responses. More recently, Cian Dorr proved semantic collapse theorems to generate a semantic collapse argument against variance. (...) The argument is significantly different from standard collapse, so it requires a new response. Here I clarify and analyze the semantic collapse argument, and explain how variantists can and should respond to it. The paper also includes an appendix showing the difficulties of positing identity variance without quantifier variance. The argument in the appendix has yet to appear in print, but is familiar to specialists. (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.

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

ABSTRACT There has been recent interest in the idea that, when metaphysicians disagree over the truth of (say) ‘There are numbers’ or ‘Chairs exist’, their dispute is merely verbal. This idea has been taken to motivate quantifier variance, the view that the meanings of quantifier expressions vary across different ontological languages, and that each of these meanings is of equal metaphysical merit. I argue that quantifier variance cannot be upheld in light of natural language theorists’ analyses (...) of quantifier expressions. The idea that metaphysicians are engaged in verbal disputes can be maintained only through alternative strategies that have nothing to do with quantifier expressions. (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.

In this paper I argue for a restriction on certain types of LF movement, which I call ‘wh-related LF movement’. Evidence comes from a number of wh-in-situ constructions in German, such as the scope-marking construction and multiple questions. For semantic reasons, the in situ element in those constructions has to move at LF to either a position reserved for wh-phrases, or even higher up in the structure. The restriction (the Minimal Quantified Structure Constraint, MQSC) is that an intervening quantified expression (...) blocks this movement. In the case of every, the MQSC leads to an unambiguously distributive interpretation of the question. In the case of all other intervening operators, including negation, it leads to ungrammaticality. (shrink)

The relationship between Lexical-Functional Grammar (LFG) functional structures (f-structures) for sentences and their semanticinterpretations can be formalized in linear logic in a way thatcorrectly explains the observed interactions between quantifier scopeambiguity, bound anaphora and intensionality.Our linear-logic formalization of the compositional properties ofquantifying expressions in natural language obviates the need forspecial mechanisms, such as Cooper storage, in representing thescoping possibilities of quantifying expressions. Instead, thesemantic contribution of a quantifier is recorded as a linear-logicformula whose use in a (...) proof will establish the scope of thequantifier. Different proofs can lead to different scopes. In eachcomplete proof, the properties of linear logic ensure thatquantifiers are properly scoped. (shrink)

The paper develops a set of quantified temporal alethic boulesic doxastic systems. Every system in this set consists of five parts: a ‘quantified’ part, a temporal part, a modal (alethic) part, a boulesic part and a doxastic part. There are no systems in the literature that combine all of these branches of logic. Hence, all systems in this paper are new. Every system is defined both semantically and proof-theoretically. The semantic apparatus consists of a kind of$$T \times W$$T×Wmodels, and the (...) proof-theoretical apparatus of semantic tableaux. The ‘quantified part’ of the systems includes relational predicates and the identity symbol. The quantifiers are, in effect, a kind of possibilist quantifiers that vary over every object in the domain. The tableaux rules are classical. The alethic part contains two types of modal operators for absolute and historical necessity and possibility. According to ‘boulesic logic’ (the logic of the will), ‘willing’ (‘consenting’, ‘rejecting’, ‘indifference’ and ‘non-indifference’) is a kind of modal operator. Doxastic logic is the logic of beliefs; it treats ‘believing’ (and ‘conceiving’) as a kind of modal operator. I will explore some possible relationships between these different parts, and investigate some principles that include more than one type of logical expression. I will show that every tableau system in the paper is sound and complete with respect to its semantics. Finally, I consider an example of a valid argument and an example of an invalid sentence. I show how one can use semantic tableaux to establish validity and invalidity and read off countermodels. These examples illustrate the philosophical usefulness of the systems that are introduced in this paper. (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)

Context is essential in virtually all human activities. Yet some logical notions seem to be context-free. For example, the nature of the universal quantifier, the very meaning of “all”, seems to be independent of the context. At the same time, there are many quantifier expressions, and some are context-independent, while others are not. Similarly, purely logical consequence seems to be context-independent. Yet often we encounter strong inferences, good enough for practical purposes, but not valid. The two types (...) of examples suggest a general problem: how to characterise the context-free logical concepts in their natural environment, that is, in the field of their context-dependent associates. A general Thesis on Quantifiers is formulated: among all quantifiers, the context-free ones are just those definable by the universal quantifier. The issue of inferences is treated following the approach introduced by Richard L. Epstein: valid ones are an extreme case, the result of the disappearance of context-dependence. This idea can be applied to an analysis of a form of abduction, called “reductive inference” in Polish literature on logic. A tentative Thesis on Inferences identifies the validity of a strong inference that is context-independent. (shrink)

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

Conditional sentences with quantifying expressions are systematically ambigous. In one reading, the if -clause restricts the domain of the overt quantifier; in the other, the if -clause restricts the domain of a covert quantifier, which defaults to epistemic necessity. Although the ambiguity follows directly from the Lewis- Kratzer line on if, it is not generally acknowledged, which has led to pseudoproblems and spurious arguments.

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

Hintikka’s semantic approach to meaning, a development of Wittgenstein’s view of meaning as use, is the general theme of this chapter. We will focus on the analysis of quantified sentences and on the scope of the principle of compositionality and compare Hintikka’s take on these issues with that of Frege. The aim of this paper is to show that Hintikka’s analysis of quantified expressions as choice functions, in spite of its obvious dissimilarities with respect to the higher-order approach, is (...) actually very close to the Fregean stance on compositionality and context dependence. In particular, we will defend that the Fregean approach to quantifiers is unavoidably linked to the idea that quantified expressions are context-dependent, and therefore should not be conceived under the traditional inside-out model for analysis. (shrink)

Could one give expression to a doctrine of essentialism without running afoul of semantical problems that are alleged to beggar systems of quantified modal logic? An affirmative answer is, I believe, called for at least in the case of individual essentialism. Individual essentialism is an ontological thesis concerning a kind of necessary connection between objects and their (essential) properties. It is not or anyhow not primarily a semantic thesis, a thesis about meanings, for example. And thus we are implicitly counselled (...) not to seek for the logical reconstruction of such necessities in theories in which necessity is a de ditto matter. A more natural-seeming target is an understanding of the structure of idioms of de re necessity. Of course, de re necessities may turn out to be special cases of necessities de ditto, with what consequences it is interesting to speculate upon, but it would be preferable if the theory of individual essences were to be prosecuted initially at least without prejudice to this other matter. A theory of individual essences therefore may find it a convenience to recognize a special category of open sentence by means of which to represent de re attributions of necessity. (shrink)

The superlative quantifiers, at least and at most, are commonly assumed to have the same truth-conditions as the comparative quantifiers more than and fewer than. However, as Geurts & Nouwen have demonstrated, this is wrong, and several theories have been proposed to account for them. In this paper we propose that superlative quantifiers are illocutionary operators; specifically, they modify meta-speech acts.Meta speech-acts are operators that do not express a speech act, but a willingness to make or refrain from making a (...) certain speech act. The classic example is speech act denegation, e.g. I don't promise to come, where the speaker is explicitly refraining from performing the speech act of promising What denegations do is to delimit the future development of conversation, that is, they delimit future admissible speech acts. Hence we call them meta-speech acts. They are not moves in a game, but rather commitments to behave in certain ways in the future. We formalize the notion of meta speech acts as commitment development spaces, which are rooted graphs: The root of the graph describes the commitment development up to the current point in conversation; the continuations from the root describe the admissible future directions.We define and formalize the meta-speech act GRANT, which indicates that the speaker, while not necessarily subscribing to a proposition, refrains from asserting its negation. We propose that superlative quantifiers are quantifiers over GRANTs. Thus, Mary petted at least three rabbits means that the minimal number n such that the speaker GRANTs that Mary petted n rabbits is n = 3. In other words, the speaker denies that Mary petted two, one, or no rabbits, but GRANTs that she petted more.We formalize this interpretation of superlative quantifiers in terms of commitment development spaces, and show how the truth conditions that are derived from it are partly entailed and partly conversationally implicated. We demonstrates how the theory accounts for a wide variety of phenomena regarding the interpretation of superlative quantifiers, their distribution, and the contexts in which they can be embedded. (shrink)

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)

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)

We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we show that (...) Ω quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma. (shrink)

This paper argues that English quantifier phrases of the form ‘every F’ admit of a literal referential interpretation, contrary to the standard semantic account of this expression, according to which it denotes a set and a second-order relation. Various arguments are offered in favor of the referential interpretation, and two likely objections to it are forestalled.

Quantifier expressions like “many” and “at least” are part of a rich repository of words in language representing magnitude information. The role of numerical processing in comprehending quantifiers was studied in a semantic truth value judgment task, asking adults to quickly verify sentences about visual displays using numerical or proportional quantifiers. The visual displays were composed of systematically varied proportions of yellow and blue circles. The results demonstrated that numerical estimation and numerical reference information are fundamental in encoding (...) the meaning of quantifiers in terms of response times and acceptability judgments. However, a difference emerges in the comparison strategies when a fixed external reference numerosity is used for numerical quantifiers, whereas an internal numerical criterion is invoked for proportional quantifiers. Moreover, for both quantifier types, quantifier semantics and its polarity biased the response direction. Overall, our results indicate that quantifier comprehension involves core numerical and lexical semantic properties, demonstrating integrated processing of language and numbers. (shrink)

One of the standard views on plural quantification is that its use commits one to the existence of abstract objects–sets. On this view claims like ‘some logicians admire only each other’ involve ineliminable quantification over subsets of a salient domain. The main motivation for this view is that plural quantification has to be given some sort of semantics, and among the two main candidates—substitutional and set-theoretic—only the latter can provide the language of plurals with the desired expressive power (given that (...) the nominalist seems committed to the assumption that there can be at most countably many names). To counter this approach I develop a modal-substitutional semantics of plural quantification (on which plural variables, roughly speaking, range over ways names could be) and argue for its nominalistic acceptability. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as "every coalition satisfying property P can achieve φ" and "there exists a coalition C satisfying property P such that C can achieve φ". We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quanti ers in terms of quanti er extensions of existential second-order logic.

Among the many possible approaches to dealing with logical omniscience, I consider here awareness and impossible worlds structures. The former approach, pioneered by Fagin and Halpern, distinguishes between implicit and explicit knowledge, and avoids logical omniscience with respect to explicit knowledge. The latter, developed by Rantala and by Hintikka, allows for the existence of logically impossible worlds to which the agents are taken to have access; since such worlds need not behave consistently, the agents’ knowledge is fallible relative to logical (...) omniscience. The two approaches are known to be equally expressive in propositional systems interpreted over Kripke semantics. In this paper I show that the two approaches are equally expressive in propositional systems interpreted over Montague-Scott (neighborhood) semantics. Furthermore, I provide predicate systems of both awareness and impossible worlds structures interpreted on neighborhood semantics and prove the two systems to be equally expressive. (shrink)

Burgess (1997), building on Quine (1953), convincingly argued that claims in quantified modal logic cannot be understood as synonymous with or logically equivalent to claims about the analyticity of certain sentences. According to modal normativism, metaphysically necessary claims instead express or convey our actual semantic rules. In this paper, I show how the normativist can use Sidelle’s (1992a, 1995) neglected work on rigidity to account for two important phenomena in quantified modal logic: the necessity of identity and the substitutivity of (...) identicals into modal contexts. (shrink)

One well known problem regarding quantifiers, in particular the 1storder quantifiers, is connected with their syntactic categories and denotations. The unsatisfactory efforts to establish the syntactic and ontological categories of quantifiers in formalized first-order languages can be solved by means of the so called principle of categorial compatibility formulated by Roman Suszko, referring to some innovative ideas of Gottlob Frege and visible in syntactic and semantic compatibility of language expressions. In the paper the principle is introduced for categorial languages (...) generated by the Ajdukiewicz’s classical categorial grammar. The 1st-order quantifiers are typically ambiguous. Every 1st-order quantifier of the type k > 0 is treated as a two-argument functorfunction defined on the variable standing at this quantifier and its scope (the sentential function with exactly k free variables, including the variable bound by this quantifier); a binary function defined on denotations of its two arguments is its denotation. Denotations of sentential functions, and hence also quantifiers, are defined separately in Fregean and in situational semantics. They belong to the ontological categories that correspond to the syntactic categories of these sentential functions and the considered quantifiers. The main result of the paper is a solution of the problem of categories of the 1st-order quantifiers based on the principle of categorial compatibility. (shrink)

One well known problem regarding quantifiers, in particular the 1st order quantifiers, is connected with their syntactic categories and denotations.The unsatisfactory efforts to establish the syntactic and ontological categories of quantifiers in formalized first-order languages can be solved by means of the so called principle of categorial compatibility formulated by Roman Suszko, referring to some innovative ideas of Gottlob Frege and visible in syntactic and semantic compatibility of language expressions. In the paper the principle is introduced for categorial languages (...) generated by the Ajdukiewicz’s classical categorial grammar. The 1st-order quantifiers are typically ambiguous. Every 1st-order quantifier of the type k > 0 is treated as a two-argument functor-function defined on the variable standing at this quantifier and its scope (the sentential function with exactly k free variables, including the variable bound by this quantifier); a binary function defined on denotations of its two arguments is its denotation. Denotations of sentential functions, and hence also quantifiers, are defined separately in Fregean and in situational semantics. They belong to the ontological categories that correspond to the syntactic categories of these sentential functions and the considered quantifiers. The main result of the paper is a solution of the problem of categories of the 1st-order quantifiers based on the principle of categorial compatibility. (shrink)

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.

This paper investigates the effects of (surface) DP-internal quantifying expressions on semantic interpretation. In particular, I investigate two syntactic constructions in which an adjective takes scope out of its embedding DP, thus raising an interesting question for strict compositionality. Regarding the first construction, I follow Larson (1999) and assume that the adjective incorporates into the determiner of its DP, forming a complex quantifier [D+A]. I present new evidence in favor of this analysis. Since Larson's semantic analysis of complex (...) quantifiers [D+A] makes a wrong prediction, I propose an alternative, empirically more adequate analysis that treats D+A compounds as pluractional quantifiers in the sense of Lasersohn (1995). Finally, I turn to the second construction, arguing that – despite superficial similarities to the first construction - it should not be analyzed in terms of complex quantifier formation, but in terms of LF-movement of the adjective to Spec,DP. The discussion suggests that there is more than one way for DP-internal modifiers to take DP-external scope in natural language. (shrink)

We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see [6]) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo [1]) to the framework of finite (...) structures, we define the concept of a meager quantifier. We show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence closed (Theorem 4.9). We prove the failure of the full congruence closure property for logics which extend first-order logic by means of meager quantifiers, arbitrary monadic quantifiers, and the Härtig quantifier (Theorem 6.1). (shrink)

On the Fregean view of NP's, quantified NP's are represented as operator-variable structures while proper names are constants appearing in argument position. The Generalized Quantifier approach characterizes quantified NP's and names as elements of a unified syntactic category and semantic type. According to the Logicality Thesis, the distinction between quantified NP's, which undergo an operation of quantifier raising to yield operator-variable structures at Logical Form and non-quantified NP's, which appear in situ at LF, corresponds to a difference in (...) logicality status. The former are logical expressions while the latter are not. Using van Benthem's [2, 3] criterion for logicality, I extend the concept of logicality to GQ's. I argue that NP's modified by exception phrases constitute a class of quantified NP's which are heterogeneous with respect to logicality. However, all exception phrase NP's exhibit the syntactic and semantic properties which motivate May to treat quantified NP's as operators at LF. I present a semantic analysis of exception phrases as modifiers of GQ's, and I indicate how this account captures the central semantic properties of exception phrase NP's. I explore the consequences of the logically heterogeneous character of exception phrase NP's for proof theoretic accounts of quantifiers in natural language. The proposed analysis of exception phrase NP's provides support for the GQ approach to the syntax and semantics of NP's. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as “every coalition satisfying property P can achieve φ” and “there exists a coalition C satisfying property P such that C can achieve φ”. We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results (...) to investigate semantic distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)