Steps towards $\Z$source

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

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

The Story in More Detail

In the earlier section on the cumulative iterative approach, we quoted Schoenfield's description of the process of set-formation. We now want to write down a few more principles, to make this story a bit more precise. Here they are:

1. stageshier. Every set is formed at some stage.

2. stagesord. Stages are ordered: some come before others.Footnote: We will actually assume---tacitly---that the stages are well-ordered. What this amounts to is explained in the chapter on ordinals. This is a substantial assumption. In fact, using a very clever technique due to Dana Scott (1974), this assumption can be avoided and then derived. (This will also explain why we should think that there is an initial stage.) We cannot go into that here; for more, see Tim Button (2021).

3. stagesacc. For any stage $S$source, and for any sets which were formed before stage $S$source: a set is formed at stage $S$source whose members are exactly those sets. Nothing else is formed at stage $S$source.

These are informal principles, but we will be able to use them to vindicate several of the axioms of Zermelo's set theory.

(We should offer a word of caution. Although we will be presenting some completely standard axioms, with completely standard names, the italicized principles we have just presented have no particular names in the literature. We simply monikers which we hope are helpful.)

Source file content/set-theory/z/separation.tex

Separation

We start with a principle to replace Naïve Comprehension:

Note that this is not a single axiom. It is a scheme of axioms. There are infinitely many Separation axioms; one for every formula $\phi(x)$source. The scheme can equally well be (and normally is) written down as follows:

In keeping with the convention noted at the start of the Set Theory part, the formulas $\phi$source in the Separation axioms may have parameters.Footnote: For an explanation of what this means, see the discussion immediately after the natural number induction schema.

Separation is immediately justified by our cumulative-iterative conception of sets we have been telling. To see why, let $A$source be a set. So $A$source is formed by some stage $S$source (by stageshier). Since $A$source was formed at stage $S$source, all of $A$source's members were formed before stage $S$source (by stagesacc). Now in particular, consider all the sets which are members of $A$source and which also satisfy $\phi$source; clearly all of these sets, too, were formed before stage $S$source. So they are formed into a set $\Setabs{x \in A}{\phi(x)}$source at stage $S$source too (by stagesacc).

Unlike Naïve Comprehension, this avoid Russell's Paradox. For we cannot simply assert the existence of the set $\Setabs{x}{x \notin x}$source. Rather, given some set $A$source, we can assert the existence of the set $R_A = \Setabs{x \in A}{x \notin x}$source. But all this proves is that $R_A \notin R_A$source and $R_A \notin A$source, none of which is very worrying.

However, Separation has an immediate and striking consequence:

The absence of a universal set---indeed, the open-endedness of the hierarchy of sets---is one of the most fundamental ideas behind the cumulative-iterative conception. So it is worth seeing that, intuitively, we could reach it via a different route. A universal set must be an element of itself. But, on our cumulative-iterative conception, every set appears (for the first time) in the hierarchy at the first stage immediately after all of its elements. But this entails that no set is self-membered. For any self-membered set would have to first occur immediately after the stage at which it first occurred, which is absurd. (We will see in the definition of the rank of a set how to make this explanation more rigorous, by using the notion of the “rank” of a set. However, we will need to have a few more axioms in place to do this.)

Here are a few more consequences of Separation and Extensionality.

It also turns out that (almost) arbitrary intersections exist:

Note the condition that $A \neq \emptyset$source, though; for $\bigcap \emptyset$source would be the universal set, vacuously, contradicting the theorem that there is no universal set.

Source file content/set-theory/z/union.tex

Union

the proposition establishing nonempty intersections gave us intersections. But if we want arbitrary unions to exist, we need to lay down another axiom:

This axiom is also justified by the cumulative-iterative conception. Let $A$source be a set, so $A$source is formed at some stage $S$source (by stageshier). Every member of $A$source was formed before $S$source (by stagesacc); so, reasoning similarly, every member of every member of $A$source was formed before $S$source. Thus all of those sets are available before $S$source, to be formed into a set at $S$source. And that set is just $\bigcup A$source.

Source file content/set-theory/z/pairs.tex

Pairs

The next axiom to consider is the following:

Here is how to justify this axiom, using the iterative conception. Suppose $a$source is available at stage $S$source, and $b$source is available at stage $T$source. Let $M$source be whichever of stages $S$source and $T$source comes later. Then since $a$source and $b$source are both available at stage $M$source, the set $\{a,b\}$source is a possible collection available at any stage after $M$source (whichever is the greater).

