Math 360, Fall 2013, Assignment 4

No doubt many people feel that the inclusion of mathematics among the arts is unwarranted. The strongest objection is that mathematics has no emotional import. Of course this argument discounts the feelings of dislike and revulsion that mathematics induces....

- Morris Kline, Mathematics in Western Culture

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

1. Subgroup.
2. Improper subgroup.
3. Trivial subgroup.
4. Cyclic subgroup (generated by a particular element).
5. Cyclic group.
6. Generator (of a cyclic group).
7. Order (of a group).
8. Order (of an element of a group).
9. GCD (of two integers).
10. Relatively prime.

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

1. Theorem concerning integer division (Theorem 6.3 in the text).
2. Classification of cyclic groups (Theorem 6.10).
3. Classification of subgroups of \(\mathbb{Z}\) (Corollary 6.7).
4. Classification of subgroups of \(\mathbb{Z}_n\) (Theorem 6.14).

Do the following problems:

1. Section 5, problems 7, 9, 22, 23, and 42.
2. Section 6, problems 1, 3, 5, 9, 23, 27, and 30.

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

Questions:

1. Can someone please recap me again what does " aleph_0" mean again? I found it in the example for the order of a group?

aleph_0 (\(\aleph_0\), pronounced aleph-naught), is the cardinality of the positive integers (and the even integers, the odd integers, and the integers, the rational numbers, etc.) It's the largest cardinality where you can still count the elements of the underlying set. You can count the positive integers by going 1,2,3... etc., and you are guaranteed to eventually reach any arbitrary integer. You can do the same for any set of cardinality \(\aleph_0\). But for larger sets (the real numbers) you can't count the elements. There is no sequence of real numbers where you're guaranteed to eventually reach any arbitrary real number.

Why is it this way? Georg Cantor, a famous mathematician who is often considered the father of set theory, recognized upon proving that the reals were uncountable that the cardinality of the reals must be higher than the cardinality of the integers (much to the dismay and anger of his contemporary Kronecker), leading him to denote the cardinality of the reals as \(\aleph_1\), and then further hypothesize that there existed cardinalities \(\aleph_0, \aleph_1, \aleph_2,\dots\), and even that eventually there could be an infinity of infinities, perhaps denoted \(\tau_0\) and that even a \(\tau_0,\tau_1,\tau_2,\dots\) could possibly exist. But the biggest challenge for him, which eventually drove him to insanity, is whether there are values between alephs, that is, does \(2^{\aleph_0}=\aleph_1\), or is there a number in between \(\aleph_0\) and \(\aleph_1\)? This question is called the Continuum Hypothesis, and we now recognize it as a theorem that can be assumed either to be true or false without contradiction (thanks to David Hilbert, who put it on his list of homework problems from hell, Godel and Cohen for the undecidable conclusion, and Zermelo/Fraenkel for the ZF/ZFC set theory axiomatization that was very important and spawned further philosophical debate). --Robert.Moray (talk) 10:30, 29 September 2013 (EDT)

2. I believe the solution to Question 2 below may be incorrect. The solution uses two matrices which are not in the set of n x n diagonal matrices. The matrices should have zero values everywhere except the diagonal in order to be considered a diagonal matrix, if my understanding is correct. I would correct it, but I'm way too slow with LaTeX. I believe the correct answer is that set of diagonal \(n\times n\) matrices with no zeros on the diagonal is in fact a subgroup of \(GL(n,\mathbb{R})\), since it is a group, and it is in fact closed under the operation.

Yes, sorry, that's right. I was thinking symmetric, not diagonal matrices. I'll change it.

3. What is the Order (of an element of a group)? I can't seem to find the definition in the book. I know Prof. Jackson mentioned it quickly in class Oct 7, but I didn't get it all down.--Evan.Blanch (talk) 12:58,

Book Problems:

