19
$\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$
  • 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 at 23:00
  • 1
    $\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 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$ – Tom Leinster May 13 at 9:45
  • 2
    $\begingroup$ (Which by the way would be a good name for this axiom.) $\endgroup$ – Asaf Karagila May 13 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 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$
  • $\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$ – David Roberts May 13 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 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$ – David Roberts May 13 at 6:45
  • $\begingroup$ @David: Well, you still have the power objects. And what are the $V_\alpha$ if not these? (Yes yes, you don't have the recursion needed for these to exist. Long live Replacement, have I said that already? :)) $\endgroup$ – Asaf Karagila May 13 at 9:47
  • 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 at 10:03
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$
  • 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$ – Tom Leinster May 13 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$ – Joel David Hamkins May 13 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$ – David Roberts May 14 at 0:30
  • 1
    $\begingroup$ @David: Are we allowed to read papers that were published by Elsevier again? $\endgroup$ – Asaf Karagila May 14 at 13:55
  • $\begingroup$ @AsafKaragila Here's a preprint version, if you don't want to give E a click researchgate.net/publication/… (I only promised not to do free work for them, not to avoid reading authors who still do :-) $\endgroup$ – David Roberts May 14 at 21:55

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.