3
$\begingroup$

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!

$\endgroup$
1
  • $\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

4
$\begingroup$

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.

$\endgroup$
5
  • $\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
4
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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