# Nonfirstorderizability

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Nonfirstorderizability
> Markdown URL: https://mediated.wiki/source/Nonfirstorderizability.md
> Source: https://en.wikipedia.org/wiki/Nonfirstorderizability
> Source revision: 1332064688
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Concept in formal logic}}
{{tech|date=March 2016}}In [formal logic](/source/formal_logic), '''nonfirstorderizability''' is the inability of a natural-language statement to be adequately captured by a formula of [first-order logic](/source/first-order_logic).  Specifically, a statement is '''nonfirstorderizable''' if there is no formula of first-order logic which is true in a [model](/source/Model_theory) 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](/source/natural_language).

The term was coined by [George Boolos](/source/George_Boolos) in his paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)".<ref name="boolos-to-be">{{cite journal |last1=Boolos |first1=George |author-link=George Boolos |title=To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables) |journal=The Journal of Philosophy |date=August 1984 |volume=81 |issue=8 |pages=430–449 |doi=10.2307/2026308 |jstor=2026308 }} Reprinted in {{cite book | first=George | last=Boolos | year=1998 | title=Logic, Logic, and Logic | publisher=[Harvard University Press](/source/Harvard_University_Press) | location=[Cambridge, MA](/source/Cambridge%2C_MA) | isbn=0-674-53767-X }}</ref>
[Willard Van Orman Quine](/source/Willard_Van_Orman_Quine) argued that such sentences call for [second-order](/source/second-order_logic) 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](/source/Property_(mathematics)), sets, etc.).

== Examples ==

=== Geach-Kaplan sentence ===
A standard example is the ''[Geach](/source/Peter_Geach)–[Kaplan](/source/David_Kaplan_(philosopher)) sentence'': "Some critics admire only one another."
If ''Axy'' is understood to mean "''x'' admires ''y''," and the [universe of discourse](/source/universe_of_discourse) is the set of all critics, then a reasonable [translation of the sentence](/source/logic_translation) into second order logic is:
<math display="block">\exists X \big( (\exists x \neg Xx) \land \exists x,y (Xx \land Xy \land Axy) \land \forall x\, \forall y (Xx \land Axy \rightarrow Xy)\big)</math>
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 <math display="inline"> ( y = x + 1 \lor x = y + 1 ) </math> for ''Axy''. This expresses that the two terms are successors of one another, in some way. The resulting proposition,
<math display="block">\exists X \big( (\exists x \neg Xx) \land \exists x,y (Xx \land Xy \land (y = x + 1 \lor x = y + 1)) \land \forall x\, \forall y (Xx \land (y = x + 1 \lor x = y + 1) \rightarrow Xy)\big)</math>
states that there is a set {{mvar|X}} with the following three properties:
* There is a number that does not belong to {{mvar|X}}, i.e. {{mvar|X}} does ''not contain all'' numbers.
* The set {{mvar|X}} is inhabited, and here this indeed immediately means there are at least two numbers in it.
* If a number {{mvar|x}} belongs to {{mvar|X}} and if {{mvar|y}} is either {{math|x + 1}} or {{math|x - 1}}, then {{mvar|y}} also belongs to {{mvar|X}}.
Recall a model of a formal theory of arithmetic, such as [first-order Peano arithmetic](/source/Peano_axioms), is called ''standard'' if it ''only'' contains the familiar natural numbers as elements (i.e., {{math|0, 1, 2, ...}}). The model is called [non-standard](/source/Non-standard_model_of_arithmetic) otherwise. The formula above is true only in non-standard models: In the standard model {{mvar|X}} would be a proper subset of all numbers that also would have to contain all available numbers ({{math|0, 1, 2, ...}}), and so it fails. And then on the other hand, in every non-standard model there is a subset {{mvar|X}} satisfying the formula.

Let us now assume that there is a first-order rendering of the above formula called {{mvar|E}}. If <math>\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](/source/Non-standard_model_of_arithmetic) 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 {{mvar|E}} exists in first-order logic.

=== Finiteness of the domain ===
There is no formula {{mvar|A}} in [first-order logic with equality](/source/First-order_logic) 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](/source/compactness_theorem) as follows.<ref>{{cite book |title=Intermediate Logic |publisher=Open Logic Project |pages=235 |url=https://builds.openlogicproject.org/courses/intermediate-logic/il-screen.pdf |access-date=21 March 2022}}</ref> Suppose there is a formula {{mvar|A}} which is true in all and only models with finite domains. We can express, for any positive integer {{mvar|n}}, the sentence "there are at least {{mvar|n}} elements in the domain". For a given {{mvar|n}}, call the formula expressing that there are at least {{mvar|n}} elements {{mvar|B<sub>n</sub>}}. For example, the formula {{mvar|B<sub>3</sub>}} is:
<math display="block">\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 display="block">A, B_2, B_3, B_4, \ldots</math>
Every finite subset of these formulae has a model: given a subset, find the greatest {{mvar|n}} for which the formula {{mvar|B<sub>n</sub>}} is in the subset. Then a model with a domain containing {{mvar|n}} elements will satisfy {{mvar|A}} (because the domain is finite) and all the {{mvar|B}} formulae in the subset. Applying the compactness theorem, the entire infinite set must also have a model. Because of what we assumed about {{mvar|A}}, the model must be finite. However, this model cannot be finite, because if the model has only {{mvar|m}} elements, it does not satisfy the formula {{mvar|B<sub>m+1</sub>}}. This contradiction shows that there can be no formula {{mvar|A}} with the property we assumed.

=== Other examples ===
* The concept of [identity](/source/identity_(philosophy)) cannot be defined in first-order languages, merely indiscernibility.<ref>{{Cite SEP |url-id=identity|title=Identity|last=Noonan|first=Harold|last2=Curtis|first2=Ben|date=2014-04-25|section=2 "The Logic of Identity"}}</ref>
* The [Archimedean property](/source/Archimedean_property) that may be used to identify the real numbers among the [real closed field](/source/real_closed_field)s.
* The [compactness theorem](/source/compactness_theorem) implies that [graph connectivity](/source/graph_connectivity) cannot be expressed in first-order logic.{{clarify|date=June 2018}}

== See also ==
* [Definable set](/source/Definable_set)
* [Branching quantifier](/source/Branching_quantifier)
* [Generalized quantifier](/source/Generalized_quantifier)
* [Plural quantification](/source/Plural_quantification)
* [Reification (linguistics)](/source/Reification_(linguistics))

== References ==
{{reflist}}

== External links ==
* [https://terrytao.wordpress.com/2007/08/27/printer-friendly-css-and-nonfirstorderizability Printer-friendly CSS, and nonfirstorderisability by Terence Tao]

Category:Logic

---
Adapted from the Wikipedia article [Nonfirstorderizability](https://en.wikipedia.org/wiki/Nonfirstorderizability) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Nonfirstorderizability?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.