Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022
1. Given a set X and a subset A ⊆ X , define a function fA : X → {0, 1} by setting
fA(x) = 1 if x ∈ A and fA(x) = 0 if x /∈ A. If B is also a subset of X , define
(fAfB)(x) = fA(x)fB(x).
(a) Work out fAfB when X = {1, 2, 3, 4, 5}, A = {2, 4, 5} and B = {1, 2, 5}.
Solution: fAfB takes that value 1 on 2 and 5 and is 0 elsewhere.
(b) What subset, if any, does fAfB correspond to?
Solution: fAfB corresponds to A ∩ B.
(c) Define f ′A by f
′
A(x) = 1 − fA(x). What subset, if any, does f
′
A correspond
to?
Solution: f ′A corresponds to X \ A.
(d) Form combinations of fA and fB which represent
(i) the union of A and B;
Solution: We have fA∪B(x) = fA(x) + fB(x)− fA(x)fB(x).
(ii) the symmetric difference A+B = (A \B) ∪ (B \ A) of A and B.
Solution: Define (fA + fB)(x) = fA(x) + fB(x) − 2fA(x)fB(x).
Alternatively, define (fA + fB)(x) = fA(x) + fB(x), where addition is
taken modulo 2.
2. For the following sets X , Y and function X → Y , determine whether the function
is injective or surjective
(a) X = N, Y = N, f(x) = x+ 1.
Solution: If x, y ∈ N and x + 1 = f(x) = f(y) = y + 1, then x = y.
Therefore f is injective. Recall that N = {0, 1, 2, . . .}. The function is not
surjective because x+ 1 = 0 has no solution with x ∈ N.
(b) X = Z, Y = Z, g(x) = x+ 1.
Solution: The function g : Z → Z, x '→ x + 1 is injective for the same
reason as in part (a). It is surjective because if x ∈ Z, x = (x − 1) + 1 =
g(x− 1).
(c) X = Z, Y = Z, h(x) = x2 + 5.
Solution: We show that the function h : Z → Z, x '→ x2 + 5 is neither
injective nor surjective. We have f(1) = 12 + 5 = 6 = (−1)2 + 5 = f(−1).
Furthermore, f(x) = x2+5 = 4 is insoluble because the square of an integer
is never negative.
(d) X = Z, Y = Z, p(x) = x3 + 1.
Solution: We show that the function p : Z→ Z, x '→ x3 + 1 is injective
but not surjective. First we prove that p is injective by establishing the
Copyright c© 2022 The University of Sydney 1
stronger result that p is increasing, that is, if x, y ∈ Z and x < y, then
p(x) < p(y). This follows from the fact the function of real variable f(x) =
x3 + 1 is increasing. Finally we show that p is not surjective. If n ! 2,
p(n) ! p(2) = 9. On the other hand if n " 1, p(n) " p(1) = 2. Therefore
p(n) )= 3 for any integer n.
(e) X is a nonempty set, Y = P(X) (the set of all subsets of X), h(x) = {x}.
Solution: The function h : X → P(X), x '→ {x} is injective because if
{x} = h(x) = h(y) = {y}, then x = y. However h is not surjective because
the empty set ∅ ∈ P(X) does not satisfy h(x) = {x} = ∅ for any x ∈ X .
*3. Given finite sets A and B, let E be a subset of A× B. For a ∈ A, let
E(a) = { b ∈ B | (a, b) ∈ E }
and for b ∈ B, let
E∨(b) = { a ∈ A | (a, b) ∈ E }.
Prove that ∑
a∈A
|E(a)| =
∑
b∈B
|E∨(b)|.
Solution: Find the cardinality |E|. For each a ∈ A there are |E(a)| pairs
(a, y) ∈ E and so |E| =
∑
a∈A
|E(a)|. Similarly, for each b ∈ B there are |E∨(b)|
pairs (x, b) ∈ E and therefore |E| =
∑
b∈B
|E∨(b)|. Equating these two expressions
for |E| gives the result.