Math 417 Homework 6: Due Friday March 7
Instructions: You can discuss these problems with others,
but write up your solutions on your own (i.e., don't just
copy someone else's solutions, else the feedback I give
you won't help you much). Please be neat and write in full sentences.
Do four of the eight problems, the four you didn't do on the exam.
- [1] Let h: A -> B be a function from a set A to a set B.
If h: A -> B is surjective, show that
h-1 : Subsets(B) -> Subsets(A) is injective.
Let E and F be subsets of B such that h-1(E) = h-1(F). Let b be any element of E;
since h is surjective, there is an a with h(a) = b. By definition, a is in h-1(E).
But h-1(E) = h-1(F), so b = h(a) is in F. I.e., every element of
E is also in F. Thus F contains E.
The same argument, starting with an element of F shows that E contains F. Thus E = F,
so h-1 is injective.
- [2] Let G be a group which has exactly three different subgroups,
including a proper subgroup H of order 7. Show that G is cyclic,
and determine |G|.
Since H is a proper subgroup, we can pick an element g of G that is not in H.
But the only subgroups of G are {e}, H and G, and g is not in {e} or H,
so <g> must be G itself.
Thus G is cyclic. (It is also finite, since every nontrivial subgroup of an
infinite cyclic group is infinite.) Now 7 divides |G| by Theorem 4.3, so we can write
|G| = 7k for some positive integer k. Since G has exactly 3 subgroups,
|G| can have only three positive divisors. Two of them are 1 and 7; if k = 1, these are the only
two, but that would mean that G has only two subgroups. Thus k is bigger than 1.
But if k is bigger than 1 but not 7, then |G| has at least four divisors:
1, 7, k and 7k. This would mean that G has at least four subgroups. Thus k must be 7
and the prime factorization of |G| must be 72, so |G| = 49.
- [3] Let {f1, f2, ...} be a sequence of integers such that
f1\ge 2 and for i > 0 such that fi+1 >= 2fi - 1.
Prove that fn >= (2n+2)/2 is true for all integers n > 0.
First, f1\ge 2 = (21+2)/2 so fn >= (2n+2)/2
is true for n = 1.
Now assume fn >= (2n+2)/2 is true for some n >= 1; we will show that
fn+1 >= (2n+1+2)/2 is true,
and hence fn >= (2n+2)/2 is true for all n > 0.
But fn >= 2fi - 1 >= 2(2n+2)/2 - 1 = (2n+1+2)/2,
as we wanted to show.
- [4] Let g and h be elements of a group G. Note that G need not be finite.
Prove that |ghg-1| = |h|. (Hint: show that
(ghg-1)i = ghig-1.)
First, note that (ghg-1)i = ghig-1
is true for i = 1, and if (ghg-1)i = ghig-1
is true for some i >= 1, then (ghg-1)i+1 =
(ghg-1)i(ghg-1) = (ghig-1)(ghg-1) =
ghi(g-1g)hg-1 = (ghi+1g-1.
Thus (ghg-1)i = ghig-1 is true for all i >= 1.
Now, if |ghg-1| = |h| were false, then either
|ghg-1| < |h| or |ghg-1| > |h|.
First, let's say |ghg-1| < |h|. Then |ghg-1| is finite,
say |ghg-1| = k. Then e = (ghg-1)k =
ghkg-1, so e = g-1eg = g-1ghkg-1g
= ehke = hk, so | h | <= k = |ghg-1|, which contradicts
|ghg-1| < |h|. Similarly, if |ghg-1| > |h|, then |h| is finite,
say |h| = n. Then e = hn so e = geg-1 = ghng-1
= (ghg-1)n, so |ghg-1| <= n = |h|, which again is a
contradiction. The only way out is for |ghg-1| = |h|.
- [5] Let G be an abelian group. Let n be a fixed positive integer.
Let the subset N of G be the set of all elements g in G such that gn = e.
Prove that N is a subgroup of G.
First, en = e so e is in N. Also, if g is in N, then gn = e
so (g-1)n = (gn)-1 = e-1 = e,
so g-1 is in N. And finally, if a and b are in N, then
an = e and bn = e, so (ab)n = anbn = ee = e
(we used the fact that G is abelian to get (ab)n = anbn),
so ab is in N. Thus N is a subgroup.
- [6]
- (a) Write (1 2 3 4 5 6)3 as a product of disjoint cycles.
Answer: (1 2 3 4 5 6)3 = (1 4)(2 5)(3 6)
- (b) Write (1 2 3)(1 2)(3 4) as a product of disjoint cycles.
Answer: (1 2 3)(1 2)(3 4) = (1 3 4)
- (c) Find |(1 2 3)(1 2)| and show how you find your answer.
Answer: (1 2 3)(1 2) = (1 3) so |(1 2 3)(1 2)| = |(1 3)| = 2.
- [7] Consider the group Z899 of integers modulo 899. Note that
899 = 29(31). For each positive integer n, determine the number of
elements of Z899 of order n. Explain how you obtain your answer.
In a finite cyclic group G, the order of an element divides the order of the group,
so the number of elements of order n is 0 if n is not 1, 29, 31 or 899.
Also, if k divides |G|, then the number of elements of order k is phi(k).
Thus there are phi(899) = phi(29)phi(31) = (29 - 1)(31 - 1) = 840 elements
of order 899, phi(31) = 30 elements of order 31, phi(29) = 28 elements of order 29,
and phi(1) = 1 element of order 1.
- [8] Give an example of a group G and a nonempty subset
H of G such that whenever a is in H and b is in H we
have ab in H, but nonetheless H is not a subgroup of G.
Let G be Z, the group of integers under addition, and let H be the positive integers.
Then H is nonempty and closed under addition, but it has no identity and no inverses, so
H is not a subgroup. Note that H needs to be an infinite subset, since otherwise we
have a theorem that tells us H would be a subgroup.