MATH2012 Fundamental Concepts of

Mathematics Notes
Billy LEUNG
June 2024

Introduction
This is an introductory mathematics course. In high school, mathematics ap-
pears to be calculations. In undergraduate-level mathematics, however, things
are more "proof"-based. This course aims to help students transition from high
school mathematics to university mathematics.
This note should be a revision note before tests or exams but not a starting
material. You are strongly advised to read the following textbook before reading
this note.
Recommended reading: Gary Chartrand, Albert D. Polimeni, Ping Zhang:
Mathematical Proofs: A Transition to Advanced Mathematics (Pearson, 2012,
Third Edition)

Contents
1 Basic Set Theory 1

2 Logic 2

3 Mathematical Induction 3

4 Equivalence Relation 3

5 Functions 4

6 Cardinalities of Sets 4

1 Basic Set Theory

We say that A is a subset of B (in symbol, A ⊂ B) if all elements in A are in
B. In Venn Diagram:

1
 B

Example 1.1. The set of square numbers (0, 1, 4, 9, etc) is a subset of the
set of non-negative integers (0, 1, 2, 3, 4, 5, 6, etc). But the set of square
numbers is not a subset of even numbers (0,2,4,6,8, etc (usually -2,-4,-6, etc are
also included)) because 1 is a square number that is not even.
By definition, A is a subset of A itself. We say that A is a proper subset of
B if A is a subset of B but B is not a subset of A.
To prove two sets X and Y are equal rigorously, we have to prove X ⊂ Y
and Y ⊂ X.
Example 1.2. (Please understand the definitions of the symbols first before you
read this example, the same for all following examples) Prove that the following
sets are equal:
A = {2a + 1 : a ∈ Z}
B = {x2 − y 2 : x, y ∈ N, x+y
2 ∈/ Z}
Solution. Obviously, we have B ⊂ A because every element in B can be written
as x2 − y 2 with x, y ∈ N and exactly one of x and y being odd and the other
being even, and in any case x2 − y 2 must be odd and hence in A.
To show that A ⊂ B, note that every element in A can be written as 2a + 1
for some a ∈ Z which can be written as (a + 1)2 − a2 , and is therefore an element
in B.
Thus A = B.

2 Logic
You will frequently see words like "there exist(s)", "for every/all/any", "if",
"only if", "if and only if", "the converse" etc in future mathematics courses.
Let’s use some not-so-mathematics examples to illustrate what these words
mean.
If you heard from the course instructor that "There exists a student that
failed MATH2012", it means that at least one student failed MATH2012, and
it does not say exactly one student failed the course in the broad sense.
If you heard from the course instructor that "For all students who score
80 or above, you will receive an A+", then you will get an A+ if you know
your score is 85. But if you score lower than 80, say you score 75, then what
the instructor said concerns nothing about you. This is because he/she just

2
guaranteed you an A+ if you score 80 or more and doesn’t mean you can’t get
an A+ if you score 75.
If the course instructor said "If you score 80 or above, you will receive an
A+", it has the same meaning as the above sentence.
If the course instructor said "You will get an A+ if and only if you get 80
or above", then it means that you will not get an A+ if you score lower than
80 (and get one if you score 80 or above).
Suppose there is a statement "If A, then B". Then the converse of this
statement is "If B, then A". For instance, if the teacher said "If you score 80
or above, you will get an A+", then the converse of what the teacher said is
"If you get an A+, you score 80 or above".

3 Mathematical Induction
You might have learned this in high school. Here we give an example that might
not appear in high school mathematics textbooks.

Example 3.1. Prove by induction that every integer greater than 11 can be
written as 4x + 5y where x and y are non-negative integers.
Solution. In high school, we mostly apply mathematical induction in this way:
"The statement is true for n = 1; if the statement is true for n = k, then we
prove that the statement is also true for n = k + 1 and so the statement is
true for all n ∈ N". However, the induction hypothesis does not work in this
example. Indeed, you should observe 12 = 4 × 3 + 5 × 0, 13 = 4 × 2 + 5 × 1,
14 = 4 × 1 + 5 × 2, 15 = 4 × 0 + 5 × 3 so the statement S(n): "n can be written
as 4x + 5y, x and y are non-negative integers" is true for n = 12, 13, 14, 15.
If S(n) is true for some integer n > 11, then n = 4x + 5y for some non-
negative integers x and y. So, n + 4 = 4(x + 1) + 5y and S(n + 4) is also true.
This completes the induction steps and S(n) is true for all integers n > 11.

