Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$M$ is a set.We denote the set of all the bijections from $M$ to itself by $K$.Is the cardinality of $K$ larger than the cardinality of $M$?

share|improve this question

2 Answers 2

up vote 12 down vote accepted

Sure it is, unless $|M|$ is $1$ or $2$. If $M$ is finite, this simply means that $|M|!>|M|$. If $M$ is infinite, then $M \simeq M \times \{0,1\}$. Let us look at bijections from $M \times \{0,1\}$ to itself.

There are at least as many of them as there are subsets of $M$. Indeed, if $A \subset M$, then you can build a bijection $\varphi\colon M \times \{0,1\} \to M \times \{0,1\}$ such that it fixes pairs $(m,0)$ and $(m,1)$ for every $m \in A$ and swaps pairs $(m,0)$ and $(m,1)$ for every $m \not \in A$.

This proves that the cardinality of the set of bijections from $M$ to itself is greater or equal to the cardinality of the power set of $M$, which is in turn strictly greater than $|M|$.

share|improve this answer
    
It seems that in the second paragraph of your argument you must use the axiom of choice to ensure that "swap" is legal. –  Luqing Ye Nov 16 '12 at 11:21
    
Why would that require AC? –  Ittay Weiss Nov 16 '12 at 11:22
    
@IttayWeiss I am wrong…… –  Luqing Ye Nov 16 '12 at 11:26
1  
To tell you the truth, I have almost no experience working without AC, and I suspect its implicit use everywhere. For instance, I don't even see how to prove that $M \simeq M \times \{0,1\}$ without AC. –  Dan Shved Nov 16 '12 at 14:49
1  
There is some use of AC in this post because indeed $M\simeq M\times2$ requires some use of choice. –  Asaf Karagila Nov 30 '12 at 9:44

In general for a cardinality $\kappa $ the cardinality of the set you describe can be written as $\kappa !$. For finite $\kappa$ the cardinality $\kappa !$ is given by the usual factorial. For infinite $\kappa $ one has $\kappa ! = 2^\kappa$. It is not difficult to prove using Cantor-Schroeder-Bernstein.

share|improve this answer
    
Thanks for your information.I will try to prove. –  Luqing Ye Nov 16 '12 at 8:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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