Philosophy:Nonfirstorderizability
{{{1}}} |
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: [math]\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)) }[/math]
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 v x = y + 1) for Axy. The result, [math]\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)) }[/math] 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 [math]\displaystyle{ \neg E }[/math] 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 Bn. For example, the formula B3 is: [math]\displaystyle{ \exists x \exists y \exists z (x \neq y \wedge x \neq z \wedge y \neq z) }[/math] which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulae [math]\displaystyle{ A, B_2, B_3, B_4, \ldots }[/math] Every finite subset of these formulae has a model: given a subset, find the greatest n for which the formula Bn 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 Bm+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]
See also
- Definable set
- Branching quantifier
- Generalized quantifier
- Plural quantification
- Reification (linguistics)
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. Reprinted in Boolos, George (1998). Logic, Logic, and Logic. Cambridge, MA: Harvard University Press. ISBN 0-674-53767-X.
- ↑ Intermediate Logic. Open Logic Project. pp. 235. https://builds.openlogicproject.org/courses/intermediate-logic/il-screen.pdf. Retrieved 21 March 2022.
- ↑ Noonan, Harold; Curtis, Ben (2014-04-25). "Identity". in Zalta, Edward N.. Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/entries/identity/.
External links
 |  |
