|
|
In mathematical logic, the classic Löwenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. A model, in this context, consists of an underlying set (often also denoted) "M", a set of relations on this set M, and a set of functions (sometimes taking several arguments) from M into itself. The theorem is named for Leopold Löwenheim and Thoralf Skolem.
| Contents |
Examples
A familiar uncountable model is the set of all real numbers with the order relation "<" as the sole relation and addition and multiplication as the functions. The axioms of ordered fields are first-order sentences; the least-upper-bound axiom is not first-order, but second-order. The theorem implies that some subfield of the reals that is countably infinite, and hence distinct from the reals, satisfies all first-order sentences satisfied by the reals. (Being a countable ordered field, it cannot satisfy the least-upper-bound axiom.) For example, the assertion that a particular polynomial equation has a solution (in the model) is a first-order sentence and therefore would be true in the countable submodel whose existence is asserted if and only if it is true in the reals.
Most mathematical structures, in particular most members of most categories that mathematicians consider, are models in the sense defined here. The Löwenheim-Skolem theorem tells us that if they are uncountable, they are not uniquely picked out by any set of first-order sentences.
A terse sketch of the proof
For every first-order sentence of the form
- <math>\forall x\ \exists y\ R(x,y)<math>
or
- <math>\forall x_1\ \cdots\ \forall x_n\ \exists y_1\ \cdots\ \exists y_m R(x_1,\dots,x_n,y_1,\dots,y_n)<math>
that is true in the model M, there is a Skolem function g, i.e., a function that maps the x to the y whose existence is asserted, so that
- <math>\forall x\ R(x,g(x))<math>
is true in M. Since there may be many such values of y, the axiom of choice must be invoked in order to infer the existence of the Skolem function.
Only countably many members of the model can be definable by first-order formulas.
[The claim above would bear elaboration!]
Here is the idea of the proof: Start with the set of all first-order-definable members of the model, and close under all Skolem functions. The closure must be at most countably infinite. That subset of the model is the submodel whose existence the theorem asserts.
More general "Löwenheim-Skolem theorems"
The theorem above assumes finite or countably infinite language. More general Löwenheim-Skolem theorems make other assumptions about cardinality. Some, like this classic one, assert the existence of smaller submodels; others assert the existence of models of larger cardinality.