4 Equivalence Relation
A binary relation ∼ on a set X is said to be
reflexive if x ∼ x for all x ∈ X;
symmetric if x ∼ y implies y ∼ x for all x, y ∈ X;
transitive if x ∼ y and y ∼ z imply x ∼ z for all x, y, z ∈ X.
A reflexive, symmetric and transitive relation ∼ on X is called an equivalence
relation.
Example 4.1. Consider the relation > on R, it is a transitive relation because
x > y and y > z imply x > z for x, y, z ∈ R. However, it is not a reflexive nor
symmetric relation (and thus not an equivalence relation) on R.
Example 4.2. Consider the relation = on R, it is a reflexive relation because
x = x for all x ∈ R; it is a symmetric relation because x = y implies y = x for

3
all x, y ∈ R; it is also a transitive relation because x = y and y = z imply x = z
for all x, y, z ∈ R. Thus = is an equivalence relation on R.

5 Functions
By a function f : A → B, we mean a map sending each element in A to an
element in B. A function f : A → B is injective if f (a) = f (b) if and only if
a = b. A function f : B → A is surjective if (in symbol B = f (A)). A function
f : A → B is bijective if it is both injective and surjective.
Example 5.1. f : N → N (2N means the set of positive even numbers) defined
by f (x) = 2x is injective. Since 1 ̸= 2x for any x ∈ N, 1 is not an image of
f and hence f is not surjective. To modify f so that it becomes a bijective
function, we can take f : N → 2N (2N means the set of positive even numbers),
f (x) = 2x.
Example 5.2. Let S be a nonempty set and P(S) the power set of S. For
any A, B ∈ P(S)\{∅}, define a relation R on P(S)\{∅} by ARB if there exists
a bijective function f : A −→ B. Show that R is an equivalence relation on
P(S)\{∅}.
Solution. Firstly, R is reflexive: for any A ∈ P(S)\{∅}, idA : A → A, x 7→ x is
a bijective function, so ARA.
Secondly, R is symmetric: for all A, B ∈ P(S)\{∅}, if ARB, then there is a
bijective f : A → B, and f −1 : B → A is a bijective map from B to A, so BRA.
Finally, R is transitive: for all A, B, C ∈ P(S)\{∅}, if ARB and BRC, then
there is a bijective f : A → B and a bijective g : B → C, so g ◦ f : A → C is a
bijective map from A to C, so ARC.

6 Cardinalities of Sets
This topic is perhaps the signature of the course. When we talk about "infinity",
we know that there are infinitely many integers, infinitely many even numbers,
infinitely many square numbers, infinitely many prime numbers, infinitely many
real numbers ......
It is natural to think that some "infinity" is bigger than some "infinity", but
it might be hard to make a reasonable comparison without reading the textbook.
After reading the textbook, we get an idea of how to define when two sets have
equal sizes using the notion of bijective functions - two sets A and B have equal
sizes if there is a bijective mapping f : A → B.
We now state some important theorems and facts without (or without de-
tailed) proof.
Example 6.1. kN ⊂ N ⊂ Z ⊂ Q for all k ∈ N. All four sets are of the same
sizes - they have countably infinite elements (countable means the set is either
finite or has equal size as N).

4
Example 6.2. R and R\Q have an uncountable number of elements and their
sizes are greater than that of N (i.e. there are injective maps from Q to R and
from Q to R\Q, but no bijective maps from Q to R nor from Q to R\Q).
Example 6.3. For any set S, no matter S is countable or uncountable, we have
|S| < |2S |(= |P(S)|).
Theorem 6.1 (Schröder-Bernstein Theorem). If A and B are sets and there
are injective maps f : A → B and g : B → A, then |A| = |B|.
Example 6.4. |2N | = |R|.
Solution. Note that |R| = |(0, 1)| by consider the bijective map f : R → (0, 1),
−
f (x) = tanπ 1x + 12 . So, it suffices to show |2N | = |(0, 1)|.
First, note that the map g : 2N → (0, 1) by g(a1 , a2 , a3 , · · · , an , · · · ) =
0.a1 a2 a3 · · · an · · · , an ∈ {0, 1} for all n ∈ N is an injective map because
g(a1 , a2 , a3 , · · · , an , · · · ) = g(b1 , b2 , b3 , · · · , bn , · · · ) if and only if an = bn for
all n ∈ N.
Second, to construct an injective map from (0, 1), it should be aware things
like 0.49̇ = 0.5. Luckily, it can be observed easily P∞ that each number in (0, 1)
can be expressed uniquely by an infinite sum i=1 a2ii with each ai ∈ {0, 1}
with no k ∈ N such that an = 1 for P all n ≥ k. After using this expression, we
∞
consider the map h : (0, 1) → 2N , h( i=1 a2ii ) = (a1 , a2 , · · · , an , · · · ), then h is
an injective map.
By Schröder-Bernstein Theorem, |2N | = |R|.
Example 6.5. |N| = |N × N|.
Solution. Firstly, the map f : N → N × N, n 7→ (n, 1) is clearly an injective
map.
Secondly, the map g : N × N → N, (a, b) 7→ (a+b−1)(a+b−2)
2 + b is injective.
(a+b−1)(a+b−2) (c+d−1)(c+d−2)
To see this, assume 2 +b = 2 + d. If a + b > c + d,
we have
(a + b − 1)(a + b − 2) (c + d)(c + d − 1)
+b≥ +b
2 2
(c + d − 1)(c + d − 2)
= +c+d−1+b
2
(c + d − 1)(c + d − 2)
> +d
2
which means g(a, b) > g(c, d), contradiction. Similarly, we cannot have c + d >
a + b. This forces a + b = c + d. When a + b = c + d, g(a, b) = g(c, d) implies
b = d and which then gives (a, b) = (c, d).
By Schröder-Bernstein Theorem, |N| = |N × N|.

