1
$\begingroup$

This pertains to Prop. $5.14$ and Theorem $5.15$ in Roitman's "Intro to Set Theory," page $68$. https://www.math.ku.edu/~roitman/SetTheory.pdf

What is the difference between these two statements? (Are they not the same, setting $\alpha=x$?).

And why does only the latter entail choice? The proof of the second states one needs the least ordinal with $|x|=|\alpha|$, but do you not need this - finding a least ordinal - in the first?

$5.14$ says:

$\forall\alpha$ an ordinal, $\exists\kappa$ an initial ordinal with $|\alpha|=|\kappa|$

and $5.15$ says:

AC [Axiom of Choice] iff $\forall x\exists\kappa$ $\kappa$ is an initial ordinal and $|x|=|\kappa|$

Thanks

$\endgroup$
3
+50
$\begingroup$

It might be better to write them in a bit plainer English: the first is

"Every ordinal is in bijection with some initial ordinal,"

while the second is

"Every set is in bijection with some initial ordinal."

Since there are lots of sets which aren't ordinals, in principle there's no reason for the first statement to imply the second. Indeed, to get from the first statement to the second statement we would need to prove

"Every set is in bijection with some ordinal,"

and this is the Well-Ordering Theorem, which is equivalent to the axiom of choice.


You also ask why the first statement is provable in ZF, since you need to pick the least ordinal with a certain property. Well, the point here is not every choice requires the axiom of choice! In ZF alone, we can prove that every set of ordinals has an $\in$-least element; in particular, every ordinal $\alpha$ is in bijection with the least ordinal in the set $\{\beta:$ there is a bijection from $\alpha$ to $\beta$$\}$, which exists by the fact above, and this ordinal is clearly an initial ordinal.

If you haven't yet proved "Every set of ordinals has an $\in$-least element" in ZF, you should try to do that.


Interesting side note: the well-ordering theorem says "every set is in bijection with some well-ordered set." To get from this to "every set is in bijection with some ordinal," we need to prove "every well-ordered set is in bijection with some ordinal." The proof of this fact uses transfinite recursion, which requires the axiom scheme of Replacement.

$\endgroup$
  • $\begingroup$ Hi Noah - Having read a bit further in text, Theorem $5.32$ is: Every well-ordered set is order-isomorphic to an ordinal. Most of the times I've seen this, it entails (if not introduces) as you said, Replacement. However it is not explicitly mentioned here. Rather the proof has $x$ well-ordered by $\leq$. And then defines a function $f$, whose range is $x$, by induction. (Skipping a few steps) it states that if $f[\alpha]=x$, then $f:\alpha\rightarrow x$ is a $1-1$ onto order-preserving map. Usually I've seen Replacement, in a simple form, as if $x$ is a set, and $f$ a function, then $f[x]$ $\endgroup$ – user12802 Mar 10 '18 at 22:06
  • $\begingroup$ is a set. Am I correct that since it is shown that $f$ is an order isomorphism, that Replacement is actually used here (except "in reverse")? $\alpha$ was not defined, by I assume it is an ordinal. Thanks $\endgroup$ – user12802 Mar 10 '18 at 22:09
  • 1
    $\begingroup$ @Andrew The key is the part where you say "and then defines a function $f$, whose range is $x$, by induction." Definitions by transfinite recursion require Replacement - or rather, showing that the object they purport to define exist and have the basic properties expected requires Replacement. $\endgroup$ – Noah Schweber Mar 10 '18 at 22:14
  • 1
    $\begingroup$ Informally, the recursive definition of $f$ looks something like: "Having defined $f(\alpha)$ for all $\alpha<\beta$, if $f\upharpoonright\beta$ is surjective onto $x$ we are done, and otherwise we send $\beta$ to the least ordinal not in the range of $f\upharpoonright \alpha$. However, in order for this to work we also need to know at each stage that "$f\upharpoonright\beta$" is in fact a set! Proving this takes replacement, the point being roughly that $f\upharpoonright\beta$ is the union of the image of a certain map from ordinals $<\beta$ to approximations of $f\upharpoonright\beta$. $\endgroup$ – Noah Schweber Mar 10 '18 at 22:17
  • $\begingroup$ Thanks - As you anticipated (and I figured you would; I should have written more) that is how $f$ was defined. Yet surprisingly, Replacement was never mentioned. With regards, $\endgroup$ – user12802 Mar 10 '18 at 22:54
2
$\begingroup$

The second one doesn't require $x$ is an ordinal. The fact that any set is equinumerous to some ordinal or cardinal is equivalent to AC, while the fact that any ordinal is equinumerous to an ordinal follows from ZF.

$\endgroup$
0
$\begingroup$

You don't need the axiom of choice in the first. The set of ordinals $\beta$ such that $|\beta| = |\alpha|$ is nonempty and thus has a least element (no choice required here... the ordinals are well-ordered by definition). Then you can show that this least element is initial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy