18
$\begingroup$

(There have been many questions on MathOverflow about the axiom scheme of replacement, including a few with a similar flavour to mine. Some have very informative answers and link to excellent papers and blog posts. I've spent a while reading the older questions etc., and as far as I know, my question isn't answered in any of them — but it's entirely possible that it is and I missed it. In that case, I'll be grateful if someone points out where.)

Consider the following statement about sets and functions, which I'll call "axiom A":

A. For all well-ordered sets $(B, \leq)$, there exist a set $X$ and a function $p: X \to B$ with the following property:

for all $b \in B$, the fibre $p^{-1}(b)$ is an infinite set of smallest cardinality greater than that of $p^{-1}(b')$ for each $b' < b$.

In the traditional notation of set theory, if $(B, \leq)$ is an ordinal $\beta$, then $p^{-1}(\alpha) \cong \aleph_\alpha$ for each $\alpha \in \beta$. So, $X$ is the disjoint union $\coprod_{\alpha \in \beta} \aleph_\alpha$ and $p: X \to \beta$ is the obvious projection.

My question is about ETCS (Lawvere's Elementary Theory of the Category of Sets) together with axiom A. In what follows, I'm going to take ETCS as the background theory. Thus, when I say "this is weaker than that", I mean weaker in the presence of ETCS.

On the one hand, A isn't a theorem of ETCS (unless, of course, ETCS is inconsistent). That's because ETCS+A proves the existence of $\aleph_\omega$ but ETCS alone doesn't.

On the other, if I'm not mistaken, A is weaker than replacement. That's because ETCS+replacement is bi-interpretable with ZFC, and unless I'm misremembering, the fact that ETCS+A is a finite list of axioms (not involving axiom schemes) somehow implies that it can't be as strong as ZFC.

So, it seems that axiom A is a weaker form of replacement. My question:

To what fragment of replacement is axiom A equivalent (in the presence of the axioms of ETCS)?

That question is a little vague, so let me focus it more:

What's the simplest statement you can think of that's true in ETCS+replacement (or equivalently ZFC) but not provable in ETCS+A?

I don't mind whether the statement is purely set-theoretic or from another part of mathematics.

Added later Incidentally, "axiom A" is equivalent (under ETCS) to the following simpler statement:

for every set $B$, there exists a map into $B$ whose fibres all have different cardinalities.

Formally: for all sets $B$, there exist a set $X$ and a map $p: X \to B$ such that for all $b, b' \in B$, if $p^{-1}(b) \cong p^{-1}(b')$ then $b = b'$.

$\endgroup$
15
  • 4
    $\begingroup$ One easy way to see that this is weaker than Replacement is to take any $\beth$-fixed point, $\delta$, and look at $V_\delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $\aleph_\alpha$ exists for every ordinal $\alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $\delta$... $\endgroup$
    – Asaf Karagila
    May 12 '19 at 23:00
  • 2
    $\begingroup$ (Oh, and I know that Axiom A is just an ad hoc name, but in case you decide to put this into further use, please note that set theory already have an Axiom A, which is the property which preceded properness in forcing. So maybe another name is preferable?) $\endgroup$
    – Asaf Karagila
    May 13 '19 at 5:25
  • 2
    $\begingroup$ @DavidRoberts: I was thinking about the fact that ETCS doesn't establish the existence of $\aleph_\alpha$ for infinite $\alpha$, and wondered what would happen if you just threw in an axiom saying that they did exist. $\endgroup$ May 13 '19 at 9:45
  • 2
    $\begingroup$ (Which by the way would be a good name for this axiom.) $\endgroup$
    – Asaf Karagila
    May 13 '19 at 9:48
  • 2
    $\begingroup$ Here's a conjecture. Since having a power set is a $\Sigma_2$ formula, and it's "sorta kinda universal" (in the sense that if you reflect that one, then you're pretty unique, to some extent), it might be that the Cantorian Axiom is equivalent to $\Sigma_2$-Replacement. It might still be weaker, though. I really don't know enough about ETCS (and its identical twin, Bounded Zermelo) to say as much. $\endgroup$
    – Asaf Karagila
    May 13 '19 at 12:06
7
$\begingroup$

Asaf points out that Axiom A is true in $V_{\delta}$ if $\delta$ is a $\beth$ fixed point. Full replacement only holds if $\delta$ is worldly. So, in $V_{\delta}$ models of these, replacement implies a proper class of $\beth$ fixed points (since all worldly cardinals are $\beth$ fixed point-sized limits of $\beth$ fixed points), but Axiom A is compatible with the statement that there are no $\beth$ fixed points. In fact, ZFC does proves that there's a proper class of $\beth$ fixed points, since for any ordinal $\alpha$ the limit of the sequence $\beta_0 = \alpha; \beta_{n+1} = \beth_{\beta_{n}}$ is a $\beth$ fixed point greater than $\alpha$.

$\endgroup$
9
  • $\begingroup$ A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting! $\endgroup$ May 13 '19 at 3:11
  • $\begingroup$ @David: You don't need choice to define $\beth$ numbers. In effect, $\beth_\alpha$ can be defined as simply the cardinality of $V_{\omega+\alpha}$ (or just iterated power sets from a fixed set). So you don't actually need choice there. Now to get the equivalent of a fixed point, use the Lindenbaum number of $V_{\beta_n}$ to define $\beta_{n+1}$ instead. Some people would argue that the Lindenbaum numbers are the $\beth$ numbers, by the way, which is another way of looking at it. $\endgroup$
    – Asaf Karagila
    May 13 '19 at 4:59
  • $\begingroup$ Of course, but to say that beth_a = a naively, where a is an ordinal, gives well-orderable powersets. And in a structural set theory like ETCS (which I do realise Tom was not necessarily asking for, but which I was thinking of in the context of the question), you don't have the von Neumann hierarchy, at least, not in an obvious way. $\endgroup$ May 13 '19 at 6:45
  • 5
    $\begingroup$ @Tom: Even the famous Borel determinacy result (which is the usual appeal of Replacement outside of set theory, although that is too debatable) only requires $\beth_{\omega_1}$ which is far, far below the least fixed point. $\endgroup$
    – Asaf Karagila
    May 13 '19 at 10:03
  • 1
    $\begingroup$ I'm sure everyone here is well aware of this, but for the completeness of MO it might be worth pointing out that if $δ$ is a fixed point of $α\mapsto\beth_α$ then $V_δ=H(δ)$ (sets hereditarily of cardinal $<\delta$), and $H(\delta)$ is a model of $\Sigma_1$-Replacement (plus all ZFC axioms besides Replacement). Indeed, in this context it follows from $\Delta_0$-Collection, and by a theorem of Lévy, $H(\delta)$ is a $\Sigma_1$-elementary submodel of the universe. $\endgroup$
    – Gro-Tsen
    May 13 '19 at 12:53
5
$\begingroup$

The principle is essentially asserting that $\aleph_\alpha$ exists for every ordinal $\alpha$. More precisely, it asserts that for every well-order type $\alpha$, there is a set of cardinality $\aleph_\alpha$; the difference is that without the replacement axiom, one doesn't necessarily have the usual von Neumann ordinals.

This axiom is not provable in Zermelo set theory, since $V_{\omega+\omega}$ models the Zermelo theory, but it has only countably many infinite cardinals, and so $\aleph_{\omega+\omega}$ does not exist in this model, even though there are orders of type $\omega+\omega$ there.

The axiom is provable in ZFC and is strictly weaker than ZFC, as has been pointed out by B2C, since $V_\kappa$ is a model of the principle if and only if $\kappa$ is a beth-fixed point $\kappa=\beth_\kappa$.

What I would like to mention is that the principle is a natural instance of the principle of recursion:

Principle of transfinite recursion. (See the account on my blog) If $A$ is any set with well-ordering $<$ and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for all $b\in A$, where $s\upharpoonright b$ denotes the function $\langle s(a)\mid a<b\rangle$.

In my blog post, The axiom of well-ordered replacement is equivalent to full replacement over Zermelo + foundation, I explain how Alfredo Roque Freire and I had realized that the axiom of well-ordered replacement is equivalent to the full replacement axiom, over the Zermelo set theory with foundation. From this it follows that the principle of transfinite recursion is equivalent to the axiom of replacement.

Corollary. The principle of transfinite recursion is equivalent to the replacement axiom over Zermelo set theory with foundation.

ZF = Z + foundation + transfinite recursion

There is no need for the axiom of choice.

My perspective is that the axiom A of the question is naturally seen as an instance of the principle of transfinite recursion, which naturally generalizes it. By adopting that principle, one arrives at ZF set theory and the axiom of replacement.

$\endgroup$
7
  • 1
    $\begingroup$ Your blog post was one of the things I read before posting, so I'll take the opportunity to ask now what I wondered then: if we're using the language of ETCS (so, no assuming that elements of sets are sets, etc.), how would you define $V$ and "class function"? $\endgroup$ May 13 '19 at 20:22
  • 1
    $\begingroup$ I'm not sure. The idea is that any definable operation should be allowed, and I'm unsure of the exact expressive power of ETCS. I worry that the language of that set-up might be limited to bounded quantifiers, in which case you are only getting replacement for $\Delta_0$-assertions, which would be weaker than full replacement. Something like the axiom of collection appearing in Kripke-Platek set theory. $\endgroup$ May 13 '19 at 21:12
  • 1
    $\begingroup$ @Tom There's doi.org/10.1016/j.apal.2013.06.004 by Awodey et al, and Mike Shulman's unreleased (unfinished?) hint from the references in (the arXiv version of) his stack semantics paper, "Michael A. Shulman. 2-categories of classes. In preparation" $\endgroup$ May 14 '19 at 0:30
  • 1
    $\begingroup$ @David: Are we allowed to read papers that were published by Elsevier again? $\endgroup$
    – Asaf Karagila
    May 14 '19 at 13:55
  • 1
    $\begingroup$ (continued) Despite all that, maybe there's some way of phrasing the transfinite recursion principle in ETCS, by thinking about it differently rather than simply attempting to mimic the ZF-type formulation. $\endgroup$ May 15 '19 at 8:36

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.