# If $X$ is infinite, then there is no surjective map $f : X \rightarrow WO(X)$

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!

• 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. Dec 10, 2019 at 18:14

## 4 Answers

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.

• 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 ? May 15, 2019 at 15:34
• Are you asking if every set (with at least two members) admits a permutation? Yes. Those that move finitely many points always exist... May 15, 2019 at 15:36
• 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) May 15, 2019 at 15:38
• (which is equivalent to proving that every non singleton set has a derangement, i.e. a permutation with no fixed-point) May 15, 2019 at 15:39
• 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.) 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).

Define

$$\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).