I had come across this question when revising an upcoming exam in Set Theory.

Here we are assuming Axiom of Choice, and $WO(X)$ denotes the set of well-orders on $X$, which was already established to be a set earlier on in the question.

I had thus far made 2 attempts at the question:

  • an argument akin to Cantor's diagonalization theorem (tried this as we have a similar conclusion for that theorem). I can't see a way to construct the diagonal.
  • to construct a function directly via AC: firstly by Cantor's Theorem establish that there are no surjection $X \rightarrow P(X)$ and then constructing an injection $g: P(X) \rightarrow WO(X)$. This would imply the conclusion needed.
    • I tried the map from $P(X) \rightarrow WO(X)$ by $S \in P(X); x \in S, y \in X-S \implies x < y$, but this did not seem to work as I cannot make the map injective.

These, combined with the fact that this argument does not seem to make use of the assumption of $X$ being infinite makes me think I've been going about this the wrong way.

Any pointers would be much appreciated!

  • $\begingroup$ A more interesting result (due to Tarski) is that, without having to assume the axiom of choice, there is no surjection from any set $X$ (finite or infinite) to the set of well-ordered subsets of $X$. This is non-trivial even if $X$ is not well-ordered. $\endgroup$ Dec 10, 2019 at 18:14

4 Answers 4


Fix one well ordering of $X$. Now every permutation of $X$ induces a distinct well ordering on $X$.

So it is enough to show there is no surjection onto the set or permutations of $X$. For each subset of $X$ choose a permutation which fixes pointwise exactly that subset. It is an injection from $\mathcal P(X)$ into the set of permutations. Well, except complements of singletons, but that's easy to get over.

  • $\begingroup$ Is there a proof that you can always find such a permutation without AC ? If not, do you know if it's consistent with ZF that $\mathfrak{S}(X)$ and $\mathcal{P}(X)$ have different cardinalities, and to what extent ? $\endgroup$ May 15, 2019 at 15:34
  • $\begingroup$ Are you asking if every set (with at least two members) admits a permutation? Yes. Those that move finitely many points always exist... $\endgroup$
    – Asaf Karagila
    May 15, 2019 at 15:36
  • $\begingroup$ No I'm asking if for every set $X$ and not co-singleton subset $A$ there is a permutation of $X$ whose fixed point set is $A$ (with AC it's easy to prove, I'm wondering without it) $\endgroup$ May 15, 2019 at 15:38
  • $\begingroup$ (which is equivalent to proving that every non singleton set has a derangement, i.e. a permutation with no fixed-point) $\endgroup$ May 15, 2019 at 15:39
  • $\begingroup$ Ah, of course you need AC for that. This was asked a couple of times before on the site. Your follow up has also been studied, I don't remember off hand, but I believe I wrote an answer either here or on MO before. (I'm sorry, I'm a bit busy the next couple of days, so I won't have time to search for this right now.) $\endgroup$
    – Asaf Karagila
    May 15, 2019 at 16:20

You don't even need choice.

If $X$ is not well-orderable, then $WO(X)=\varnothing$, so there is no map $X\to WO(X)$ at all and in particular no surjective map.

If $X$ is well-orderable, then $X$ is in bijection with $\{0,1\}\times X$, and you can then can use diagonalization to see that $f:X\to WO(\{0,1\}\times X)$ cannot be surjective:

Let $f$ be given and choose a well-ordering $\leq$ of $X$. Now consider the following well-ordering $\preceq$ of $\{0,1\}\times X$:

  • $(i,x)\preceq (j,y)$ whenever $x\ne y$ and $x\le y$.

  • For each $x$, $(0,x)$ and $(1,x)$ have the opposite relation under $\preceq$ than they have under $f(x)$.

Then $\preceq$ is not in the range of $f$.


Yet another approach: let $\kappa$ be the cardinality of $X$ and consider the successor cardinal $\kappa^+$. Every element of $\kappa^+$ has cardinality at most $\kappa$ and in particular every element of $\kappa^+\setminus\kappa$ has cardinality exactly $\kappa$. Since $|\kappa^+\setminus\kappa|=\kappa^+$ (removing a subset of smaller cardinality cannot change the cardinality of an infinite set), this means there are $\kappa^+$ different order-types of well-ordered sets of cardinality $\kappa$. Choosing a well-ordering of $X$ for each of these order-types, we find that $|WO(X)|\geq \kappa^+>\kappa=|X|$.


Let $(X, \le)$ be given.

If $T$ is any subset of $X$ with $2$ or more elements, then there is a bijective transformation $\gamma_{\,T}: T \to T$ satisfying

$\tag 1 \text{For every } u \in T, \quad \gamma_{\,T}(u) \ne u$

(see this).


$\tag 2 \mathcal B(X) = \{ S \in \mathcal P(X) \, | \, S \text{ is infinite } \text{ and } X \setminus S \text{ is infinite } \}$

For every $S \in \mathcal B(X)$ we can construct a bijection $\beta_S$ on $X$ that is the identity on $S$ and 'scrambles' the elements in $X \setminus S$.

So we can inject $\mathcal B(X)$ into the bijective transformations of $X$. Since $|\mathcal{B}(X)| = 2^{|X|}$ (see this), we conclude that the bijective transformation on $X$ has cardinality $2^{|X|}$.

An easy argument shows that the cardinality of $WO(X)$ can't be less than $2^{|X|}$ (c.f. Asaf Karagila's answer)..

So a surjection from $X$ onto $WO(X)$ is not possible.

Note: I'm fairly confident that if you go through this carefully you will find you do not need the axiom of choice (c.f. Henning Makholm's answer).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .