Elementary class

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

${\displaystyle \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

${\displaystyle \rho _{2}={}}$ "${\displaystyle \exists x_{1}\exists x_{2}(x_{1}\not =x_{2})}$",

${\displaystyle \rho _{3}={}}$ "${\displaystyle \exists x_{1}\exists x_{2}\exists 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 ${\displaystyle \rho _{n}}$ says that there are at least n elements.) The infinite σ-structures are precisely the models of the theory

${\displaystyle 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 ${\displaystyle \{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots \}}$ would be inconsistent. By the compactness theorem, for some natural number n the set ${\displaystyle \{\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 ${\displaystyle n+1}$ or more elements.

However, there is a basic elementary class K' in the signature σ' = σ ${\displaystyle \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 ${\displaystyle (\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 ${\displaystyle \sigma '}$, which consists of P along with a unary function symbol f. Let ${\displaystyle K'}$ be the class of all ${\displaystyle \sigma '}$-structures such that f is a bijection and P holds for x iff P does not hold for f(x). ${\displaystyle 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.