Löwenheim-Skolem's theorem

The Löwenheim-Skolem theorem says that a countable set of statements of the first order predicate logic that is fulfilled in a model with an uncountably infinitely large universe is always also fulfilled in a model with a countably infinitely large domain.

Explanation and consequences

Some important terms of the sentence are briefly explained: A model represents (in a mathematically describable form) certain circumstances that exist when certain statements are true. One then says that the model fulfills the statements . The domain (also called the individual area or carrier) contains those individuals whose existence is assumed in the model. A set is said to be countably infinite if it is as large as the set of natural numbers . An uncountably infinite set is greater than the set of natural numbers. A set is at least as large as a set if there is an injective function of to . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

In comparison to the theorem of Löwenheim and Skolem, an easy to prove result of model theory says: If a set of statements is fulfilled by a certain infinite model, then it is always also fulfilled by a model with a larger domain. Together with the Löwenheim-Skolem theorem, it follows that a countable set of propositions that has an infinite model at all also always has a model with a countably infinite domain. From the theorem follows u. a. that by means of first-order predicate logic, no infinite structures (especially natural numbers) can be described unambiguously except for isomorphism .

The restriction to the first-level predicate logic is essential; the sentence can not be transferred to the second-level predicate logic.

If a cardinal number is not smaller than the power of the considered consistent set of statements, then this always has a model of power . In particular, there are models of any size. This statement is also often referred to as the Löwenheim-Skolem theorem, sometimes the Löwenheim-Skolem - Tarski theorem . ${\displaystyle \kappa }$ ${\displaystyle \kappa }$

history

The theorem was first proven by Leopold Löwenheim in 1915. Historically, it is the first nontrivial result of model theory.

In 1920 Albert Thoralf Skolem Löwenheim generalized the result. On the one hand, he showed that the set of statements themselves can be countably infinite (while Löwenheim had only proven his theorem for individual statements), on the other hand, he proved that an uncountable domain can always be restricted to a countable subdomain while maintaining the fulfillment relation (For the latter, however, the axiom of choice must be assumed). Skolem makes use of the famous Skolem form in his proof .

In modern representations of logic, the theorem is usually presented as a corollary from the proof of the completeness theorem of predicate logic. At the time of Löwenheim and Skolem, the completeness had not yet been proven, so that they could not build on this result. Conversely, at least Skolem's proof could easily have been transformed into a proof of completeness.

The Skolem Paradox

If one assumes that the Zermelo-Fraenkel set theory is consistent, then every finite axiomatic system from the Zermelo-Fraenkel set theory has a countable model. This follows from the Löwenheim-Skolem theorem and has already been explained above. However, in the Zermelo-Fraenkel set theory a finite axiomatic system can be given, so that the existence of an uncountable set follows. ${\displaystyle \Psi }$

However, the contradiction is resolved when one realizes what countability means in relation to a model. Be a system of . Furthermore, if there is a set that is uncountable in the model , then this means that there is no surjection in this model . The set denotes the set of natural numbers relative to the model . However, this does not mean that the set is uncountable even from the perspective of the metalanguage . ${\displaystyle M}$ ${\displaystyle \Psi }$ ${\displaystyle A\in M}$ ${\displaystyle M}$ ${\displaystyle f\colon {\mathcal {N}}\rightarrow A}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle M}$ ${\displaystyle M}$

Skolem himself saw the result as paradoxical , hence the term Skolem's paradox .

Hilary Putnam's model theory argument

The Löwenheim-Skolem theorem was applied to representational systems in philosophy by the philosopher and logician Hilary Putnam in order to substantiate the following thesis: The assignment of truth in all possible worlds does not fix the reference of linguistic expressions.

Web links

• Timothy Bays:  Skolem's Paradox. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
• Richard Zach, Paolo Mancosu, Calixto Badesa: The Development of Mathematical Logic from Russell to Tarski: 1900-1935. In: Leila Haaparanta (Ed.): The History of Modern Logic. Oxford University Press, New York and Oxford 2009. pp. 178 ff., Ucalgary.ca (English).

Individual evidence

1. ^ Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic. 4th edition. Spectrum Academic Publishing House, Heidelberg u. a. 1996, ISBN 3-8274-0130-5 , Chapter VI, § 2, sentence 2.4.
2. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 , pp. 87 ff .
3. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 , pp. 91 .
4. ^ Hilary Putnam: Reason, Truth and History. Cambridge University Press, Cambridge 1981, ISBN 0-521-23035-7 .
5. ^ Hilary Putnam: Realism and Reason. Cambridge University Press, Cambridge u. a. 1983, ISBN 0-521-24672-5 ( Philosophical Papers 3).