3
$\begingroup$

There are many equivalent statements of the axiom of choice. One of them is that every set can be well-ordered.

I would like to state the axiom of choice as

Trichotomy holds for cardinality of sets.

What I mean by this is that if A and B are sets, (and the vertical bars denote cardinality,) then one and only one of the following three statements are true:

  • $|A|<|B|$;
  • $|A|=|B|$;
  • $|A|>|B|$.

Definitions

    • $|A|\le|B|$ if and only if there exists an injective function $$F:A\rightarrowtail B.$$
    • $|A|<|B| := |A|\le|B|\land\lnot|B|\le|A|$;
    • $|A|=|B| := |A|\le|B|\land|B|\le|A|$, (note Cantor-Bernstein theorem);
    • $|A|>|B| := \lnot|A|\le|B|\land|B|\le|A|$.

Choice implies trichotomy

If the axiom of choice is accepted, then every set S can be well-ordered, and in fact brought into one-to-one correspondence with an ordinal number, (of the class ON.) Of any two ordinal numbers, one is included as a set in the other. Therefore if $\alpha$ and $\beta$ are ordinal numbers such that $\alpha\subseteq\beta$, there exists an injective function, namely a restriction of the identity function: $$I|_\alpha:\alpha\rightarrowtail\beta.$$ If A and B are sets, then there are ordinal numbers $\alpha$ and $\beta$ such that bijections $$G:\alpha\rightarrow A$$ $$H:\beta\rightarrow B$$ exist.

If $\alpha\subseteq\beta$, then $$H\circ I|_\alpha\circ G^{-1}:A\rightarrowtail B$$ is an injective function and $|A|\le|B|$.

Otherwise $\beta\subseteq\alpha$ and $$G\circ I|_\beta\circ H^{-1}:B\rightarrowtail A$$ is an injective function and $|B|\le|A|$.

Negation of choice implies that trichotomy fails

When we reject the axiom of choice we have to accept the existence of a set S that cannot be well-ordered. In fact there is no injective function from such a set S to any ordinal number, because even without the axiom of choice, every set of ordinal numbers can be well-ordered.

Suppose there is some ordinal number $\sigma\in{\bf ON}$ such that no injective function $F:\sigma\rightarrowtail S$ exists. Then neither $|\sigma|\le|S|$ nor $|S|\le|\sigma|$, and so trichotomy fails.

Otherwise for all $\sigma\in{\bf ON}$, there exists an injective function $$F_\sigma:\sigma\rightarrowtail S,$$ and $$\bigcup\limits_{\sigma\in{\bf ON}}F_\sigma`(\sigma)$$ (where the tick mark $`$ denotes the image under the function) is at the same time a proper class and a subset of the set S, which would violate the axiom schema of comprehension.

Question Is this proof valid? Is it well known? Is there a simpler or better way to express this? Are there statements I've made that need to be better qualified?

$\endgroup$
  • $\begingroup$ I feel that you may be confusing the Axiom of Choice with the Generalized Continuum Hypothesis. (en.wikipedia.org/wiki/Continuum_hypothesis) $\endgroup$ – Justin Benfield Nov 2 '16 at 19:01
  • 2
    $\begingroup$ @Justin: Definitely not. $\endgroup$ – Brian M. Scott Nov 2 '16 at 19:02
  • 1
    $\begingroup$ @Justin: How so? $\endgroup$ – Asaf Karagila Nov 2 '16 at 19:02
  • $\begingroup$ Closely related: Asaf's answer to a previous Question sketches a proof that total ordering of cardinals implies the axiom of choice (the converse being fairly obvious). $\endgroup$ – hardmath Nov 2 '16 at 19:02
  • 2
    $\begingroup$ @Justin: Yes, but what does that have to do with anything? You could just as well claim that the OP is confusing the Axiom of Choice with the Axiom of Constructibility, as the latter implies GCH as well as AC (and in fact Global Choice). $\endgroup$ – Asaf Karagila Nov 2 '16 at 19:12
5
$\begingroup$

Your proof is not entirely correct. It can be fixed in one of two ways: applying Hartogs' theorem, or proving Hartogs' theorem. And recall that Hartogs' theorem states that for every set there is an ordinal which cannot be injected into the set.

The issue main is that you have actually applied global choice here, in choosing for each ordinal an injection. There will certainly be more than just one. Another is that it's not clear how you argue using comprehension that you got a proper class.

You can claim that because for each ordinal there is some injection into $S$, then for every ordinal there will be a subset of $S$ which can be well-ordered of order type $\sigma$. Therefore we can find an injection from the class of ordinals into $\mathcal{P(P(}S))$, by considering all the collections of $\subseteq$-chains in $\mathcal P(S)$ with each order type. And this of course is impossible (this is effectively Hartogs' theorem).


The first implication is just fine.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Hartogs_number -- that is key. $\endgroup$ – Annorlunda Nov 2 '16 at 19:12
  • $\begingroup$ Yes. That is the key to the door you're trying to open. $\endgroup$ – Asaf Karagila Nov 2 '16 at 19:13
  • $\begingroup$ "The issue main is that you have actually applied global choice here, in choosing for each ordinal an injection." -- I'm not so sure it's necessary to choose as I have done. What about the union of the ranges of all the injective functions from any element of ON to S ? -- but Hartogs # would make that unnecessary. $\endgroup$ – Annorlunda Nov 2 '16 at 19:20
  • 1
    $\begingroup$ Well, that can be trivially shown to be $S$, even if you just restrict yourself to the ordinal $1$. $\endgroup$ – Asaf Karagila Nov 2 '16 at 19:27
  • $\begingroup$ Sure, but I believe it can also be shown to be a proper class. The ordinals cannot all fit into a set. $\endgroup$ – Annorlunda Nov 2 '16 at 19:37

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.