Second Order Logic
SECOND ORDER LOGIC
Secondorder logic is the extension of firstorder logic obtained by introducing quantification of predicate and function variables. A firstorder formula, say Fxy, may be converted to a secondorder formula by replacing F with a dyadic relation variable X, obtaining Xxy. Existential quantification yields ∃X Xxy, which may be read "there is a relation that x bears to y." In general relation variables of all adicities are admissible. Similarly, quantifiable function variables may be introduced.
Semantics for the SecondOrder Logic
A structure, with nonempty domain D, for a secondorder language includes relation domains Rel_{n} (D ) and function domains Func_{n} (D ). In general Rel_{n} (D ) C P (D^{n} ), where P (D^{n} ) is the power set of D^{n}. Similarly, the function domains Func_{n}(D ) are subsets of the collection of n place total functions on D. Such secondorder structures are called Henkin or general structures. If X is an n place relation variable, a formula ∃X φ(X ) is true in a Henkin structure M if there is an n place relation R ∈ Rel_{n} (D ) such that φ(X ) is true in M when X has the value R. There is a similar definition for formulas of the form ∀X φ(X ) and for formulas with quantified function variables. A formula φ is a Henkin semantic consequence of a set Δ of formulas if φ is true in all Henkin models of Δ.
The relation domain Rel_{n}(D ) need not contain all subsets of D^{n}. If Rel_{n}(D ) = P (D^{n} ) for each n, we say that each relation domain is full (similarly for function domains) and that the structure is full, standard or principal. Secondorder logic restricted to full structures is called full or standard secondorder logic. A formula φ is a full semantic consequence of a set Δ if φ is true in all full models of Δ. A formula is valid if it is true in all full structures.
In Henkin semantics, the Completeness, Compactness and LöwenheimSkolem Theorems hold because Henkin structures can be reinterpreted as manysorted firstorder structures. This yields Henkin's Completeness Theorem: There exists a deductive system DS such that if φ is a Henkin consequence of axioms Δ then there is a deduction of φ from Δ using the rules of DS. For further details, see Shapiro 1991, Shapiro 2001, or van Dalen 1994.
Expressive Power
Following Gottfried Leibniz, we may define "x = y " as "any property of x is a property of y." The corresponding secondorder definition ∀x ∀y (x = y ↔ ∀X (Xx → Xy )) is valid. In contrast with firstorder logic, there are categorical secondorder theories with infinite models: All full models are isomorphic. For example, let Δ be the theory with axioms ∀x (s (x ) ≠ 0), ∀x ∀y (s (x ) = s (y ) → x = y ) and ∀X [(X 0 ∧ ∀x (Xx → Xs (x ))) → ∀xXx ]. Any full model of Δ is isomorphic to the structure (N , 0, S ), where N is the set of natural numbers and S the successor operation. So, the LöwenheimSkolem Theorems fail in full secondorder logic. Consider the theory Δ ∪ {c ≠ 0, c ≠ s 0, c ≠ ss 0, …}, with c a constant. This theory has no full model, but any finite subset of it has a full model. So the Compactness Theorem fails, too.
Extending Δ with the recursion axioms for addition and multiplication, we obtain the theory PA_{2} whose unique full model up to isomorphism is the natural number structure (N, 0, S, +, x). Similarly there is an axiom system whose unique full model up to isomorphism is the ordered field of real numbers, (R , 0, 1, +, x, <). More generally there exist secondorder formulas expressing cardinality claims inexpressible in firstorder logic. The most striking example concerns the Continuum Hypothesis (CH), which says that there is no cardinal number between ℵ_{0} and 2^{ℵ0}. Results due to Kurt Gödel and Paul Cohen imply that the Continuum Hypothesis is independent of standard axiomatic set theory (ZFC). But there is a secondorder formula CH* which is valid just in case CH is true.
If we augment PA_{2} with inference rules for the secondorder quantifiers and the monadic comprehension scheme ∃X ∀x (Xx ↔ φ), we obtain axiomatic secondorder arithmetic, Z_{2}. (See Simpson 1998 for a detailed investigation of Z_{2} and its subsystems.) One may construct a Gödel sentence G, true just in case G is not a theorem of Z_{2}. Now, all full models of Z_{2} are isomorphic to (N, 0, S, +, x). So an arithmetic sentence φ is true just in case φ is a full semantic consequence of Z_{2}. G is thus a full semantic consequence of Z_{2} but not a theorem of Z_{2}. The Completeness Theorem therefore fails; there is no sound and complete, recursively axiomatized, deductive system for full secondorder logic. Indeed the set of secondorder validities is not recursively enumerable. For further details see Shapiro 1991, Shapiro 2001, or Enderton 2001.
Is SecondOrder Logic Logic?
Secondorder comprehension has the form ∃X ∀x _{1} … ∀x _{n}(Xx _{1}…x _{n} ↔ φ). Should such existential axioms count as logical? Does this violate the topicneutrality of logic? W. V. Quine argued that secondorder logic is "set theory in sheep's clothing" because "set theory's staggering existential assumptions are cunningly hidden … in the tacit shift from schematic predicate letter to quantifiable variable" (Quine 1970, p. 68). Another reason for not counting secondorder logic as logic is that the full semantic consequence relation does not allow a complete proof procedure.
In reply George Boolos pointed out that the obvious translation from secondorder formulas to firstorder settheoretic formulas does not map valid formulas to settheoretic theorems. For example ∃X ∀yXy is valid, while ∃x ∀y (y ∈ x ) is refutable in axiomatic set theory. Furthermore ∃X ∃x ∃y (Xx ∧ Xy ∧ x ≠ y ) is not valid, and so "secondorder logic is not committed to the existence of even a twomembered set" (Boolos 1975 [1998], pp. 40–41). Furthermore firstorder logic does have a complete proof procedure, but the set of firstorder validities is undecidable (Church's Theorem), while the monadic fragment is decidable. So why is completeness used to draw the line between logic and mathematics rather than decidability?
The Interpretation of SecondOrder Variables
George Boolos (1984, 1985) has provided monadic secondorder logic with a novel interpretation: the plural interpretation. Certain natural language locutions that receive monadic secondorder formalizations are perhaps better analysed as instances of plural quantification. For example the GeachKaplan sentence, "Some critics admire only one another," may be formalized as ∃X (∃xXx ∧ ∀x ∀y (Xx ∧ Axy → x ≠ y ∧ Xy )). This formula is nonfirstorderizable (not equivalent to a firstorder formula containing just the predicates A and =). According to the usual interpretation, its truth implies the existence of a collection. The plural interpretation reads "There are some [critics] such that, for any x and y, if x is one of them and admires y, then y is not x and y is one of them." Rather than asserting the existence of a collection, this is a plural means of referring to individuals. Secondorder logic can also be applied to set theory. In this context we can interpret monadic secondorder quantification over sets as plural quantification.
See also Computability Theory; FirstOrder Logic; Gödel, Kurt; Leibniz, Gottfried Wilhelm; Logic, History of: Modern Logic: From Frege to Gödel; Mathematics, Foundations of; Proof Theory; Quine, Willard Van Orman.
Bibliography
Boolos, George. Logic, Logic and Logic. Cambridge, MA: Harvard University Press, 1998.
Boolos, George. "Nominalist Platonism." Philosophical Review 94 (1985): 327–344. Reprinted in Boolos 1998.
Boolos, George. "On SecondOrder Logic." Journal of Philosophy 72 (1975): 509–527. Reprinted in Boolos 1998.
Boolos, George. "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)." Journal of Philosophy 81 (1984): 430–449. Reprinted in Boolos 1998.
Enderton, Herbert. A Mathematical Introduction to Logic. San Diego, CA: Harcourt/Academic Press, 2001.
Shapiro, Stewart. Foundations Without Foundationalism: A Case for SecondOrder Logic. Oxford: Oxford University Press, 1991.
Shapiro, Stewart. "SecondOrder Logic." In Blackwell Guide to Philosophical Logic, edited by Lou Goble. Oxford: Blackwell, 2001.
Simpson, Stephen G. Subsystems of SecondOrder Arithmetic. Berlin: Springer, 1998.
Quine, W. V. O. Philosophy of Logic. Cambridge, MA: Harvard University Press, 1970.
van Dalen, Dirk. Logic and Structure. Berlin: SpringerVerlag, 1994.
Jeffrey Ketland (2005)
Cite this article
Pick a style below, and copy the text for your bibliography.

MLA

Chicago

APA
"Second Order Logic." Encyclopedia of Philosophy. . Encyclopedia.com. 19 Aug. 2018 <http://www.encyclopedia.com>.
"Second Order Logic." Encyclopedia of Philosophy. . Encyclopedia.com. (August 19, 2018). http://www.encyclopedia.com/humanities/encyclopediasalmanacstranscriptsandmaps/secondorderlogic
"Second Order Logic." Encyclopedia of Philosophy. . Retrieved August 19, 2018 from Encyclopedia.com: http://www.encyclopedia.com/humanities/encyclopediasalmanacstranscriptsandmaps/secondorderlogic
Citation styles
Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).
Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.
Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the mostrecent information available at these sites:
Modern Language Association
The Chicago Manual of Style
http://www.chicagomanualofstyle.org/tools_citationguide.html
American Psychological Association
Notes:
 Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
 In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.