Notation of permutation

Question

I have a question about the notation of the permutation. I am looking at a proof that shows composition of two permutations is a permutation. There it says, let us assume the contrary, let $T(S(a_1))=T(S(a_2))$, assuming that $T$ and $S$ are permutations of a set $A$. My question is, are $a_1$ and $a_2$ are permutations, or they are just some element? For example, let $A=\{1,2,3,4\}$. Then is $a_1$ just an element like $1$ or $2$ etc. or, it is a permutation like $(1,2,4,3)$. I appreciate any help. Thanks

Answer 1

As you presented it $a_1$ and $a_2$ are elements in the set you're applying the permutations.

Among other things a permutation is an injective function. So given two permutations $S,T$ on the set $A=\{a_1, \ldots ,\ a_n\}$ you want to prove (among other things) that $T\circ S$ is an injection from $A$ to $A$, that is for any $a_1, a_2\in A$ you want to show that $(T\circ S)(a_1)=(T\circ S)(a_2)$, which is the same as $T(S(a_1))=T(S(a_2))$.

After proving the above by the pigeonhole principle you can conclude that $T\circ S$ is also a surjection and hence a permutation.

My favourite version of the pigeonhole principle (which the more uself here) goes as follows:

If $X$ is a finite set and $f\colon X\longrightarrow X$ in an injection, then $f$ is a surjection.

Answer 2

$a_1$ and $a_2$ are elements like $1$, $2$ etc.

How do I know this? Remember that a permutation $P$ on a set $A$ is defined as a bijective function $A \to A$ - that is to say:

1. For every $a \in A$ there exists $b \in A$ such that $a=P(b)$. (Surjectivity)
2. If $P(c) = P(d)$ then $c = d$ (for all $c, d \in A$). (Injectivity)

(Note that if $A$ is a finite set (as it usually is when talking about permutations) then conditions (1) and (2) are equivalent.)

So if you want to show that $T \circ S$ - the composition of two permutations - is a permutation, then you have to show that it satisfies condition (2). The natural first step to show that is to suppose that $T(S(a_1)) = T(S(a_2))$ for $a_1, a_2 \in A$ and then try to show that $a_1=a_2$.