Nonfirstorderizability

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: $\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 by turning it into a formula in the language of arithmetic . Substitute the formula ${\textstyle (y=x+1\lor x=y+1)}$ for Axy. The result, $\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 set $X$ with these properties:

There are at least two numbers in $X$
There is a number that does not belong to $X$ , i.e. $X$ does not contain all numbers.
If a number $x$ belongs to $X$ and $y$ is $x + 1$ or $x - 1$ , $y$ also belongs to $X$ .

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 $0, 1, 2, ...$ 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 $X$ must contain all available numbers $0, 1, 2, ...$ . In addition, there is a set $X$ satisfying the formula in every non-standard model.

Let us assume that there is a first-order rendering of the above formula called $E$ . 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 $E$ exists in first-order logic.

Finiteness of the domain

There is no formula $A$ 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 $A$ which is true in all and only models with finite domains. We can express, for any positive integer $n$ , the sentence "there are at least $n$ elements in the domain". For a given $n$ , call the formula expressing that there are at least $n$ elements $B n$ . For example, the formula $B 3$ is: $\exists x\exists y\exists z(x\neq y\wedge x\neq z\wedge y\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},\ldots$ Every finite subset of these formulae has a model: given a subset, find the greatest $n$ for which the formula $B n$ is in the subset. Then a model with a domain containing $n$ elements will satisfy $A$ (because the domain is finite) and all the $B$ formulae in the subset. Applying the compactness theorem, the entire infinite set must also have a model. Because of what we assumed about $A$ , the model must be finite. However, this model cannot be finite, because if the model has only $m$ elements, it does not satisfy the formula $B m+1$ . This contradiction shows that there can be no formula $A$ 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.^{[clarification needed]}

References

^ Boolos, George (August 1984). "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)". The Journal of Philosophy. 81 (8): 430–449. 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.
^ Intermediate Logic (PDF). Open Logic Project. p. 235. Retrieved 21 March 2022.
^ Noonan, Harold; Curtis, Ben (2014-04-25). "Identity". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.

External links

Printer-friendly CSS, and nonfirstorderisability by Terence Tao

[boolos-to-be-1] Boolos, George (August 1984). "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)". The Journal of Philosophy. 81 (8): 430–449. 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.

[2] Intermediate Logic (PDF). Open Logic Project. p. 235. Retrieved 21 March 2022.

[3] Noonan, Harold; Curtis, Ben (2014-04-25). "Identity". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.

[1]

[2]

[3]