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)

Following on Westerståhl’s argument that many is not Conservative [9], I propose an intensional account of Conservativity as well as intensional versions of EXT and Isomorphism closure. I show that an intensional reading of many can easily possess all three of these, and provide a formal statement and proof that they are indeed proper intensionalizations. It is then discussed to what extent these intensionalized properties apply to various existing readings of many.

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.

I show that the contemporary dominant analysis of natural language quantifiers that are one-place determiners by means of binary generalized quantifiers has failed to explain why they are, according to it, conservative. I then present an alternative, Geachean analysis, according to which common nouns in the grammatical subject position are plural logical subject-terms, and show how it does explain that fact and other features of natural language quantification.

The currently standard philosophical conception of existence makes a connection between three things: certain ways of talking about existence and being in natural language; certain natural language idioms of quantification; and the formal representation of these in logical languages. Thus a claim like ‘Prime numbers exist’ is treated as equivalent to ‘There is at least one prime number’ and this is in turn equivalent to ‘Some thing is a prime number’. The verb ‘exist’, the verb phrase ‘there is’ and the (...) quantifier ‘some’ are treated as all playing similar roles, and these roles are made explicit in the standard common formalization of all three sentences by a single formula of first-order logic: ‘(∃ x )[P( x ) & N( x )]’, where ‘P( x )’ abbreviates ‘ x is prime’ and ‘N( x )’ abbreviates ‘ x is a number’. The logical quantifier ‘∃’ accordingly symbolizes in context the role played by the English words ‘exists’, ‘some’ and ‘there is’. (shrink)

Ways of Scope Taking is concerned with syntactic, semantic and computational aspects of scope. Its starting point is the well-known but often neglected fact that different types of quantifiers interact differently with each other and other operators. The theoretical examination of significant bodies of data, both old and novel, leads to two central claims. (1) Scope is a by-product of a set of distinct Logical Form processes; each quantifier participates in those that suit its particular features. (2) Scope interaction is (...) further constrained by the semantics of the interacting operators. The arguments are developed using Minimalist syntax, Generalized Quantify theory, Discourse Representation Theory, and algebraic semantics. The contributors (Beghelli, Ben-Shalom, Doetjes, Farkas, Gutiérrez Rexach, Honcoop, Stabler, Stowell, Szabolcsi and Zwarts) make tightly related theoretical assumptions and focus on related empirical phenomena, which include the direct and inverse scope of quantifiers, distributivity, negation, modal and intensional contexts, weak islands, event-related readings, interrogatives, wh/quantifier interactions, and Hungarian syntax. An introduction to the formal semantics background is provided. Audience: Linguists, philosophers, computational and psycholinguists; advanced undergraduates, graduate students and researchers in these fields. (shrink)

Frege’s project has been characterized as an attempt to formulate a complete system of logic adequate to characterize mathematical theories such as arithmetic and set theory. As such, it was seen to fail by Gödel’s incompleteness theorem of 1931. It is argued, however, that this is to impose a later interpretation on the word ‘complete’ it is clear from Dedekind’s writings that at least as good as interpretation of completeness is categoricity. Whereas few interesting first-order mathematical theories are categorical or (...) complete, there are logical extensions of these theories into second-order and by the addition of generalized quantifiers which are categorical. Frege’s project really found success through Gödel’s completeness theorem of 1930 and the subsequent development of first- and higher-order model theory. (shrink)

In this paper, I have proposed a compositional semantic analysis of exception NPs from which three core properties of exception constructions could be derived. I have shown that this analysis overcomes various empirical and conceptual shortcomings of prior proposals of the semantics of exception sentences. The analysis was first formulated for simple exception NPs, where the EP-complement was considered a set-denoting term and the EP-associate was a monadic quantifier. It was then generalized in two steps: first, in order to account (...) for quantified EP-complements, and second, in order to account for polyadic quantifiers as the EP-associates. An additional assumption that was made in several places was that EPs may operate at the level of implications. The consequences of this assumption, though, still have to be investigated. (shrink)

