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 \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) 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 \lor x = y + 1 ) for
Axy. This expresses that the two terms are successors of one another, in some way. The resulting proposition, \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) states that there is a set with the following three properties: • There is a number that does not belong to , i.e. does
not contain all numbers. • The set is inhabited, and here this indeed immediately means there are at least two numbers in it. • If a number belongs to and if is either or , then also belongs to . 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 \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 exists in first-order logic.
Finiteness of the domain 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. 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: \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 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.
Other examples • The concept of
identity cannot be defined in first-order languages, merely indiscernibility. • 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. == See also ==