0
$\begingroup$

I am learning about permutations right now. This is the definition in my textbook and one that is also similarly on Wikipedia.

A permutation of a set $X$ is a bijection $p: X \rightarrow X$ on that set

Every definition of a permutation I have seen claims that permutations on a set X is bijective. I am trying to reason this out formally, but I think I am not doing it properly. For a permutation to be a bijection on a set $X$, the function must be one-to-one and onto.

Let us define a set with $n$ elements as $X_n = \{1,2,\dots n\}$. The permutations of $X_n$ total $n!$. Each element in $X_n$ will have $1!, 2!, \dots n!$ permutations. Now it looks pretty clear to me that this is one-to-one and onto, but how do I state this more formally to make the conclusion more obvious to others?

$\endgroup$
  • 5
    $\begingroup$ I think you mean $p : X \rightarrow X$ in your highlight? $\endgroup$ – Stuartg98 Apr 7 at 16:11
  • 2
    $\begingroup$ If you are struggling with this then ask yourself how you define a permutation. For example, what is a permutation on $\{1,2,3,4,5\}$ by your definition? $\endgroup$ – John Douma Apr 7 at 16:15
  • $\begingroup$ It's not clear to me exactly what your question is, but math.stackexchange.com/questions/1399781/… may be relevant. $\endgroup$ – Eric Wofsey Apr 7 at 16:27
  • $\begingroup$ @JohnDouma Before reading the answers, I didn't really know. After reading the answers, I would say a permutation is the # of all the ways you can reorder the elements $\{1,2,3,4,5}\$, which would be 5! $\endgroup$ – Evan Kim Apr 7 at 17:59
  • $\begingroup$ @EricWofsey I will take a look, it looks like an interesting post $\endgroup$ – Evan Kim Apr 7 at 18:00
1
$\begingroup$

With permutations we are counting all the ways to rearrange the elements into a set of $n$ elements. Clearly we use every element and the elements of the codomain are the same size, so naturally the function is bijective.

$\endgroup$
1
$\begingroup$

It follows from the definition of a permutation really. In basic terms, if you have a line of n objects, a permutation is a reordering of those objects. You are not extending the number of positions available or reducing the number of objects, so all positions in the new line are filled by the original objects. It is onto. Since we cannot have two objects occupy the same position in the line, it is also one to one. Hence it is bijective.

$\endgroup$

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.