I argue that the conjunction of perdurantism (the view that objects are temporally extended) and universalism (the thesis that any old class of things has a mereological fusion) gives rise to undesired complications when combined with certain plausible assumptions concerning the semantics of tensed statements.

This chapter argues that special quantifiers such as 'something' when occurring in argument position are not ordinary or substitutional quantifiers; rather they have a reifying force introducing a domain of tropes or kinds of tropes to quantify over.

Convergent realists desire scientific methods that converge reliably to informative, true theories over a wide range of theoretical possibilities. Much attention has been paid to the problem of induction from quantifier-free data. In this paper, we employ the techniques of formal learning theory and model theory to explore the reliable inference of theories from data containing alternating quantifiers. We obtain a hierarchy of inductive problems depending on the quantifier prefix complexity of the formulas that constitute the data, and we (...) provide bounds relating the quantifier prefix complexity of the data to the quantifier prefix complexity of the theories that can be reliably inferred from such data without background knowledge. We also examine the question whether there are theories with mixed quantifiers that can be reliably inferred with closed, universal formulas in the data, but not without. (shrink)

We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.

In this paper I revisit the main arguments for a predicate analysis of descriptions in order to determine whether they do in fact undermine Russell's theory. I argue that while the arguments without doubt provide powerful evidence against Russell's original theory, it is far from clear that they tell against a quantificational account of descriptions.

The interpretation of if -clauses in the scope of ordinary quantifiers has provoked semanticists into extraordinary measures, such as abandoning compositionality or claiming that if has no meaning. We argue that if -clauses have a normal conditional meaning, even in the scope of ordinary quantifiers, and that the trick is to have the right semantics for conditionals.

Cirquent calculus is a novel proof theory permitting component-sharing between logical expressions. Using it, the predecessor article ‘Elementary-base cirquent calculus I: Parallel and choice connectives’ built the sound and complete axiomatization $\textbf{CL16}$ of a propositional fragment of computability logic. The atoms of the language of $\textbf{CL16}$ represent elementary, i.e. moveless, games and the logical vocabulary consists of negation, parallel connectives and choice connectives. The present paper constructs the first-order version $\textbf{CL17}$ of $\textbf{CL16}$, also enjoying soundness and completeness. The language of (...) $\textbf{CL17}$ augments that of $\textbf{CL16}$ by including choice quantifiers. Unlike classical predicate calculus, $\textbf{CL17}$ turns out to be decidable. (shrink)

§1. Introduction. After the pioneering work of Mostowski [29] and Lindström [23] it was Jon Barwise's papers [2] and [3] that brought abstract model theory and generalized quantifiers to the attention of logicians in the early seventies. These papers were greeted with enthusiasm at the prospect that model theory could be developed by introducing a multitude of extensions of first order logic, and by proving abstract results about relationships holding between properties of these logics. Examples of such properties areκ-compactness.Any (...) set of sentences of cardinality ≤ κ, every finite subset of which has a model, has itself a model.Löwenheim-Skolem Theorem down toκ.If a sentence of the logic has a model, it has a model of cardinality at most κ.Interpolation Property.If ϕ and ψ are sentences such that ⊨ ϕ → Ψ, then there is θ such that ⊨ ϕ → θ, ⊨ θ → Ψ and the vocabulary of θ is the intersection of the vocabularies of ϕ and Ψ.Lindstrom's famous theorem characterized first order logic as the maximal ℵ0-compact logic with Downward Löwenheim-Skolem Theorem down to ℵ0. With his new concept of absolute logics Barwise was able to get similar characterizations of infinitary languagesLκω. But hopes were quickly frustrated by difficulties arising left and right, and other areas of model theory came into focus, mainly stability theory. No new characterizations of logics comparable to the early characterization of first order logic given by Lindström and of infinitary logic by Barwise emerged. What was first called soft model theory turned out to be as hard as hard model theory. (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)

The Moral Law is fulfilled iff everything that ought to be the case is the case, and The Good is realised in a possible world w at a time t iff w is deontically accessible from w at t. In this paper, I will introduce a set of temporal modal deontic systems with propositional quantifiers that can be used to prove some interesting theorems about The Moral Law and The Good. First, I will describe a set of systems without (...) any propositional quantifiers. Then, I will show how these systems can be extended by a couple of propositional quantifiers. I will use a kind of TxW semantics to describe the systems semantically and semantic tableaux to describe them syntactically. Every system will include a constant · that stands for The Good. ‘·’ is read as ‘The Good is realised’. All systems that contain the propositional quantifiers will also include a constant '*' that stands for The Moral Law. '*' is read as ‘The Moral Law is fulfilled’. I will prove that all systems (without the propositional quantifiers) are sound and complete with respect to their semantics and that all systems (including the extended systems) are sound with respect to their semantics. It is left as an open question whether or not the extended systems are complete. (shrink)

Quantification over individuals, times, and worlds can in principle be made explicit in the syntax of the object language, or left to the semantics and spelled out in the meta-language. The traditional view is that quantification over individuals is syntactically explicit, whereas quantification over times and worlds is not. But a growing body of literature proposes a uniform treatment. This paper examines the scopal interaction of aspectual raising verbs (begin), modals (can), and intensional raising verbs (threaten) with quantificational subjects in (...) Shupamem, Dutch, and English. It appears that aspectual raising verbs and at least modals may undergo the same kind of overt or covert scope-changing operations as nominal quantifiers; the case of intensional raising verbs is less clear. Scope interaction is thus shown to be a new potential diagnostic of object-linguistic quantification, and the similarity in the scope behavior of nominal and verbal quantifiers supports the grammatical plausibility of ontological symmetry, explored in Schlenker (2006). (shrink)

