A basic elementary class Let σ be a signature consisting only of a
unary function symbol
f. The class
K of σ-structures in which
f is
one-to-one is a basic elementary class. This is witnessed by the theory
T, which consists only of the single sentence :\forall x\forall y( (f(x)=f(y)) \to (x=y) ).
An elementary, basic pseudoelementary class that is not basic elementary Let σ be an arbitrary signature. The class
K of all infinite σ-structures is elementary. To see this, consider the sentences :\rho_2={} "\exist x_1\exist x_2(x_1 \not =x_2)", :\rho_3={} "\exist x_1\exist x_2\exist x_3((x_1 \not =x_2) \land (x_1 \not =x_3) \land (x_2 \not =x_3))", and so on. (So the sentence \rho_n says that there are at least
n elements.) The infinite σ-structures are precisely the models of the theory :T_\infty=\{\rho_2, \rho_3, \rho_4, \dots\}. But
K is not a basic elementary class. Otherwise the infinite σ-structures would be precisely those that satisfy a certain first-order sentence τ. But then the set \{\neg\tau, \rho_2, \rho_3, \rho_4, \dots\} would be inconsistent. By the
compactness theorem, for some natural number
n the set \{\neg\tau, \rho_2, \rho_3, \rho_4, \dots, \rho_n\} would be inconsistent. But this is absurd, because this theory is satisfied by any finite σ-structure with n+1 or more elements. However, there is a basic elementary class
K' in the signature σ' = σ \cup {
f}, where
f is a unary function symbol, such that
K consists exactly of the reducts to σ of σ'-structures in
K'.
K' is axiomatised by the single sentence (\forall x\forall y(f(x) = f(y) \rightarrow x=y) \land \exists y\neg\exists x(y = f(x))),, which expresses that
f is injective but not surjective. Therefore,
K is elementary and what could be called basic pseudo-elementary, but not basic elementary.
Pseudo-elementary class that is non-elementary Finally, consider the signature σ consisting of a single unary relation symbol
P. Every σ-structure is
partitioned into two subsets: Those elements for which
P holds, and the rest. Let
K be the class of all σ-structures for which these two subsets have the same
cardinality, i.e., there is a bijection between them. This class is not elementary, because a σ-structure in which both the set of realisations of
P and its complement are countably infinite satisfies precisely the same first-order sentences as a σ-structure in which one of the sets is countably infinite and the other is uncountable. Now consider the signature \sigma', which consists of
P along with a unary function symbol
f. Let K' be the class of all \sigma'-structures such that
f is a bijection and
P holds for
x iff P does not hold for
f(x). K' is clearly an elementary class, and therefore
K is an example of a pseudo-elementary class that is not elementary.
Non-pseudo-elementary class Let σ be an arbitrary signature. The class
K of all finite σ-structures is not elementary, because (as shown above) its complement is elementary but not basic elementary. Since this is also true for every signature extending σ,
K is not even a pseudo-elementary class. This example demonstrates the limits of expressive power inherent in
first-order logic as opposed to the far more expressive
second-order logic. Second-order logic, however, fails to retain many desirable properties of first-order logic, such as the
completeness and
compactness theorems. == References ==