Notes to Skolem's Paradox

1. This is probably the place to highlight some notational conventions. Throughout this entry, we will let =, ¬, →, and ∃ constitute the official first-order logical vocabulary, and we will treat ∧, ∨, ↔, and ∀ as abbreviations. (We will make free use of these abbreviations wherever they seem to improve readability.) Unless otherwise noted, we work in the language of first-order set theory—i.e., the language which has “∈” as its sole non-logical primitive. We say that a formula is in this language when it is built up from ∈ together with the standard logical connectives.

Throughout this entry, we will use boldface letters to denote models and the corresponding unbolded letters to denote the domains of those models: so, M is a model and M is its domain, N is a model and N is its domain, etc. That being said, we will often abuse notation and write things like “M is countable” or “m ∈ M” when we really mean that “M is countable” or that “m ∈ M ”; in context, this should never cause any confusion. Finally, unless otherwise specified, all models should be assumed to be for the language of set theory—i.e., as above, the language with ∈ as its sole non-logical primitive.

Unless otherwise noted, we will use ⊨ to denote first-order satisfaction and ⊦ to denote first-order provability. If m is an element of some model M and φ(x) is a formula with only x free, then we will write M ⊨ φ[m] to mean that m lives in the subset of M on which φ(x) comes out true. For more on model-theoretic notation, see the entries on model theory and first-order model theory. For basic set-theoretic notation, see the entry on set theory.

2. We said above that Cantor's conclusion that there are different kinds of infinity may initially seem somewhat surprising. This needs qualification. At first glance, after all, it may seem obvious that some infinite sets are larger than others. If, for instance, we measure the “size” of a set by means of the subset relation—so, A is smaller than B if and only if A is a proper subset of B—then it will be trivial to show that there are different kinds of infinity. On this definition, after all, the set of even numbers is smaller than the set of natural numbers, the set of natural numbers is smaller than the set of integers, and the set of integers is smaller than the set of rational numbers. It is only after we filter our whole analysis through Cantor's new definition of cardinality—and so discover that the whole sequence of even numbers, natural numbers, integers, rational numbers, etc. consists of sets of the same size—that we begin to suspect that all infinite sets should have the same size, that, one way or another, by hook or by crook, we should be able to conjure up a bijection between any two infinite sets. It's against this backdrop that Cantor's Theorem starts to look somewhat surprising.

3. This isn't the way Löwenheim himself would have formulated the theorem, but it's the most perspicuous formulation for our purposes. For a detailed discussion of Löwenheim's own formulation and proof, see Badesa 2004.

4. For a comprehensive survey of the mathematics surrounding the Löwenheim-Skolem Theorems, see Ebbinghaus 2007.

5. This theorem is originally due to Tarski. It gets its name from the fact that it allows us to start with a countable model of T and then generate models of arbitrarily large cardinality.