In this paper we investigate the class of MV-algebras equipped with two quantifiers which commute as a natural generalization of diagonal-free two-dimensional cylindric algebras. In the 40s, Tarski first introduced cylindric algebras in order to provide an algebraic apparatus for the study of classical predicate calculus. The diagonal–free two-dimensional cylindric algebras are special cylindric algebras. The treatment here of MV-algebras is done in terms of implication and negation. This allows us to simplify some results due to Di Nola and (...) Grigolia :125–139, 2004) related to the characterization of a quantifier in terms of some special sub-algebra associated to it. On the other hand, we present a topological duality for this class of algebras and we apply it to characterize the congruences of one algebra via certain closed sets. Finally, we study the subvariety of this class generated by a chain of length n + 1. We prove that the subvariety is semisimple and we characterize their simple algebras. Using a special functional algebra, we determine all the simple finite algebras of this subvariety. (shrink)

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)

Previous theorists have claimed that Russell’s theory of definite descriptions gives the wrong truth conditions to sentences in which definite descriptions are embedded under certain other operators; but the other operators used, such as conditionals and propositional attitude verbs, have introduced intensional and hyperintensional complications that might be thought to obscure the point against Russell. This paper shows that the same kind of problem arises when the operator in question allows the context to be extensional. It is further argued that (...) presuppositional theories of definite descriptions give intuitively satisfying analyses of the novel data. (shrink)

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like $\exists ^{ \ge 3/4} y$ which says that "for at least 3/4 of all y". These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier $\exists ^{ \ge r} y$ , where y is (...) a tuple of variables. 2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope. 3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities pR for each predicate symbol R. 4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs). 5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers. 6. We allow each pR , as well as each r in the probability quantifier $(\exists ^{ \ge r} y)$ , to depend on the size of the universe. (shrink)

THEOREM 1. (⋄ ℵ 1 ) If B is an infinite Boolean algebra (BA), then there is B 1 such that $|\operatorname{Aut} (B_1)| \leq B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut} (B_1)\rangle \equiv \langle B, \operatorname{Aut}(B)\rangle$ . THEOREM 2. (⋄ ℵ 1 ) There is a countably compact logic stronger than first-order logic even on finite models. This partially answers a question of H. Friedman. These theorems appear in §§ 1 and 2. THEOREM 3. (a) (⋄ ℵ 1 ) If (...) B is an atomic ℵ 1 -saturated infinite BA, ψ ε L ω 1ω and $\langle B, \operatorname{Aut} (B)\rangle \models\psi$ then there is B 1 such that $|\operatorname{Aut}(B_1)| \leq |B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut}(B_1)\rangle\models\psi$ . In particular if B is 1-homogeneous so is B 1 . (b) (a) holds for B = P(ω) even if we assume only CH. (shrink)

Still, some may still want to say it. If so, my replies may gain nothing better than a stalemate against such persistence, though I can hope that earlier revelations will discourage others from persisting. But two replies are possible. Both come down, one circuitously, to an issue with us from the beginning: whether the language of the right side of (10) is suspect. For if (10) is to support instances for (6) which are about objects, that clause must itself be (...) about objects. (These would be ones assigned by variants of I it mentions to constants it mentions.) Yet Barwise and I would call it implicitly about functions. Ironically, the discussion surrounding (10), hoping to settle that issue, could only do so if the issue were already settled, revealing decisively the ontology of (10). If irritating, this is also inevitable, given the Tarskian spirit of the ensivioned semantics for QLB.A second reply begins by noting that a QLB semantics which implies (10) cannot simply be assumed. Even a QL semantics augmented to imply (11) is not trivial to frame, as I will let readers confirm. On the QLB project, Barwise comments thus:It is not possible to explain the meaning of an essential use of branching quantification ... inductively, by treating one quantifier at a time in a first-order fashion. Some use of higher-type abstract objects is essential. (BQE75)But believers in a modest ontology for QLB can claim a non sequitur here. For (10), as they read it, succeeds without mentioning abstract objects, though not in the “one quantifier at a time” way which Barwise rightly finds impossible. This is not yet to say the same about a QLB semantics implying (10). But that too can be said, as it happens, with as good a conscience as with (10). A suitable treatment can begin by somehow linearizing non QL sentences like (6). Still assuming prefixes whose rows each consist, speaking loosely, of n universal quantifiers followed by a single existential, we could simply line up these rows in any order, with unique deconcatenatability being assured. From then on, it gets both tedious and complex. A full syntax is essential, and some surprising categories arose in mine. I will spare readers all details, except to say that one can indeed “treat one quantifier at a time”, if not “in first-order fashion”: schematic rules for treating n quantifiers at once can be eschewed. Unsurprisingly, heavy use is made of the “depending only on” idiom seen in (10). Nor does it surprise me that this semantics can succeed, with that idiom available. Roughly, if open talk about functions works in a semantics for QLF, what I read as implicit talk about them should work in a semantics for QLB See [6] for a start on a semantics aspiring to handle sentences like (6) without invoking abstract objects. See also my comments on its notion of dependence, in [9]. . So even from a bare sketch, we can see that this new semantics settles nothing. It just leads back to the stalemate. Barwise and I will read crucial clauses as talking implicitly about functions, but this general charge against an idiom is equally deniable wherever the idiom occurs: in a reading for (6), say, or in the metalanguage can hardly repress a motherhood slogan: better dead than obscurely read. But that just denies the denial, unhelpfully. A better comment is the reminder that the claim stays alive only in a form which no one has ever imagined for it. The QLB quantifiers that cannot be shown not to range over objects are not the items anyone would ever have pointed to in illustrating the unkillable claim. (shrink)