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(y^{2} - x^{2}) - 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) = x^{2} 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.