6. This theorem is, once again, due to Tarski. It's called the downward theorem because it allows us to start with a large model and then generate a (smaller) submodel. Two further notes are in order here. First, in saying that our new model, N, is a submodel of our original model, M, we mean the domain of N is a subset of the domain of M and that the two models agree on the interpretation of the constants, predicates, relations and functions in our language—e.g., for any n₁, … , n_m in the domain of N and any R in our language, N ⊨ R[n₁, … , n_m ] ⇔ M ⊨ R[n₁, … , n_m ]. Second, as it's stated above, the downward theorem depends upon the assumption that our language is countable. (If our language isn't countable, then we would need the additional assumption that λ is at least as large as the size of our language.) For expository convenience, the remainder of this entry will limit itself to the case of countable languages—so, from here on out “language”=“countable language.”

7. This final result is due to Mostowski. For a definition of transitivity—and a discussion of its philosophical significance in the context of Skolem's Paradox—see section 2.3.

8. We should note, here, that the initial assumption that our axioms have any model is non-trivial—after all, the second incompleteness theorem ensures that we can't prove the existence of such models from within our axiomatization. What's more, some of the results we'll examine later in this entry involve even stronger model-existence assumptions—e.g., the existence of a transitive model for our axioms is strictly stronger than the mere existence of a model for our axioms. Now, having highlighted these kinds of worries here, we will to suppress them for the remainder of this entry (so, from here on out, we simply assume that our axioms have models, transitive models, etc.). For a more-detailed discussion of the philosophical issues raised by the possible non-existence of such models, see Bays 2007b. For more-technical information on the strength of various model-existence assumptions see Ebbinghaus 2007 and section 1 of Bays 2007a.

9. Some care is needed here. There are many ways of understanding what it is for a model to “capture” a set-theoretic notion; on some of them, even finite cardinality notions can't be nicely captured. For now, the important point is just that there is a way of understanding what it is for a model to “capture” a set-theoretic notion on which finite cardinality notions can be captured but the countable/uncountable distinction cannot. See section 3.1 for a detailed discussion of the relevant distinctions.

10. In particular, let φ_n(x) be the formula which says that x has at least n members (for n a natural number). Then for any model, M, and any element, m ∈ M,

∀x (M ⊨  φ_n[m]) ⇔ {m′ ∈ M | M ⊨ m′ ∈ m } is infinite.

So, we can use the whole set of φ_n's to capture the notion “x has infinitely many members.”

11. Any model which gets membership right will have to have a well-founded membership relation. Hence, it will also get the structure of the natural numbers right. So, the usual formulation of “x is finite” will pick out all and only those sets which have finitely many members in M—i.e., those m ∈ M such that {m′ ∈ M  | M ⊨ m′ ∈ m } is finite.

12. The introduction is to a reprinting of the paper in van Heijenoort 1967. See pp. 290–291.

13. So, Ω(x) is an open formula with x as its only free variable, and Ω[mˆ] is the result of evaluating this formula in M under the assumption that x designates mˆ (see footnote 1).

14. So, “¬” means not, “∨” means or, “∧” means and, etc.

15. As before, Ω(x) is an open formula with x as its only free variable; Ω(m) is the result of replacing the free instances of x with a name for m. In particular, then, Ω(mˆ) is obtained by replacing the relevant instances of x with a name for mˆ.

16. Recall, here, that a bijection between the sets x and y is just a one-to-one correspondence between the members of x and the members of y. As we saw in section 1, to say that x is countable is just to say there exists such a bijection between x and the natural numbers; to say that x is uncountable is to say that there are no such bijections.

17. We should note, here, that there are many different ways of explicating the notion “x is uncountable,” depending on how we decide to “code up” basic notions like ordered pair or natural number. The above discussion assumes that our set theorist has made the same decisions that we made when we originally formulated Ω(x). Since any particular formulation of Ω(x) corresponds to some such explication, this assumption involves no loss of generality.

18. More generally, for any two objects a and b, we can find a countable model M such that 1.) M ⊨ ZFC and 2.) a and b are elements of M such that M ⊨ a ∈ b. For more details on this construction, see section 2 of Bays 2007a.

19. Again, see section 2 of Bays 2007a for further details on these constructions.

20. Recall that these are precisely the bijections which prove that the set {m′ | M ⊨ m′ ∈ m } is countable; hence, they are bijections which, for one reason or another, M fails to properly appreciate (see section 2.3 for one way that this might happen; see sections 3-5 of Bays 2007a for more details and for other possibilities).

21. Actually, we get something a bit stronger than this. If m₂ ∈ M, then for any set m₁,  m₁ ∈ m₂  ⇔ M ⊨ m₁ ∈ m₂. So, we don't need the initial assumption that m₁ ∈ M. In particular, then, for any m ∈ M,   m = { m′ ∈ M  | M ⊨ m′ ∈ m }. So, transitive models not only get membership right, they also completely capture the notion “x is a member of m” where m itself is an element of the relevant model.