1. 5.7

   Which of the sets\[\mathbb{R}, \mathbb{Q}^+, 7\mathbb{Z}, i\mathbb{R}, \pi\mathbb{Q}, \{\pi^n|n\in\mathbb{Z}\}\] are subgroups of the group \(\mathbb{C}^*\) of nonzero complex numbers under multiplication? \(i\mathbb{R}\) is the set of pure complex numbers, and \(\pi\mathbb{Q}\) is the set of rational multiples of pi.

2. 5.9

   Is the set of diagonal \(n\times n\) matrices with no zeros on the diagonal a subgroup of \(GL(n,\mathbb{R})\), which is the set of invertible \(n\times n\) matrices with real number entries?

3. 5.22

   Describe the elements of the set generated by:

   \(\left [\begin{array}{cc}0 & -1\\ -1 & 0\end{array}\right ]\)

   (as a subgroup of \(GL(n,\mathbb{R})\).) (So the group operation is matrix multiplication.)

4. 5.23

   Do the same thing as for 5.22, but with the matrix:

   \(\left [ \begin{array}{cc} 1 & 1\\ 0 & 1\end{array} \right ]\)

5. 5.42

   Let \(\phi : G \rightarrow G^{\prime}\) be a group isomorphism. Prove that if \(G\) is cyclic, then \(G^{\prime}\) is cyclic.

6. 6.1

   Find the quotient and remainder of \(42/9\).

7. 6.3

   Find the quotient and remainder of \(-50/8\).

8. 6.5

   Find the greatest

Solutions:

Definitions

1. Subgroup.

   Definition:

   Let \(H\) be a subset of a group \((G,*)\) \(H\) is also a subgroup of \(G\) if it is closed under \(*\), and it is a group under \(*\).

   Example:

   The integers under addition are a subgroup of the real numbers under addition.

   Non-Example:

   The positive integers are not a subgroup of the integers under addition, because the positive integers lack an identity and inverses.

2. Improper Subgroup.

   Definition:

   If we have a group \(G\), \(G\) is the improper subgroup of itself.

   Example:

   The integers with addition are the improper subgroup of the integers with addition.

   Non-Example:

   The even integers with addition are not the improper subgroup of the integers with additon.

3. Trivial Subgroup.

   Definition:

   If we have a group \(G\), then the trivial subgroup of \(G\) is the subgroup consisting of only the identity element.

   Example:

   The group \((\{0\},+)\) is the trivial subgroup of the integers with addition.

   Non-Example:

   The even integers are not the trivial subgroup of the integers with addition.

4. Cyclic Subgroup.

   Definition:

   The cyclic subgroup of a group \(G\) generated by \(a\in G\) is the subgroup \(< a>\) of \(G\) such that \(< a > = \{a^n | n\in \mathbb{Z}\}\)

   Example:

   The even integers are a cyclic subgroup of the integers, generated by 2 (or -2).

   Non-Example:

5. Generator of a Cyclic Group.

   Definition:

   A generator of a group \(G\) is an element \(a\in G\) such that every element of \(G\) is a power of \(a\), i.e. \(\forall b\in G: \exists n\in \mathbb{Z}: b = a^n\)

   Example:

   1 is a generator of the integers under addition.

   Non-Example:

   2 is not a generator of the integers under addition.

6. Order of a Group.

   Definition:

   The order of a group is just the cardinality of the underlying set.

   Example:

   The order of the integers is \(\aleph_0\).

   Non-Example:

   The order of \(\mathbb{Z}/0\) is not 0.

