Skolem's paradox

One of the earliest results in set theory, published by Cantor in 1874, was the existence of different sizes, or cardinalities, of infinite sets. An infinite set X is called 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. In 1874, Cantor proved that the real numbers were uncountable; in 1891, he proved by his diagonal argument the more general result known as Cantor's theorem: for every set S , the power set of S cannot be in bijection with S itself. When Zermelo proposed his axioms for set theory in 1908, he proved Cantor's theorem from them to demonstrate their strength. In 1915, Leopold Löwenheim gave the first proof of what Skolem would prove more generally in 1920 and 1922, the Löwenheim–Skolem theorem.{{sfn|van Heijenoort == The result and its implications ==

In 1922, Skolem pointed out the seeming contradiction between the Löwenheim–Skolem theorem, which implies that there is a countable model of Zermelo's axioms, and Cantor's theorem, which states that uncountable sets exist, and which is provable from Zermelo's axioms. "So far as I know," Skolem wrote, "no one has called attention to this peculiar and apparently 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 the finite positive integers?" However, this is only an apparent paradox. 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 between a set and the natural numbers must exist. This correspondence itself is a set. Skolem resolved the paradox by concluding that such a set does not necessarily exist in a countable model; that is, countability is "relative" to a model, and countable, first-order models are incomplete. Though Skolem gave his result with respect to Zermelo's axioms, it holds for any standard first-order theory of sets, such as ZFC. Consider Cantor's theorem as a long formula in the formal language of ZFC. If ZFC has a model, call this model \mathrm{M} and its domain \mathbb{M}. The interpretation of the element symbol \in , or \mathcal{I} ( \in ), is a set of ordered pairs of elements of \mathbb{M}in other words, \mathcal{I} ( \in ) is a subset of \mathbb{M} \times \mathbb{M}. Since the Löwenheim–Skolem theorem guarantees that \mathbb{M} is countable, then so must be \mathbb{M} \times \mathbb{M}. Two special elements of \mathbb{M} model the natural numbers \mathbb{N} and the power set of the natural numbers \mathcal{P} ( \mathbb{N} ) . There is only a countably infinite set of ordered pairs in \mathcal{I} ( \in ) of the form \langle x , \mathcal{P} ( \mathbb{N} ) \rangle, because \mathbb{M} \times \mathbb{M} is countable. That is, only countably many elements of \mathbb{M} model members of the uncountable set \mathcal{P} ( \mathbb{N} ) . However, there is no contradiction with Cantor's theorem, because what it states is simply that no element of \mathbb{M} models a bijective function from \mathbb{N} to \mathcal{P} ( \mathbb{N} ) . Skolem used the term "relative" to describe when the same set could be countable in one model of set theory and not countable in another: relative to one model, no enumerating function can put some set into correspondence with the natural numbers, but relative to another model, this correspondence may exist. He described this as the "most important" result in his 1922 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. Skolem described his work as a critique of (first-order) set theory, intended to illustrate its weakness as a foundational system: == Reception by the mathematical community ==

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. In 1928, Abraham Fraenkel still described the result as an antinomy: In 1925, John 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 commented 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 Skolem's paradox a hoax, and he spoke against Skolem's "relativism" in 1931. 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, as Zermelo was a mathematical Platonist who opposed intuitionism and finitism in mathematics. Zermelo believed in a kind of infinite Platonic ideal of logic, and he held that mathematics had an inherently infinite character. 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 of set theory in 1930. 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. The surprise with which set theorists met Skolem's paradox in the 1920s was a product of their times. Gödel's completeness theorem and the compactness theorem, theorems which illuminate the way that first-order logic behaves and established its finitary nature, were not first proved until 1929. Leon Henkin's proof of the completeness theorem, which is now a standard technique for constructing countable models of a consistent first-order theory, was not presented until 1947. Thus, in the 1920s, the particular properties of first-order logic that permit Skolem's paradox were not yet understood. It is now known that Skolem's paradox is unique to first-order logic; if set theory is studied using higher-order logic with full semantics, then it does not have any countable models. By the time that Zermelo was writing his final refutation of the paradox in 1937, the community of logicians and set theorists had largely accepted the incompleteness of first-order logic. Zermelo left this refutation unfinished. == Later opinions ==

Later mathematical logicians did not view Skolem's paradox a fatal flaw in set theory. Stephen Cole Kleene described 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 concluded: "there is no absolute notion of countability". Geoffrey Hunter described the contradiction as "hardly even a paradox". Fraenkel et al. claimed 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 of first-order axioms is complete. Other mathematicians such as Reuben Goodstein and Hao Wang have gone so far as to adopt what is called a "Skolemite" view: that not only does the Löwenheim-Skolem theorem prove that set-theoretic notions of countability are relative to a model, but that every set is countable from some "absolute" perspective. L. E. J. Brouwer was another early adherent to the idea of absolute countability, arguing from the vantage of mathematical intuitionism that all sets are countable. Both the Skolemite view and Brouwer's intuitionism stand in opposition to mathematical Platonism, but Carl Posy denies the idea that Brouwer's position was a reaction to earlier set-theoretic paradoxes. Skolem was another mathematical intuitionist, but he denied that his ideas were inspired by Brouwer. Countable models of Zermelo–Fraenkel set theory have become common tools in the study of set theory. Paul Cohen's method for extending set theory, forcing, is often explained in terms of countable models, and was described by Akihiro Kanamori as a kind of extension of Skolem's paradox. The fact that these countable models of Zermelo–Fraenkel set theory still satisfy the theorem that there are uncountable sets is not considered a pathology; Jean van Heijenoort described it as "not a paradox...[but] a novel and unexpected feature of formal systems". Hilary Putnam considered Skolem's result a paradox, but one of the philosophy of language rather than of set theory or formal logic. He extended Skolem's paradox to argue that not only are set-theoretic notions of membership relative, but semantic notions of language are relative: there is no "absolute" model for terms and predicates in language. Timothy Bays argued that Putnam's argument applies the downward Löwenheim-Skolem theorem incorrectly, while Tim Button argued that Putnam's claim stands despite the use or misuse of the Löwenheim-Skolem theorem. Appeals to Skolem's paradox have been made several times in the philosophy of science, with scholars making use of Skolem's idea of the relativity of model structures. ==See also==