Permutation Of A Set

Formal Definition

A permutation of a set $A$ is a function $\phi:A \rightarrow A$ that is both one-to-one and onto.

Informal Definition

Essentially, a permutation is an ordering of the elements within the set.

Example(s)

Suppose that $A = {1, 2, 3, 4 ,5}$. One permutation of the set $A$ would look like

(1)
\begin{align} 1 \rightarrow 3 \\ 2 \rightarrow 5 \\ 3 \rightarrow 1 \\ 4 \rightarrow 4 \\ 5 \rightarrow 2 \end{align}

Suppose that $\sigma$ is the permutation given by equation (2). We write $\sigma$ in a more standard notation, changing the columns to rows in parentheses and omitting the arrows, as

(2)
\begin{align} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \end{align}

so that $\sigma(1)= 3, \; \sigma(2) = 5,$ and so on.

Non-example(s)

Let $A = {1,2,3,4,5}$ and let $\tau$ and $\psi$ be functions with $A$ being the domain of each. Now suppose $\tau$ is as follows:

(3)
\begin{align} \tau = \begin{pmatrix}1&2&3&4&5 \\ 1&4&4&2&3 \end{pmatrix} \end{align}

This is not a permutation since the function is neither one-to-one nor onto. Also, suppose $\psi$ looks like

(4)
\begin{align} \psi = \begin{pmatrix}1&2&3&4&5 \\ 4&5&6&1&3 \end{pmatrix} \end{align}

Even though this function is one-to-one, it is not a function mapping elements of $A$ to other elements of $A$ since $6 \notin A$, so $\psi$ is not a permutation of A either.