MA10209 Algebra 1A

Sheet 2 solutions: GCS

5-x-12

This work to be handed in Hand in work to your tutor by 13:00, Monday Oct 15.
1. In each case, determine whether the statement really defines a map, or it is defective in some way.
(a) f : C C defined by f (z) = 1/z for each z C.
Solution This is not a map because f (0) is not assigned a value. You could rectify this by making 0 an
exception, and defining f (0) as you please.
(b) g : C C defined, for each z C, by letting g(z) be the complex number such that g(z)2 = z.
Solution This is not a map because the alleged recipe is ambiguous. For example i2 = (i)2 = 1, so
g(1) is not properly defined.
(c) h is the function cos x.
Solution This is not a map because neither domain nor codomain is specified.
(d) j : R R defined, for each x R, by j(x) = sin(cos(tan(x))).
Solution This is not a map because tan /2 is not a real number.
p

(e) k : Q Q by, for each x Q, k(x) = |x| (with the convention that
means take the non-negative
square root).

Solution This is not a map because 2 6 Q.

2. In each case, determine which of the properties injectivity, surjectivity and bijectivity are enjoyed by the given
function. Please give reasons.
(a) f1 : N Z defined by f1 (x) = x2 for each x N.
Solution This map is injective because if m, n N and f1 (m) = f1 (n), then m2 = n2 so (mn)(m+n) = 0
and so m = n. It is not surjective since 1 is not a square of a natural number. Since this map is not
surjective, it is also not bijective.
(b) f2 : Z Z defined by f2 (x) = x2 for each x Z.
Solution This map is neither injective nor surjective. It is not injective because 12 = (1)2 . It is not
surjective because 1 is not a square of an integer. This miserable map is therefore not bijective.
(c) f3 : C R defined by f3 (x) = |x| for each x C.
Solution This map is not injective since f3 (1) = f3 (1). It is not surjective since |x| is never negative.
Therefore f3 is not bijective.
(d) f4 : C {r2 | r R} defined by f4 (x) = |x| for each x C.
Solution It is not injective because 12 = (1)2 . However, it is surjective because if y {r2 | r R},
then f4 (y) = y. This map is therefore not bijective.
(e) f5 : N {1, 2, 3, 4, 5, 6, 7, 8, 9} defined by letting f5 (x) be the leftmost digit in the ordinary base 10
(decimal) representation of n.
Solution This map is not injective because f5 (1) = 1 = f5 (10). However, it is surjective because if
z {1, 2, 3, 4, 5, 6, 7, 8, 9}, then f5 (z) = z. This map is therefore not bijective.
(f) f6 : {r | r R, /2 < r < /2} R defined by letting f6 (x) = tan x.
Solution The map tan is well-defined on this interval (dodgy places such as /2 are not in the domain),
and is strictly increasing. It is therefore injective. Also between /2 and /2, tan assumes all real values.
This function is therefore surjective and hence bijective.
3. Let In = {1, 2, . . . n} be the set which consists of the first n natural numbers, and let S = {0, 1}. In each case
you should justify your answer, for a numerical response will not suffice.

(a) How many maps f are there such that f : In S?

