Motivation
Suppose every object in a set of inputs has an output satisfying a specified condition. There may be many acceptable outputs for each input. Can we put enough of them into one set? Can we choose exactly one for each input? Can we collect every possible output? These are three different questions.
Replacement immediately answers a special case: when every input has exactly one output, the outputs form a set. Its uniqueness hypothesis cannot simply be omitted. Nevertheless ZF proves that, for a set of inputs, some set contains an acceptable output for every input. This is the Collection schema. The proof will bound the ranks of suitable outputs, without choosing those outputs themselves.
We work in ZF and use the earlier construction of ordinal ranks and the cumulative hierarchy. In particular,
No form of Choice is assumed until it is explicitly named.
What Collection asserts
Definition 1.3.1
(Collection schema)
Fix a first-order formula , with set parameters . The formula need not give a unique , and its quantifiers need not be bounded. If is a set, the corresponding instance of Collection is
The resulting is a witness bound: every input has at least one acceptable output in it. It may contain irrelevant objects, and it need not contain all acceptable outputs. It also need not distinguish which output goes with which input.
Definition 1.3.2
(Strong Collection)
Strong Collection adds the requirement that every member of is useful for some input:
The word “strong” here describes this additional coverage condition, not a selecting function. A single output may serve many inputs, and one input may still have many outputs in .
Like Separation and Replacement, Collection is a schema: there is an instance for each formula. We are not introducing a ZF variable that ranges over all formulas, or a truth predicate for the universe. In every argument below, is fixed.
Bounding ranks without choosing witnesses
Theorem 1.3.3
(Collection and Strong Collection in ZF)
For every fixed formula , ZF proves both the Collection instance and the Strong Collection instance displayed above. Their proofs require no axiom of choice.
Proof
(Least witness ranks bound the outputs)
Suppose . For each , consider the ordinal ranks of its acceptable outputs. This nonempty definable collection of ordinals has a least member; denote it by . Precisely,
Why can we take a least rank when we have not formed a set of all witness ranks? In the proof for one fixed , take one existing witness . Separation inside gives the nonempty set of attainable ranks at most . It has a least ordinal. No larger attainable rank could be smaller than that ordinal, so the least rank is independent of . This proves existence and uniqueness of without selecting one witness for every .
The rule is now single-valued and definable. Replacement therefore gives the set
For each , at least one acceptable output has rank . Since , every such output belongs to . Thus satisfies Collection. We have collected the unique ordinal bounds, not a family of chosen witnesses.
To obtain Strong Collection, use Separation once more:
The least-rank witnesses remain in , so every input is still served. Its defining condition also makes each member useful for some input. If , then , and ; both assertions hold.
Proof X-ray
The unique helper is a rank, not a witness
The premise gives existence of a witness for each input, but generally gives no unique witness. It does give a unique least possible ordinal rank. Replacement applies to that new single-valued rule. Power Set and transfinite recursion supply the hierarchy stage containing all outputs of those least ranks, and Separation removes irrelevant objects if desired.
The proof never passes from “each fiber is nonempty” to “choose a member of every fiber”. Even the use of one witness in the local least-rank argument is within a proof about a single fixed input; the final definition of does not depend on a family of such choices.
The construction explains the word bound. It asserts existence of a sufficiently high stage, not an effective algorithm for finding that stage from a formula. Testing whether a formula has a witness at a given rank can involve arbitrary unbounded set-theoretic quantification.
Recovering functional Replacement
Theorem 1.3.4
(Collection plus Separation gives Replacement)
Over the usual remaining ZF axioms, Collection and Replacement are equivalent schemas when Separation is available. The direction from Replacement to Collection, proved above, uses the ZF rank theorem. The direction from Collection to Replacement needs only Collection followed by Separation.
Proof
(Collection implies Replacement)
Suppose a formula has exactly one output for every . Collection provides meeting the acceptable outputs for every input. Separate
If some is an output of an input , Collection gives an output for that same input. Uniqueness forces , so . Conversely every is an output by definition. Consequently
which is exactly the image-set assertion of Replacement.
The uniqueness step is essential here, as the following failure shows.
Counterexample mode
Separating a witness bound without uniqueness
Claim: if every has at least one output, then separating the outputs from a Collection bound yields the set of all outputs. Take and let say that is an ordinal. The set is a Collection bound, and separation gives . But is also an acceptable output and . Worse, no set can contain all outputs here, since the ordinals form a proper class. The repaired statement assumes exactly one output for each input; then the argument above shows is the full image.
This theorem does not claim equivalence over every weak fragment of set theory: the direction from Replacement used ranks, hierarchy stages and the other stated ZF resources.
A relation is not yet a selecting function
Once Collection supplies , Separation inside gives a set relation
Definition 1.3.5
(Total relation and selecting function)
Every input has an -successor. Such a relation is often called total on , meaning that it is defined everywhere on its input domain. This does not mean that it is a total order. It need not be a function, because a fiber
can contain several members. A selecting function for the original condition is a set function with domain such that for every .
Theorem 1.3.6
(Arbitrary set-indexed witness selection is Choice)
Over ZF, the scheme asserting that every condition admits a selecting function is equivalent to the Axiom of Choice. Each instance concerns a set domain ; it does not assert one class function choosing throughout the universe.
Proof
(Choose from the fibers, and recover Choice)
Assume AC. Apply Collection and form the nonempty fibers above. Each fiber is uniquely defined from , so Replacement forms the set . AC gives a function on with for every . Put . Replacement constructs its graph, and membership in proves the required condition. Repeated equal fibers cause no difficulty: the same selected element can be used for each of them. For empty , take the empty function.
Conversely, let be any set-indexed family of nonempty sets. Use the formula saying , with the given family as a parameter. The selecting-function scheme gives for every , which is AC.
This equivalence identifies an additional principle; it is not a proof here that AC is independent of ZF. Particular selecting functions may be definable without AC. If every acceptable output is an ordinal, take the least acceptable ordinal. If every fiber is a nonempty subset of , take its least member. The important question is whether the particular rule already determines a unique output.
Worked examples
Worked example 1.3.7
(A finite computation of the rank bound)
Let and let say that is an ordinal with . The least possible witness is , whose rank is . Thus the construction gives , , and .
The set contains a suitable witness for every input, but it also contains many irrelevant objects. Strong Collection removes them and gives . This is not a selecting function: for input , both and remain acceptable, as does . The separately defined rule does select one witness, because the ordinal order supplies a canonical least one.
Worked example 1.3.8
(An already supplied family has a direct union bound)
Suppose is a set function on and each is nonempty. Its range is a set, so is a set. Every lies inside , hence already supplies a witness bound for . Invoking the general Collection theorem is unnecessary for this particular bound.
For instance, take and . The rank construction has least ranks , so suffices, and its useful witnesses are . The direct union bound also contains the larger witnesses , and . Different witness bounds can therefore contain different numbers of alternatives. Neither forming their union nor filtering by rank is the general task of selecting one member of every arbitrary nonempty set.
Worked example 1.3.9
(The ranks can require a limit bound)
For , require . These outputs are unique, so Replacement directly constructs their range. To compare with the general proof, recall that : the ranks of members of are exactly the ordinals below , giving the defining supremum .
The least witness ranks are therefore , and
Every requested is a member of . No stage with finite contains them all: it already misses the requested object , whose rank equals that stage's index. There are only countably many inputs, but the membership-depth bound is a limit ordinal, rather than a finite stage or the number of inputs.
Worked example 1.3.10
(Collection does not collect every possible output)
Take and let mean “ is an ordinal”. The bound works, and so does . There is no set of all acceptable outputs: the ordinals form a proper class. Indeed, if the set contained exactly all ordinals, would be an ordinal, and its successor would belong to . Then would imply , impossible for an ordinal.
The harmless assertion “a set supplies enough witnesses” is therefore compatible with the impossibility of “a set contains every witness”. The rank construction returns here, using the least possible witness rank zero.
Common mistakes and summary
Common mistake
(Replacement applied to a many-valued formula)
Do not apply Replacement directly to a many-valued formula. Identify a genuinely unique helper, as the least witness rank was, or first supply a set in which Separation can operate.
Common mistake
(Proving Collection by taking one witness per input)
“Take one witness for each input” is not a proof of Collection in ZF: it introduces precisely the selection issue the rank proof avoids.
A witness bound is not a function, an exact image, a computable search bound or a set of all possibilities. Collection gives enough bounded alternatives. Uniqueness makes those alternatives sufficient to recover the exact image in Replacement. A simultaneous choice of one alternative for every arbitrary set-indexed problem is the additional selecting-function principle equivalent to AC. No independence or full-course coverage claim follows from this chapter.
Exercises
Quick check
(Check both Collection and Strong Collection when . Which sets can satisfy the strong form? What is the selecting function?)
Each condition quantifies over inputs in .
Solution · Answer
The assertion is vacuous, so every set satisfies ordinary Collection. Strong Collection also requires each to have an input in , which is impossible; thus exactly satisfies it. The unique function with empty domain is the empty graph, and its selection condition is vacuous.
Quick check
(Repeat the finite rank calculation for and saying that is an ordinal above . List and identify the useful-witness subset. Explain why that subset is not a function on .)
Compute the least witness rank for each input first.
Solution · Answer
The least ranks are and , so . We have , , and . Its ordinal members above at least one input are and , so . This is a set of possible values, not a graph with a specified unique value at each input; input has two acceptable values in it. The graph of a selector, for example, is .
Quick check
(Let , and let mean . Construct the relation explicitly. Show that it is total on but fails the function condition. Give two selecting functions.)
Separate the pairs inside .
Solution · Answer
Separation gives . Input has a successor, so is total. It has two distinct successors because the finite ordinals and differ, so the uniqueness clause for a function fails. The graphs and are distinct selecting functions, each satisfying the condition.
Quick check
(Suppose and is merely a Collection bound. Prove that the exact image is contained in . Explain why the same argument fails if uniqueness is dropped.)
Compare an arbitrary output with the output that supplies for the same input.
Solution · Answer
If is any output, choose an input with . Collection provides with . Uniqueness at that input gives . Without uniqueness, and may differ. For example, with one input and all ordinals acceptable, is a Collection bound but omits the acceptable output .
Quick check
(Let be a set of ordinals. For each , require an ordinal . Construct a selecting function in ZF, and also give one ordinal witness that serves every input. Include empty and explain why neither construction needs AC.)
Successor and union are both uniquely specified operations on ordinals.
Solution · Answer
Put . The successor is uniquely specified, so Replacement constructs the graph of this function and . Also let and . A union of ordinals is an ordinal; every satisfies . Thus is a witness bound using one common value. If , is empty, and the common-value condition is vacuous. Successor and union are specified constructions; no arbitrary simultaneous selections occur.
Quick check
(Assuming AC, apply the selecting-function theorem when has witnesses of unboundedly many ranks for each . Explain why the proof still works, and why it does not first form the collection of all witnesses.)
Follow the proof: Collection comes before Choice.
Solution · Answer
Collection first supplies one hierarchy stage meeting the acceptable outputs for every input. Separate the nonempty bounded fibers , and apply AC to their set-indexed family as in the theorem. AC is used only to select within those already existing nonempty sets. Larger-rank witnesses can be ignored because the goal is one acceptable output, not all outputs. The class of all witnesses need not be a set and never becomes an input to either Replacement or AC.