Löwenheim–Skolem theorem
From Wikipedia, the free encyclopedia
In mathematical logic, the classic Löwenheim–Skolem theorem states that for any countable first-order language L with signature 
and L-structure M, there exists a countably infinite elementary substructure N 
M. A natural and useful corollary of this theorem is that every consistent L-theory has a countable model.
Here, a signature consists of a set of constants 
, functions 
, relation symbols 
, and a function 
representing the arity of function and relation symbols. An L-structure, in this context, consists of an underlying set (often also denoted "M") and an interpretation of the constant, function, and relation symbols of L. An interpretation of the constant symbols of L in M is simply a function 
. Similarly, an interpretation of a σ(f)-ary function 
is an assignment to the graph of an σ(f)-ary function 
in M while an interpretation of a relation 
is an assignment to a σ(R)-ary relation in M. The language L is countable if the set of constant, function, and relation symbols in L is countable.
The theorem is named for Leopold Löwenheim and Thoralf Skolem.
Contents |
[edit] 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.
[edit] A terse sketch of the proof
For every first-order sentence of the form
or
that is true in the model M, there is a Skolem function f, i.e., a function that maps the x to the y whose existence is asserted, so that
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.
Some members of the model can be directly defined by first-order formulas, that is, their existence is asserted by sentences of the form
and since there are only countably many first-order formulas, only countably many members can be directly defined in this way.
Here is the idea of the proof: Start with the set of all first-order-definable members of the model, and then close it 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.
[edit] 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 ("downward" Löwenheim-Skolem theorems); others assert the existence of models of larger cardinality ("upward" Löwenheim-Skolem theorems).
[edit] References
- Wilfrid Hodges (1997), "A Shorter Model Theory", Cambridge University Press, ISBN 0521587131
- María Manzano (1999), "Model Theory", Oxford University Press, ISBN 0198538510
- Rothmaler, Philipp (2000), "Introduction To Model Theory", CRC
