Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first-order theory has an infinite model, then for every infinite cardinal number "κ" it has a model of size "κ", and that no first-order theory with an infinite model can have a unique model up to isomorphism. As a consequence, first-order theories are unable to control the cardinality of their infinite models. The (downward) Löwenheim–Skolem theorem is  one of the two key properties, along with the compactness theorem, that are used in Lindström's theorem to characterize first-order logic. In general, the Löwenheim–Skolem theorem does not hold in stronger logics such as second-order logic. Theorem. In its general form, the Löwenheim–Skolem Theorem states that for every signature "σ", every infinite "σ"-structure "M" and every infinite cardinal number , there is a "σ"-structure "N" such that and such that The theorem is often divided into two parts corresponding to the two cases above. The part of the theorem asserting that a structure has elementary substructures  of all smaller infinite cardinalities is known as the downward Löwenheim–Skolem Theorem. The part of the theorem asserting that a structure has elementary extensions of all larger cardinalities is known as the upward Löwenheim–Skolem Theorem. Discussion. Below we elaborate on the general concept of signatures and structures. Concepts. Signatures. A signature consists of a set of function symbols "S", a set of relation symbols "S", and a function formula_1 representing the arity of function and relation symbols. (A nullary function symbol is called a constant symbol.) In the context of first-order logic, a signature is sometimes called  a language. It is called countable if the set of function and relation symbols in it is countable, and in general the cardinality of a signature is the cardinality of the set of all the symbols it contains. A first-order theory consists of a fixed signature and a fixed set of sentences (formulas with no free variables) in that signature. Theories are often specified by giving a list of axioms that generate the theory, or by giving a structure and taking the theory to consist of the sentences satisfied by the structure. Structures / Models. Given a signature "σ", a  σ-structure "M" is a concrete interpretation of the symbols in "σ". It consists of an underlying set (often also denoted by ""M"") together with an interpretation of the function and relation symbols of "σ". An interpretation of a constant symbol of "σ" in "M" is simply an element of "M". More generally, an interpretation of an "n"-ary function symbol "f" is a function from "M" to "M". Similarly, an interpretation of a relation symbol "R" is an "n"-ary relation on "M", i.e. a subset of "M". A substructure of a "σ"-structure "M" is obtained by taking a subset "N" of  M which is closed under the interpretations of all the function symbols in "σ" (hence includes the interpretations of all constant symbols in "σ"), and then restricting the interpretations of the relation symbols to "N". An elementary substructure is a very special case of this; in particular an elementary substructure satisfies exactly the same first-order sentences as the original structure (its elementary extension). Consequences. The statement given in the introduction follows immediately by taking "M" to be an infinite model of the theory. The proof of the upward part of the theorem also shows that a theory with arbitrarily  large finite models must have an infinite model; sometimes this is considered to be part of the theorem. A theory is called categorical if it has only one model, up to isomorphism. This term was introduced by , and for some time thereafter mathematicians hoped they could put mathematics on a solid foundation by describing a categorical first-order theory of some version of set theory. The Löwenheim–Skolem theorem dealt a first blow to this hope, as it implies that a first-order theory which has an infinite model cannot be categorical. Later, in 1931, the hope was shattered  completely by Gödel's incompleteness theorem. Many consequences of the Löwenheim–Skolem theorem seemed counterintuitive to logicians in the early 20th century, as the distinction between first-order and non-first-order properties was not yet understood. One such consequence is the existence of uncountable models of true arithmetic, which satisfy every first-order induction axiom but have non-inductive subsets. Let N denote the natural numbers and R the reals. It follows from the theorem that the theory of (N, +, ×, 0, 1) (the theory of true first-order arithmetic) has uncountable models, and that the theory of  (R, +, ×, 0, 1) (the theory of real closed fields) has a countable model. There are, of course, axiomatizations characterizing (N, +, ×, 0, 1) and (R, +, ×, 0, 1) up to isomorphism. The Löwenheim–Skolem theorem shows that these axiomatizations cannot be first-order. For example, in the theory of the real numbers, the completeness of a linear order used to characterize R as a complete ordered field, is a non-first-order property. Another consequence that was considered particularly troubling is the existence of a countable model of set theory, which nevertheless must satisfy the  sentence saying the real numbers are uncountable. Cantor's theorem states that some sets are uncountable. This counterintuitive situation came to be known as Skolem's paradox; it shows that the notion of countability is not absolute. Proof sketch. Downward part. For each first-order formula_2-formula formula_3 the axiom of choice implies the existence of a function such that, for all formula_5, either or Applying the axiom of choice again we get a function from the first-order formulas formula_8 to such functions formula_9 The family of functions formula_10 gives rise to a preclosure operator formula_11 on the power  set of formula_12 for formula_14 Iterating formula_11 countably many times results in a closure operator formula_16 Taking an arbitrary subset formula_17 such that formula_18, and having defined formula_19 one can see that also formula_20 Then formula_21 is an elementary substructure of formula_12 by the Tarski–Vaught test. The trick used in this proof is essentially due to Skolem, who introduced function symbols for the Skolem functions formula_10 into the language. One could also define the formula_10 as partial functions such that formula_10 is defined if and only if formula_26 The only important point is that formula_11 is a preclosure operator  such that formula_28 contains a solution for every formula with parameters in formula_29 which has a solution in formula_12 and that Upward part. First, one extends the signature by adding a new constant symbol for every element of "M". The complete theory of "M" for the extended signature "<nowiki>σ'</nowiki>" is called the "elementary diagram" of "M". In the next step one adds "κ" many new constant symbols to the signature and adds to the elementary diagram of "M" the sentences "c" ≠ "c<nowiki>'</nowiki>" for any two distinct new constant symbols "c" and "c <nowiki>'</nowiki>". Using the compactness theorem, the resulting theory is easily seen to be consistent. Since its models must have cardinality at least "κ", the downward part of this theorem guarantees the existence of a model "N" which has cardinality exactly "κ". It contains an isomorphic copy of "M" as an elementary substructure. In other logics. Although the (classical) Löwenheim–Skolem theorem is tied very closely to first-order logic, variants hold for other logics. For example, every consistent theory in second-order logic has a model smaller than the first supercompact cardinal (assuming one exists). The minimum size  at which a (downward) Löwenheim–Skolem–type theorem applies in a logic is known as the Löwenheim number, and can be used to characterize that logic's strength. Moreover, if we go beyond first-order logic, we must give up one of three things: countable compactness, the downward Löwenheim–Skolem Theorem, or the properties of an abstract logic. Historical notes. This account is based mainly on . To understand the early history of model theory one must distinguish between "syntactical consistency" (no contradiction can be derived using the deduction rules for first-order logic) and "satisfiability" (there is a model). Somewhat  surprisingly, even before the completeness theorem made the distinction unnecessary, the term "consistent" was used sometimes in one sense and sometimes in the other. The first significant result in what later became model theory was "Löwenheim's theorem" in Leopold Löwenheim's publication "Über Möglichkeiten im Relativkalkül" (1915): Löwenheim's paper was actually concerned with the more general Peirce–Schröder "calculus of relatives" (relation algebra with quantifiers). He also used the now antiquated notations of Ernst Schröder. For a summary of the paper in English and using modern notations see . According to the received historical view, Löwenheim's proof  was faulty because it implicitly used Kőnig's lemma without proving it, although the lemma was not yet a published result at the time. In a revisionist account, considers that Löwenheim's proof was complete. It is somewhat ironic that Skolem's name is connected with the upward direction of the theorem as well as with the downward direction: Sources. The Löwenheim–Skolem theorem is treated in all introductory texts on model theory or mathematical logic.