4
$\begingroup$

Reading this problem I remembered trying to solve the following problem. For a set $A$, denote by $S_A=\{ f : A \to A | f \text{ is bijective }\}$. Denote by $|X|$ the cardinal number of $|X|$.

Prove that for two sets $X,Y$ we have $|X|=|Y| \Leftrightarrow |S_X|=|S_Y|$.

I didn't manage to solve the case where $X,Y$ are infinite, and don't even know how to start. I tried to represent $X$ as a subset of $Y$( if $|X|<|Y|$) and maybe find a permutation in $S_Y \setminus S_X$.

  • 0
    For the forward direction: if $|X|=|Y|$ then let $h\colon X\to Y$ be a bijection. Then I'm sure one can prove that $S_X = h^{-1}S_Yh = \{ h^{-1}\circ f\circ h\colon f\in S_Y \}$, and hence $|S_X| = |S_Y|$.2011-10-18

1 Answers 1

3

First, note that your claim is false: if $|X|=0$, $|Y|=1$, then $|S_X|=|S_Y|=1$. If we exclude this case, then the claim is true for finite sets, since then we have $|S_X|=|X|!$.

If $X$ is infinite, then (assuming choice), $|S_X|=2^{|X|}$. So your claim becomes a claim about cardinal exponentiation. The generalized continuum hypothesis implies your claim, while the statement "$2^{\aleph_0}=2^{\aleph_1}$" refutes it. Both these statements are known to be independent of ZFC (assuming ZFC is consistent), so your claim is also independent of ZFC.

  • 0
    I don't know. For a proof, think about 2-cycles and 3-cycles.2013-12-27