2
$\begingroup$

Hi so we know the set of all functions from a set X $\phi \rightarrow$ {0,1} create a one to one correspondence from the power set of X to the set of all functions but we are looking at certain subsets of the set of all functions. What if we look at the set of all permutation of a particular set X will it also be one to one correspondence with the power set ?

$\endgroup$
4
$\begingroup$

That depends on whether the set if finite or infinite. If $X$ is finite, say with $n$ elements, then there are $n!$ permutations of $X$, but only $2^n$ subsets, and $n!>2^n$ for all $n\ge 3$. If $X$ is infinite, however, say of cardinality $\kappa$, then $X$ has $2^\kappa$ permutations and $2^\kappa$ subsets. There are $\kappa^\kappa=2^\kappa$ functions from $X$ to $X$, so $X$ has at most $2^\kappa$ permutations, and it’s not hard to produce $2^\kappa$ distinct permutations of $X$. (For example, we can use the fact that $\kappa+\kappa=\kappa$ to partition $X$ into $\kappa$ two-point sets. For each family $\mathscr{A}$ of these two-point sets we have the permutation of $X$ that interchanges the two elements in each $A\in\mathscr{A}$.) Note, though, that we’re using the axiom of choice in the discussion of infinite $X$.

$\endgroup$
1
$\begingroup$

If $X$ is finite with at least three elements, then the answer is no. There are $n!$ permutations but only $2^n$ subsets for a set of size $n$. And a simple induction argument shows that $2^n<n!$, for $n>2$.

For an infinite set this is true, but there is no "natural and explicit" bijection, since the proof is using the axiom of choice, and we cannot avoid it either.

$\endgroup$
  • $\begingroup$ Don't you mean for n>3? 8 is not less than 6. $\endgroup$ – user107952 Jun 18 '15 at 1:01

Your Answer

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