The Iterative Conception

Source file content/set-theory/story/story.tex

Source file content/set-theory/story/extensionality.tex

Extensionality

The very first thing to say is that sets are individuated by their elements. More precisely:

We assumed this throughout the part on sets, functions, and relations. But it bears repeating. The Axiom of Extensionality expresses the basic idea that a set is determined by its elements. (So sets might be contrasted with concepts, where precisely the same objects might fall under many different concepts.)

Why embrace this principle? Well, it is plausible to say that any denial of Extensionality is a decision to abandon anything which might even be called set theory. Set theory is no more nor less than the theory of extensional collections.

The real challenge in the part on set theory, though, is to lay down principles which tell us which sets exist. And it turns out that the only truly “obvious” answer to this question is provably wrong.

Source file content/set-theory/story/russells-paradox-again.tex

Russell's Paradox (again)

In the part on sets, functions, and relations, we worked with a naïve set theory. But according to a very naïve conception, sets are just the extensions of predicates. This naïve thought would mandate the following principle:

Tempting as this principle is, it is provably inconsistent. We saw this in the section Russell's Paradox, but the result is so important, and so straightforward, that it's worth repeating. Verbatim.

Russell discovered this result in June 1901. (He did not, though, put the paradox in quite the form we just presented it, since he was considering Frege's set theory, as outlined in Grundgesetze. We will return to this in the section on Frege's Basic Law Five.) Russell wrote to Frege on June 16, 1902, explaining the inconsistency in Frege's system. For the correspondence, and a bit of background, see Jean van Heijenoort (1967), pp. 124–8.

It is worth emphasising that this two-line proof is a result of pure logic. Granted, we implicitly used a (non-logical?)\ axiom, Extensionality, in our notation $\Setabs{x}{x \notin x}$source; for $\Setabs{x}{\phi(x)}$source is to be the unique (by Extensionality) set of the $\phi$sources, if one exists. But we can avoid even the hint of Extensionality, just by stating the result as follows: there is no set whose members are exactly the non-self-membered sets. And this has nothing much to do with sets. As Russell himself observed, exactly similar reasoning will lead you to conclude: no man shaves exactly the men who do not shave themselves. Or: no pug sniffs exactly the pugs which don't sniff themselves. And so on. Schematically, the shape of the result is just:

And that's just a theorem (scheme) of first-order logic. Consequently, we can't avoid Russell's Paradox just by tinkering with our set theory; it arises before we even get to set theory. If we're going to use (classical) first-order logic, we simply have to accept that there is no set $R = \Setabs{x}{x\notin x}$source.

The upshot is this. If you want to accept Naïve Comprehension whilst avoiding inconsistency, you cannot just tinker with the set theory. Instead, you would have to overhaul your logic.

Of course, set theories with non-classical logics have been presented. But they are---to say the least---non-standard. The standard approach to Russell's Paradox is to treat it as a straightforward non-existence proof, and then to try to learn how to live with it. That is the approach we will follow.

Source file content/set-theory/story/predicativity.tex

Predicative and Impredicative

The Russell set, $R$source, was defined via $\Setabs{x}{x \notin x}$source. Spelled out more fully, $R$source would be the set which contains all and only those sets which are not non-self-membered. So in defining $R$source, we quantify over the domain which would contain $R$source (if it existed).

This is an impredicative definition. More generally, we might say that a definition is impredicative iff it quantifies over a domain which contains the object that is being defined.

In the wake of the paradoxes, Whitehead, Russell, Poincaré and Weyl rejected such impredicative definitions as “viciously circular”:

