Nonfirstorderizability

This article may be too technical for most readers to understand. Please to make it understandable to non-experts, without removing the technical details. (March 2016) (Learn how and when to remove this template message)

In formal logic, nonfirstorderizability is the inability of an expression to be adequately captured in particular theories in first-order logic. Nonfirstorderizable sentences are sometimes presented as evidence that first-order logic is not adequate to capture the nuances of meaning in natural language.

The term was coined by George Boolos in his well-known paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)." Quine argued that such sentences call for second-order symbolization, which can be interpreted as plural quantification over the same domain as first-order quantifiers use, without postulation of distinct "second-order objects" (properties, sets, etc.).

Examples[]

• The concept of identity cannot be defined in first-order languages, merely indiscernibility.^[1]
• The compactness theorem implies that graph connectivity cannot be expressed in first-order logic.^{[clarification needed]}
• The Archimedean property that may be used to identify the real numbers among the real closed fields.
• A standard example is the Geach–Kaplan sentence: "Some critics admire only one another."

If Axy is understood to mean "x admires y," and the universe of discourse is the set of all critics, then a reasonable translation of the sentence into second order logic is:

$${\displaystyle \exists X(\exists x,y(Xx\land Xy\land Axy)\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land Axy\rightarrow Xy))}$$

That this formula has no first-order equivalent can be seen as follows. Substitute the formula (y = x + 1 v x = y + 1) for Axy. The result,

$${\displaystyle \exists X(\exists x,y(Xx\land Xy\land (y=x+1\lor x=y+1))\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land (y=x+1\lor x=y+1)\rightarrow Xy))}$$

states that there is a nonempty set which is closed under the predecessor and successor operations and yet does not contain all numbers. Thus, it is true in all nonstandard models of arithmetic but false in the standard model. Since no first-order sentence has this property, the result follows.

See also[]

• Branching quantifier
• Generalized quantifier
• Plural quantification
• Reification (linguistics)

References[]

• George Boolos (1984). "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)". Journal of Philosophy. The Journal of Philosophy, Vol. 81, No. 8. 81 (8): 430–49. doi:10.2307/2026308. JSTOR 2026308. Reprinted in Boolos, George (1998). Logic, Logic, and Logic. Cambridge, MA: Harvard University Press. ISBN 0-674-53767-X.

External links[]

• Printer-friendly CSS, and nonfirstorderisability by Terence Tao

This logic-related article is a stub. You can help Wikipedia by .

• v
• t