When does collection imply replacement?

Question

In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that $\phi(x,y)$, then there exists a set $B$ such that $y\in B$ if and only if $\phi(x,y)$ for some $x\in A$. That is, $B$ is the "image" of $A$ under the "definable class function" $\phi$.

The related axiom schema of collection modifies this by not requiring $y$ to be unique, but only requiring $B$ to contain some $y$ for each $x$ rather than all of them. However, there are at least two different versions of this.

1. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$ (this is Wikipedia's version; I'll call it "weak collection").

2. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that (1) for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$, and (2) for all $y\in B$ there is an $x\in A$ with $\phi(x,y)$ (I'll call this "strong collection").

The third possibly relevant axiom is the axiom schema of separation, which states that for any $\phi$ and any set $A$ there exists a set $B\subseteq A$ such that $x\in B$ if and only if $x\in A$ and $\phi(x)$.

I know the following implications between these axioms:

• Strong collection implies weak collection, since it has the same hypotheses and a stronger conclusion.
• Strong collection implies replacement, since it has a weaker hypothesis and the same conclusion.
• Replacement implies separation (assuming excluded middle): apply replacement to the formula "($\phi(x)$ and $y=\lbrace x\rbrace$) or ($\neg\phi(x)$ and $y=\emptyset$)" and take the union of the resulting set.
• Together with AC and foundation, replacement implies weak collection: let $\psi(x,V)$ assert that $V=V_\alpha$ is the smallest level of the von Neumann hierarchy such that there exists a $y\in V_\alpha$ with $\phi(x,y)$, apply replacement to $\psi$ and take the union of all the resulting $V_\alpha$.
• Weak collection and separation together imply strong collection: separation cuts out the subset of $B$ consisting of those $y$ such that $\phi(x,y)$ for some $x\in A$.

My question is: does weak collection imply replacement (and hence also separation and strong collection) without assuming separation to hold a priori? Feel free to assume all the other axioms of ZFC (including $\Delta_0$-separation). I'm fairly sure the answer is "no," but several sources I've read seem to assume that it does. Can someone give a definitive answer, and ideally a reference?

Answer 1

The answer is no, if you allow me to adopt some weak-but-equivalent forms of the other axioms. And the reason is interesting:

• A shocking number of the axioms of set theory are true in the non-negative real line R⁺, with the usual order < being used to interpret set membership. (!)

Let's just check. For example, Extensionality holds, because if two real numbers have the same predecessors, then they are equal. The emptyset axiom holds, since there are no non-negative reals below 0. The Union axiom holds, since for any real x, the reals less than x are precisely the reals that are less than something less than x. (Thus, every set is its own union.) A weakened version of the Power set axioms holds, the Proper Power set, which asserts that for every x, there is a set p whose elements are the strict substs of x. This is because for any real number x, the reals below x are precisely the reals y (other than x), all of whose predecessors are less than x. (Thus, every real is its own proper power set.) An alternative weakening of power set would say: for every x, there is p such that y subset x implies y in p. This is true in the reals by using any p > x. A weakened pairing axiom states similarly: for every x,y, there is z with x ε z and y ε z. This is true in the reals by using any z above both x and y. The Foundation axiom is no problem, since 0 is in every nonempty set. Also, similarly AC holds in the form about families of disjoint nonempty sets, since this never occurs in this model. The Weak Collection Axiom holds since if every y < x has phi(x,y,w), then in fact any y in the same interval will work (since this structure has many automorphisms), and so we may collect witness with any B above x and w. Note that Separation fails, since, for example, {0} does not exist in this model. Also, Replacement fails for the same reason.

Similar interesting models can be built by considering the structure (ORD,<) built using only ordinals, or the class { V_α | α in ORD }. These also satisfy all of the weakened forms of the ZFC axioms without Separation, using Collection in place of Replacement.

Thus, part of the answer to your question is that it depends on what you mean by the "other axioms of ZFC".

Apart from this, however, let me say that the term Weak Collection is usually used to refer to the axioms that restrict the complexity of the formulas in the usual Collection scheme, rather than the axiom that you state. For example, in Kripke Platek set theory KP, a weak fragment of ZFC, one has collection only for Sigma_1 formulas, and this is described as a Weak Collection axiom. (What you call Weak Collection is usually just called Collection.) And there is a correspondingly weakened version of Separation in KP.

But I am happy to adopt your terminology here. You stated that AC plus Replacement implies Weak Collection, but this is not quite right. You don't need any AC. Instead, as your argument shows, what you need is the cumulative V_α hierarchy, which is built on the Power set axiom, not AC. That is, If you have Replacement and Power set and enough else to build the V_α hierarchy, then you get Collection as you described, even if AC fails. For example, ZF can be axiomatized equivalently with either Collection or Replacement.

Your question is a bit unusual, since usually Separation is regarded as a more fundamental axiom than Replacement and Collection, and more in keeping with what we mean by set theory. After all, if one has a set A and a property phi(x), particularly when phi is very simple, it is one of the most basic set theoretic constructions to be able to form { x in A | phi(x) }, and any set theory violating this is not very set-like. We don't really want to consider models of set theory where many instances of Separation fail (for example, Separation for atomic formula is surely elemental).

Incidentally, there is another version of a weakening of Collection in the same vein as what you are considering. Namely, consider the scheme of assertions, whenever phi(x,y) is a property, that says for every set A, there is a set B such that for every a in A, if there is b with phi(a,b), then there is b in B such that phi(a,b).

---

OK, let me now give a positive answer, with what I think is a more sensible interpretation of your question. I take what I said above (and Dorais's comment) to show that we shouldn't consider set theories where the Separation Axiom fails utterly. Rather, what we want is some very weak set theory, such as the Kripke Platek axioms, and then ask the relationship between Weak Collection and Replacement over those axioms. And here, you get the postive result as desired.

Theorem. If KP holds, then Weak Collection implies Replacement.

Proof. Assume KP plus (Weak) Collection. First, I claim that this is enough to prove a version of the Reflection Principle, since that proof amounts to taking successive upward Skolem hulls, which is what Collection allows. That is, I claim that for every set x and any formula phi, there is a transitive set Y such that x in Y and phi(w) is absolute between Y and the universe V. This will in effect turns any formula into a Delta₀ formula using parameter Y.

Applying this, suppose we have a set A and every a in A has a unique b such that phi(a,b). By the Reflection Principle, let Y be a large set transitive containing A such that phi(a,b) and "exists b phi(a,b)" are absolute between Y and V. So Y has all the desired witnesses b for a in A. But also, now { b | exists a in A phi(a,b) } is a Delta₀ definable subset of Y, since we can bound the quantifier again by Y. So the set exists. So Replacement holds. QED

I think we can get away with much less than KP. Perhaps one way to do the argument is to just prove Separation by induction on the complexity of formulas. One can collect witnesses by (weak) Collection, and this turns the formulas into lower complexity, using the new bound as a bound on the quantifiers.