This dissertation investigates the ways in which natural language restricts the domains of quantifiers. Adverbs of quantification are analyzed as quantifying over situations. The domain of quantifiers is pragmatically constrained: apparent processes of "semantic partition" are treated as pragmatic epiphenomena. The introductory Chapter 1 sketches some of the background of work on natural language quantification and begins the analysis of adverbial quantification over situations. Chapter 2 develops the central picture of "semantic partition" as a side-effect of pragmatic processes of anaphora (...) resolution. I argue that the apparent effects of topic/focus articulation and presuppositional information on the interpretation of quantifiers are not the result of a direct and local mechanism of sentence grammar. Instead, I develop an analysis where the link is established via the anaphoric dependence of quantifier domains on the discourse context. Chapter 3 discusses the analysis of conditional clauses as quantifier restrictors, concentrating on the question whether conditional clauses restrict quantifiers directly or indirectly. A treatment is explored which has if-clauses constrain the value of the hidden domain variable of the restricted quantifier. Chapter 4, on unless-clauses, and Chapter 5, on only if- and even if-clauses, present some issues in the compositional analysis of complex conditional clauses. These chapters significantly expand the data coverage of the theory of A-quantification. Building on previous work of mine on exceptives, I analyze unless-clauses as exceptive operators on A-quantifiers. The analysis of only if-clauses, treated as conditional clauses that combine if with the focus adverb only, unearthes some interesting new properties. Chapter 6, finally, examines the phenomenon of donkey-anaphora in the light of the results of the previous chapters. I show that a solution to the proportion problem may become possible once we combine the situation-semantic approach to adverbial quantification with the pragmatic theory developed in Chapter 2 and further elaborated in the analysis of donkey anaphora in complex conditionals. (shrink)

Recent work in natural language semantics leads to some new observations on generalized quantifiers. In § 1 we show that English quantifiers of type $ $ are booleanly generated by their generalized universal and generalized existential members. These two classes also constitute the sortally reducible members of this type. Section 2 presents our main result--the Generalized Prefix Theorem (GPT). This theorem characterizes the conditions under which formulas of the form Q1x 1⋯ Qnx nRx 1⋯ xn and q1x 1⋯ qnx nRx (...) 1⋯ xn are logically equivalent for arbitrary generalized quantifiers Qi, qi. GPT generalizes, perhaps in an unexpectedly strong form, the Linear Prefix Theorem (appropriately modified) of Keisler & Walkoe (1973). (shrink)

In this paper, I show that the availability of what some authors have called the weak reading and the strong reading of donkey sentences with relative clauses is systematically related to monotonicity properties of the determiner. The correlation is different from what has been observed in the literature in that it concerns not only right monotonicity, but also left monotonicity (persistence/antipersistence). I claim that the reading selected by a donkey sentence with a double monotone determiner is in fact the one (...) that validates inference based on the left monotonicity of the determiner. This accounts for the lack of strong reading in donkey sentences with MON determiners, which have been neglected in the literature. I consider the relevance of other natural forms of inference as well, but also suggest how monotonicity inference might play a central role in the actual process of interpretation. The formal theory is couched in dynamic predicate logic with generalized quantifiers. (shrink)

This paper addresses the two interpretations that a combination ofnegative indefinites can get in concord languages like French:a concord reading, which amounts to a single negation, and a doublenegation reading. We develop an analysis within a polyadic framework,where a sequence of negative indefinites can be interpreted as aniteration of quantifiers or via resumption. The first option leadsto a scopal relation, interpreted as double negation. The secondoption leads to the construction of a polyadic negative quantifiercorresponding to the concord reading. Given that (...) sentential negationparticipates in negative concord, we develop an extension of thepolyadic approach which can deal with non-variable binding operators,treating the contribution of negation in a concord context assemantically empty. Our semantic analysis, incorporated into agrammatical analysis formulated in HPSG, crucially relies on theassumption that quantifiers can be combined in more than one wayupon retrieval from the quantifier store. We also considercross-linguistic variation regarding the participation ofsentential negation in negative concord. (shrink)

Putting individual constants and quantifiers into the same syntactic category within first-order language promises to have far-reaching consequences: a syntax of this kind can reveal the potential of any such language, allowing us to realize that a vast class of noun phrases, including non-denoting terms, can be accommodated in the new syntax as expressions suited to being subjects of sentences. In the light of this, a formal system that is an extension of classical first-order logic is developed here, and is (...) equipped with an appropriate semantics. An ontological interpretation of the new logic is then also provided, with several categories of object and notions of existence being distinguished. Last but not least, a modal version of the logic, with some interesting formal features, is proposed. (shrink)

This essay offers a conception of logic by which logic may be considered to be exceptional among the sciences on the backdrop of a naturalistic outlook. The conception of logic focused on emphasises the traditional role of logic as a methodology for the sciences, which distinguishes it from other sciences that are not methodological. On the proposed conception, the methodological aims of logic drive its definitions and principles, rather than the description of scientific phenomena. The notion of a methodological discipline (...) is explained as a relation between disciplines or practices. Logic serves as a methodological discipline with respect to any theoretical practice, and this generality, as well as logic’s reflexive nature, distinguish it from other methodological disciplines. Finally, the evolution of model theory is taken as a case study, with a focus on its methodological role. Following recent work by John Baldwin and Juliette Kennedy, we look at model theory from its inception in the mid-twentieth century as a foundational endeavour until developments at the end of the century, where the classification of theories has taken centre-stage. (shrink)

