I have a theory that the axiom of choice is equivalent to the statement that sets of distinct cardinals are well ordered by cardinality. I can prove that the axiom of choice implies this. However I am having trouble proving the other way. I want to prove, without choice, that any set is in bijection with a set of distinct cardinals. I don't know if this is true, but if it is could someone provide a proof for me? Thank you.

  • 1
    $\begingroup$ The question of whether (without choice) "any set is in bijection with a set of distinct cardinals" is very interesting, and as far as I know, it is open. I strongly suspect the answer is no, even if we relax the requirement to "For every $X$ there is a set $Y$ of distinct cardinalities, and a surjection from $Y$ onto $X$". $\endgroup$ – Andrés E. Caicedo May 9 '14 at 2:08
  • $\begingroup$ Isn't it true that every set $A$ of cardinals is well-ordered ? (the order of the ordinals restricted to $A$). If so, the statement "any set is in bijection with a set of distinct cardinals" should imply the axiom of choice, right ? $\endgroup$ – Archimondain May 9 '14 at 3:06
  • $\begingroup$ @Archimondain: Every set of cardinals is wellordered if you assume choice; without choice they needn't even be linearly ordered. $\endgroup$ – Malice Vidrine May 9 '14 at 3:20
  • $\begingroup$ @Archimondain: See my answer about this. $\endgroup$ – Asaf Karagila May 9 '14 at 4:01
  • $\begingroup$ Thanks, indeed to me every cardinal was an ordinal, I was unaware of an extension of the notion of cardinality to every sets, in case of the absence of choice. $\endgroup$ – Archimondain May 9 '14 at 4:02

If every set of cardinal numbers is well-ordered by cardinality, then in particular any two cardinals are comparable by cardinality (i.e., trichotomy holds).

To see that trichotomy implies the well-ordering theorem: Let $X$ be any set that we want to well-order, and let $\alpha$ be its Hartogs number, which is the first ordinal that cannot be injected into $X$. (The existence of such an ordinal can be proved without Choice; it is the union of the ordinals that represent the order types of relations that well-order subsets of $X$). Since by assumption $|\alpha|\le|X|$ is not true, trichotomy tells us that $|X|<|\alpha|$, so there exists an injection $X\to\alpha$, and therefore $X$ can be well-ordered.


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.