This comes from S.Lang - Basic Mathematics,Exercise 11, page 374.

Let $J_n$ be the set of the integers $1,2,3,...,n$. (an ordered set?)
Prove that the number of permutations of $J_n$ is equal to n!.

The exercise is answered as follow:

We assume it true for $n$. Let $\tau_k$ $(k=1,...,n)$ be transposition which interchanges $n+1$ and $k$ for $k=1,...,n$.
Let $S_n$ be the set of permutations of $J_n$. We have to show that the permutations $\; I\sigma,\tau_1\sigma,...,\tau_n\sigma \;$ for $\sigma$ in $S_n$ give all distinct permutations of $J_{n+1}$. Suppose that $\,\tau_i\sigma=\tau_j\sigma'\,$ for some indices $\,i,j\,$ and some $\sigma,\sigma'$ in $S_n$. Since $\tau_i\sigma(n+1)=i$ and $\tau_j\sigma'(n+1)=j,\,$ it follows that $\tau_i=\tau_j$. Multiplying on the left by $\tau_i(=\tau_j),$ we conclude that $\sigma=\sigma'$.$\;$ If $\,\sigma'=\tau_i\sigma,\,$ then looking at the effect on the number $n+1$ we conclude that this cannot be so. Hence the permutations $\;\sigma,\tau_1\sigma,...,\tau_n\sigma \;$ with $\,\sigma$ in $S_n$ are all distinct.
If $\gamma$ is permutation of $J_{n+1}$,then either $\gamma$ leaves $n+1$ fixed, in which case $\gamma$ is already in $S_n$, or $\gamma(n+1)=i$ for some $i$ with $1\le i \le n$. In this case $\tau_i \gamma$ leaves $n+1$ fixed, so $\tau_i \gamma=\sigma$ is element of $S_n$, and $\gamma=\tau_i \sigma.\;$ Thus we have found all permutations of $J_{n+1}$. We assume by induction that there are $n!$ permutations in $S_n$. To each $\sigma$ in $S_n$ we have associated the $n+1$ permutations $\; \sigma,\tau_1\sigma,...,\tau_n\sigma \;$ in $S_{n+1}$. Hence the number of permutations in $S_{n+1}$ is $(n+1)n!=(n+1)!$

Permutation is defined (in the book) as:

By permutation of $J_n$, we mean mapping $\sigma:J_n \to J_n$ having the following property. If $\,i,j$ are in $J_n$ and $i \ne j$, then $\sigma(j) \ne \sigma(i)$. Thus the image of permutation consist of $n$ distinct integers $\sigma(1),...,\sigma(n)$, which must be the integers $1,2,...,n$ in different order.

I don't understand the following:

$(A)$ $\quad\sigma:J_n \to J_n$ means that $\sigma(x)$ is defined only when $x \in J_n$ ??
$(B)\quad$ This means that if $J_n$ is subset of some set $N$, then $\sigma:N\to N$ leaves fixed every $x$ such that $x\in N$ and $x\notin J_n$, but may or may not leave fixed elements $x$ such that $x\in J_n$ so we can consider this permutation of the set $J_n$??

In the proof we see: $\;\tau_k\sigma(n+1)=k$ and $\tau_k\sigma(k)=n+1$ where $k\in J_n$. If $(A)$ is true, then we can't do that (namely, $\sigma(n+1)$) because $n+1\notin J_n$.
Do I interpret the definition wrong? Do the fact that $J_n$ is subset of $J_{n+1}$ change anything? As you see I'm completely confused.

Some simple example:
Let $J_3=\{1,2,3\}\;$ and $\;J_4=\{1,2,3,4\}$.
Let $\sigma=\begin{bmatrix} 1 &2 &3 \\ 3 &2 &1 \end{bmatrix}$ and $\tau$ be transposition which interchanges $3$ and $4$. So, $\tau:J_4\to J_4$?
What is $\sigma(4)$ or $\tau\sigma(4)$?
If $(A)$ is true do I get: $\tau\sigma(J_3)=\begin{bmatrix} 1 &2 &3\\ 4 &2 &1 \end{bmatrix}$ but $\tau\sigma(J_4)$ and $\tau\sigma(4)$ is undefined?

If $(B)$ is true I should get: $\tau\sigma(J_4)=\begin{bmatrix} 1 &2 &3 &4\\ 4 &2 &1 &3 \end{bmatrix}$ which seems to be the result needed to make sense out of the proof.

  • 1
    $\begingroup$ (A) $\sigma:J_n\mapsto J_n$ means that $\sigma(x)$ is only defined when $x\in J_n$, yes. But for (B), this means that you cannot even talk about $\sigma(x)$ for an $x\not\in J_n$; the concept itself doesn't make any sense. It's as though you asked for the square root of blue. $\endgroup$ – Steven Stadnicki Dec 1 '17 at 2:11
  • 1
    $\begingroup$ The book is being really sloppy where it says to consider the case $\sigma'=\tau_i\sigma$, because strictly speaking the domains of the former are two aren't the same (the domain of $\sigma'$ is $J_n$ but the domain of $\tau_i\sigma$ is $J_{n+1}$); it's true that you can use the embedding of $J_n$ into $J_{n+1}$ to consider $\sigma'$ as an element of $S_{n+1}$, but it should be much more explicit about that. $\endgroup$ – Steven Stadnicki Dec 1 '17 at 2:16
  • $\begingroup$ @Steven Stadnicki That should be $N\to N$ Right ? $\endgroup$ – Rumata Dec 1 '17 at 2:17
  • $\begingroup$ (in fact, strictly speaking this embedding is necessary even to write $\tau_i\sigma$.) $\endgroup$ – Steven Stadnicki Dec 1 '17 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.