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 7^{2}, so |G| = 49.

- [3] Let {f
_{1}, f_{2}, ...} be a sequence of integers such that f_{1}\ge 2 and for i > 0 such that f_{i+1}>= 2f_{i}- 1. Prove that f_{n}>= (2^{n}+2)/2 is true for all integers n > 0.

First, f_{1}\ge 2 = (2^{1}+2)/2 so f_{n}>= (2^{n}+2)/2 is true for n = 1. Now assume f_{n}>= (2^{n}+2)/2 is true for some n >= 1; we will show that f_{n+1}>= (2^{n+1}+2)/2 is true, and hence f_{n}>= (2^{n}+2)/2 is true for all n > 0. But f_{n}>= 2f_{i}- 1 >= 2(2^{n}+2)/2 - 1 = (2^{n+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}= gh^{i}g^{-1}.)

First, note that (ghg^{-1})^{i}= gh^{i}g^{-1}is true for i = 1, and if (ghg^{-1})^{i}= gh^{i}g^{-1}is true for some i >= 1, then (ghg^{-1})^{i+1}= (ghg^{-1})^{i}(ghg^{-1}) = (gh^{i}g^{-1})(ghg^{-1}) = gh^{i}(g^{-1}g)hg^{-1}= (gh^{i+1}g^{-1}. Thus (ghg^{-1})^{i}= gh^{i}g^{-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}= gh^{k}g^{-1}, so e = g^{-1}eg = g^{-1}gh^{k}g^{-1}g = eh^{k}e = h^{k}, so | h | <= k = |ghg^{-1}|, which contradicts |ghg^{-1}| < |h|. Similarly, if |ghg^{-1}| > |h|, then |h| is finite, say |h| = n. Then e = h^{n}so e = geg^{-1}= gh^{n}g^{-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 g
^{n}= e. Prove that N is a subgroup of G.

First, e^{n}= e so e is in N. Also, if g is in N, then g^{n}= e so (g^{-1})^{n}= (g^{n})^{-1}= e^{-1}= e, so g^{-1}is in N. And finally, if a and b are in N, then a^{n}= e and b^{n}= e, so (ab)^{n}= a^{n}b^{n}= ee = e (we used the fact that G is abelian to get (ab)^{n}= a^{n}b^{n}), 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.

- (a) Write (1 2 3 4 5 6)
- [7] Consider the group
**Z**_{899}of integers modulo 899. Note that 899 = 29(31). For each positive integer n, determine the number of elements of**Z**_{899}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.