If we follow them in rejecting the vicious-circle principle, then we might attempt to replace the disastrous Naïve Comprehension Scheme (of the section Russell's Paradox again) with something like this:

So long as sets$^{\prime}$source are not sets, no contradiction will ensue.

Unfortunately, Predicative Comprehension is not very comprehensive. After all, it introduces us to new entities, sets$^\prime$source. So we will have to consider formulas which quantify over sets$^\prime$source. If they always yield a set$^\prime$source, then Russell's paradox will arise again, just by considering the set$^\prime$source of all non-self-membered sets$^\prime$source. So, pursuing the same thought, we must say that a formula quantifying over sets$^\prime$source yields a corresponding set$^{\prime\prime}$source. And then we will need sets$^{\prime\prime\prime}$source, sets$^{\prime\prime\prime\prime}$source, etc. To prevent a rash of primes, it will be easier to think of these as sets$_0$source, sets$_1$source, sets$_2$source, sets$_3$source, sets$_4$source,ldots. And this would give us a way into the (simple) theory of types.

There are a few obvious objections against such a theory (though it is not obvious that they are overwhelming objections). In brief: the resulting theory is cumbersome to use; it is profligate in postulating different kinds of objects; and it is not clear, in the end, that impredicative definitions are even all that bad.

To bring out the last point, consider this remark from Frank Plumpton Ramsey:

Ramsey's point is that “the tallest man in the group” is an impredicative definition; but it is obviously perfectly kosher.

One might respond that, in this case, we could pick out the tallest person by predicative means. For example, maybe we could just point at the man in question. The objection against impredicative definitions, then, would clearly need to be limited to entities which can only be picked out impredicatively. But even then, we would need to hear more, about why such “essential impredicativity” would be so bad.Footnote: For more, see Øystein Linnebo (2010).

Admittedly, impredicative definitions are extremely bad news, if we want our definitions to provide us with something like a recipe for creating an object. For, given an impredicative definition, one would genuinely be caught in a vicious circle: to create the impredicatively specified object, one would first need to create all the objects (including the impredicatively specified object), since the impredicatively specified object is specified in terms of all the objects; so one would need to create the impredicatively specified object before one had created it itself. But again, this is only a serious objection against “essentially impredicatively” specified sets, if we think of sets as things that we create. And we (probably) don't.

As such---for better or worse---the approach which became common does not involve taking a hard line concerning (im)\-pre\-di\-ca\-tiv\-ity. Rather, it involves what is now regarded as the cumulative-iterative approach. In the end, this will allow us to stratify our sets into “stages”---a bit like the predicative approach stratifies entities into sets$_0$source, sets$_1$source, sets$_2$source, ldots---but we will not postulate any difference in kind between them.

Source file content/set-theory/story/cumulative-approach.tex

The Cumulative-Iterative Approach

Here is a slightly fuller statement of how we will stratify sets into stages:

This is a sketch of the cumulative-iterative conception of set. It will underpin the formal set theory that we present in the part on set theory.

Let's explore this in a little more detail. As Shoenfield describes the process, at every stage, we form new sets from the sets which were available to us from earlier stages. So, on Shoenfield's picture, at the initial stage, stage $0$source, there are no earlier stages, and so a fortiori there are no sets available to us from earlier stages.Footnote: Why should we assume that there is a first stage? See the footnote to stagesord in the section The Story in More Detail. So we form only one set: the set with no elements $\emptyset$source. At stage $1$source, exactly one set is available to us from earlier stages, so only one new set is $\{\emptyset\}$source. At stage $2$source, two sets are available to us from earlier stages, and we form two new sets $\{\{\emptyset\}\}$source and $\{\emptyset, \{\emptyset\}\}$source. At stage $3$source, four sets are available to us from earlier stages, so we form twelve new setsldots. As such, the cumulative-iterative picture of the sets will look a bit like this (with numbers indicating stages):

So: why should we embrace this story?

One reason is that it is a nice, tractable story. Given the demise of the most obvious story, i.e., Naïve Comprehension, we are in want of something nice.

But the story is not just nice. We have a good reason to believe that any set theory based on this story will be consistent. Here is why.

Given the cumulative-iterative conception of set, we form sets at stages; and their elements must be objects which were available already. So, for any stage $S$source, we can form the set

The reasoning involved in proving Russell's Paradox will now establish that $R_S$source itself is not available before stage $S$source. And that's not a contradiction. Moreover, if we embrace the cumulative-iterative conception of set, then we shouldn't even have expected to be able to form the Russell set itself. For that would be the set of all non-self-membered sets that “will ever be available”. In short: the fact that we (provably) can't form the Russell set isn't surprising, given the cumulative-iterative story; it's what we would predict.

Source file content/set-theory/story/urelements.tex

Urelements or Not?

In the next few chapters, we will try to extract axioms from the cumulative-iterative conception of set. But, before going any further, we need to say something more about urelements.

The picture of the section The Cumulative Iterative Approach allowed us only to form new sets from old sets. However, we might want to allow that certain non-sets---cows, pigs, grains of sand, or whatever---can be elements of sets. In that case, we would start with certain basic elements, urelements, and then say that at each stage $S$source we would form “all possible” sets consisting of urelements or sets formed at stages before $S$source (in any combination). The resulting picture would look more like this:

So now we have a decision to take: Should we allow urelements?

Philosophically, it makes sense to include urelements in our theorising. The main reason for this is to make our set theory applicable. To illustrate the point, recall from the chapter The Size of Sets that we say that two sets $A$source and $B$source have the same size, i.e., $\cardeq{A}{B}$source, iff there is a bijection between them. Now, if the cows in the field and the pigs in the sty both form sets, we can offer a set-theoretical treatment of the claim “there are as many cows as pigs”. But if we ban urelements, so that the cows and the pigs do not form sets, then that set-theoretical treatment will be unavailable. Indeed, we will have no straightforward ability to apply set theory to anything other than sets themselves. (For more reasons to include urelements, see Michael Potter 2004, pp. vi, 24, 50–1.)

Mathematically, however, it is quite rare to allow urelements. In part, this is because it is very slightly easier to formulate set theory without urelements. But, occasionally, one finds more interesting justifications for excluding urelement from set theory:

So: a focus on applicability would suggest including urelements; a focus on a reductive foundational goal (reducing mathematics to pure set theory) might suggest excluding them. Mild laziness, too, points in the direction of excluding urelements.

We will follow the laziest path. Partly, though, there is a pedagogical justification. Our aim is to introduce you to the elements of set theory that you would need in order to get started on the philosophy of set theory. And most of that philosophical literature discusses set theories formulated without urelements. So this book will, perhaps, be of more use, if it hews fairly closely to that literature.

Source file content/set-theory/story/grundgesetze.tex

Appendix: Frege's Basic Law V

In the section Russell's Paradox again, we explained that Russell's formulated his paradox as a problem for the system Frege outlined in his Grundgesetze. Frege's system did not include a direct formulation of Naïve Comprehension. So, in this appendix, we will very briefly explain what Frege's system did include, and how it relates to Naïve Comprehension and how it relates to Russell's Paradox.

Frege's system is second-order, and was designed to formulate the notion of an extension of a concept.Footnote: Strictly speaking, Frege attempts to formalize a more general notion: the “value-range” of a function. Extensions of concepts are a special case of the more general notion. See Richard Kimberly Heck (2012), pp. 8–9 for the details. Using notation inspired by Frege, we will write $\fregeext{x}{F(x)}$source for the extension of the concept $F$source. This is a device which takes a predicate, “$F$source”, and turns it into a (first-order) term, “$\fregeext{x}{F(x)}$source”. Using this device, Frege offered the following definition of membership:

roughly: $a \in b$source iff $a$source falls under a concept whose extension is $b$source. (Note that the quantifier “$\exists G$source” is second-order.) Frege also maintained the following principle, known as Basic Law V:

roughly: concepts have identical extensions iff they are coextensive. (Again, both “$F$source” and “$G$source” are in predicate position.) Now a simple principle connects membership with property-satisfaction:

And this yields Naïve Comprehension almost immediately:

Russell's Paradox follows by taking $F$source as given by $\forall x(Fx \liff x \notin x)$source.