Worksheet 11 - Hints and Selected Solution
1. For which sets A is it the case that the only bijection
from A to A is the identity?
Answer. For sets A consisting of exactly one element, as well as for the empty
set.
2. Let A be the set of the days of the week. Let f assign to each day of the
week the number of letters
in its name in English. Is f an injection?
Answer. No. f(Monday) = f(Sunday) but Monday ≠ Sunday.
3. Let A be the set of subsets of 
that have
even size, and let B be the set of subsets of
that have odd size. Establish a bijection
from A to B. (
)
Proof. Let A be the collection of even-sized subsets of
, and let B be the collection of
odd-sized subsets. For each x ∈ A, define f(x) as follows:
By this definition, #(x) and #(f(x)) differ by one, so f(x)
is a set of odd size and f maps A into
B.
We claim first that f is one-to-one. Consider distinct x, y ∈ A. If both
contain or both omit n,
then f(x) and f(y) agree on whether they contain n but differ outside {n}. If
exactly one of {x, y }
contains n, then exactly one of {f(x), f(y)} contains n. Thus f(x) ≠ f(y), and f
is one-to-one.
We next claim that f is onto. If z ∈ B, then flipping whether n is present
in z yields a subset x
such that f(x) = z, so f is also onto, and hence f is a bijection.
4. Verify that 
defines a bijection from the
interval [0, 1] to R. (Hint: In the proof that
f is surjective, use the quadratic formula.) ()
Proof. f is injective Suppose that f(x) = f(y). Then we obtain that
(2x - 1)2y(1 - y) = (2y - 1)2x(1 - x),
which simplifies further to 2(y2 - x2) - 2(y - x) = 4xy(y - x). If y ≠ x, then
we can divide
by 2(y - x) to obtain y + x - 1 = 2xy. Rewriting this as -xy = (x - 1)(y - 1)
makes it clear
that there is no solution when x, y ∈[ 0, 1], since the left side is negative and
the right side is
positive. Therefore we conclude that x = y, and so f is injective.
f is surjective Suppose that f(x) = b. We solve for
x to obtain x ∈[0, 1] such that f(x) = b.
Observe that b = 0 is achieved by 
, so we may assume that b ≠ 0. Clearing fractions
leads to 
, or
. The quadratic formula yields
The magnitude of the square root is larger than lbl.
Therefore, choosing the negative sign in
the numerator yields a negative x, which is not in the domain of f. We therefore
choose the
positive sign.
If b > 0, then the square root is less than b + 1, and we obtain
. Also, the
square root is bigger than 1, so x > 0. If b < 0, then let b' = -b. The formula
for x becomes
, where b' > 0. the square root is strictly between 1 and
b' + 1, so x is
strictly
between 1/2 and 0. In each case, we have found x in the domain [0, 1] such that f(x) = b,
and
we have thus established that f is onto.
5. Let f and g be surjections from R to R, and let h = fg be their product. Must
h also be surjective?
Give a proof or a counterexample.
Counterexample. Let f, g : R → R be defined by f(x) = g(x) = x. Then both f and
g are
surjective, but (f ยท g)(x) = x2 is not surjective.
6. Determine which formulas below define surjections from
onto 
:
(a) f(a, b) = a + b.
Answer. Not surjective. (Why?)
(b) f(a, b) = ab.
Answer. Surjective. (Why?)
(c) f(a, b) = ab(b + 1)/2.
Answer. Surjective. (Why?)
(d) f(a, b) = (a + 1)b(b + 1)/2.
Answer. Not surjective. (Why?)
(e) f(a, b) = ab(a + b)/2.
Answer. Not surjective (Why?)
7. Given f : R → R, suppose that there are positive constants c, α such that
for all x, y ∈ R,
. Prove that f is injective.
Proof. Suppose that f is not injective. Then there exist distinct numbers x and
y such that
f(x) = f(y). Since 
, this contradicts the hypothesis.
8. If f : A → B and g : B → C are bijections, prove that
.
Proof. We use exercise 11. Since f and g are bijections, both are invertible. Note that
and
9. Given f : A → B and g : B → C, let h = g o f. Determine
which of the following statements are
true. Give proofs for the true statements and counterexamples for the false
statements.
(a) If h is injective, then f is injective.
Answer. True. (Why?)
(b) If h is injective, then g is injective.
Answer. False. (Why?)
(c) If h is surjective, then f is surjective.
Proof. False. (Why?)
(d) If h is surjective, then g is surjective.
Proof. True. (Why?)
10. Consider f : A → B and g : B → A. Answer each question below by providing a
proof or a
counterexample.
(a) If f(g(y)) = y for all y ∈ B, does it follow that f is a bijection?
Proof. No. (Why?)
(b) If g(f(x)) = x for all x ∈ A, does it follow that f(g(y)) = y for all y ∈ B?
Proof. No. (Why?)
11. Consider f : A → B and g : B → A. Prove that if f o g and g o f are identity
functions, then f is
a bijection. In particular, prove that
(a) If f o g is the identity function on B, then f is surjective.
Proof. If y ∈ B then f(g(y)) = y. Hence there is an element of A mapped to y by
f, namely,
the element g(y). This shows that f satisfies the definition of a surjection.
b) If g o f is the identity function on A, then f is
injective.
Proof. If x ∈ A, we have that g(f(x)) = x. If f is not injective, then there
exist distinct
elements 
∈ A such that
. If we apply g to both sides of the
equality,
we obtain 
, which contradicts our choice of
distinct elements.
Hence our assumption that f is not injective must be wrong.
12. Consider f : A → A. Prove that if f o f is injective, then f is injective.
Proof. Suppose that f(x) = f(y). Then f(f(x)) = f(f(y)). By the definition of
composition, this
yields (f o f)(x) = (f o f)(y). The hypothesis that f o f is injective yields
now that x = y. We
have proved that f(x) = f(y) implies x = y, and so f is injective.
13. Construct an explicit bijection from the closed interval [0, 1] onto the
open interval [0, 1]. ()
Hint. This is a very nice problem. In short, no hint!
14. Consider the function g : R → R defined by
where for any x ∈ R, [x ] denotes the largest natural
number less than or equal to x. (For example,
, and 
.) Let f : N
→ Q be the function defined by
the following
rule:
Then prove that f is a bijection between N and
, where denotes the set
.
(At least convince yourself that this is true!)
Remark. This last exercise should be a final project.
