# Is Replacement motivated by ranked iterative conception of sets?

When one reads the Wikipedia article on the Von Neumann Universe, one gets the impression that the idea of "the cumulative hierarchy" serves as a motivation for $$ZFC$$. I don't see really how this is the case. I don't see any of the definitions given to the cumulative hierarchy in that page implying Replacement at all.

Also when one reads in Boolos-The Iterative Conception of Set, page: 228, one gets the following:

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.

It appears that what Boolos is saying is that: when we extend the rough iterative conception of set with a ranking function, then we get Replacement.

EDIT: I've mis-understood Boolos here, as Noah point in his comments and answer, Boolos was not taking about extending the iterative conception of set with a ranking function. So the rest of this post addresses the first point that I've referred to that is mentioned in the Wikipedia article. However, Boolos seems to be saying that Replacement is not related to the iterative conception of sets, and that it is an extra-thought. Which in some sense backs my argumentation that I'll present below.

I'll try here to capture the notion of building a hierarchy from below in class ambiance. So let's work in mono-sorted first order logic with identity and membership.

Define: $$set(x) \iff \exists y (x \in y)$$

Axioms: $$ID$$ axioms +

Class axioms:

$$C_1$$. Extensionality: $$\forall a,b (\forall x (x \in a \leftrightarrow x \in b) \to a=b)$$

$$C_2$$. Class comprehension schema: if $$\varphi$$ is a formula in which $$x$$ is not free, then all closures of: $$\exists x \forall y (y \in x \leftrightarrow set(y) \wedge \varphi)$$ are axioms.

Define: $$x=\{y|\varphi\} \iff \forall y (y \in x \leftrightarrow set(y) \wedge \varphi)$$

Let $$V=\{x| set(x)\}$$

Define: $$R\text{ is a ranking function on V } \iff R \text{ is a function on V} \wedge \\\exists < [\text {< is a well ordering relation on range}(R) \wedge \forall x,y \in V (x \in y \to R(x) < R(y))]$$

Define: $$r \text{ is a rank }\iff \exists x (r=R(x))$$

Hierarchy axioms: There exists $$R$$ such that:

$$H_1$$. Ranking: $$R$$ is a ranking function on $$V$$

$$H_2$$. Stages: for every rank $$r$$: $$\forall x (\forall y \in x (R(y) \leq r) \to x \in V)$$

$$H_3$$. Infinity: There exists a limit rank.

$$H_4$$. Height: $$\forall x \in V (\text{well ordered}(x) \to \exists y \subset range(R) [x \text { isomorphic to } y])$$

/ Theory definition finished.

Now I think this clearly captures the ranking function as built form below, which is the heart behind the philosophy of iterative conception of sets [one can easily see that the axiom $$H_4$$ clearly depicts this building from blow direction]. However, I don't see this reaching to the strength of $$ZF$$? I think it might reach to the strength of the first fixed point on the $$\omega$$ function of von Neumann ordinals.

If I'm correct then the addition of $$Replacement$$ schema to the rest of axioms of $$ZF$$ is better be considered as a large cardinal axiom, rather than being viewed as grounded in the cumulative hierarchy concept. Accordingly Replacement is to be grounded in limitation of size concept, that a set sized definable (parameters allowed) class is a set, and this is a notion about cardinality, rather than it being a notion about a Hierarchy or ranking or stages or iteration or the alike. A possible backing to this view is that presented by Randall Holmes here. However I'm still not sure of the above, since there is a lot of talk about the cumulative hierarchy constituting a motivation for axioms of ZFC is already well known, hence my question:

1. Is replacement provable in the above ranked Hierarchy class theory?
2. IF not, then how are we to understand that having the von Neumann universe constitute a motivation for Replacement schema?
• Related: mathoverflow.net/questions/228168/… especially the remarks by Arnon Avron that I quoted. I think Avron would say that Replacement is not motivated by the cumulative hierarchy per se, and I think his argument is a pretty good one. – Timothy Chow Nov 24 '18 at 5:10
• @TimothyChow from what I've read actually Avron is advocating replacement, but he is against the combination of it with power, and he thinks the later is the culprite. Anyhow I speaking here about the cumulative hierarchy and power is a theorem here, indeed we can have a hierarchy of stages that are not power stages, we can have a hierarchy of constructive powers like in $L$, but this is not the point raised here, I like the head post of the page you've referred in your comment. Look at his question which he puts it in a naive (and the right way I think) manner, to be continued.... – Zuhair Al-Johar Nov 24 '18 at 8:03
• .. [continuation], now lets ask ourselves a simple question, what determines the height of each stage in the hierarchy? it ought to be a "set" I believe, I mean an ordinal that is already formed within the levels of the cumulative hierarchy, since we agreed that sets are objects that are created therein! BUT if we hold that, which is in my opinion the natural way to build a hierarchy from below, now as I said if we hold that then we don't get replacement, we'll only get our hierarchy indexed by ordinals less than the first fixed point on the omega function, much weaker than replacement. – Zuhair Al-Johar Nov 24 '18 at 8:16
• In nutshell replacement doesn't come from building sets by iterative powering from below. [note that what is meant by replacement here is more precisely the addition of replacement schema to the rest of axioms of ZF] – Zuhair Al-Johar Nov 24 '18 at 8:20
• I agree with your basic point that the concept of the cumulative hierarchy doesn't directly suggest Replacement---that's (part of) the reason why Z (as opposed to ZF) is a viable axiomatic system. I suspect Avron would ask, "Why not Replacement?" since he thinks that Replacement is a basic feature of our conception of sets. Not every axiom has to be justified directly from the cumulative hierarchy; e.g., we don't justify Extensionality by arguing that Extensionality is motivated by the cumulative hierarchy. – Timothy Chow Nov 25 '18 at 15:41

EDIT: I've rewritten for clarity.

First, re: your claim "It appears that what Boolos is saying is that: when we extend the rough iterative conception of set with a ranking function, then we get Replacement," this is incorrect, or at least incomplete. Boolos' principle is basically just saying "$$Ord$$ is regular," which when combined with just a small bit of replacement (which Boolos has already baked in) gives full replacement.

The key point is phrasing the hypothesis correctly. When Boolos writes

If each set is correlated with at least one stage (no matter how), ...

this is just saying "For every class relation $$R\subseteq Sets\times Stages$$ such that $$dom(R)$$ is all of $$Sets$$, ..."

This makes his whole proposed principle simply:

Suppose $$R\subseteq Sets\times Stages$$ is a class relation such that $$dom(R)$$ is all of sets. Then for every set $$z$$, there is some stage $$s$$ such that for each $$w\in z$$ there is a stage $$t$$ with $$(i)$$ $$t$$ earlier than $$s$$ and $$(ii)$$ $$wRt$$.

ZFC satisfies this principle by taking $$s=\sup\{\min(R^{-1}(w)): w\in z\}+1,$$ which exists by Replacement. Conversely, we can use Boolos' principle to prove Replacement by using it to find a sufficiently large stage that all witnesses have appeared with respect to the usual rank notion, and then applying separation. In gory detail:

• Suppose we have an instance of replacement: that is, a set $$z$$ and a formula $$\varphi$$ (with parameters) such that for each $$w\in z$$ there is exactly one $$y$$ with $$\varphi(w,y)$$.

• Let $$rank$$ be the usual ranking function on the universe of sets. Consider now the following relation $$R$$:

• If $$w\not\in z$$, we set $$wR\alpha$$ for every ordinal $$\alpha$$.

• If $$w\in z$$, we set $$wR\alpha$$ if the unique $$y$$ satisfying $$\varphi(w,y)$$ has $$rank(y)=\alpha$$.

• The relation $$R$$ satisfies the hypotheses of Boolos' principle (conflating ordinals and stages), and so that principle gives us some ordinal $$\theta$$ such that for each $$w\in z$$, the unique $$y$$ satisfying $$\varphi(w,y)$$ has $$rank(y)=\theta$$.