Remark 6.1. It should be noted that the map (a, b) 7→ (a+b−1)(a+b−2)

2 + b is
bijective, making Schröder-Bernstein Theorem not that useful in the proof. An-
other construction of an injective map from N × N makes use of the fundamental
theorem of arithmetic.

5
Exam Questions
We use the 2020 June Exam to demonstrate how you can apply what you have
learned in class to answer the exam questions.

1. Prove or disprove each of the following statements:

(a) For any nonempty sets A, B, C, D,

(A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D)
(b) For any subset A of the set I of irrational numbers, if A is infinite, then A
is uncountable.
(c) For any nonempty sets A, B and for any function f : A −→ B, if
X = f −1 (f (X)) for any subset X of A, then f is injective.
(d) For any
nonempty sets A, B and for any function f : A −→ B, if
f f −1 (Y ) = Y for any subset Y of B, then f is surjective.
Solution. (a) False. For instance, when A = {1}, B = {2}, C = {3}, D = {4},
(A × B) ∪ (C × D) = {(1, 2), (3, 4)} while
(A ∪ C) × (B ∪ D) = {(1, 2), (3, 2), (1, 4), (2, 4)}.
(b) False. For instance A = {n + π : n ∈ N} ⊂ I is a countably infinite subset
of I.
−1
(c) True, because if f (x) = f (y), {x}
= f ({f (x)}) = f −1 ({f (y)}) = {y}.
−1 −1
(d) True, for any b ∈ B, f f (Y ) = Y implies f ({b}) ̸= ϕ and f (x) = b
for some x ∈ f −1 ({b}). So f is surjective.
2. Consider the sequence a1 , a2 , a3 , . . . of numbers satisfying a1 = 4, a2 = 14
and

an = 4an−1 − an−2 for any integer n ≥ 3

Find a general formula for an and prove by induction that your answer is
correct.
(Hint: Consider the quadratic equation x2 − 4x + 1 = 0.) √
Solution. Solve the quadratic equation√x2 − 4x + 1 =√0, the roots are 2 ± 3.
So the formula for an should be a(2 + 3)n + b(2 − 3)n for some constants a
and b. One can easily find that a = b = 1, then use M.I. to prove the formula.
3. Let R be the relation on R2 defined by

(a, b)R(c, d) if (ab = 0 and cd = 0) or (ac > 0 and bd > 0)

(a) Prove that R is an equivalence relation.

(b) Find all the distinct equivalence classes and hence give a partition of R2
with respect to R.
Solution. Firstly, (a, b)R(a, b) for all (a, b) ∈ R2 as if we do not have ab = 0,
then a, b ̸= 0 and get a2 > 0 and b2 > 0. So R is reflexive.
Next, R is symmetric because if we have (a, b)R(c, d), then (ab = 0 and
cd = 0) or (ac > 0 and bd > 0), which is the same as saying (ba = 0 and
dc = 0) or (ca > 0 and db > 0), hence (c, d)R(a, b).