7. GCD of Two Integers.

   Definition:

   The GCD of two integers is the greatest common divisor of the integers. For integers \(a,b\) their GCD is the greatest integer \(g\) such that \(a=ng\) and \(b=mg\) (i.e. \(g\) is the biggest integer that goes into both of the other integers evenly.

   Example:

   The GCD of 10 and 15 is 5.

   Non-Example:

   The GCD of 10 and 16 is not 5.

This is a theorem, not the definition. We actually define $\mathrm{GCD}(a,b)$ the be the non-negative generator of the subgroup of $\mathbb{Z}$ generated by $a$ and $b$. (This is a good definition even when one or both of $a,b$ are negative or zero. The theorem you quote is true only when both $a$ and $b$ are positive.) --Steven.Jackson (talk) 09:38, 8 October 2013 (EDT)

1. Relatively Prime.

   Definition:

   Two integers are relatively prime if their greatest common divisor is 1.

   Example:

   6 and 55 are relatively prime.

   Non-Example:

   6 and 9 are not relatively prime.

Theorems

1. Theorem Concerning Integer Division

   For any integers \(a\) and \(b\) with $b\neq0$, there are unique integers \(q\) and \(r\), such that \(0 \leq r < b\), and \(a=bq+r\).

2. Classification of Cyclic Groups

   Every cyclic group is isomorphic either to \(\mathbb{Z}\), or to \(\mathbb{Z}_n\). Specifically, infinite cyclic groups are isomorphic to \(\mathbb{Z}\), and groups of order \(n\) are isomorphic to \(\mathbb{Z}_n\).

3. Classification of Subgroups of \(\mathbb{Z}\)

   The subgroups of \(\mathbb{Z}\) under addition are the subgroups \(n\mathbb{Z}\), i.e. the subgroups of \(\mathbb{Z}\) are the cyclic subgroups generated by the elements of \(\mathbb{Z}\). (So the even integers, the multiples of 3, and 4, and 5, etc.) The subgroups $n\mathbb{Z}$ and $m\mathbb{Z}$ are equal if and only if $n=\pm m$.

4. Classification of Subgroups of \(\mathbb{Z}_n\)

   Take a cyclic group \(G\) with generator \(a\). This means that every element of \(G\) is a "power" of \(a\), i.e. \(\forall g\in G: \exists s \in \mathbb{Z}: g = a^s\). Furthermore, \(g\) generates a cyclic subgroup of \(G\) (possibly a trivial or improper subgroup, but a subgroup). This subgroup, \(<g>\), contains \(n/gcd(n,s))\) elements, and is therefore isomorphic to \(\mathbb{Z}_{n/gcd(n,s)}\). So for the cyclic group \(\mathbb{Z}_6 = <1>\), the subgroup generated by \(2=2*1 = 1^2\) is of order \(6/gcd(6,2) = 6/2 = 3\) elements, and is isomorphic to \(\mathbb{Z}_3\). We checked this in class\[<2> = \{1,2,4\}\]. The subgroups $\left\langle a\right\rangle$ and $\left\langle b\right\rangle$ are equal if and only if $\mathrm{gcd}(a,n) = \mathrm{gcd}(b,n)$.

Book Problem Solutions

1. 5.7

   \(\mathbb{R}\) is not a subgroup - it is not a group at all, because 0 has no multiplicative inverse. \(\mathbb{Q}^{+}\) is a subgroup, because all the positive rational numbers have inverses, 1 is an identity, and multiplication is associative. \(7\mathbb{Z}\) is not a subgroup - this is all the integer multiples of 7, which don't have inverses or an identity under multiplication. \(i\mathbb{R}\) is a not a subgroup - it is not closed under multiplication. \(\pi\mathbb{Q}\) is not a subgroup - it contains no identity or inverses. \(\pi^n\) is a subgroup - \(\pi^0\) is the identity, \(\pi^{-a}\) is the inverse of \(\pi^a\), multiplication is already associative, and \(\pi^n * \pi^m = \pi^{m+n}\), so it's closed.

