Upward Löwenheim–Skolem theorem

From Wikipedia, the free encyclopedia

The Upward Löwenheim–Skolem theorem states that for any first-order language L and L-theory T with an infinite model or arbitrary large finite models, T has models of arbitrarily larger cardinalities.

For a fixed language L with cardinality $κ$ , the theorem can be regarded as a special case of the Löwenheim-Skolem theorem which in its most general form asserts the existence of models of any consistent L-theory of arbitrary infinite cardinalities of size at least $κ$ .

[edit] Examples

Let L be the empty language (i.e. language of equality). Then there is no theory that axiomatizes all finite sets because any such theory would have an infinite model by the Upward Löwenheim–Skolem theorem.

[edit] Proof

Let L be a first-order language, T an L-theory with models of arbitrarily large finite cardinalities or an infinite model, and $κ$ an infinite cardinal. Then let C be an infinite set of constants not in L of size $κ$ and let $S = \{c_i \neq c_j| i \neq j; i,j \in \kappa\}$ . Then $T \cup S$ is a collection of L(C)-sentences. Now it is clear that every finite subset of $T \cup S$ is satisfiable since T has models of arbitrarily large finite cardinalities or one of infinite cardinality. Consequently, it follows from the Compactness theorem that $T \cup S$ is consistent. Therefore, by Gödel's completeness theorem, $T \cup S$ has a model. It's L-reduct is then a model of T whose cardinality is greater than or equal to $| C | = κ$ .