Solution You can define a map by a finite sequence of n independent choices: f (1) can be 0 or 1, then
f (2) can be 0 or 1 and so on. There are 2n such sequences of choices, and so 2n such maps. It is no accident
that the choices, viewed as lists of digits, are the numbers from 0 to 2n 1 written in binary, with initial
strings of zeros as padding on the front to make the string have length n.
(b) How many surjective maps f are there such that f : In S?
Solution There are 2n maps from In to S, of which two, the constant maps, are not surjective. Therefore
there are 2n 2 surjective maps.
(c) How many injective maps f are there such that f : In S?
Solution If n > 2 there are none. If n = 2 there are two injective maps (the bijective maps). If n = 1
there are two injective maps.
(d) How many bijective maps f are there such that f : In In ?
Solution There are n choices as to the value of f (1). Having defined f (1), there are n 1 choices for the
value of f (2) and so on. The total number of bijections is therefore n!.
(e) How many surjective maps f are there such that f : In In ?
Solution A surjective map from a set of size n to a set of size n must also be injective, and therefore
bijective. Conversely, any such bijective map must be surjective. Therefore this question is simply a
repetition of the previous question, so the answer is n!
(f) How many injective maps f are there such that f : In In ?
Solution An injective map from a set of size n to a set of size n must also be surjective, and therefore
bijective. Conversely, any such bijective map must be injective. Therefore this question is simply a
repetition of the previous question, so the answer is n!
4. Let f : A B be a map. Let X = {f (a) | a A} B. Show that there is a (natural) surjective map
g : A X and a (natural) injective map h : X B such that f = h g. Hint: There are obvious recipes
which define the maps g and h. This is what the word natural means in this context.
Solution Define g by g(a) = f (a) for each a A. This is clearly surjective. Define h : X B by h(x) = x
for every x X. This is clearly injective. Moreover, if a A, then (h g)(a) = h(g(a)) = h(f (a)) = f (a).
Now h g and f have the same domain, the same codomain, and act the same way, so h g = f . This is an
interesting factorization result: any map can be expressed as a surjective map composed with an injective map;
surjective first, injective last.
5. Suppose that f : A B and g : B C are maps. In each case, you should either give a proof that the result
follows, or a specific example to show that it does not follow.
(a) Suppose that g f is injective. Does it follow that f is injective?
Solution Yes it does follow that f is be injective. This is because if a1 , a2 A and f (a1 ) = f (a2 ), then
g(f (a1 )) = g(f (a2 )) and so (g f )(a1 ) = (g f )(a2 ). However, g f is injective so a1 = a2 .
(b) Suppose that g f is injective. Does it follow that g is injective?
Solution It does not follow. Let A = {1}, B = {1, 2} and C = A. Define f by f (1) = 1, and g by
g(1) = 1 and g(2) = 1. Therefore g is not injective but g f : {1} {1} is defined by (g f )(1) = 1 and
is injective.
(c) Suppose that g f is surjective. Does it follow that f is surjective?
Solution It does not follow. Let A = {1}, B = {1, 2} and C = A. Define f by f (1) = 1, and g by
g(1) = 1 and g(2) = 1. Therefore f is not surjective but g f : {1} {1} is defined by (g f )(1) = 1
and is surjective.
(d) Suppose that g f is surjective. Does it follow that g is surjective?
Solution Yes it does follow that g must be surjective. Suppose that c C. Now g f is surjective so
there is a A such that (g f )(a) = c. Therefore g(f (a)) = c. Now f (a) B and has the property that
g(f (a)) = c. Therefore g is surjective.
6. Suppose that f : A A and g : A A. In each case, you should either give a proof that the result follows,
or a specific example to show that it does not follow. We omit brackets from compositions of three (or more)
functions since the associative law has been established.

