Why is replacement true in the intuitive hierarchy of sets?

Question

I am currently trying to understand why the axiom (schema) of replacement is true in the intuitive hierarchy of sets. The axiom states that if $F$ is a unary operation and if $x$ is a set, then the set $\{F(y):y\in x\}$ exists.

I have already checked Shoenfield's article "Axioms of set theory". There he describes the notion of set via the idea of a hierarchy: At the bottom (first stage) there are non-set entities (also called atoms), which may for example be natural numbers. At the second stage we can form each set of these atoms. If we take the atoms to be the natural numbers, then we can form each set of natural numbers at this stage. In the third stage it is possible to form each set of objects generated at stages $1$ and $2$. We can go on and imagine stages $4, 5, 6, 7, …$ . In every case, at each stage we can form all sets of objects that lie "lower" in the hierarchy.

The author also adresses the issue "If we have a collection of stages, under which circumstances is there a stage after these stages?". Certainly, there can't be a stage after all stages (Russell paradox). But we can agree on these two principles:

• for each stage there is a stage after it
• and if we have ("countably many") stages $S_1, S_2, S_3, \dots$, then there exists a stage after these stages.

Thus for example there is a stage $\omega$ after the stages $1, 2, 3, 4, 5, \dots$ and a stage $\omega + 1$ after $\omega$ and a stage $\omega + 2$ after $\omega + 1$. One can see that we again get a sequence $\omega, \omega + 1, \omega + 2, \omega + 3, \omega + 4, \dots$ of stages and can conclude there must be a stage $\omega + \omega$ after these. One can proceed in this way and get very many stages.

But in order to justify replacement we need a third principle that tells us when there is a stage after a collection of stages: namely, if we have a set $x$ and for every $y\in x$, a stage $S_y$, and $\mathbf S$ is the collection of all stages $S_y$ where $y\in x$. For me it's hard to imagine why there should be a stage after all stages in $\mathbf S$. Shoenfield tries to explain this as follows:

Suppose that as each stage $S$ is completed, we take each $y$ in $x$ which is formed at $S$ and complete the stage $S_y$. When we reach the stage at which $x$ is formed, we will have formed each $y$ in $x$ and hence completed each stage $S_y$ in $\mathbf S$.

Can you explain this in more detail? Why does this imply that there is a stage after all stages in $\mathbf S$? Can you give examples?

Answer 1

I found an alternative explanation which I find helpful on page 239 of Shoenfield's text book Mathematical logic:

Suppose that we have a set $A$, and that we have assigned a stage $S_a$ to each element $a$ of $A$. Since we can visualize the collection $A$ as a single object (viz., the set $A$), we can also visualize the collection of stages $S_a$ as a single object; so we can visualize a situation in which all these stages are completed. Hence there is to be a stage which follows all of the stages $S_a$. This result is called the principle of cofinality.

Answer 2

Suppose that as each stage $S$ is completed, we take each $y$ in $x$ which is formed at $S$ and complete the stage $S_y$. When we reach the stage at which $x$ is formed, we will have formed each $y$ in $x$ and hence completed each stage $S_y$ in $\mathbf S$.

This is actually a circular justification, and here is why.

Firstly, we ought to be able to label our stages by their ranks. We can do so for computable ordinal ranks, but it is not clear where the labels are going to come from past that point. In other words, the computable ordinals as a whole is a well-defined notion but not a single object that we can use as a label. However, let us temporarily suspend consideration of that issue, since the next one is the more serious circularity.

Secondly, IF it holds that (A) every time you form a stage $S$ you also form stages at all the ranks that were formed in $S$, THEN the quoted argument is basically saying that if you ever manage to form a set $x$, it must have been formed at some stage $k$, at which all members of $x$ must have been formed at some stage prior to $k$, and hence by the big assumption (A) all the stages labelled by a member of $x$ would have already been formed. Thus in stage $(k+1)$ the set $\{ S_y : y \in x \}$ would be formed, since it is a subset of what has been formed by stage $k$.

