Nonfirstorderizability Explained

In formal logic, nonfirstorderizability is the inability of a natural-language statement to be adequately captured by a formula of first-order logic. Specifically, a statement is nonfirstorderizable if there is no formula of first-order logic which is true in a model if and only if the statement holds in that model. Nonfirstorderizable statements 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 paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)".^[1] 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

Geach-Kaplan sentence

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:$$\backslash exists\; X\; (\backslash exists\; x,y\; (Xx\; \backslash land\; Xy\; \backslash land\; Axy)\; \backslash land\; \backslash exists\; x\; \backslash neg\; Xx\; \backslash land\; \backslash forall\; x\backslash ,\; \backslash forall\; y\; (Xx\; \backslash land\; Axy\; \backslash rightarrow\; Xy))$$

That this formula has no first-order equivalent can be seen by turning it into a formula in the language of arithmetic . Substitute the formula $(y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1)$ for Axy. The result,$$\backslash exists\; X\; (\backslash exists\; x,y\; (Xx\; \backslash land\; Xy\; \backslash land\; (y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1))\; \backslash land\; \backslash exists\; x\; \backslash neg\; Xx\; \backslash land\; \backslash forall\; x\backslash ,\; \backslash forall\; y\; (Xx\; \backslash land\; (y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1)\; \backslash rightarrow\; Xy))$$states that there is a set with these properties:

• There are at least two numbers in
• There is a number that does not belong to, i.e. does not contain all numbers.
• If a number belongs to and is or, also belongs to .

A model of a formal theory of arithmetic, such as first-order Peano arithmetic, is called standard if it only contains the familiar natural numbers as elements. The model is called non-standard otherwise. Therefore, the formula given above is true only in non-standard models, because, in the standard model, the set must contain all available numbers . In addition, there is a set satisfying the formula in every non-standard model.

Let us assume that there is a first-order rendering of the above formula called . If

\neg E were added to the Peano axioms, it would mean that there were no non-standard models of the augmented axioms. However, the usual argument for the existence of non-standard models would still go through, proving that there are non-standard models after all. This is a contradiction, so we can conclude that no such formula exists in first-order logic.

Finiteness of the domain

There is no formula in first-order logic with equality which is true of all and only models with finite domains. In other words, there is no first-order formula which can express "there is only a finite number of things".

This is implied by the compactness theorem as follows.^[2] Suppose there is a formula which is true in all and only models with finite domains. We can express, for any positive integer, the sentence "there are at least elements in the domain". For a given, call the formula expressing that there are at least elements . For example, the formula is:$$\backslash exists\; x\; \backslash exists\; y\; \backslash exists\; z\; (x\; \backslash neq\; y\; \backslash wedge\; x\; \backslash neq\; z\; \backslash wedge\; y\; \backslash neq\; z)$$which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulae$$A,\; B\_2,\; B\_3,\; B\_4,\; \backslash ldots$$Every finite subset of these formulae has a model: given a subset, find the greatest for which the formula is in the subset. Then a model with a domain containing elements will satisfy (because the domain is finite) and all the formulae in the subset. Applying the compactness theorem, the entire infinite set must also have a model. Because of what we assumed about, the model must be finite. However, this model cannot be finite, because if the model has only elements, it does not satisfy the formula . This contradiction shows that there can be no formula with the property we assumed.

Other examples

• The concept of identity cannot be defined in first-order languages, merely indiscernibility.^[3]
• The Archimedean property that may be used to identify the real numbers among the real closed fields.
• The compactness theorem implies that graph connectivity cannot be expressed in first-order logic.

See also

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

External links

• Printer-friendly CSS, and nonfirstorderisability by Terence Tao

Notes and References

1. Boolos . George . George Boolos . To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables) . The Journal of Philosophy . August 1984 . 81 . 8 . 430–449 . 10.2307/2026308 . 2026308 . Reprinted in Book: Boolos, George . 1998 . Logic, Logic, and Logic . . . 0-674-53767-X .
2. Book: Intermediate Logic . Open Logic Project . 235 . 21 March 2022.
3. identity. Identity. Noonan. Harold. Curtis. Ben. 2014-04-25. 2 "The Logic of Identity".