2. 5.9

   This is not a subgroup, as it is not closed. Consider:

   \(\left [ \begin{array}{cc} 1 & -1 \\ -1 & 1\end{array}\right ] \times \left [ \begin{array}{cc} 1 & 1\\ 1 & 1\end{array}\right ] = \left[\begin{array}{cc} 0 & 0\\ 0 & 0\end{array} \right ]\)

   Please see me question about this in the "Questions" section above. I believe this answer may be incorrect.

   The first solution is incorrect. It makes use of symmetric, not diagonal matrices. The \(n\times n\) diagonal matrices with no zeroes on the diagonal is a group. Given two diagonal matrices \(A\) and \(B\), the \(i,i\) entry of \(A\times B\) is \(A_{i,i} * B_{i,i}\). So it is closed under inverses (set each entry of \(B\) to the inverse (in real multiplication) of the corresponding entry of \(A\)), it contains the identity (the matrix with all 1's on the diagonal) and it is closed under the operation: multiplying two non-zero real numbers always gives you a real number.

3. 5.22

   There are only two elements in this group:

   \(\left [ \begin{array}{cc} 0 & -1\\ -1 & 0 \end{array} \right ],\left [ \begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right ]\)

4. 5.23

   The elements of this group are all of the form ( with \(n\in \mathbb{Z}^+\):

   \(\left [ \begin{array}{cc} 1 & n\\ 0 & 1\end{array}\right ]\)

5. 5.42

   We need to show that \(\exists a^{\prime} \in G^{\prime}: G^{\prime} = <a>\). There is an element \(a \in G\) such that for every \(b\in G\), \(a^n = b\).Let \(a^{\prime} = \phi(a)\). Then, because \(\phi(a*b) = \phi(a)*\phi(b)\), and by surjectivity of isomorphisms, for any \(b^{\prime}\in G^{\prime}\), there is\[b \in G: b^{\prime} = \phi(b) = \phi(a^n) = \phi(a*a*\cdots*a) = \phi(a) * \phi(a) * \cdots *\phi(a) = a^{\prime} * a^{\prime} * \cdots *a^{\prime} = a^n\]. That last step isn't rigorous, it requires a proof by induction, but it's pretty obvious that it's true.

6. 6.1

   The quotient is 4 and the remainder is 6.

7. 6.3

   The quotient is -7 and the remainder is 6.

8. 6.5

   The greatest common divisor is 8.

9. 6.9

   So given an element \(a^s \in G\), the order of the subgroup it generates is \(n/gcd(n,s)\). We need the order of the generated subgroup to be 8, i.e. we need \(gcd(n,s) = 1\). The positive integers less than 8 that are relatively prime to 8 are 1, 3, 5 and 7. So there are four generators of this group.

10. 6.23

    So we have, to start, the trivial subgroup and the improper subgroup. The other subgroups will all be generated by elements of \(\mathbb{Z}_36\) that are not relatively prime to 36. Furthermore, two subgroups will be equal if they are generated by elements whose greatest common divisors with 36 are the same. So we need to create an equivalence relation where two integers \(n\) and \(m\) are equivalent if \(gcd(n,36) = gcd(m,36)\).

    List of elements by gcd(n,36):

    • gcd = 1: 1,5,7,11,13,17,19,23,25,29,31,35
    • gcd = 2: 2,10,14,20,22,26,34
    • gcd = 3: 3,15,21,33
    • gcd = 4: 4,8,16,28,32
    • gcd = 6: 6,30
    • gcd = 9: 9,27,
    • gcd = 12: 12,24
    • gcd = 18: 18
    So we have 10 subgroups\[<0>,<1>,<2>,<3>,<4>,<6>,<9>,<12>,<18>\]. The subgroup diagram is kind of complicated, so I'm not going to try to draw it. But, for two subgroups \(n\) and \(m\)\[<m>\subset <n>\] if and only if \(n\) divides \(m\).

11. 6.27

    The orders of the subgroups are the factors of 12. So there are subgroups of order 1, 2, 3, 4, 6, and 12, given by \(<0>,<6>,<4>,<3>,<2>,<1>\) respectively. (A subgroup of \(\mathbb{Z}_n\) of order \(m\) is generated by \(n/m\), as long as this divides evenly.

12. 6.30

    I think this is already correct.

Actually the order of $a$ is the least positive integer $n$ such that $a^n=e$. (If no such integer exists we say that $a$ has infinite order.) --Steven.Jackson (talk) 09:38, 8 October 2013 (EDT)