If the circularity is not clear enough, it is because it is meaningless to say that one can form stages that come after the current formation step at that step itself! The boot-strapping process has to still respect the order of formation to be ontologically meaningful. More precisely, it could be that you can never form the stage with a particular rank $m$, because (A) might require that forming some stage at a rank $r$ lower than $m$ necessitates forming $S_m$ just because $m$ has already been formed in $S_r$, but you obviously cannot...

Instead, for a non-circular ontological justification you would have to do something like the following. First define the ordinals as isomorphism classes of well-orderings. Then we start generating stages using the following rules:

1. If you have generated an ordinal $k$ and you have generated $S_k$, then you can generate $S_{k+1}$.
2. If you have generated an ordinal $k$ and you have generated $S_j$ for every ordinal $j < k$, then you can generate $S_k$.

This scheme generates everything given by your first two principles. However, it fails to generate $S_{ω_1}$, because to get there you would have to generate $S_j$ for all countable ordinals $j$, but we can only generate countably many stages, yet there cannot be a countable enumeration of countable ordinals. Note that this latter fact can be proven without assuming that there is a set of all the countable ordinals, so we actually do know that we cannot get past all the stages with countable rank even if $ω_1$ is not represented by any set (such as if we have a weaker interpretation of the power-set). Furthermore, even if we do have the standard power-set interpretation and so $ω_1$ is represented by a member in $S_{ω+ω}$, we still cannot get past countable-rank stages without already assuming their existence prior to our construction!

I just found a paper by Christopher Menzel that describes on pages 10-11 the same circularity as I point out here, and he cites a number of previous writings on the matter, including a paper by George Boolos that states on page 15 the following (which I rephrased to the language used here and emphasized some points):

There is an extension of the stage theory from which the axioms of replacement could have been derived. We could have taken as axioms all instances of a principle which may be put, 'If each set is correlated with at least one stage (no matter how), then for any set $z$ there is a stage s such that for each member $w$ of $z$, $s$ is later than some stage with which $w$ is correlated'.

This bounding or cofinality principle is an attractive further thought about the interrelation of sets and stages, but it does seem to us to be a further thought, and not one that can be said to have been meant in the rough description of the iterative conception. For that there are exactly $ω_1$ stages does not seem to be excluded by anything said in the rough description; it would seem that $S_{ω_1}$ (see below) is a model for any statement that can (fairly) be said to have been implied by the rough description, and not all of the axioms of replacement hold in $S_{ω_1}$. (*) Thus the axioms of replacement do not seem to us to follow from the iterative conception.

(*) Worse yet, $S_{δ_1}$ would also seem to be such a model. ($δ_1$ is the first uncomputable ordinal.)

This is perfectly in line with my answer, which goes further to explain why we cannot reach the $ω_1$-th stage without already having something much stronger than the iterative conception of the cumulative hierarchy.

Answer 3

My intuition for why (second-order) replacement is true is that the cumulative hierarchy should not stop at some detectable level. If your universe is just barely big enough for some phenomenon to happen in it, then this isn't yet the whole universe. Thus, for example, if we have already created a set $x$ and we have an operation $F$ (outside the hierarchy- that's why this is going to give second-order replacement), then the universe won't be just barely big enough to contain all the values $F(y)$ for $y\in x$. If, for each $y\in x$, there is a set $F(y)$, then the cumulative hierarchy should continue beyond the point where all these $F(y)$'s have become available.

To justify the usual, first-order replacement scheme, I need, in addition to this intuition supporting second-order replacement, the intuition that a first-order formula, with quantification over all sets, is meaningful, so that what I understand for arbitrary operations $F$ can be applied, in particular, to operations defined by first-order formulas.

If I were to doubt the replacement schema, I'd probably doubt the second paragraph above, rather than the first. That is, I'd doubt the meaningfulness of quantification over all sets before I'd doubt the principle that the cumulative hierarchy continues beyond any well-defined stopping point.

Note that my intuition for second-order replacement amounts to a reflection principle, and that reflection principles can also help (somewhat) with my second paragraph, since they reduce quantification over the whole universe to quantification over suitable initial segments of the cumulative hierarchy.

Finally, to avoid misunderstanding, I emphasize that all of the preceding is not mathematics but an attempt to describe a philosophical intuition. The level of precision in my formulation is not that of mathematics nor that of philosophy but that of a mathematician attempting to do philosophy.