Math 360, Fall 2013, Assignment 5

I was at the mathematical school, where the master taught his pupils after a method scarce imaginable to us in Europe. The proposition and demonstration were fairly written on a thin wafer, with ink composed of a cephalic tincture. This the student was to swallow upon a fasting stomach, and for three days following eat nothing but bread and water. As the wafer digested the tincture mounted to the brain, bearing the proposition along with it.

- Jonathan Swift, Gulliver's Travels

Carefully define the following terms, then give one example and one non-example of each:

1. Subgroup generated by a subset.
2. Finitely generated group (hint to produce a non-example: Theorem 7.6 implies that finitely generated groups must be countable).
3. Permutation (of a set \(A\)).
4. Symmetric group (of a set \(A\)).
5. Symmetric group (on \(n\) letters).
6. Group of permutations (be careful -- this is not a synonym for "symmetric group").
7. Dihedral group.

Carefully state the following theorems (you need not prove them):

1. Cayley's Theorem.

Solve the following problems:

1. Section 7, problems 3 and 6.
2. Section 8, problems 1, 5, 7, 9, 40, 42, and 46.

--------------------End of assignment--------------------

Questions:

Hello! I just want to confirm something with permutations. So lets say that we have two permutations $\tau$ and $\phi$, and we are asked to take the product $\tau \phi$. Does this mean that line up the permutations as $\tau$ first, $\phi$ second? So then if we had $\tau^2\phi$, that would be $\tau * \tau * \phi$, and then we would determine the values for the product by looking at $\phi$ then $\tau$ then $\tau$? --Robert.Moray (talk) 11:27, 6 October 2013 (EDT)

In the composition $\tau\phi$, the function $\phi$ is acting first. But you're right that $\tau^2\phi$ is obtained by letting $\phi$ act, followed by $\tau$ and then $\tau$ again. --Steven.Jackson (talk) 09:48, 8 October 2013 (EDT)

Book Problems

1. 7.3

2. 7.6

3. 8.1

4. 8.5

5. 8.7

6. 8.9

7. 8.40

8. 8.42

9. 8.46

Solutions:

Definitions

1. Subgroup Generated by a Subset.

   Definition:

   Given a group \(G\), and a subset \(S\) of \(G\), the subgroup generated by \(S\) is the smallest subgroup containing \(S\).

   Example:

   In the integers, the subgroup generated by \(\{2,6\}\) is \(2\mathbb{Z}\) - the integer multiples of 2. (For the integers, the subgroup generated by a set is the cyclic subgroup generated by the gcd of all the elements of the set).

   Non-Example:

   The subgroup generated by \(\{4,8\}\) is not \(2\mathbb{Z}\) - while this subgroup does contain both elements, it is not the smallest subgroup that does so (that would be \(4\mathbb{Z}\).

2. Finitely Generated Group.

   Definition:

   A group \(G\) is finitely generated if there is a finite subset \(S\subseteq G\) such that the subgroup generated by \(S\) is all of \(G\).

   Example:

   The integers are finitely generated (by 1).

   Non-Example:

   Uncountable sets are not finitely generated - \(\mathbb{R}\), for instance. Any element in \(S\) can be written as \(a_1^{k_1}a_2^{k_2}\cdots a_n^{k_n}|n\in \mathbb{Z}, a_i \in S\). The number of such representations is \(\aleph_0\).

3. Permutation of a Set A.

   Definition:

   A permutation of a \(A\) is a function \(\phi:A\rightarrow A\) that is one to one and onto (bijective).

   Example:

   \(f(x)=x+1,f:\mathbb{R}\rightarrow \mathbb{R}\) is a permutation of \(\mathbb{R}\).

   Non-Example:

4. Symmetric Group of a Set A.

   Definition:

   Example:

   Non-Example:

5. Symmetric Group on n Letters.

   Definition:

   Example:

   Non-Example:

6. Group of Permutations.

   Definition:

   Example:

   Non-Example:

7. Dihedral Group.

   Definition:

   Example:

   Non-Example:

Theorems

1. Cayley's Theorem

Book Problems

1. 7.3

2. 9.1

3. 9.5

4. 9.7

5. 9.9

6. 9.40

7. 9.42

8. 9.46

Theorem $\forall n \ge 3 (S_n$ is non abelian$)$

Proof

We notice that n must be an positive integer value of at least 3, so we will use the Principle of Mathematical Induction. Suppose $n=3$, looking at $S_n$, we can show by counterexample that $S_n$ is not abelian. To do so, take $\tau$ and $\phi$, two permutations such that $\tau,\phi \in S_3$. Define:

$\tau = \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{smallmatrix}\bigr)$ and $\phi = \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix}\bigr)$. :::Taking the product $\tau\phi$, we find that $\tau\phi= \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix}\bigr)=\bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{smallmatrix}\bigr)$, but examining $\phi\tau$, we see $\phi\tau=\bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{smallmatrix}\bigr)=\bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{smallmatrix}\bigr)$. This shows that $\tau\phi\neq\phi\tau$, thus by counterexample, $S_n$ is not abelian and the base case is proved. :::Now, suppose that $S_{n-1}$ is not abelian. We must show that $S_n$ is not abelian. Examining our induction hypothesis, we know that $\bigl(\begin{smallmatrix} 1 & 2 & 3 & \dots & n-1\\ \dots & \dots & \dots & \dots & \dots \end{smallmatrix}\bigr)$ is roughly what a permutation would look like, and we know that since it isn't abelian, we must be able to find at least one input where the order of multiplication matters, as we did with the base case. From the base case, however, we know that if we have two permutations of $S_{n-1}$, $\bigl(\begin{smallmatrix} 1 & 2 & 3 & \dots & n-1\\ 2 & 3 & 1 & \dots & \dots\\ \end{smallmatrix}\bigr)$ and $\bigl(\begin{smallmatrix} 1 & 2 & 3 & \dots & n-1\\ 2 & 1 & 3 & \dots & \dots\\ \end{smallmatrix}\bigr)$, then regardless of the other values we choose for the counterexample, we know that the products will differ in at least these 3 places. Also, since $S_n$ contains $S_{n-1}$, that counterexample must also be contained in $S_n$, and we can choose any value for the $n^{th}$ column with those 3 places still differing. ::::Therefore the case of $S_n$ is proved, and by the Principle of Mathematical Induction, the proof is complete. ''Q.E.D.'' ::::: Here is a strategy that avoids induction: show that whenever $n\geq3$, $S_n$ contains a subgroup isomorphic to $S_3$. Since $S_3$ is non-abelian, this forces $S_n$ to be non-abelian. --[[User:Steven.Jackson|Steven.Jackson]] ([[User talk:Steven.Jackson|talk]]) 09:48, 8 October 2013 (EDT) ::::::: Is this because we know $S_n$ is a group and that commutativity is a structural property, thus if $S_3$ is isomorphic to $S_n$, and $S_3$ is not commutative, than $S_n$ cannot be commutative either? --[[User:Robert.Moray|Robert.Moray]] ([[User talk:Robert.Moray|talk]]) 23:37, 8 October 2013 (EDT) :::::::: I don't mean to say that $S_n$ is isomorphic to $S_3$ (it can't be when $n>3$ since the orders are different) but that it contains a (proper) subgroup isomorphic to $S_3$. One can show that any subgroup of an abelian group is abelian; taking the contrapositive, one gets that any group with a nonabelian subgroup is itself nonabelian. --Steven.Jackson (talk) 07:10, 9 October 2013 (EDT)