Next: First-order arithmetic
In 1915 Löwenheim gave a nearly complete proof of the fact that if a first-order formula has a model, then it has a finite or countable model. A tidy, correct version of this was given by Skolem in 1922. We will give the more general version for arbitrary sets of formulas and arbitrary languages.
PROOF.
Let
, and
let
be a Skolemization of
.
Then expand
to a model
of
.
Let
be the subset of S generated by the constants and the range of
.
is closed under the operations of
; so let
be the
structure obtained by restricting the functions and relations of
to
. One sees that
, and that
. By reducing back to the original language we have the desired model of
.
A remarkable consequence of this result is the existence of small models of axiomatic first-order set theory (provided any model exists).
This seems to pose an obvious problem, because in such set theories one can prove that the power set of a set has strictly greater cardinality than the set -- but if we have a countable model then all of our sets are countable. This is called Skolem's paradox.
EXERCISES
Next: First-order arithmetic