Plural quantification

Last updated

In mathematics and logic, plural quantification is the theory that an individual variable x may take on plural , as well as singular, values. As well as substituting individual objects such as Alice, the number 1, the tallest building in London etc. for x, we may substitute both Alice and Bob, or all the numbers between 0 and 10, or all the buildings in London over 20 stories.

Contents

The point of the theory is to give first-order logic the power of set theory, but without any "existential commitment" to such objects as sets. The classic expositions are Boolos 1984 and Lewis 1991.

History

The view is commonly associated with George Boolos, though it is older (see notably Simons 1982), and is related to the view of classes defended by John Stuart Mill and other nominalist philosophers. Mill argued that universals or "classes" are not a peculiar kind of thing, having an objective existence distinct from the individual objects that fall under them, but "is neither more nor less than the individual things in the class". (Mill 1904, II. ii. 2, also I. iv. 3).

A similar position was also discussed by Bertrand Russell in chapter VI of Russell (1903), but later dropped in favour of a "no-classes" theory. See also Gottlob Frege 1895 for a critique of an earlier view defended by Ernst Schroeder.

The general idea can be traced back to Leibniz. (Levey 2011, pp. 129–133)

Interest revived in plurals with work in linguistics in the 1970s by Remko Scha, Godehard Link, Fred Landman, Friederike Moltmann, Roger Schwarzschild, Peter Lasersohn and others, who developed ideas for a semantics of plurals.

Background and motivation

Multigrade (variably polyadic) predicates and relations

Sentences like

Alice and Bob cooperate.
Alice, Bob and Carol cooperate.

are said to involve a multigrade (also known as variably polyadic, also anadic) predicate or relation ("cooperate" in this example), meaning that they stand for the same concept even though they don't have a fixed arity (cf. Linnebo & Nicolas 2008). The notion of multigrade relation/predicate has appeared as early as the 1940s and has been notably used by Quine (cf. Morton 1975). Plural quantification deals with formalizing the quantification over the variable-length arguments of such predicates, e.g. "xx cooperate" where xx is a plural variable. Note that in this example it makes no sense, semantically, to instantiate xx with the name of a single person.

Nominalism

Broadly speaking, nominalism denies the existence of universals (abstract entities), like sets, classes, relations, properties, etc. Thus the plural logics were developed as an attempt to formalize reasoning about plurals, such as those involved in multigrade predicates, apparently without resorting to notions that nominalists deny, e.g. sets.

Standard first-order logic has difficulties in representing some sentences with plurals. Most well-known is the Geach–Kaplan sentence "some critics admire only one another". Kaplan proved that it is nonfirstorderizable (the proof can be found in that article). Hence its paraphrase into a formal language commits us to quantification over (i.e. the existence of) sets.

Boolos argued that second-order monadic quantification may be systematically interpreted in terms of plural quantification, and that, therefore, second-order monadic quantification is "ontologically innocent". [1]

Later, Oliver & Smiley (2001), Rayo (2002), Yi (2005) and McKay (2006) argued that sentences such as

They are shipmates
They are meeting together
They lifted a piano
They are surrounding a building
They admire only one another

also cannot be interpreted in monadic second-order logic. This is because predicates such as "are shipmates", "are meeting together", "are surrounding a building" are not distributive. A predicate F is distributive if, whenever some things are F, each one of them is F. But in standard logic, every monadic predicate is distributive. Yet such sentences also seem innocent of any existential assumptions, and do not involve quantification.

So one can propose a unified account of plural terms that allows for both distributive and non-distributive satisfaction of predicates, while defending this position against the "singularist" assumption that such predicates are predicates of sets of individuals (or of mereological sums).

Several writers[ who? ] have suggested that plural logic opens the prospect of simplifying the foundations of mathematics, avoiding the paradoxes of set theory, and simplifying the complex and unintuitive axiom sets needed in order to avoid them.[ clarification needed ]

Recently, Linnebo & Nicolas (2008) have suggested that natural languages often contain superplural variables (and associated quantifiers) such as "these people, those people, and these other people compete against each other" (e.g. as teams in an online game), while Nicolas (2008) has argued that plural logic should be used to account for the semantics of mass nouns, like "wine" and "furniture".

Formal definition

This section presents a simple formulation of plural logic/quantification approximately the same as given by Boolos in Nominalist Platonism (Boolos 1985).

Syntax

Sub-sentential units are defined as

Full sentences are defined as

The last two lines are the only essentially new component to the syntax for plural logic. Other logical symbols definable in terms of these can be used freely as notational shorthands.

This logic turns out to be equi-interpretable with monadic second-order logic.

Model theory