Kripke [1975] gives a formal theory of truth based on Kleene's strong evaluation scheme. It is probably the most important and influential that has yet been given—at least since Tarski. However, it has been argued that this theory has a problem with generalized quantifiers such as All—that is, All ϕs are ψ—or Most. Specifically, it has been argued that such quantifiers preclude the existence of just the sort of language that Kripke aims to deliver—one that contains its own truth predicate. (...) In this paper I solve the problem by showing how Kleene's strong scheme, and Kripke's theory based on it, can in a natural way be extended to accommodate the full range of generalized quantifiers. (shrink)

In standard model-theoretic semantics, the meaning of logical terms is said to be fixed in the system while that of nonlogical terms remains variable. Much effort has been devoted to characterizing logical terms, those terms that should be fixed, but little has been said on their role in logical systems: on what fixing their meaning precisely amounts to. My proposal is that when a term is considered logical in model theory, what gets fixed is its intension rather than its extension. (...) I provide a rigorous way of spelling out this idea, and show that it leads to a graded account of logicality: the less structure a term requires in order for its intension to be fixed, the more logical it is. Finally, I focus on the class of terms that are invariant under isomorphisms, as they render themselves more easily to mathematical treatment. I propose a mathematical measure for the logicality of such terms based on their associated Löwenheim numbers. (shrink)

This paper explores the question of what makes diagrammatic representations effective for human logical reasoning, focusing on how Euler diagrams support syllogistic reasoning. It is widely held that diagrammatic representations aid intuitive understanding of logical reasoning. In the psychological literature, however, it is still controversial whether and how Euler diagrams can aid untrained people to successfully conduct logical reasoning such as set-theoretic and syllogistic reasoning. To challenge the negative view, we build on the findings of modern diagrammatic logic and introduce (...) an Euler-style diagrammatic representation system that is designed to avoid problems inherent to a traditional version of Euler diagrams. It is hypothesized that Euler diagrams are effective not only in interpreting sentential premises but also in reasoning about semantic structures implicit in given sentences. To test the hypothesis, we compared Euler diagrams with other types of diagrams having different syntactic or semantic properties. Experiment compared the difference in performance between syllogistic reasoning with Euler diagrams and Venn diagrams. Additional analysis examined the case of a linear variant of Euler diagrams, in which set-relationships are represented by one-dimensional lines. The experimental results provide evidence supporting our hypothesis. It is argued that the efficacy of diagrams in supporting syllogistic reasoning crucially depends on the way they represent the relational information contained in categorical sentences. (shrink)

Context Shifting Arguments (CSA) ask us to consider two utterances of an unambiguous, non-vague, non-elliptic sentence S. If the consensus intuition is that what’s said, or expressed or the truth-conditions, and so possibly the truthvalues, of these utterances differ, then CSA concludes S is context sensitive. Consider, for example, simultaneous utterances of ‘I am wearing a hat’, one by Stephen, one by Jason. Intuitively, these utterances can vary in truth-value contingent upon who is speaking the sentence, while holding hat-wearing constant, (...) and so they express distinct propositions and differ in their truth conditions. Since these differences are not the result of ambiguity (lexical or structural), vagueness, conversational implicature, or syntactic ellipsis, we have pretty strong evidence that ‘I am wearing a hat’ is context sensitive. (shrink)

Many philosophers, following David Lewis, believe that we should look to counterpart theory, not quantified modal logic, as a means of understanding modal discourse. We argue that this is a mistake. Significant parts of modal discourse involve either implicit or explicit reference to what is actually the case, raising the question of how talk about actuality is to be represented counterpart-theoretically. By considering possible modifications of Lewis's counterpart theory, including actual modifications due to Graeme Forbes and Murali Ramachandran, we argue (...) that no coherent version of counterpart theory can provide a plausible representation of talk about actuality, and so, we conclude, counterpart theory should be rejected. (shrink)

Within Linguistics the semantic analysis of natural languages (English, Swahili, for example) has drawn extensively on semantical concepts first formulated and studied within classical logic, principally first order logic. Nowhere has this contribution been more substantive than in the domain of quantification and variable binding. As studies of these notions in natural language have developed they have taken on a life of their own, resulting in refinements and generalizations of the classical quantifiers as well as the discovery of new types (...) of quantification which exceed the expressive capacity of the classical quantifiers. We refer the reader to Keenan and Westerståhl (1997) for an overview of results in this area. Here, we focus on one property of quantification in natural language—its inherently sortal nature—which distinguishes it from quantification in classical logic. (shrink)