(a) Suppose that g f and f g are both bijective. Does it follow that f and g are both bijective?
Solution By 5(a) both f and g are injective. By 5(d) both f and g are surjective. Therefore both f and
g are bijective.
(b) Suppose that f f is bijective. Does it follow that f is bijective?
Solution By 5(a) f is injective. By 5(d) f is surjective, Therefore f is bijective. Alternatively use 6(a)
and put g = f .
(c) Suppose that f g f is bijective. Does it follow that g is bijective?
Solution f g f = (f g) f so by 5(a), f is injective. Also f g f = f (g f ), so by 5(d) f is
surjective. Therefore f is bijective and has an inverse map f 1 . Now f 1 (f g f ) is the composition
of bijective maps and so is bijective. However f 1 (f g f ) = (f 1 f ) (g f ) = IdA (g f ) = g f
is bijective. Now (g f ) f 1 = g (f f 1 ) = g IdA = g is the composition of bijective maps and so is
bijective.
7. Consider the maps f, g : Z Z defined by f (x) = x + 1 for each x Z and g(x) = 2x for each x Z.
(a) Determine all maps h : Z Z such that f h = h f .
Solution Suppose that h is such a map. Then h(x) + 1 = h(x + 1) for each integer x (?). Let h(0) = t
for some t N. We claim that h(y) = t + y for every y Z.
We will prove this by induction on y when y N. Suppose that the result is true when y = r and try to
deduce that the result holds when y = r + 1. Now h(r + 1) = h(r) + 1 by (?). By inductive hypothesis,
h(r) = t + r so h(r + 1) = h(r) + 1 = (t + r) + 1 = t + (r + 1). This is precisely what is required, so
h(y) = t + y for all natural numbers y.
Now suppose that y < 0. Let z = y. We will prove by induction on z N that h(z) = t z. This result
holds when z = 0. Suppose that the result holds when z = r, and try to deduce that the result holds when
z = r + 1. Now h(r) = h(r 1) + 1 by (?). Therefore h(r 1) = h(r) 1. Now h(r) = t r by
inductive hypothesis. Therefore h(r 1) = (t r) 1 = t (r + 1). This is precisely what is required,
so h(y) = t y for all natural numbers y.
Since h(0) = t, it follows that h(x) = t + x for all integers x.
We have not finished, because all we have done is to show that if h commutes (in the sense of composition)
with f , then h must be one of these maps given by the recipe h(x) = t + x where t is fixed, and x is
arbitrary. We have to check to see if any of the maps of this form actually do commute with f . Suppose
that t is an integer and that h(x) = t + x for all x Z. We need to compare f h and h f . They
both have domain Z and codomain Z, so the action is the only thing at issue. Suppose that w Z. Then
(f h)(w) = f (h(w)) = f (t+w) = t+w +1. On the other hand (hf )(w) = h(f (w)) = h(w +1) = t+w +1.
Therefore f h = h f and all maps of the given form commute with f . Note, by the way, that all these
maps h are bijections, something which was not specified in advance.
(b) Determine all maps j : Z Z such that g j = j g.
Solution A map j : Z Z satisfies our condition if, and only if, g(j(x)) = j(g(x)) i.e. 2j(x) = j(2x)
for each x Z. We can manufacture functions which obey this condition readily: for odd m we assign the
value of j(m) arbitrarily (i.e. just select an integer value, and you can choose different values for different
odd m). The value 0 is special, since 2j(0) = j(0) so j(0) = 0. If n is even but not 0, define f (n) to be
2f (n/2). This is an inductive definition, since if n/2 happens to be even, the definition requires f (n/2) to
be 2f (n/4) and so on. Any map we make in this way will satisfy the condition, and so will commute with
g.
(c) Determine all maps k : Z Z such that both f k = k f and g k = k g.
Solution We are looking for functions k which arise as solutions to both previous parts. Thus there must
be an integer t such that k(x) = t + x for each x Z by part (a). Now from part (b), k(0) = 0 so t = 0.
We need look no further. There is only one possibility; k is the identity function. Now IdZ does commute
with f and g, and in fact it (composition) commutes with all maps from Z to Z.
8. Exhibit (i.e. give examples of) bijections between the given sets:
(a) Domain N, codomain Z.
Solution We define such a map f : N Z. If n is even, let f (n) = n/2. If n is odd, then f (n) = (1n)/2.

(b) Domain N2 , codomain Z.

