Please Login to access more options.

Problem 24 (The Span Of A Set Of Permutations Is Closed)

Let $S$ be a set of permutations of $X$. Show that $\text{span}(S)$ is closed. In other words, show that once you form the span of a set $S$ of permutations of $X$, you cannot obtain any new permutations by spanning the span. For this reason, we'll often refer to $\text{span}(S)$ as the closure of $S$.

Solution

By way of contradiction assume that $\sigma_1,\sigma_2,\cdot\cdot\cdot,\sigma_n \in \span(S)$ for some $n \in \mathbb{N}$ such that $\sigma_c = \sigma_1 \circ \sigma_2 \circ \cdot\cdot\cdot \circ \sigma_n \not\in \span(S)$.

From Ben: What about powers that appear above elements? Have you considered every possible case?

In other words, there exists some composition combination of permutations of elements in $\span(S)$ that is not in $\span(S)$. Choose an arbitrary $\sigma_k$ such that $k \in \mathbb{N}$ and $k \leq n$. Because $\sigma_k \in \span(S)$, it follows that $\sigma_k$ can be written as a composition combination of permutations in $S$. Because this is clearly true for all $\sigma_1,\sigma_2,\cdot\cdot\cdot,\sigma_n \in \span(S)$, it follows that $\sigma_c$ can be written as a compositions combination of permutations in $S$. Thus, $\sigma_c \in \span(S)$, a contradiction. It then follows that $\span(S) = \span(\span(S))$, and thus, $\span(S)$ is closed.

From Ben: Proving that two sets are equal requires that we prove each is a subset of the other. I think you have only proven that one of the sets is a subset of the other.
In addition, it appears that you are trying to use a proof by contradiction, but then you are directly proving something as well. Come by. Let's chat about this one. Or you can read my proof (see the links below for the one that ends with "Ben"). I'm sure we can come up with a shorter, better proof.
Tags

Change these as needed.

  • Week2 - Which week are you writing this problem for?
  • Jason - Sign your name by just changing "YourName" to your wiki name.
  • NeedsWork
  • 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.