I am trying to pin-point where Replacement is required in a specific definition by Transfinite Recurson. In the general proof of the Transfinite Recursion Theorem, it is noted that Replacement is used

  1. to guarantee that $F \restriction \alpha$ (i.e. the range of the function being defined) is always a set (because its domain $\alpha$ is a set),

  2. to prove that $dom (F)$ is all of ON (by reductio)

But suppose our specific definition is something like:

$P(0) = 0$

$P(\alpha+1) = P(\alpha) \cup \wp (P(\alpha))$

$P(\lambda) = \bigcup_{\alpha < \lambda} P(\alpha)$

I don't see where Replacement is necessary since it seems that the existence of $P(\alpha+1)$ follows by Union and Powerset, and the existence of $P(\lambda)$ follows from that by Union. Suppose, moreover, that we just want to define this function up to some set $\lambda$ (as opposed to a proper class). Then is Replacement being used at all?

  • $\begingroup$ Note also that, the way you've written it, you use the axiom of pairing to obtain $P(\alpha +1)$. (This, however, isn't necessary as defining $P(\alpha+1) = \wp(P(\alpha))$ gives the same sequence.) $\endgroup$ Oct 12 '17 at 18:20

the existence of $P(\lambda)$ follows from that by Union

This isn't true. To get $P(\lambda)$ from Union we would need, not just each $P(\alpha)$ for $\alpha<\lambda$, but the whole set $\{P(\alpha):\alpha<\lambda\}$. This isn't something we can get without Replacement.

The easiest way to convince yourself that this might be an issue, I think, is to think about the set $V_\omega$. $V_\omega$ is a model of all of ZFC except for the axiom of infinity; in particular, it satisfies Union. And each finite ordinal is in $V_\omega$. But we can't apply Union to get $\omega\in V_\omega$, since we don't have a single set containing all the finite ordinals to apply it to. Now this is a silly example, but hopefully it convinces you that Union on its own doesn't actually have very much power in terms of building "limit stages" of sequences of sets.

Think of it this way: in order to use Union, we need to already have "collected" all the sets whose union we want to take into one single set. And this "collection" is where Replacement (usually) comes in. (On that note, it's worth pointing out that there's an axiom scheme called "Collection" which is in most contexts equivalent to Replacement.)

It's a good exercise at this point to show the following:

$V_{\omega+\omega}$ is a model of Z (= ZF without the Replacement scheme).

(And in fact ZF proves this.) There's nothing particularly hard here, just go through the axioms one by one and show they hold in $V_{\omega+\omega}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.