The standard definition I usually find regarding permutations is a bijection from a set to itself, in other words:
$\text{a function }f:\{ 1, 2,\dots,n \} \mapsto \{ 1, 2,\dots,n \} \text{ which is a bijection is a} \textit{ permutation}$
and is often written in a two row format, such as
$\sigma=
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1
\end{pmatrix}$
I am quite confused as to why we decide to formalize permutations in this way. Are we not making the strong assumption that there is some natural ordering of the elements of our set? For instance, if my set was $A:=\{ \{1,4\}, \{6,0\}, \{9,3\} \}$ then I cannot see how to apply the definition and notation above.
I would be much happier to formalize the permutation as a bijective function which maps every element $a \in A$ to its position in the ordered sequence $f(a) \in \{ 1,\dots,|A| \}$, formally $f:A\mapsto \{ 1,2,\dots,|A| \}$ because it does not make any assumption about $A$.
Although I hardly see this form, which makes me suspect there exists some undesirable or incorrect feature of this definition.
Best Answer
For any set $A$ you can define $$ \operatorname{Sym}(A) = \left\{\,\sigma:A\to A\ \middle|\ \text{$\sigma$ bijective}\,\right\} $$ and call the elements permutations on $A$. In fact this will always be a group and for $A=\{1,2,\dots,n\}$ you get the usual permutation group $S_n$.
The reason we want self-maps is that we want to compose permutations, this gives us the group structure of $\operatorname{Sym}(A)$.
A bijective function $A\to\{1,2,\dots,|A|\}$ would not define a permutation of the elements of $A$, it would just give a total order on $A$. For a permutation you want to assign to every $a\in A$ a unique $\sigma(a)\in A$, so you need $\sigma:A\to A$.