22. Here, the expression “f : ω → m is a bijection” is a (natural) abbreviation for a much longer formula in the language of formal set theory. The relationship between this formula and the ordinary English expression “f : ω → m is a bijection” is similar to that between Ω(x) and “x is uncountable.” Note also that because M is transitive, m = { m′ ∈ M  | M ⊨ m′ ∈ m }. So there's no difference between saying that “f : ω → { m′ ∈ M  | M ⊨ m′ ∈ m } is a bijection” and saying that “f : ω → m is a bijection.” For convenience, therefore, we'll use the latter notation throughout the rest of this example.

23. Note, here, that it's only because M is transitive that we can reliably construe the model-theoretic interpretation of Ω(x) as saying anything about bijections at all. (That's the significance of the second point in the last full paragraph.) If M were not transitive, then there would be no general reason for thinking that the model-theoretic interpretation of the portion of Ω(x) which follows the initial existential quantifier has anything much to do with bijections.

24. In formulating this axiom, we've used “⊆” as an abbreviation for a slightly longer expression in the official language of set theory. Since the subset relation is absolute for transitive models—i.e., since transitive models get the relation “x is a subset of y” right—this abbreviation is innocuous.

25. So, if X={1, 2, 3}, then the power set of X is { ∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3} }.

26. For dialectical reasons, Resnik's original argument focused on Wang's System of set theory, rather than on ZFC. But his basic point carries over to the ZFC context, and, for our purposes, it's more perspicuous to discuss it there.

27. As in the power set case, this analysis turns on the way M interprets a particular universal quantifier. Since M is transitive, M gets individual real numbers right: if m ∈ M, then M ⊨ “m is a real number” if and only if m really is a real number. Consider, then, the sentence: ∀x [x ∈ R ↔ “x is a real number”]. On its ordinary English interpretation, this sentence says that R contains all the real numbers. On its model-theoretic interpretation, however, the sentence only says that R contains all the real numbers which happen to live in M, as these are the only real numbers which get “seen” by the initial ∀x quantifier in the sentence.

28. That is, if M is a model for second-order ZFC, then M ⊨ “m has cardinality κ” if and only if the set {m′ ∈ M  | M ⊨ m′ ∈ m } really does have cardinality κ. A similar, though slightly more complicated, fact holds in the power set case. We should note, here, that Zermelo's argument assumes that we're using standard models for second-order logic. The argument fails if we allow the use of first-order Henkin models to interpret the second-order formalism. For more on the difference between standard models and Henkin models, see sections 2 and 3 of the entry on second-order and higher-order logic.

29. More precisely, they prove that all of the usual formulations of the Löwenheim-Skolem theorem are independent of a certain strong form of intuitionistic set theory, and they show that these formulations are also straightforwardly falsified by principles which many constructivists would want to accept. Of course, this doesn't rule out the possibility that some unusual variant of the theorem will turn out to be provable in some non-standard form of “constructivist” set theory; at present, though, that seems an unlikely scenario. See pp 35–36 of their paper for Tennant and McCarty's own thoughts on this matter.

30. By way of example, there's no automatic conflict between a sentence of the form ∃x φ(x) and one of the form ¬∃x [ψ(x) ∧ φ(x) ]. In effect, this point is just a more-formal version of the point about quantification that was made back in section 2.2.

31. In contemporary terms, this is the conception of axioms which underlies much of modern algebra. The axioms of group theory, for instance, characterize what it means for a mathematical structure to count as a group, what it takes for a particular element to be the identity element of a group, and what counts as the inverse of a particular element. But there's no single ur-group which the axioms are trying to describe—there's just a whole class of (equally intended) groups which the axioms serve to characterize.

32. See pp. 295–296 of Skolem 1922 for Skolem's characterization of Zermelo's axioms. We should note that it's an open question whether Skolem has properly understood Zermelo on this matter. In his later writings—including those where he directly responds to Skolem's Paradox—Zermelo clearly employed an algebraic conception of axioms (see, e.g., Zermelo 1930). But it's unclear whether we should read that conception back into the original 1908 axiomatization to which Skolem was responding. See Taylor 1993 and Ebbinghaus 2003 for more on this interpretive issue.

