7
$\begingroup$

Does one need the axiom of replacement in the small object argument and in the transfinite construction of free algebras?

My motivation for the question is that I heard that the axiom of replacement is never needed in practice.

If the answer is "yes", how can one avoid the axiom of replacement in practical applications of these two theorems?

Note that one can't use ordinals if one doesn't allow the axiom of replacement (I think).

$\endgroup$
5
  • $\begingroup$ By the way, what would be other suspicious-of-using-replacement candidates for pieces of "real" mathematics (meaning: non-foundational and non-set-theoretic)? $\endgroup$
    – user333306
    Aug 4, 2021 at 20:08
  • 4
    $\begingroup$ Regarding the claim about ordinals, although indeed one needs replacement in order to prove the existence of infinite von Neumann ordinals, nevertheless one can still have numerous very large well-orderings without using any replacement, and these often suffice for carrying out transfinite constructions. $\endgroup$ Aug 4, 2021 at 20:40
  • 3
    $\begingroup$ If I'm not mistaken, when using ordinals outside of set theory, Replacement most often comes in for an "exhaustion" argument: there are too many ordinals for such and such process to never terminate, so it must terminate. In the small object argument, as far as I can tell, there is no such exhaustion: the "termination ordinal" is set ahead of time (by the compactness of the domains of the maps). $\endgroup$ Aug 4, 2021 at 22:21
  • 3
    $\begingroup$ I think a slightly more accurate heuristic would be to say that you need replacement when you are defining by induction or recursion a function whose codomain is a not a priori a set. The Hartogs theorem on wellorderings – in its original form – does not require replacement. $\endgroup$
    – Zhen Lin
    Aug 4, 2021 at 22:45
  • $\begingroup$ related mathoverflow.net/questions/382466/… $\endgroup$
    – Tim Campion
    Aug 5, 2021 at 21:47

1 Answer 1

7
$\begingroup$

The way it is usually presented, certainly yes. As you point out it usually refers to possibly uncountable regular ordinals, which would usually mean von Neumann ordinals. Once you have the regular ordinal, say $\kappa$, then regardless of whether $\kappa$ is a von Neumann ordinal or just a well ordered set, you need to define a sequence of objects $K_\alpha$ for each $\alpha < \kappa$, and take colimits at each limit stage, and overall at the end. That kind of argument does seem to require replacement, as far as I can see. Certainly it is possible to define a sequence of sets, even of length $\omega$ whose colimit does not provably exist in the category of sets under $\mathbf{ZFC}$ minus replacement (since $V_{\omega + \omega}$ is a model of that theory, and we can define the sequence $K_n := V_{\omega + n}$).

On the other hand, there are two alternative versions of the small object argument in Swan, W-types with reductions and the small object argument that don't use replacement (and also don't use definitions by recursion into universes of small types, which is, roughly speaking, the type theoretic version of replacement). The first can be carried out in a topos with natural number object and satisfying the choice principle $\mathbf{WISC}$, which I believe holds for any Grothendieck topos under the assumptions of $\mathbf{ZFC}$ minus replacement. The second is specific to the case of monic generating cofibrations in presheaf toposes, but does not require $\mathbf{WISC}$, so would work in a metatheory of $\mathbf{ZF}$ minus replacement. Both arguments are for a slightly non standard definition of cofibrantly generated, and they have a different format to the usual proof using ordinals. Instead of defining a sequence of objects along an ordinal, there are just two steps, first define a $W$-type, and then either quotient it (for the first argument) or carve out a subobject (for the second).

$\endgroup$
10
  • $\begingroup$ I hadn't realized what you said in your first paragraph, thanks for that ! I think I'm a bit confused about internal vs external here though: suppose you have no replacement at all, then you can't actually define that sequence ($n\mapsto V_{\omega +n}$) as a sequence, even though you can define it by a formula. In particular it seems to me like Set is still cocomplete even without replacement. $\endgroup$ Aug 5, 2021 at 13:25
  • $\begingroup$ (that does not change your argument from the first paragraph of course : to define the sequence of objects needed for the small object argument as usually presented, you still need replacement) $\endgroup$ Aug 5, 2021 at 13:26
  • $\begingroup$ Yes, I agree - the best convention is to not count these "large" sequences as diagrams or maybe not call them sequences at all, so a category does not need to have their colimits in order to be considered cocomplete. $\endgroup$
    – aws
    Aug 5, 2021 at 13:31
  • $\begingroup$ @MaximeRamzi Any elementary topos is complete and cocomplete from “its own” point of view. This is a kind of trick using clever definitions and indeed in the context of this theorem the sequence in question is not a legitimate diagram. $\endgroup$
    – Zhen Lin
    Aug 5, 2021 at 14:30
  • $\begingroup$ @ZhenLin : thanks for pointing that out, I wasn't sure !! $\endgroup$ Aug 5, 2021 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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