But hold on! Why assume that there are any stages after $M$source? If there are none, then our justification will fail. So, to justify Pairs, we will have to add another principle to the story we told in the section giving the iterative story in more detail, namely:

1. stagessucc. There is no last stage.

Is this principle justified? Nothing in Shoenfield's story stated explicitly that there is no last stage. Still, even if it is (strictly speaking) an extra addition to our story, it fits well with the basic idea that sets are formed in stages. We will simply accept it in what follows. And so, we will accept the Axiom of Pairs too.

Armed with this new Axiom, we can prove the existence of plenty more sets. For example:

Source file content/set-theory/z/powerset.tex

Powersets

We will proceed with another axiom:

Our justification for this is pretty straightforward. Suppose $A$source is formed at stage $S$source. Then all of $A$source's members were available before $S$source (by stagesacc). So, reasoning as in our justification for Separation, every subset of $A$source is formed by stage $S$source. So they are all available, to be formed into a single set, at any stage after $S$source. And we know that there is some such stage, since $S$source is not the last stage (by stagessucc). So $\Pow{A}$source exists.

Here is a nice consequence of Powersets:

In this proof, Powerset interacts with Separation. And that is no surprise. Without Separation, Powersets wouldn't be a very powerful principle. After all, Separation tells us which subsets of a set exist, and hence determines just how “fat” each Powerset is.

Source file content/set-theory/z/infinity-again.tex

Infinity

We already have enough axioms to ensure that there are infinitely many sets (if there are any). For suppose some set exists, and so $\emptyset$source exists (by the proposition establishing the empty set). Now for any set $x$source, the set $x \cup \{x\}$source exists by the proposition deriving basic pair constructions. So, applying this a few times, we will get sets as follows:

1. $\emptyset$source

2. $\{\emptyset\}$source

3. $\{\emptyset, \{\emptyset\}\}$source

4. $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$source

5. $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\}$source

and we can check that each of these sets is distinct.

We have started the numbering from $0$source, for a few reasons. But one of them is this. It is not that hard to check that the set we have labelled “$n$source” has exactly $n$source members, and (intuitively) is formed at the $n$sourceth stage.