33. Skolem also suggests, though without giving a proof, that the notions finite and simply infinite sequence will also turn out to be relative. In fact, Skolem was right about this, as a simple application of the compactness theorem shows.

34. A similar point applies to the group theory example from footnote 31. Clearly, the particular object which counts as the “identity element” will vary as we move from group to group, as will the range of our quantifiers. But we can still use formulas in our language to capture central group-theoretic notions—e.g., that an element lives in the center of a group or that an element has order 17. And if we expand our language, then we can capture even more notions—e.g., that the predicate “P ” picks out a normal subgroup of the larger group that we are studying. Of course, we can't do this for every group-theoretic notion—there's no formula which exactly captures the notion “x lives in the subgroup generated by y and z.” But the fact that we can't succeed in this case is an interesting mathematical theorem—it's not something which just drops out trivially from the algebraic nature of our axioms. What Skolem has shown, in effect, is that the set-theoretic notion “x is uncountable” is more like the notion “x lives in the subgroup generated by y and z” than like the notion “x has order 17.”

35. This way of putting things may be slightly misleading. Skolem's primary focus in his paper is on Zermelo's 1908 axiomatization of set theory, and Skolem clearly understands this axiomatization algebraically. So, the relativity argument against Zermelo really is the central argument of the paper, even if that argument stands in service of a larger anti-foundationalist project and even if it doesn't lead to more-general arguments for set-theoretic relativity.

36. We should emphasize, here, that this step in the Skolemite argument borders on being an outright theorem. Given a strong enough understanding of the algebraic conception of set theory, and given the right understanding of “relativity,” the conditional claim that the algebraic conception entails some form of set-theoretic relativity just follows from the Löwenheim-Skolem theorems. Those who would object to set-theoretic relativity, therefore, are advised to focus their attention on the Skolemites' initial arguments for the algebraic conception rather than on their subsequent arguments for relativity.

37. Klenk's argument is a little more complicated that this sentence may suggest. Klenk starts by giving a number of arguments in favor of what we're calling the algebraic conception of set theory, and she then notes that any of these arguments would tend to make the Skolemite position look somewhat plausible. But she also notes that an analysis like that given in section 2 will allow a committed realist to evade the Skolmite conclusions. She ends by suggesting that we resolve this stand-off by adopting some kind of formalism about set theory.

38. More formally, suppose that ZFC ⊦ ∃x [φ(x ) ∧ ∀y (φ(y ) → x=y )].

39. In effect, our worry here is that the initial arguments in step 1 do all of the real philosophical work for the Skolemite and that the Löwenheim-Skolem theorems themselves simply tag along for the ride (and, perhaps, play some flag-waving role in promoting the Skolemite argument). As indicated in the main text, we think there's at least a reading of the Skolemite argument which avoids this kind of trivialization and which allows the Löwenheim-Skolem theorems to do some genuine work. That being said, this is a rather delicate argument to put together, and it's not clear that any actual Skolemites have managed to do so successfully.

40. Of course, this also makes step 1 substantially harder for the Skolemite. We suspect that many of the considerations discussed in our initial exposition of step 1—e.g., the grab bag of arguments against “platonism” which appear in so many developments of the Skolemite position—will turn out to be inadequate on this new reading of the argument.

41. To be fair, many presentations of the Skolemite argument look a lot like the simple argument discussed a few paragraphs ago, so this technical response still plays an important role in clarifying the overall dialectic.

42. Of course, some philosophers take a similar line about ZFC. But, in the case of ZFC, it is at least an open question whether this is the right line to take. In the case of group theory or topology, it is the only line which makes any real sense.

43. Recall, once again, that none of these conclusions are forced upon the realist. The realist has a perfectly good explanation as to why these various “instances” are, at best, countable approximations to the real power set of ω or the real set of real numbers. So we're making some pretty big concessions to follow the Skolmite even this far. See section 2.4 for a more-detailed development of this kind of point.

