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.).
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:In words, this states that there exists a collection of critics with the following properties: The collection forms a proper subclass of all the critics; it is inhabited (and thus non-empty) by a member that admires a critic that is also a member; and it is such that if any of its members admires anyone, then the latter is necessarily also a member.
That this formula has no first-order equivalent can be seen by turning it into a formula in the language of arithmetic. To this end, substitute the formula for Axy. This expresses that the two terms are successors of one another, in some way. The resulting proposition,states that there is a set with the following three properties:
Recall 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 (i.e.,). The model is called non-standard otherwise. The formula above is true only in non-standard models: In the standard model would be a proper subset of all numbers that also would have to contain all available numbers, and so it fails. And then on the other hand, in every non-standard model there is a subset satisfying the formula.
Let us now assume that there is a first-order rendering of the above formula called . If
\negE
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:which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulaeEvery 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.