The paper is about the interpretation of opaque verbs like “seek”, “owe”, and “resemble” which allow for unspecific readings of their (indefinite) objects. It is shown that the following two observations create a problem for semantic analysis: (a) The opaque position is upward monotone: “John seeks a unicorn” implies “John seeks an animal”, given that “unicorn” is more specific than “animal”. (b) Indefinite objects of opaque verbs allow for higher-order, or “underspecific”, readings: “Jones is looking for something Smith is looking (...) for” can express that there is something unspecific that both Jones and Smith are looking for. Given (a) and (b), it would seem that the following inference is hard to escape, if the premisses are construed unspecifically and the conclusion is taken on its under- specific reading: Jones is looking for a sweater. Smith is looking for a pen. Smith is looking for something Jones is looking for. (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)

In this paper I discuss Ernst Zermelo’s ideas concerning the possibility of developing a system of infinitary logic that, in his opinion, should be suitable for mathematical inferences. The presentation of Zermelo’s ideas is accompanied with some remarks concerning the development of infinitary logic. I also stress the fact that the second axiomatization of set theory provided by Zermelo in 1930 involved the use of extremal axioms of a very specific sort.1.

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which (...) follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since. (shrink)

The language of standard propositional modal logic has one operator (? or ?), that can be thought of as being determined by the quantifiers ? or ?, respectively: for example, a formula of the form ?F is true at a point s just in case all the immediate successors of s verify F.This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and generalized (...) quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of ? and ? (shrink)

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which (...) follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since. (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.

Gareth Evans'' proposal, as amended by Steven Neale –that a definite pronoun with a quantifiedantecedent that does not bind it has the sense ofa definite description – has been challenged inthe singular case by appeal to counter-examplesinvolving failure of the uniqueness condition forthe legitimacy of a singular description. Thischallenge is here extended to the plural.Counter-examples are provided by cases in which aplural description `the Fs'' does not denote,despite the propriety of the use of `they'' or`them'' it is to replace, because (...) of failure ofcumulativeness. A noncumulative predicate isnot distributive, and conditions for thelegitimacy of `the Fs'' designed to accommodatenondistributive `Fs'' are given in the context ofa two sorted theory with generalized quantifiers.Failure of cumulativeness is not to be confusedwith failure of maximality as Neale and othersdefine it. If not all Fs are Gs, `The Fs are Gs''is false; but it does not follow that `the Fs'' isillegitimate; and if `Fs'' is distributive. it isso only if there are no Fs. These differencesgranted, I give a partial defense of theEvans–Neale proposal from deficiencies in analternative based on the views of P. T.Geach. (shrink)

We axiomatize all quantifier properties which can be expressed by a universal condition on the class of algebras of sets.

This paper addresses the two interpretations that a combination ofnegative indefinites can get in concord languages like French:a concord reading, which amounts to a single negation, and a doublenegation reading. We develop an analysis within a polyadic framework,where a sequence of negative indefinites can be interpreted as aniteration of quantifiers or via resumption. The first option leadsto a scopal relation, interpreted as double negation. The secondoption leads to the construction of a polyadic negative quantifiercorresponding to the concord reading. Given that (...) sentential negationparticipates in negative concord, we develop an extension of thepolyadic approach which can deal with non-variable binding operators,treating the contribution of negation in a concord context assemantically empty. Our semantic analysis, incorporated into agrammatical analysis formulated in HPSG, crucially relies on theassumption that quantifiers can be combined in more than one wayupon retrieval from the quantifier store. We also considercross-linguistic variation regarding the participation ofsentential negation in negative concord. (shrink)

We consider some modal languages with a modal operator $D$ whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

Numerical probabilities are eliminated in favor of qualitative notions, with an eye to isolating what it is about probabilities that is essential to judgements of acceptability. A basic choice point is whether the conjunction of two propositions, each acceptable, must be deemed acceptable. Concepts of acceptability closed under conjunction are analyzed within Keisler's weak logic for generalized quantifiers — or more specifically, filter quantifiers. In a different direction, the notion of a filter is generalized so as to allow sets with (...) probability non-infinitesimally below 1 to be acceptable. (shrink)

In this paper I propose and defend a semantically based account of the distribution of DPs in existential there-sentences in English in opposition to the pragmatic account proposed in Zucchi (1995). The two analyses share many features, making it possible to study variation along the semantics/pragmatics dimension while holding the rest constant.

The semantics of noun phrases (NPs) is of crucial importance for both philosophy and linguistics. Throughout much of the history of the debate about the semantics of noun phrases there has been an implicit assumption about how they are to be understood. Basically, it is the assumption that NPs come only in two kinds. In this paper we would like to make that assumption explicit and discuss it and its status in the semantics of natural language. We will have a (...) look at how the assumption is to be understood more precisely, what its methodological status should be, whether it has been abandoned in recent work in semantics, and whether it should be abandoned in future work. To do all this, it’s best to start with some historical context. (shrink)