44. We should probably say a bit more about the local context of this argument. Putnam's goal in this section of his paper is to show that indeterminacy of reference leads to an indeterminacy in truth value for sentences like V=L—that, in his words, these sentences “have no determinate truth value … they are just true in some intended models and false in others.” As a result, it doesn't “make sense” to think that “ ‘V=L’ is really false, even though it is consistent with set theory” (p. 5). Now, because Putnam takes himself to be arguing against Gödel—who thought that there was a unique “intended model” of set theory and that V=L was false in that model—Putnam doesn't feel the need to argue for an intended model satisfying V≠L (he assumes that Gödel will grant him the existence of this model). Hence, Putnam thinks that if he can simply find an intended model which satisfies V=L, then he will have finished his argument; in his words, he will have shown that Skolem's famous “ ‘relativity of set-theoretic notions’ extends to a relativity of the truth value of ‘V=L’ ” (p. 8). For more on the mathematics of this example—e.g., for definitions of V and L—see Jech 1978 and Kunen 1980.

45. To put all this in Putnam's terms, let OP be a set of real numbers which codes up all of the measurements which human beings will ever make. Then Putnam writes:

Now, suppose we formalize the entire language of science within the set theory ZF plus V=L. Any model for ZF which contains an abstract set isomorphic to OP can be extended to a model for this formalized language of science which is standard with respect to OP; hence … we can find a model for the entire language of science which satisfies ‘everything is constructible’ and which assigns the correct value to all physical magnitudes. (p. 7)

46. A few more details may be in order here. Let X be countable collection of real numbers. Putnam's proof begins by noting that, in the special case in which we allow our ω-model to be countable, we can code both the model and X by single reals. In this case, therefore, the theorem can be formulated as a Π₂ sentence of the form: (For every real s) (There is a real M ) such that (… M, s …). From here, Putnam argues as follows:

Consider this sentence in the inner model V=L. For every s in the inner model—i.e., for every s in L—there is a model—namely L itself—which satisfies ‘V=L’ and contains s. By the downward Löwenheim-Skolem theorem, there is a countable submodel which is elementarily equivalent to L and contains s. (Strictly speaking, we need here not just the downward Löwenheim-Skolem theorem, but the ‘Skolem Hull’ construction which is used to prove that theorem.) By Gödel's work, this countable submodel itself lies in L, and, as is easily verified, so does the real that codes it. So, the above Π₂ -sentence is true in the inner model V=L.

But Shoenfield has proved that Π₂ -sentences are absolute: if a Π₂ -sentence is true in L, then it must be true in V. So the above sentence is true in V. (p. 6)

For more-detailed discussions of the mathematical side of this argument, see Bays 2001; Bellotti 2005; Bays 2007b; and Hafner 2005. See Jech 1978 and Kunen 1980 for the relevant set-theoretic background (e.g., on L and on Shoenfield absoluteness).

47. Here, an ω-model is just a model which gets the natural numbers right—i.e., a model in which the “natural numbers” of the model are isomorphic to the real natural numbers. Putnam needs the notion of finitute to capture first-order languages, because the sentences of a first-order language can be of arbitrary finite length, but they cannot be infinite. Further the fact that ZFC uses axioms schemes to capture replacement and separation means that we really need the generality here—these schemes can't even be formulated without using the notion of an arbitrary formula. A similar point applies to the way the definition of first-order satisfaction makes use of recursion.

48. This reflects the standard reading of Putnam's argument in the literature (Devitt 1984, chapter 11; Lewis 1984; Taylor 1991; Van Cleve 1992; Hale and Wright 1997). Recently, however, several commentators have challenged this interpretation. They argue that Putnam's “just more theory” talk is merely supposed to highlight the theoretical inadequacy of several particular theories of reference; it's not supposed to provide a general argument of the type sketched above (Anderson 1993; Douven 1999; Haukioja 2001). See Garcia-Carpintero 1996 and Bays 2008 (§ 2) for some critical thoughts on these revisionary interpretations of Putnam's argument.