| • Science | • People | • Locations | • Timeline |
| Contents | ||
In mathematical logic, second-order logic is an extension of first-order logic allowing quantification over subsets of a domain, or functions from the domain into itself, rather than only over individual members of the domain. Thus, for example, if the domain is the set of all real numbers, one can assert in first-order logic the existence of an additive inverse of each real number by writing
but one needs second-order logic to assert the least-upper-bound property of the real numbers:
and insert in place of the dots a statement that if A is nonempty and has an upper bound in R then A has a least upper bound in R.
An optimist might attempt to reduce second-order logic to first-order logic in the following way. Expand the domain from the set of all real numbers to the union of that set with the set of all sets of real numbers. Add a new binary predicate to the language: the membership relation. Then sentences that were second-order become first-order.
But notice that the domain was asserted to include all sets of real numbers. That requirement has not been reduced to a first-order sentence! But might there be some way to accomplish the reduction? The classic Löwenheim-Skolem theorem entails that there is not. That theorem implies that there is some countably infinite subset of R, whose members we will call internal numbers, and some countably infinite set of sets of internal numbers, whose members we will call "internal sets", such that the domain consisting of internal numbers and internal sets satisfies all of the first-order sentences satisfied by the domain of real-numbers-and-sets-of-real-numbers. In particular, it satisfies a sort of least-upper-bound axiom that says, in effect:
Countability of the set of all internal numbers (in conjunction with the fact that those form a densely ordered set) necessarily implies that that set does not satisfy the full least-upper-bound axiom. Countability of the set of all internal sets necessarily implies that is not the set of all subsets of the set of all internal numbers (since Cantor's theorem implies that the set of all subsets of a countably infinite set is an uncountably infinite set).
Yet another profound difference between first-order and second-order logic is the topic of the next section.
It is a corollary of Gödel's incompleteness theorem that one cannot have any notion of provability of second-order formulas that simultaneously satisfies these three desired attributes:
This is sometimes expressed by saying that second-order logic does not admit a proof theory.
In this respect second-order logic differs from first-order logic.
When predicate logic was invented by Frege, he did use different variables to distinguish quantification over objects from quantification over properties and sets; but he did not see himself as doing two different kinds of logic. After the discovery of Russell's Paradox it was realized that something was wrong with his system. Eventually logicians found that restricting Frege's logic in various ways—to what is now called first-order logicModel theory Logic First-order predicate calculus or first-order logic FOL is a theory in symbolic logic that permits the formulation of quantified statements such as "there is at least one X such that. or "for any X, it is the case that. where X is an el—eliminated this problem: sets and properties cannot be quantified over in first-order-logic alone. The now-standard hierarchyA hierarchy (Greek hieros sacred, arkho rule) is a system of ranking and organizing things. Different fields use the word in slightly different ways, but a particular definition (below) captures the core of almost all uses. Originally, "hierarchy" meant " of orders of logics dates from this time.
It was found that set theorySet theory is the mathematical theory of sets, which represent collections of abstract objects. It has a central role in modern mathematical theory, providing the basic language in which most of mathematics is expressed. For more information on set theory could be formulated as an axiomatized system within the apparatus of first-order logic (at the cost of several kinds of completeness, but nothing so bad as Russell's Paradox), and this was done (see Zermelo-Fraenkel set theoryThe Zermelo-Fraenkel axioms of set theory (ZF are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. When the axiom of choice is included, the resulting sys), as sets are vital for mathematicsMathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of "figures and numbers". In the formalist view, it is the investigation of axiomatically defined abstract structures. ArithmeticArithmetic Arithmetic or arithmetics in common usage is a branch of (or the forerunner of) mathematics which records elementary properties of certain operations on numerals, though in usage by professional mathematicians, it often is treated as synonym fo, mereologyMereology is the branch of logic, mathematics, and metaphysics dealing with part-whole relationships. It was first formalized by Stanislaw Lesniewski, and greatly elaborated later by Henry Leonard and Nelson Goodman. Mereology was in part motivated by the, and a variety of other powerful logical theories could be formulated axiomatically without appeal to any more logical apparatus than first-order quantification, and this led to a general decline in work in second (or any higher) order logic.
This rejection was actively advanced by some logicians, most notably W. V. QuineWillard Van Orman Quine ( June 25, 1908 December 25, 2000) was one of the most influential American philosophers and logicians of the 20th century. Overview Sometimes referred to as the "philosopher's philosopher", Quine is the quintessential model of an. Quine advanced the view that in predicate-language sentences like Fx the "x" is to be thought of as a variable or name denoting an object and hence can be quantified over, as in "For all things, it is the case that . . ." but the "F" is to be thought of as an abbreviation for an incomplete sentence, not the name of an object (not even of an abstract object like a property). For example, it might mean " . . . is a dog." But it makes no sense to think we can quantify over something like this. (Such a position is quite consistent with Frege's own arguments on the concept-object distinction).
In recent years second-order logic has made something of a recovery, bouyed by George Boolos' interpretaion of second-order quantification as plural quantification over the same domain of objects as first-order quantification. Boolos furthermore points to the nonfirstorderizability of sentences such as "Some critics admire only each other" and "Some of Fianchetto's men went into the warehouse unaccompanied by anyone else."