7
$\begingroup$

Let $S_A$ be set of all bijections over $A$ such that $Card(A)=\kappa$. Define foctorial as $\kappa!:=Card(S_A)$. Show that if $\kappa$ is infinite, then : $\kappa!=2^\kappa$

First, I've proved this definition is well-defined. Then I wanted to use Cantor-Schroeder-Bernstein's theorem to find injections between $S_A$ and $2^A$ or $\mathcal{P}A$, but I'm still searching for it. If it is possible, then there's no need to use Axiom of Choice and it is provable in ZF.

Actually, injection of desired functions must be proved directly from injection of $f\in S_A$. So my first attempt was following function which isn't injective !

$H(f)(a) = \left\{ \begin{array}{lc} 1 & f(a)=a\\ 0 & \# \end{array}\right.$

Now let's find an injection from $S_A$ to $2^A$ and from $\mathcal{P}A$ to $S_A$, or another injections !

$\endgroup$

1 Answer 1

6
$\begingroup$

You can't find a solution which doesn't use some part of the axiom of choice (as shown by Dawson and Howard), but you don't need the entire assumption of the axiom of choice (as shown by Pincus).

John W. Dawson, Jr. and Paul E. Howard, Factorials of infinite cardinals, Fund. Math. 93 (1976), no. 3, 186--195.

David Pincus, A note on the cardinal factorial, Fund. Math. 98 (1978), no. 1, 21--24.

It perhaps should be pointed out that assuming the axiom of choice this is a simple calculation since $2^A\leq S_A\leq A^A=2^A$ for all infinite cardinals. (See Factorial of Infinite Cardinal for details.)

$\endgroup$
2
  • 1
    $\begingroup$ So which injections are employed to infer that : $2^A\leq S_A$ and $S_A\leq A^A$ ? $\endgroup$ May 24, 2014 at 12:36
  • 2
    $\begingroup$ $S_A$ is an actual subset of $A^A$, the set of all functions from $A$ to $A$; and $2^A$ goes into $S_A$ by defining for each set $B\subseteq A$ a complete derangement which fixes its complement (e.g. partition it into pairs and switch each pair). This, of course, fails to work for singletons but there are only $A$ of them, so we can ignore that in terms of cardinality (i.e. we first prove that $\mathcal P(A)$ and $\{B\subseteq A\mid |B|>1\}$ has the same cardinality, then we inject the second set into $S_A$). $\endgroup$
    – Asaf Karagila
    May 24, 2014 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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