0
$\begingroup$

Following is one of the definition of a permutation of a nonempty set:

The permutation of a nonempty set A is an ordered list of elements of A.

Following is another definition of a permutation of a nonempty set:

A bijective function from A (a nonempty set) to A is called a permutation of A.

Some books said that both of the definitions are the same. How can this two definitions are the same? For example, according to the first definition, the permutations of the set {1, 2, 3} are 123, 213, 132, 321, 312, 231. But according to the second definition, the permutations of the set {1, 2, 3} are the sets:

{(1, 1), (2, 2), (3, 3)}, {(1, 2), (2, 1), (3, 3)}, {(1, 3), (2, 1), (3, 2)}, {(1, 2), (2, 3), (3, 1)}, {(1, 3), (2, 2), (3, 1)}, {(1, 1), (2, 3), (3, 2)}.

In my knowledge, a function from a set C to a set D is a relation from C to D in which every element of C appears exactly once as the first component of an ordered pair in the relation from C to D. Also, in my knowledge, the order of the elements in a set is unimportant when we talk about function according to the previous definition of a function. However, some books said that, for example, 123 is a permutation of the set {1, 2, 3} and 123 determine the function {(1, 1), (2, 2), (3, 3)} and therefore the two definitions of a permutation of a nonempty set is the same. In what way 123 determine {(1, 1), (2, 2), (3, 3)}. Why don't 123 determine {(2, 1), (1, 2), (3, 3)}?

$\endgroup$
  • 1
    $\begingroup$ The ordered list in the first definition is the image of the bijective function. Take just the second component of each bijection, and you will get an ordered list. $\endgroup$ – Prahlad Vaidyanathan Oct 21 '13 at 15:29
  • $\begingroup$ They're equivalent definitions, but the exact correspondence between "ordered lists of all elements of $A$" and "bijective functions from $A$ to $A$" is only clear if there is a natural ordering of the elements of $A$. Saying that the list [blue, frog, yellow] is a permutation of those three elements isn't very helpful. $\endgroup$ – mjqxxxx Oct 21 '13 at 15:38
1
$\begingroup$

To call them "the same" is a bit of an abuse of language (albeit a common one that you get used to quite quickly). I would prefer to describe them as "equivalent".

In fact, because $A$ is here an arbitrary set, it seems even more dangerous than usual to call them "the same", because to get from the ordered list to the bijection requires having some fixed ordering on $A$, which isn't part of the data. If $A=\{1,\dotsc,n\}$, then there is at least a "default" ordering that you can use.

In conclusion, I think you are right to be nervous about calling these two definitions the same, but if you fix some ordering on $A$, then you get a bijection between the two types of permutation; you convert an ordered list into the bijection mapping the first element of $A$ (under the fixed ordering) to the first element of the ordered list, and so on, and convert a bijection $\varphi\colon A\to A$ into the ordered list $\varphi(a_1),\varphi(a_2),\dotsc$, where $a_i$ is the $i$-th element of $A$ under the fixed ordering.

$\endgroup$
  • $\begingroup$ Elaborating. If $A=\{5, \heartsuit, \circ\}$ then permutation $5 \to \heartsuit, \circ\to\circ, \heartsuit \to 5$ can not be represented as an ordered list unless you specify an ordering for $A$. (Recall that $A$ is not ordered, so it is exactly the same as $\{\circ, 5, \heartsuit\}$. And now think of sets whose elements cannot be put in a "list" (think points on the plane). The bijective mapping $(x,y) \mapsto (-y,x)$ is a permutation of plane points, but you'll run into trouble trying to put that down as an ordered list. $\endgroup$ – Drini Oct 21 '13 at 15:50
  • $\begingroup$ If I add certain ordering on the set $A$, then how can I get a bijection between the two types of permutation? Can you please give some simple examples? $\endgroup$ – shuxue Oct 21 '13 at 16:19
  • 1
    $\begingroup$ @user71798 Henry has already done that in his answer, in which $A=\{1,2,3\}$ with the order $1,2,3$. See for example that the list $2,1,3$ represents the bijection $1\mapsto 2$, $2\mapsto 1$ and $3\mapsto 3$; the $i$-th element of $A$ in the chosen order (in this case $i$) maps to the $i$-th element of the list. $\endgroup$ – mdp Oct 21 '13 at 16:25
0
$\begingroup$

There is a natural equivalence between the two given the way you have laid out the bijective function with the domain ordered:

  • {(1, 1), (2, 2), (3, 3)} $\equiv (1,2,3)$

  • {(1, 2), (2, 1), (3, 3)} $\equiv (2,1,3)$

  • {(1, 3), (2, 1), (3, 2)} $\equiv (3,1,2)$

  • {(1, 2), (2, 3), (3, 1)} $\equiv (2,3,1)$

  • {(1, 3), (2, 2), (3, 1)} $\equiv (3,2,1)$

  • {(1, 1), (2, 3), (3, 2)} $\equiv (1,3,2)$

$\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.