Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a well-orderable infinite set $A$, can we always say that the set $$\left\{R\in A\times A:\langle A,R\rangle\, \text{is a well-ordering}\right\}$$ has cardinality $2^{|A|}$? How much Choice is required for the proof of this?

I believe that where $A$ is countably infinite, we can proceed without any use of Choice. Is that correct?

share|cite|improve this question
up vote 7 down vote accepted

This is a delicate matter. Do you mean all the well orders or just up to isomorphism?

For the former observe, for example, that if a set $A$ has one well-ordering then any permutation induces a different well-ordering, although of the same order type. For the natural numbers there are $2^{\aleph_0}$ many permutations so there are at least continuum many well-orders, and that is just of one isomorphism type! On the other hand, there can only be continuum many relations, so we have exhausted the cardinality.

We can continue by induction on the $\aleph$-cardinals, in fact, this is the only way we can resume. Why? Well, if a set has any well-ordering then it has to be in bijection with an ordinal, and if it is infinite this ordinal can be an $\aleph$-number. The argument for $\omega_1$, $\omega_2$ and so on is the same as above and this would require no choice at all.

If a set cannot be well-ordered, well... it has no well-ordering! However if we assume the axiom of choice then every set can be well-ordered and going through cardinals is enough. So arguing this claim for all sets is to require the full axiom of choice.

On the other hand, if you are interested in order types rather than mere orders than the claim that there are $2^A$ many is in fact to assert the Generalized Continuum Hypothesis, since for a set of cardinality $\kappa$ there are only $\kappa^+$ many ordinals of cardinality $\kappa$, and therefore only $\kappa^+$ many order types.

Whether or not $2^\kappa=\kappa^+$ is undecided in ZFC.

share|cite|improve this answer
I was actually asking about all well-orders, not just up to isomorphism (I am familiar with the latter result). So no choice at all, eh? Excellent! Thanks, Asaf. – Cameron Buie Jun 30 '12 at 19:11
@CameronBuie: Not at all, it is not hard to prove that if $|A|=\aleph_\alpha$ then there are $2^{\aleph_\alpha}$ many permutations, and it is not hard to prove that if you apply two different permutations to a concrete well-order the result is two different well-orders. – Asaf Karagila Jun 30 '12 at 19:12
Minor addendum: The amount of choice required to assert $2^\kappa = \kappa^+$ is "all of it, and more", since GCH implies the full Axiom of Choice, but is not implied by it. – Henning Makholm Jun 30 '12 at 22:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.