# Math 417 Homework 1: Due Friday January 24

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.
• [1] If X and Y are sets and f : X -> Y and g : Y -> X are functions such that fg = 1Y and gf = 1X, show that f is bijective.

By Lemma 1 (January 17) we know that if gf = 1X, then f is injective and g is surjective. Thus f is injective. But we also are given that fg = 1Y. Applying Lemma 1 again we see that f (the one on the left) is surjective (and g is injective). Thus f is injective and surjective, hence bijective.

• [2] Let X be a nonempty set. If f and g are elements of Perm(X), show that fg is too. (Hint: First show fg is injective, then show fg is surjective. You can cite results from the book, if that is helpful, but then be sure you understand the book's proof of the result you cite!)

We first check that fg is injective. Suppose that (fg)(b) = (fg)(c) for some elements b, c of X. (It's not easy to generate a composition symbol that all web browsers understand, so I'm using (fg) instead. However, it' s easier to type fg(b) for (fg)(b), so that's what I'll do hereafter.) This means f(g(b)) = f(g(c)). Since f is a permutation, it is bijective, hence injective, hence f(g(b)) = f(g(c)) implies g(a) = g(b). But for the same reason g is injective too, so it follows that a = b. Thus fg is injective.
Now we check that fg is surjective. Let x be an arbitrary element of X. Since f is surjective, there is an element y such that f(y) = x. But g is also surjective, so g(z) = y for some z. Now we have fg(z) = f(y) = x, so fg is surjective.
Since fg is injective and surjective, it is bijective, hence fg is a permutation; i.e., fg is an element of Perm(X), as we wanted to show.

I now want to give an alternate proof, but I need some new notation. Given any sets A and B and any function h : A -> B, let C be a subset of A. Define h(C) to be the set { h(a) : a is an element of C }; we call h(C) the image of C under h. It is just the set of all values of h that you get by plugging in elements from C. (Thus given a function h from A to B, we also get a function from the set of subsets of A to the set of subsets of B, which is also usually denoted h. Using the same name for two different things is usually verboten because it is too confusing, but this is what's done in this case. It is not usually a problem, because you can tell which h is meant by seeing what is being plugged into it, either an element or a subset.)
One more bit of notation. Given our function h : A -> B and any subset D of B, let h-1(D) be the subset { a in A : h(a) is in D }, called the inverse image of D under h. Note that this defines a function from the set of subsets of B to the set of subsets of A. (The notation h-1 for the inverse image function is unfortunate, since the same notation is used for the inverse function, when it exists. But not all functions have an inverse under composition, only the bijective ones do. However, for any function you always have the inverse image function. Again you can tell whether h-1 refers to the inverse function or the inverse image function by whether what is being plugged in is an element of B or a subset of B.)
Note that saying h is surjective is the same thing as saying that h(A) = B; i.e., everything in B is the image under h of something in A. And saying that h is injective is the same as saying that | h-1({b}) | <= 1 for every element b of B; i.e., each element of B is the image under h of at most one element of A.
Now the proof: since f and g are permutations, both are bijective, hence injective and surjective. Since both are surjective we have g(X) = X and f(X) = X, hence fg(X) = f(g(X)) = f(X) = X. Thus fg is surjective. And given any y in X, suppose we pick b and c from (fg)-1({y}). Then fg(b) = y = fg(c), but f is injective so g(b) = g(c), and g is injective so b = c. Thus (fg)-1({y}) has at most one element, so fg is injective. Thus fg is surjective and injective, hence bijective.

• [3] If X is a finite set of |X| = n elements, show that |Perm(X)| = n!.

First note that if A is a finite set and f is an injective function f : A -> A, then f is surjective. To see this, using the notation introduced in the alternate proof of [2] above, note that being injective means that |f(A)| = |A|; i.e., the number of elements you get by plugging elements of A into f is just the number you started with, |A|. But f(A) is a subset of A, so this means that f(A) = A, so f is surjective. Thus the set of injective functions from A to A is the same as the set of bijective functions. Thus to count Perm(A), it is enough to count the injective functions from A to A. We'll do this in the case of our finite set X. Enumerate the elements of X as X = { x1, x2, ... , xn }. To define a function f : X -> X, we simply need to specify f(xi) for each i, and for f to be injective it is enough that f(xj) never equals f(xi) for i1) so there are n possible assignments. To f(x2) we can assign anything except f(x1), so there are n-1 choices. Continuing in this way, we see that there are n(n-1)(n-2)...(3)(2)1 = n! injective (and hence bijective) assignments. I.e., |Perm(X)| = n!.

• [4] Give two reasons why the set of all odd integers does not form a group under the operation of addition.

One reason is that + is not a binary operation on the set of odd integers, since the sum of any two odds is even. Also, there is no identity element (since there is no operation), and elements don't have inverses.

• [5] Let X be the set of all real numbers except -1 (i.e., X = R - {-1}). Define a binary operation * on X by the rule a*b = ab + a + b.

Note that * is a binary operation. Certainly it defines a binary operation on the set R of all real numbers. The question is: given b and c in X, is b*c always in X (i.e., never equal to -1)? But -1 = b*c = bc + b + c = (b+1)(c+1) - 1 implies (b+1)(c+1) = 0, and hence either b = -1 or c = -1, which would mean that either b or c wasn't in X to begin with. Thus * really is a binary operation on X. means that either

• (a) Does * have an identity element? If so, what is it?

Yes, 0 is an identity for *: a*0 = a0 + a + 0 = a and 0*a = 0a + 0 + a = a.

• (b) Is * associative?

Yes. We have to check that a*(b*c) = (a*b)*c for any a, b and c in X. But a*(b*c) = a*(bc + b + c) = a(bc + b + c) + a + (bc + b + c) and (a*b)*c = (ab + a + b)*c = (ab + a + b)c + (ab + a + b) + c, but it's easy to see that a(bc + b + c) + a + (bc + b + c) = (ab + a + b)c + (ab + a + b) + c.

• Is X a group under *?

Yes. All we need to check is that every element has an inverse with respect to *. But if b is in X, let c = -b/(b+1). Since b is not -1, we know -b/(b+1) is defined and it is not itself -1 (since -b/(b+1) = -1 implies 0 = -1). But now b*c = bc + b + c = b(-b/(b+1)) + b + (-b/(b+1)) = 0, and similarly (or noting that * is commutative) we see that c*b = 0. Thus the inverse of b is -b/(b+1).