Nonfirstorderizability

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

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 $(\; y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1\; )$ for Axy. This expresses that the two terms are successors of one another, in some way. The resulting proposition,

$$\backslash exists\; X\; \backslash big(\; (\backslash exists\; x\; \backslash neg\; Xx)\; \backslash land\; \backslash exists\; x,y\; (Xx\; \backslash land\; Xy\; \backslash land\; (y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1))\; \backslash land\; \backslash forall\; x\backslash ,\; \backslash forall\; y\; (Xx\; \backslash land\; (y\; =\; x\; +\; 1\; \backslash lor\; x\; =\; y\; +\; 1)\; \backslash rightarrow\; Xy)\backslash big)$$

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, 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 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 $\backslash 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 {{mvar|E}} exists in first-order logic.

There is no formula {{mvar|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.{{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}} 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_n}}. For example, the formula {{mvar|B₃}} 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 {{mvar|n}} for which the formula {{mvar|B_n}} 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_m+1}}. This contradiction shows that there can be no formula {{mvar|A}} with the property we assumed.

• The concept of identity cannot be defined in first-order languages, merely indiscernibility.{{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"}}
• 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.{{clarify|date=June 2018}}

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

{{reflist}}

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

Category:Logic