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).