Please Login to access more options.

Theorem (The Composition Of Permutations Is A Permutation)

Let $X$ be a set. Suppose that $\sigma_1, \sigma_2, \ldots,\sigma_k$ are permutations of $X$. Then the composition $\sigma_1\circ \sigma_2\circ \ldots\circ \sigma_k$ is a permutation of $X$.

Problem 11 (The Composition Of Permutations Is A Permutation)

Prove theorem (The Composition Of Permutations Is A Permutation). As some reminders, you may use the following facts that you proved in either Math 301 or Math 340. You may use these facts without proof.

  • The composition of two injective functions is injective.
  • The composition of two surjective functions is surjective.
  • A function is a bijection if it is both injective (1 to 1) and surjective (onto). Hence, the composition of two bijective functions is a bijection.
  • You might find induction helps you get from a composition of two bijective functions is bijective to the composition of $n$ bijective functions is bijective.

Solution

Let $X$ be a nonempty set. Define $s_n = \sigma_1 \circ \sigma_2 \circ \cdots \circ \sigma_n \circ \sigma_{n + 1}$ where $\sigma_k$ for all $k \in \mathbb{N}$ are the permutations from $X$ to $X$. Let $S = \left\{ n \in \mathbb{N}\; \Big|\; s_n\; \text{is a bijection from}\; X\; \text{to}\; X \right\}$. Consider the statement

$$ s_1 = \sigma_1 \circ \sigma_2 \nonumber\; . $$

Since we know that $\sigma_1$ and $\sigma_2$ are both bijective, it follows that their composition must be bijective; therefore, $s_1$ is bijective and thus $1 \in S$.

Suppose now that $k \in S$, which means that $s_k = \sigma_1 \circ \sigma_2 \circ \cdots \circ \sigma_{k} \circ\sigma_{k + 1}$ is a bijection. Then consider $s_{k + 1}$ which is

$$ s_{k + 1} = \sigma_1 \circ \sigma_2 \circ \cdots \circ \sigma_{k + 1} \circ \sigma_{k + 2}\; . $$

From the following computation we will show that $s_{k + 1}$ is a composition of to bijective functions, namely,

$$ \begin{align} s_{k + 1} &= \sigma_1 \circ \sigma_2 \circ \cdots \circ \sigma_{k + 1} \circ \sigma_{k + 2} \nonumber \\ &= s_k \circ \sigma_{k + 2}\; \nonumber. \end{align} $$

And thus we clearly see that $s_{k + 1}$ is bijective since $s_k$ and $\sigma_{k + 2}$ are bijective. It then follows from mathematical induction that $S = \mathbb{N}$.

Q.E.D.

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.