Solution Let X = {2u 3v | u, v N} N. Define a map g : N2 X by g((u, v)) = 2u 3v for all (u, v)
N2 . Now g is surjective by design. It is also injective because if 2u1 3v1 = 2u2 3v2 then 2u1 u2 = 3v2 v1 .
Therefore u1 = u2 and v1 = v2 as required.
Define a map h : X N as follows. List the elements of X in ascending order of size as x1 , x2 , x3 , . . ..
Let h(xi ) = i. This is clearly a bijection. Now h g : N2 N is a composition of bijections and so is a
bijection. If we now borrow the map f from part (a), we find that f (h g) : N2 Z is a composition
of bijections and so is a bijection as required.
(c) Domain {r | r R, 0 < r < 1}, codomain R.
Solution Define a map g : {r | r R, 0 < r < 1} {r | r R, /2 < r < /2} via g(t) = r /2.
We must verify that this is a bijection (at some point we you will be able to regard this as obvious, but
at the moment we are still being scrupulous). In terms of the number line, multiplication by is a an
enlargement from 0. Then subtraction of /2 is a translation. The interval {r | r R, 0 < r < 1} is thus
stretched to have the correct length by holding its (non-existent) left end still, and pulling its (non-existent)
right end to the right until the interval has length . The resulting interval is then slid to the left. We must
express this more formally. We have a map from {r | r R, 0 < r < 1} to {r | r R, 0 < r < } defined
by multiplication by . There is also a map from {r | r R, 0 < r < } to {r | r R, /2 < r < /2}
defined by subtraction of /2. Perhaps the recipes which define these two maps are so easy that we will
allow ourselves to say that they are each obviously bijections. Their composition is therefore a bijection as
required.
Now borrow the map f6 from 2(f), and form the composition of bijections f6 g : {r | r R, 0 < r <
1} R, which must be a bijection.
(d) (interesting) Domain {A | A N, |A| < }, codomain N.
Solution Let S = {A | A N, |A| < }. Given s S, define a sequence a1 , a2 , a3 , . . . by ai = 1 if i s,
and ai = 0 if i 6 s. Then write this sequence backwards and read it as a binary number, and finally add 1
(to stop yourself getting 0 6 N when s = ). Put another way, define : S N by
(s) = 1 +

aj 2j1 .

j=1

The apparently infinite nature of this sum is spurious, since all but finitely many summands are 0. In fact
one should neglect all such summands, so that we end up doing algebra rather than analysis. An exception
must be made for the empty set, and then () = 1. The map is injective, since different non-negative
integers have different
binary representations. Moreover, is surjective, since if m N {0} has binary
P
j1 , then we define t S via i t if, and only if, a = 1. Then (t) = m + 1.
a
representation
i
j=1 j 2
9. (A little trickier) Suppose that S is a finite set of size n and that f : S S is a bijection. Define f 0 = IdS
and if m > 0 is a positive integer, then we define f m to be f f m1 . Prove that f n! = IdS , the identity map
from S to S.
Solution If S = the result is clear so we may assume that S 6= . Suppose that s S. Consider the n + 1
terms s, f (s), f 2 (s), . . . , f n (s). We introduce the notation f 0 (s) for s. Since there are only n elements of S, two
of these terms must coincide (they must be the same). Therefore there are integers u, v with 0 u < v n
such that f u (s) = f v (s). Now f is a bijection with inverse f 1 . Apply the map (f 1 )u to both sides, to discover
that s = f vu (s). Now 0 < v u = k n. Therefore there is a positive integer k with k n and f k (s) = s.
Now k is a divisor of n! since it appears in the list 1, 2, 3, . . . , n. Therefore n! = kl for some positive integer l.
Now
f n! (s) = f kl (s) = (f k f k f k )(s)
where there are l maps of the form f k being composed. Now f k (s) = s so f n! (s) = s. Since s S was arbitrary,
this forces f = IdS .
10. Tutor pacifier. For enthusiasts only. Prove that there exist two functions f, g : R R such that f g is
strictly decreasing and g f is strictly increasing. A map h : R R is said be strictly increasing (respectively
decreasng) if whenever x, y R and x < y, then h(x) < h(y) (respectively h(x) > h(y)).
Solution Not yet!