• Now consider $$V_{\theta+1} =$$ the sets of rank $$\le\theta$$ in the usual sense (the set-hood of $$V_\theta$$ needs to be justified, and as I commented below ZC alone isn't up to the job, but if I recall correctly the hypothesis that each "stage class" is a set is indeed built in). Because $$\theta$$ is large enough to see all the sets we care about appear, applying separation to $$V_{\theta+1}$$ we get that the class $$\{y: \exists w\in z(\varphi(w,y))\}$$ is a set. So we're done.

Actually, it's arguable that Boolos isn't identifying stages with ordinals at this, well, stage. However, that makes no difference: full replacement lets us conflate arbitrary well-orderings and ordinals, and Boolos' principle restricted to ordinals-as-stages gives full replacement as per the above.

Now, the theory you describe is quite different, and your comment on its limitations is correct: it's much weaker than ZFC. In particular, it holds in the structure $$M=(L_{\theta+1},\in)$$, where $$\theta$$ is the least fixed point of the map $$\alpha\mapsto\omega_\alpha$$. (I use $$L$$ instead of $$V$$ to control the length of well-orderings that show up; whether $$(V_{\theta+1},\in)$$ satisfies your theory is independent of ZFC, since we could have the continuum much larger than $$\theta$$.)

As to your philosophical critique of replacement, this is of course a somewhat subjective issue. I waffle on whether it's built into the cumulative hierarchy idea already; I tend to fall on the side of "yes," but that's not universal, and it seems Boolos takes the opposing position ("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"). I do certainly think that Replacement, and before that Infinity, do indeed constitute "ur-large-cardinal" principles. I believe Kanamori's article In praise of replacement backs majority-me against Boolos, but I haven't read it in a while so I can't promise it's fully on-topic (I do remember it being quite good though).

• Yes, I understand the schematic point you'r raising, but here I'm speaking in term of "classes" and so we can reduce schemas into single axioms. Anyhow, you are right regarding the "at least one" point that Boolos had mentioned, this can be translated here by changing $H_1$ into R is a relation (i.e. a set of ordered pairs) that is a superclass of a ranking function on V, this way R can be one-many relation, or even many-many relation, and we can have part of it being the function you've mentioned. to be continued.... – Zuhair Al-Johar Nov 23 '18 at 19:59
• @ZuhairAl-Johar That still doesn't seem strong enough to me: the point of Boolos is that all definable ranking functions need to be considered. And if you make $R$ a many-many relation, then it doesn't necessarily contain any information (e.g. $R=V\times V$). The right axiom, if you want to work in class theory, is "For any class $R$, if $R$ is a ranking function then ...." – Noah Schweber Nov 23 '18 at 20:02
• continuation..., but notice that the function you've spoken about is not fulfilling Boolos, since it is not membership sensitive, I can have a singleton of a doubleton set, and by then the member of that singleton is sent to $\omega_{\omega}$ while the singleton is sent to $\omega$, however the union of it with a ranking function would be a function that satisfy Boolos. However this branching by supersetting a ranking function is not desirable at all, and it is not related to the iterative principle, as Boolos himself admits. And so although my formlation might have not captured Boolos's ... – Zuhair Al-Johar Nov 23 '18 at 20:04
• yet it is more into the heart of this issue. About your remark that "this" theory implies replacement, then do you mean by "this" the theory I've formulated here or Boolos's theory, if you mean the former, then please tell me how, how for example I can prove that $\omega_{\omega_{\omega_{...}}}$ (i.e. $\omega$ times) is a set in this theory? – Zuhair Al-Johar Nov 23 '18 at 20:06
• Again, we're not adding ranking functions, that's not what Boolos is talking about. In modern terms he's considering the principle "Every class function from sets to ordinals is "locally bounded,"" or "Ord is regular." – Noah Schweber Nov 23 '18 at 20:36