## 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*_{1}, … , *n*_{m} in
the domain of **N** and any *R* in our language,
**N**
⊨
*R*[*n*_{1}, … ,
*n*_{m} ] ⇔ **M**
⊨
*R*[*n*_{1},
… , *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*_{2} ∈
**M**, then for *any* set *m*_{1},
*m*_{1} ∈ *m*_{2} ⇔ **M**
⊨ *m*_{1} ∈ *m*_{2}. So, we
don't need the initial assumption that *m*_{1} ∈
**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 formalizethe entire language of sciencewithin the set theory ZFplusV=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 isstandard with respect to OP; hence … we can find a modelfor the entire language of sciencewhich 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 Π_{2} 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 modelV=L. For everys in the inner model—i.e., for everysin L—there is a model—namely L itself—which satisfies ‘V=L’ and containss. By the downward Löwenheim-Skolem theorem, there is a countable submodel which is elementarily equivalent to L and containss. (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 Π_{2}-sentence is true in the inner model V=L.But Shoenfield has proved that Π

_{2}-sentences areabsolute: if a Π_{2}-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.