4
$\begingroup$

I've some trouble calculating the cardinality of the set of the permutations of a given set $ A $. For notational purpose let $ k = |A|$ and define $ P_A = \{ f : A \to A | f \text{ is a bijective function } \} $

Clearly if $ A $ is a finite set, the cardinality of $ P_A $ is $ k! $, but the interesting case is when $ A $ is infinite. Again, it is obvious that $|P_A| \leq 2^k $. But i can't find neither a lower upper bound or the lower bound to conclude by Schroeder-Berstein. Any hints or corrections? Thanks in advance!

Following the hint given by Asaf Karagila, I worked out this answer:

I'll put [AC] where i used AC to prove the following fact

So starting from [AC] $ k \cdot k = k$ [AC] there exists a family of $ k $ pairwise disjoint subset of $ A $ each of them of cardinality $k$. Let's call them $\{ B_i \}_{i \in k} $. Let $ F := { f \colon k \to \{0, 1} | \text{ f is a function } \} $. Define $ F^* := F \setminus \text{ costant functions }$. Note that $|F^*|= 2^k $. For each $ f \in F^*$ let $ J_f :=\{i \in k | f(i) =1\} $ and let $ U_f := \{ \bigcup_{j \in J_f} B_j \}$. It is immediate to prove that for each $ f $ we have $|U_f|=|U_f^c| =k $. So we have the $2^k $ partitions of $A $. With a little abuse of notations I denote with $2^k $ an index set of this size. For each $ i \in 2^k $ let $ (P1_i, P2_i) $ a partition of $ A $. [AC] for each partition choose one bijection $g_i: P1_i \to P2_i $. Now we can define $ 2^k $ permutations in this way. For each $ i\in 2^k $ let $ h_i : A \to A $ with $ h_i(a)=g_i(a) $ if $ a \in P1_i $ otherwise $ h_i = g^{-1} $. is is easy to see that it is a permutation.

$\endgroup$
  • 2
    $\begingroup$ Sorry to be slow, but what's your obvious injection of $P_A$ into the powerset of $A$ getting $|P_A|\leq 2^k$? $\endgroup$ – Kevin Carlson Feb 3 '14 at 20:38
  • 5
    $\begingroup$ @Kevin, $P_A\subseteq\mathcal P(A\times A)$. $\endgroup$ – Asaf Karagila Feb 3 '14 at 20:40
  • $\begingroup$ @Asaf Karagila i was ispired by one of your (very good) answer (math.stackexchange.com/questions/191006/… ) when you say "there are $2^k $ way of enumerating a set in $[ A]^k $" so i supposed that if two functions "differ" by a permutation of the domain they enumerate the same subset $\endgroup$ – Riccardo Feb 3 '14 at 20:58
  • $\begingroup$ And so tried to calculate the size of the set $\endgroup$ – Riccardo Feb 3 '14 at 20:59
  • $\begingroup$ A (probably) silly question: by constant functions in $F$ do you mean $f_0(i) = 0, f_1(i) = 1, i \in k$? So $\text{card}~F^* = \text{card}~F - 2 = 2^k - 1 = 2^k$? $\endgroup$ – Andrey Surovtsev Aug 17 at 14:17
3
$\begingroup$

HINT: Prove that there are $2^k$ partitions of $A$ into equipotent two parts. Given such partition $\{A_1,A_2\}$ choose a bijection $f\colon A_1\to A_2$ and use $f$ to define a permutation of $A$.

Note the heavy use of the axiom of choice. It is needed.


Based on the suggested solution, here's a much better outline for a solution:

Fix a bijection $f\colon A\to A\times A$, and fix a permutation of $A$ which is not the identity, $\pi$. Now given $A'\subseteq A$ define a permutation of $A\times A$, $$\pi_A(a,b)=\begin{cases}(a,\pi b) & a\in A'\\ (a,b) & a\notin A'\end{cases}$$

This defines $2^{|A|}$ permutations of $A\times A$, and therefore of $A$.

$\endgroup$
  • $\begingroup$ Ok, now I try to work it out the hints $\endgroup$ – Riccardo Feb 3 '14 at 21:43
  • $\begingroup$ Mmmh it doesn't allow me to post long comments, I'll edit my question, can you please check the reasoning? I'm interested in quoting correctly when AC is needed $\endgroup$ – Riccardo Feb 3 '14 at 22:28
  • 1
    $\begingroup$ @Steven: I think that it's provably never $|A|$. Also note that every set has a cardinality, it just doesn't have to be an $\aleph$ number. Some sets would have strictly more than $2^{|A|}$ permutations, but I'm not sure how well we can fine tunes these inequalities. Controlling power sets cardinality is one of the greatest challenges when creating models of set theory. $\endgroup$ – Asaf Karagila Feb 3 '14 at 22:48
  • 1
    $\begingroup$ @Ric: No. Just any non-trivial permutation works. Try to see why! $\endgroup$ – Asaf Karagila Feb 4 '14 at 9:57
  • 1
    $\begingroup$ @AndreySurovtsev: Yes, that's the idea. You're right about the subscript, but I think it's best to not make trivial edits like that on posts which are this old, so I'm just going to keep it this way for now. $\endgroup$ – Asaf Karagila 2 days ago

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.