6
Finally, R is transitive because if (a, b)R(c, d) and (c, d)R(e, f ), then (ab = 0
and cd = 0) or (ac > 0 and bd > 0), and (cd = 0 and ef = 0) or (ce > 0 and
df > 0). If cd = 0, we must have ab = 0 and ef = 0, so (a, b)R(e, f ). If cd ̸= 0,
then c, d ̸= 0, moreover, ac > 0, bd > 0, ce > 0 and df > 0, which imply
ae = (ac)(ce)
c2 > 0 and bd = (bd)(df
d2
)
> 0, so (a, b)R(e, f ) in this case as well.
4. Let f : R −→ R be a function satisfying

f (yf (x) + y) = xy + f (y) for any x, y ∈ R (*)

(a) Prove that f is injective. Hence show that f (0) = 0.
(b) Prove that f is surjective.
(c) Hence, or otherwise, find all functions f : R −→ R satisfying (*).
Solution. (a) For x, y ∈ R,
f (x) = f (y) ⇒ f (1 · f (x) + 1) = f (1 · f (y) + 1) ⇒ x + f (1) = y + f (1) ⇒ x = y.
So, f is injective. Hence, plug x = 0 into (∗), we have f (yf (0) + y) = f (y) for
all y ∈ R, this forces yf (0) + y = y and f (0) = 0.
(b) For any r ∈ R, f (f (r − f (1)) + 1) = (r − f (1)) · 1 + f (1) = r, so f is
surjective.
(c) Assume y ̸= 0, plug x = − −fy(y) into (∗), we get f (yf ( −fy(y) ) + y) = 0. By
the injectivity of f , we must have yf ( −fy(y) ) + y = 0 forcing f ( −fy(y) ) = −1 for
all y ∈ R\{0}. By the injectivity of f again, we have −fy(y) = −f1(1) = −f (1)
for all y ∈ R\{0}. This means f (y) = f (1)y for all y ∈ R. It can be checked
easily that f (x) = mx, m ̸= 0 are possible.
5. (a) Prove that for any positive integer m,
(
m m 1( mod 3) if m is even
5 ≡2 ≡
2( mod 3) if m is odd
(b) Prove that if there exist positive integers x, y, z satisfying the equation

3x + 4y = 5z
then z must be even. Write z = 2k for some positive integer k. Prove that k
must be odd and y must be even.
(c) Hence, or otherwise, prove that (x, y, z) = (2, 2, 2) is the only positive
integral solution of the equation 3x + 4y = 5z .
(Hint: Use (b) and consider modulo 8.)
Solution. (a) Can be done by M.I. easily.
(b) Consider modulo 3, we get immediately from the equation and (a) that z
must be even. Consider modulo 4, we get immediately that x is even. Then
write z = 2k and x = 2t, we get (5k − 3t )(5k + 3t ) = 4x = 22x , by fundamental
theorem of arithmetic, we must have 5k − 3t = 2a and 5k + 3t = 2b for some
a, b ∈ N such that a + b = 2x, which means 2 · 5k = 2a + 2b , which means one
of a and b equals 1 by comparing the exponents of 2 in the prime factorization
of both sides. Then, we get 5k − 3t = 2, and consider modulo 8, we get k being

7
 2t
odd. Finally, consider that (5k − 2y )(5k − 2y ) = 32t , we get 2y = 3 2−1 ≡ 1
(mod 3), so y is even.
(c) We know from the above discussion that 5k − 2y = 1 and 5k + 2y = 32t
(where z = 2k, x = 2t, k is odd). Consider modulo 8, y can be at most 2 (and
must be even by (b)), it is easy to check that there is only one possible
solution (x, y, z) = (2, 2, 2).
6. (a) Use the Schröder-Bernstein Theorem to prove that Nm is denumerable
for any m ∈ N.
(Hint: For the function from Nm to N, use the Fundamental Theorem of
Arithmetic to help you to construct an injective function.)
(b) For any m ∈ N, a function f : Z −→ N is said to be periodic with period m
if f (x + m) = f (x) for any x ∈ Z. Denote by Pm the set of all periodic
functions f : Z −→ N with period m. Use (a) and the Schröder-Bernstein
Theorem to prove that Pm is denumerable for any m ∈ N.
(Hint: First show that |Pm | = |Nm |. Construct an injective function
Φ : Pm −→ Nm and an injective function Ψ : Nm −→ Pm .)
Solution. (a) Straightforward if you follow the hint.
(b) Take Ψ : Nm → Pm , (a1 , a2 , · · · , am ) 7→ fa1 a2 ···am : Z → N,
fa1 a2 ···am (i) = ai for 1 ≤ i ≤ m. Then take Ψ : Pm → Nm ,
f 7→ (f (1), f (2), · · · , f (m)).