What, if anything, do permutations have to do with order?

Question

My course notes have:

$$ \text{"A bijective function } f:X\rightarrow X \text{ is called a } permutation \text{ of } X" \tag{0}. $$

So let

$$A=\{1,2,3\} \tag{1.1},$$ $$f:A\rightarrow A \text{ be a } 3\text{-cycle on } A \text{ given by } f(1)=2,\;f(2)=3,\;f(3)=1. \tag{1.2}$$

Then we can write $$ f(\{1,2,3\})=\{1,2,3\}. \tag{2} $$ To be sure, if we wish, we can alternatively write $$ f(\{1,2,3\})=\{2,3,1\}, \tag{3} $$ but we are under no obligation to do so, and we could just as easily write $(3)$ if $f$ were the identity function.

Hence my question: what, if anything, do permutations have to do with order?

Answer 1

If $f : A \to B$ is a function, and $X \subseteq A$, it is common to write $$ f(X) = \{f(x) \mid x \in X\}, $$ as you have done. This is not especially practical though for your purposes, because as you've noticed, sets are fundamentally unordered. So let's do something different: if $(a_1, \ldots, a_n)$ is a sequence of elements of $A$ (so the order is preserved), I propose that we use the notation $$ f((a_1, \ldots, a_n)) = (f(a_1), \ldots, f(a_n)). $$ This means that if we pick an ordering for $A$ to begin with -- in your case, since $A = \{1, 2, 3\}$, we can use the standard ordering -- we can put the elements of $A$ into a sequence in that ordering. That gives us the sequence $(1, 2, 3)$. Then if we apply $f$ we see $$ f((1, 2, 3)) = (2, 3, 1); $$ we have produced a different ordering using $f$. In fact, you can prove that two different permutations always give a different ordering, and you can prove that any ordering can be made using a permutation. Thus we have a one-to-one correspondence between permutations and orderings. And this is what permutations have to do with order.

Answer 2

I think the confusion lies with the notation of functions. When we write $f:X\rightarrow Y$, $X$ and $Y$ are the domain and codomain of the function respectively. For a permutation, these have to be the same set.

The way you defined $f$ in your question is absolutely fine. It's a valid permutation.

But we cannot write: $f(\{1,2,3\})=\{1,2,3\}$ since function $f$ does not take sets as an input. It takes elements of that set as an input.

Now to your question:

What does it have to do with order?

Because $f$ maps elements from one set to the same set, and because it is bijective (meaning that there is a one-to-one correspondence from one set to the other) you can perhaps see how it reorders the elements in some sense. In other words if we have elements of the set in some order, and we apply the function on them (on every individual element) then the result is a different ordering of those elements.