Plural logic's model theory/semantics is where the logic's lack of sets is cashed out. A model is defined as a tuple where is the domain, is a collection of valuations for each predicate name in the usual sense, and is a Tarskian sequence (assignment of values to variables) in the usual sense (i.e. a map from singular variable symbols to elements of ). The new component is a binary relation relating values in the domain to plural variable symbols.

Satisfaction is given as

Where for singular variable symbols, means that for all singular variable symbols other than , it holds that , and for plural variable symbols, means that for all plural variable symbols other than , and for all objects of the domain , it holds that .

As in the syntax, only the last two are truly new in plural logic. Boolos observes that by using assignment relations, the domain does not have to include sets, and therefore plural logic achieves ontological innocence while still retaining the ability to talk about the extensions of a predicate. Thus, the plural logic comprehension schema does not yield Russell's paradox because the quantification of plural variables does not quantify over the domain. Another aspect of the logic as Boolos defines it, crucial to this bypassing of Russell's paradox, is the fact that sentences of the form are not well-formed: predicate names can only combine with singular variable symbols, not plural variable symbols.

This can be taken as the simplest, and most obvious argument that plural logic as Boolos defined it is ontologically innocent.

See also

Notes

  1. Harman, Gilbert; Lepore, Ernest (2013), A Companion to W. V. O. Quine, Blackwell Companions to Philosophy, John Wiley & Sons, p. 390, ISBN   9781118608029 .

Related Research Articles

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

<span class="mw-page-title-main">Original proof of Gödel's completeness theorem</span>

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 is not easy to read today; it uses concepts and formalisms that are no longer used and terminology that is often obscure. The version given below attempts to represent all the steps in the proof and all the important ideas faithfully, while restating the proof in the modern language of mathematical logic. This outline should not be considered a rigorous proof of the theorem.

A proposition is a central concept in the philosophy of language, semantics, logic, and related fields, often characterized as the primary bearer of truth or falsity. Propositions are also often characterized as being the kind of thing that declarative sentences denote. For instance the sentence "The sky is blue" denotes the proposition that the sky is blue. However, crucially, propositions are not themselves linguistic expressions. For instance, the English sentence "Snow is white" denotes the same proposition as the German sentence "Schnee ist weiß" even though the two sentences are not the same. Similarly, propositions can also be characterized as the objects of belief and other propositional attitudes. For instance if one believes that the sky is blue, what one believes is the proposition that the sky is blue. A proposition can also be thought of as a kind of idea: Collins Dictionary has a definition for proposition as "a statement or an idea that people can consider or discuss whether it is true."

In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term. Functional predicates are also sometimes called mappings, but that term has additional meanings in mathematics. In a model, a function symbol will be modelled by a function.

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can be identified with the set of formulas in the language.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic.

In mathematical logic, an atomic formula is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic. Compound formulas are formed by combining the atomic formulas using the logical connectives.

In mathematics, the notion of cylindric algebra, developed by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Cylindric algebras are Boolean algebras equipped with additional cylindrification operations that model quantification and equality. They differ from polyadic algebras in that the latter do not model equality.

In logic, the monadic predicate calculus is the fragment of first-order logic in which all relation symbols in the signature are monadic, and there are no function symbols. All atomic formulas are thus of the form , where is a relation symbol and is a variable.

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier. Lindström quantifiers generalize first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers. They were introduced by Per Lindström in 1966. They were later studied for their applications in logic in computer science and database query languages.

This article gives a sketch of a proof of Gödel's first incompleteness theorem. This theorem applies to any formal theory that satisfies certain technical hypotheses, which are discussed as needed during the sketch. We will assume for the remainder of the article that a fixed theory satisfying these hypotheses has been selected.

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics.

In mathematical logic, predicate functor logic (PFL) is one of several ways to express first-order logic by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices called predicate functors that operate on terms to yield terms. PFL is mostly the invention of the logician and philosopher Willard Quine.

In semantics, donkey sentences are sentences that contain a pronoun with clear meaning but whose syntactic role in the sentence poses challenges to linguists. Such sentences defy straightforward attempts to generate their formal language equivalents. The difficulty is with understanding how English speakers parse such sentences.

In mathematical logic, a witness is a specific value t to be substituted for variable x of an existential statement of the form ∃xφ(x) such that φ(t) is true.

In mathematical logic the theory of pure equality is a first-order theory. It has a signature consisting of only the equality relation symbol, and includes no non-logical axioms at all.

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier in the first order formula expresses that everything in the domain satisfies the property denoted by . On the other hand, the existential quantifier in the formula expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true. By a result in descriptive complexity, a set of natural numbers is a spectrum if and only if it can be recognized in non-deterministic exponential time.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

References