State the Löwenheim-Skolem Theorem. Give some examples indicating how it is used

Question

State the Löwenheim-Skolem Theorem. Give some examples indicating how it is used, in both the

Explanation / Answer

Precise statement The modern statement of the theorem is both more general and stronger than the version for countable signatures stated in the introduction. In its general form, the Löwenheim–Skolem Theorem states that for every signature s, every infinite s-structure M and every infinite cardinal number ? = |s| there is a s-structure N such that |N| = ? and * if ? < |M| then N is an elementary substructure of M; * if ? > |M| then N is an elementary extension of M. The theorem is often divided into two parts corresponding to the two bullets 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. 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. For historical variants of the theorem, see the notes below. [edit] Examples and consequences 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, the completeness of a linear order, which is used to characterize the real numbers as a complete ordered field, is a non-first-order property. A theory is called categorical if it has only one model, up to isomorphism. This term was introduced by Oswald Veblen in 1904, 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. 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. This counterintuitive situation came to be known as Skolem's paradox; it shows that the notion of countability is not absolute.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.