Skolem's paradox
Encyclopedia
In mathematical logic
and philosophy
, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem
. Thoralf Skolem
(1922) was the first to discuss the seemingly contradictory aspects of the theorem, and to discover the relativity of set-theoretic notions now known as non-absoluteness
. Although it is not an actual antinomy
like Russell's paradox
, the result is typically called a paradox
, and was described as a "paradoxical state of affairs" by Skolem (1922: p. 295).
Skolem's paradox is that every countable
axiomatisation of set theory
in first-order logic
, if it is consistent, has a model
that is countable. This appears contradictory because it is possible to prove, from those same axioms, a sentence which intuitively says (or which precisely says in the standard model of the theory) that there exist sets that are not countable. Thus the seeming contradiction is that a model which is itself countable, and which contains only countable sets, satisfies the first order sentence that intuitively states "there are uncountable sets".
A mathematical explanation of the paradox, showing that it is not a contradiction in mathematics, was given by Skolem (1922). Skolem's work was harshly received by Ernst Zermelo
, who argued against the limitations of first-order logic, but the result quickly came to be accepted by the mathematical community.
The philosophical implications of Skolem's paradox have received much study. One line of inquiry questions whether it is accurate to claim that any first-order sentence actually states "there are uncountable sets". This line of thought can be extended to question whether any set is uncountable in an absolute sense. Recently, the paper "Models and Reality" by Hilary Putnam
, and responses to it, led to renewed interest in the philosophical aspects of Skolem's result.
, published by Georg Cantor
in 1874, was the existence of uncountable sets, such as the powerset of the natural numbers, the set of real numbers, and the Cantor set
. An infinite set X is countable if there is a function that gives a one-to-one correspondence between X and the natural numbers, and is uncountable if there is no such correspondence function. When Zermelo proposed his axioms for set theory in 1908, he proved Cantor's theorem
from them to demonstrate their strength.
Löwenheim (1915) and Skolem (1920, 1923) proved the Löwenheim–Skolem theorem
. The downward form of this theorem shows that if a countable
first-order
axiomatisation is satisfied by any infinite structure
, then the same axioms are satisfied by some countable structure. In particular, this implies that if the first order versions of Zermelo's axioms of set theory are satisfiable, they are satisfiable in some countable model. The same is true of any consistent first order axiomatisation of set theory.
More specifically, let B be a countable model of Zermelo's axioms. Then there is some set u in B such that B satisfies the first-order formula saying that u is uncountable. For example, u could be taken as the set of real numbers in B. Now, because B is countable, there are only countably many elements c such that c ∈ u according to B, because there are only countably many elements c in B to begin with. Thus it appears that u should be countable. This is Skolem's paradox.
Skolem went on to explain why there was no contradiction. In the context of a specific model of set theory, the term "set" does not refer to an arbitrary set, but only to a set that is actually included in the model. The definition of countability requires that a certain one-to-one correspondence, which is itself a set, must exist. Thus it is possible to recognize that a particular set u is countable, but not countable in a particular model of set theory, because there is no set in the model that gives a one-to-one correspondence between u and the natural numbers in that model.
Skolem used the term "relative" to describe this state of affairs, where the same set is included in two models of set theory, is countable in one model, and is not countable in the other model. He described this as the "most important" result in his paper. Contemporary set theorists describe concepts that do not depend on the choice of a transitive model as absolute
. From their point of view, Skolem's paradox simply shows that countability is not an absolute property in first order logic. (Kunen 1980 p. 141; Enderton 2001 p. 152; Burgess 1977 p. 406).
Skolem described his work as a critique of (first-order) set theory, intended to illustrate its weakness as a foundational system:
, meaning that the axioms would have exactly one model, consisting of all sets. Skolem's result showed this is not possible, creating doubts about the use of set theory as a foundation of mathematics. It took some time for the theory of first-order logic to be developed enough for mathematicians to understand the cause of Skolem's result; no resolution of the paradox was widely accepted during the 1920s. Fraenkel (1928) still described the result as an antinomy:
In 1925, von Neumann presented a novel axiomatization of set theory, which developed into NBG set theory. Very much aware of Skolem's 1922 paper, von Neumann investigated countable models of his axioms in detail. In his concluding remarks, Von Neumann comments that there is no categorical axiomatization of set theory, or any other theory with an infinite model. Speaking of the impact of Skolem's paradox, he wrote,
Zermelo at first considered the Skolem paradox a hoax (van Dalen and Ebbinghaus, 2000, p. 148 ff.), and spoke against it starting in 1929. Skolem's result applies only to what is now called first-order logic
, but Zermelo argued against the finitary
metamathematics
that underlie first-order logic (Kanamori 2004, p. 519 ff.). Zermelo argued that his axioms should instead be studied in second-order logic
, a setting in which Skolem's result does not apply. Zermelo published a second-order axiomatization in 1930 and proved several categoricity results in that context. Zermelo's further work on the foundations of set theory after Skolem's paper led to his discovery of the cumulative hierarchy and formalization of infinitary logic
(van Dalen and Ebbinghaus, 2000, note 11).
Fraenkel et al. (1973, pp. 303–304) explain why Skolem's result was so surprising to set theorists in the 1920s. At the time, Gödel's completeness theorem
and the compactness theorem
had not yet been proved. These theorems illuminated the way that first-order logic behaves and established its finitary nature. The method of Henkin models, now a standard technique for constructing countable models of a consistent first-order theory, was not developed until 1950. Thus, in 1922, the particular properties of first-order logic that permit Skolem's paradox to go through were not yet understood. It is now known that Skolem's paradox is unique to first-order logic; if set theory is formalized using higher-order logic
then it does not have any countable models.
first-order axioms is complete.
Countable models of ZF have become common tools in the study of set theory. Forcing, for example, is often explained in terms of countable models. The fact that these countable models of ZF still satisfy the theorem that there are uncountable sets is not considered a pathology; van Heijenoort (1967) describes it as "a novel and unexpected feature of formal systems." (van Heijenoort 1967, p. 290)
Although mathematicians no longer consider Skolem's result paradoxical, the result is often discussed by philosophers. In the setting of philosophy, a merely mathematical resolution of the paradox may be less than satisfactory.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
and philosophy
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
. Thoralf Skolem
Thoralf Skolem
Thoralf Albert Skolem was a Norwegian mathematician known mainly for his work on mathematical logic and set theory.-Life:...
(1922) was the first to discuss the seemingly contradictory aspects of the theorem, and to discover the relativity of set-theoretic notions now known as non-absoluteness
Absoluteness (mathematical logic)
In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures . Theorems about absoluteness typically establish relationships between the absoluteness of formulas and their syntactic form.There are two weaker forms of partial absoluteness...
. Although it is not an actual antinomy
Antinomy
Antinomy literally means the mutual incompatibility, real or apparent, of two laws. It is a term used in logic and epistemology....
like Russell's paradox
Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
, the result is typically called a paradox
Paradox
Similar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
, and was described as a "paradoxical state of affairs" by Skolem (1922: p. 295).
Skolem's paradox is that every countable
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
axiomatisation of set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
in first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, if it is consistent, has a model
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
that is countable. This appears contradictory because it is possible to prove, from those same axioms, a sentence which intuitively says (or which precisely says in the standard model of the theory) that there exist sets that are not countable. Thus the seeming contradiction is that a model which is itself countable, and which contains only countable sets, satisfies the first order sentence that intuitively states "there are uncountable sets".
A mathematical explanation of the paradox, showing that it is not a contradiction in mathematics, was given by Skolem (1922). Skolem's work was harshly received by Ernst Zermelo
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...
, who argued against the limitations of first-order logic, but the result quickly came to be accepted by the mathematical community.
The philosophical implications of Skolem's paradox have received much study. One line of inquiry questions whether it is accurate to claim that any first-order sentence actually states "there are uncountable sets". This line of thought can be extended to question whether any set is uncountable in an absolute sense. Recently, the paper "Models and Reality" by Hilary Putnam
Hilary Putnam
Hilary Whitehall Putnam is an American philosopher, mathematician and computer scientist, who has been a central figure in analytic philosophy since the 1960s, especially in philosophy of mind, philosophy of language, philosophy of mathematics, and philosophy of science...
, and responses to it, led to renewed interest in the philosophical aspects of Skolem's result.
Background
One of the earliest results in set theorySet theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, published by Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
in 1874, was the existence of uncountable sets, such as the powerset of the natural numbers, the set of real numbers, and the Cantor set
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of remarkable and deep properties. It was discovered in 1875 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883....
. An infinite set X is countable if there is a function that gives a one-to-one correspondence between X and the natural numbers, and is uncountable if there is no such correspondence function. When Zermelo proposed his axioms for set theory in 1908, he proved Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
from them to demonstrate their strength.
Löwenheim (1915) and Skolem (1920, 1923) proved the Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
. The downward form of this theorem shows that if a countable
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
first-order
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
axiomatisation is satisfied by any infinite structure
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
, then the same axioms are satisfied by some countable structure. In particular, this implies that if the first order versions of Zermelo's axioms of set theory are satisfiable, they are satisfiable in some countable model. The same is true of any consistent first order axiomatisation of set theory.
The paradoxical result and its mathematical implications
Skolem (1922) pointed out the seeming contradiction between the Löwenheim–Skolem theorem on the one hand, which implies that there is a countable model of Zermelo's axioms, and Cantor's theorem on the other hand, which states that uncountable sets exist, and which is provable from Zermelo's axioms. "So far as I know," Skolem writes, "no one has called attention to this paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities... How can it be, then, that the entire domain B [a countable model of Zermelo's axioms] can already be enumerated by means of finite positive integers?" (Skolem 1922, p. 295, translation by Bauer-Mengelberg)More specifically, let B be a countable model of Zermelo's axioms. Then there is some set u in B such that B satisfies the first-order formula saying that u is uncountable. For example, u could be taken as the set of real numbers in B. Now, because B is countable, there are only countably many elements c such that c ∈ u according to B, because there are only countably many elements c in B to begin with. Thus it appears that u should be countable. This is Skolem's paradox.
Skolem went on to explain why there was no contradiction. In the context of a specific model of set theory, the term "set" does not refer to an arbitrary set, but only to a set that is actually included in the model. The definition of countability requires that a certain one-to-one correspondence, which is itself a set, must exist. Thus it is possible to recognize that a particular set u is countable, but not countable in a particular model of set theory, because there is no set in the model that gives a one-to-one correspondence between u and the natural numbers in that model.
Skolem used the term "relative" to describe this state of affairs, where the same set is included in two models of set theory, is countable in one model, and is not countable in the other model. He described this as the "most important" result in his paper. Contemporary set theorists describe concepts that do not depend on the choice of a transitive model as absolute
Absoluteness (mathematical logic)
In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures . Theorems about absoluteness typically establish relationships between the absoluteness of formulas and their syntactic form.There are two weaker forms of partial absoluteness...
. From their point of view, Skolem's paradox simply shows that countability is not an absolute property in first order logic. (Kunen 1980 p. 141; Enderton 2001 p. 152; Burgess 1977 p. 406).
Skolem described his work as a critique of (first-order) set theory, intended to illustrate its weakness as a foundational system:
- "I believed that it was so clear that axiomatization in terms of sets was not a satisfactory ultimate foundation of mathematics that mathematicians would, for the most part, not be very much concerned with it. But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come for a critique." (Ebbinghaus and van Dalen, 2000, p. 147)
Reception by the mathematical community
A central goal of early research into set theory was to find a first order axiomatisation for set theory which was categoricalMorley's categoricity theorem
In model theory, a branch of mathematical logic, a theory is κ-categorical if it has exactly one model of cardinality κ up to isomorphism....
, meaning that the axioms would have exactly one model, consisting of all sets. Skolem's result showed this is not possible, creating doubts about the use of set theory as a foundation of mathematics. It took some time for the theory of first-order logic to be developed enough for mathematicians to understand the cause of Skolem's result; no resolution of the paradox was widely accepted during the 1920s. Fraenkel (1928) still described the result as an antinomy:
- "Neither have the books yet been closed on the antinomy, nor has agreement on its significance and possible solution yet been reached." (van Dalen and Ebbinghaus, 2000, p. 147).
In 1925, von Neumann presented a novel axiomatization of set theory, which developed into NBG set theory. Very much aware of Skolem's 1922 paper, von Neumann investigated countable models of his axioms in detail. In his concluding remarks, Von Neumann comments that there is no categorical axiomatization of set theory, or any other theory with an infinite model. Speaking of the impact of Skolem's paradox, he wrote,
- "At present we can do no more than note that we have one more reason here to entertain reservations about set theory and that for the time being no way of rehabilitating this theory is known."(Ebbinghaus and van Dalen, 2000, p. 148)
Zermelo at first considered the Skolem paradox a hoax (van Dalen and Ebbinghaus, 2000, p. 148 ff.), and spoke against it starting in 1929. Skolem's result applies only to what is now called first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, but Zermelo argued against the finitary
Finitism
In the philosophy of mathematics, one of the varieties of finitism is an extreme form of constructivism, according to which a mathematical object does not exist unless it can be constructed from natural numbers in a finite number of steps...
metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
that underlie first-order logic (Kanamori 2004, p. 519 ff.). Zermelo argued that his axioms should instead be studied in second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
, a setting in which Skolem's result does not apply. Zermelo published a second-order axiomatization in 1930 and proved several categoricity results in that context. Zermelo's further work on the foundations of set theory after Skolem's paper led to his discovery of the cumulative hierarchy and formalization of infinitary logic
Infinitary logic
An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs. Some infinitary logics may have different properties from those of standard first-order logic. In particular, infinitary logics may fail to be compact or complete. Notions of compactness and...
(van Dalen and Ebbinghaus, 2000, note 11).
Fraenkel et al. (1973, pp. 303–304) explain why Skolem's result was so surprising to set theorists in the 1920s. At the time, Gödel's completeness theorem
Gödel's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. It was first proved by Kurt Gödel in 1929....
and the compactness theorem
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
had not yet been proved. These theorems illuminated the way that first-order logic behaves and established its finitary nature. The method of Henkin models, now a standard technique for constructing countable models of a consistent first-order theory, was not developed until 1950. Thus, in 1922, the particular properties of first-order logic that permit Skolem's paradox to go through were not yet understood. It is now known that Skolem's paradox is unique to first-order logic; if set theory is formalized using higher-order logic
Higher-order logic
In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and a stronger semantics...
then it does not have any countable models.
Contemporary mathematical opinion
Contemporary mathematical logicians do not view Skolem's paradox as any sort of fatal flaw in set theory. Kleene (1967, p. 324) describes the result as "not a paradox in the sense of outright contradiction, but rather a kind of anomaly". After surveying Skolem's argument that the result is not contradictory, Kleene concludes "there is no absolute notion of countability." Hunter (1971, p. 208) describes the contradiction as "hardly even a paradox". Fraenkel et al. (1973, p. 304) explain that contemporary mathematicians are no more bothered by the lack of categoricity of first-order theories than they are bothered by the conclusion of Gödel's incompleteness theorem that no consistent, effective, and sufficiently strong set offirst-order axioms is complete.
Countable models of ZF have become common tools in the study of set theory. Forcing, for example, is often explained in terms of countable models. The fact that these countable models of ZF still satisfy the theorem that there are uncountable sets is not considered a pathology; van Heijenoort (1967) describes it as "a novel and unexpected feature of formal systems." (van Heijenoort 1967, p. 290)
Although mathematicians no longer consider Skolem's result paradoxical, the result is often discussed by philosophers. In the setting of philosophy, a merely mathematical resolution of the paradox may be less than satisfactory.