Please Login to access more options.

Problem 40 (Properties Of Closed Sets Of Permutations)

Let $H$ be a nonempty closed set of permutations of a set $X$.

  1. Show that the identity function $id_X$ is in $H$.
  2. Show that if $\sigma\in H$, then so is $\sigma^{-1}$.
  3. Show that if $\alpha\in H$ and $\beta\in H$, then $\alpha\circ \beta\in H$.
  4. Show that if $\alpha,\beta,\gamma\in H$, then $\alpha\circ (\beta\circ \gamma) = (\alpha\circ \beta)\circ \gamma$.

Solution

1. Since $X$ is nonempty, we can pick $\sigma \in H$. Since $H$ is closed, we know $\sigma ^0 = id_x \in H$.

2. Suppose $\sigma \in H$. Since $H$ is closed, we know $H=\text{span}(H)$. Since $\sigma \in H$, we know $\sigma ^{-1}$ is a composition combination of permutations in $H$. By the definition of span, this means $\sigma ^{-1} \in \text{span}(H)$. Since $H=\text{span}(H)$, we know $\sigma ^{-1} \in H$.

3. Suppose $\alpha , \beta \in H$. Since $H$ is closed, we know $H=\text{span}(H)$. Since $\alpha , \beta \in H$, and $\alpha \circ \beta = \alpha ^1 \circ \beta ^1$, we know $\alpha \circ \beta$ is a composition combination of permutations in $H$. This means $\alpha \circ \beta \in \text{span}(H)$. Since $H=\text{span}(H)$, it follows that $\alpha \circ \beta \in H$.

4. Let $\alpha , \beta , \gamma \in H$. Since $\alpha , \beta , \gamma$ are permutations, we know $\alpha , \beta , \gamma$ are functions. Since function composition is associative, we conclude $\alpha \circ (\beta \circ \gamma) = (\alpha \circ \beta) \circ \gamma$.

Tags
  • 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.