But. This gives us infinitely many sets, but it does not guarantee that there is an infinite set, i.e., a set with infinitely many members. And this really matters: unless we can find a (Dedekind) infinite set, we cannot construct a Dedekind algebra. But we want a Dedekind algebra, so that we can treat it as the set of natural numbers. (Compare the section on Dedekind's argument for an infinite set.)

Importantly, the axioms we have laid down so far do not guarantee the existence of any infinite set. So we have to lay down a new axiom:

It is easy to see that the set $I$source given to us by the Axiom of Infinity is Dedekind infinite. Its distinguished element is $\emptyset$source, and the injection on $I$source is given by $s(x) = x\cup \{x\}$source. Now, the theorem extracting a Dedekind algebra from a Dedekind-infinite set showed how to extract a Dedekind Algebra from a Dedekind infinite set; and we will treat this as our set of natural numbers. More precisely:

You can now look back and check that the set labelled “$n$source”, a few paragraphs earlier, will be treated as the number $n$source.

We will discuss this significance of this stipulation in the section on selecting the natural numbers. For now, it enables us to prove an intuitive result:

The question remains, though, of how we might justify the Axiom of Infinity. The short answer is that we will need to add another principle to the story we have been telling. That principle is as follows:

1. stagesinf. There is an infinite stage. That is, there is a stage which (a) is not the first stage, and which (b) has some stages before it, but which (c) has no immediate predecessor.

The Axiom of Infinity follows straightforwardly from this principle. We know that natural number $n$source is formed at stage $n$source. So the set $\omega$source is formed at the first infinite stage. And $\omega$source itself witnesses the Axiom of Infinity.

This, however, simply pushes us back to the question of how we might justify stagesinf. As with stagessucc, it was not an explicit part of the story we told about the cumulative-iterative hierarchy. But more than that: nothing in the very idea of an iterative hierarchy, in which sets are formed stage by stage, forces us to think that the process involves an infinite stage. It seems perfectly coherent to think that the stages are ordered like the natural numbers.

This, however, gives rise to an obvious problem. In the section on Dedekind's argument for an infinite set, we considered Dedekind's “proof” that there is a Dedekind infinite set (of thoughts). This may not have struck you as very satisfying. But if stagesinf is not “forced upon us” by the iterative conception of set (or by “the laws of thought”), then we are still left without an intrinsic justification for the claim that there is a Dedekind infinite set.

There is much more to say here, of course. But hopefully you are now at a point to start thinking about what it might take to justify an axiom (or principle). In what follows we will simply take stagesinf for granted.

Source file content/set-theory/z/milestone.tex

$\Z^-$source: a Milestone

We will revisit stagesinf in the next section. However, with the Axiom of Infinity, we have reached an important milestone. We now have all the axioms required for the theory $\Zminus$source. In detail:

The name stands for Zermelo set theory (minus something which we will come to later). Zermelo deserves the honour, since he essentially formulated this theory in his 1908.Footnote: For interesting comments on the history and technicalities, see Michael Potter (2004), Appendix A.

This theory is powerful enough to allow us to do an enormous amount of mathematics. In particular, you should look back through the Sets, Functions, and Relations part, and convince yourself that everything we did, naïvely, could be done more formally within $\Zminus$source. (Once you have done that for a bit, you might want to skip ahead and read the appendix on closure, comprehension, and intersection.) So, henceforth, and without any further comment, we will take ourselves to be working in $\Zminus$source (at least).

Source file content/set-theory/z/nat.tex

Selecting our Natural Numbers

In the definition of omega and the natural numbers, we explicitly defined the expression “natural numbers”. How should you understand this stipulation? It is not a metaphysical claim, but just a decision to treat certain sets as the natural numbers. We touched upon reasons for thinking this in the reflections section on relations, the reflections section on arithmetization and the section on Dedekind's argument for an infinite set. But we can make these reasons even more pointed.

Our Axiom of Infinity follows John von Neumann (1925). But here is another axiom, which we could have adopted instead:

Had we used Zermelo's axiom, instead of our (von Neumann-inspired) Axiom of Infinity, we would equally well have been given a Dedekind infinite set, and so a Dedekind algebra. On Zermelo's approach, the distinguished element of our algebra would again have been $\emptyset$source (our surrogate for $0$source), but the injection would have been given by the map $x \mapsto \{x\}$source, rather than $x \mapsto x \cup \{x\}$source. The simplest upshot of this is that Zermelo treats $2$source as $\{\{\emptyset\}\}$source, whereas we (with von Neumann) treat $2$source as $\{\emptyset, \{\emptyset\}\}$source.

Why choose one axiom of Infinity rather than the other? The main practical reason is that von Neumann's approach “scales up” to handle transfinite numbers rather well. We will explore this from the chapter on ordinals onwards. However, from the simple perspective of doing arithmetic, both approaches would do equally well. So if someone tells you that the natural numbers are sets, the obvious question is: Which sets are they?

This precise question was made famous by Paul Benacerraf (1965). But it is worth emphasising that it is just the most famous example of a phenomenon that we have encountered many times already. The basic point is this. Set theory gives us a way to simulate a bunch of “intuitive” kinds of entities: the reals, rationals, integers, and naturals, yes; but also ordered pairs, functions, and relations. However, set theory never provides us with a unique choice of simulation. There are always alternatives which---straightforwardly---would have served us just as well.

Source file content/set-theory/z/arbintersections.tex

Appendix: Closure, Comprehension, and Intersection

In the section presenting set theory Z minus as a milestone, we suggested that you should look back through the naïve work of the Sets, Functions, and Relations part and check that it can be carried out in $\Zminus$source. If you followed that advice, one point might have tripped you up: the use of intersection in Dedekind's treatment of closures.

Recall from the definition of closure under a function that

But this should ring alarm bells: since Naïve Comprehension fails, there is no guarantee that $\Setabs{X}{\phi(X)}$source exists. It looks dangerously, then, like such definitions are cheating.

Fortunately, they are not cheating; or rather, if they are cheating as they stand, then we can engage in some honest toil to render them kosher. That honest toil was foreshadowed in the proposition establishing nonempty intersections, when we explained why $\bigcap A$source exists for any $A \neq \emptyset$source. But we will spell it out explicitly.

Given Extensionality, if we attempt to define $C$source as $\bigcap\Setabs{X}{\phi(X)}$source, all we are really asking is for an object $C$source which obeys the following:

Now, suppose there is some set, $S$source, such that $\phi(S)$source. Then to deliver the intersection membership condition tagged star, we can simply define $C$source using Separation, as follows:

We leave it as an exercise to check that this definition yields the intersection membership condition tagged star, as desired.

And this general strategy will allow us to circumvent any apparent use of Naïve Comprehension in defining intersections. In the particular case which got us started on this line of thought, namely that of $\closureofunder{f}{o}$source, here is how that would work. We began the proof of the result giving the properties of closure under a function by noting that $o \in \ran{f}\cup\{o\}$source and that $\ran{f} \cup \{o\}$source is $f$source-closed. So, we can define what we want thus: