Week 1 Notes

Mathematics for
Data Science 1

Set theory: the number system, sets and their operations, relations and their types, and functions and their types.

11 chapters87 worked examples~105 min read

Number systemSets and operationsRelationsFunctions

Chapters

01Natural Numbers and IntegersCounting, operations, factors, primes
02Rational NumbersFractions, gcd, density
03Real and Complex NumbersIrrationals, the number family
04Sets: The BasicsMembership, subsets, power set
05Building Sets and Set OperationsComprehension, intervals, ∪ ∩ −
06Sets in ActionComprehension examples, Venn counting
07RelationsCartesian product, binary relations
08Types of RelationsReflexive, symmetric, transitive, equivalence
09FunctionsDomain, codomain, range, graphs
10Types of FunctionsInjective, surjective, bijective
11Week 1 Summary SheetAll topics

Number system · Part 1 of 3

Natural Numbers and Integers

Mathematics starts with counting. In this topic we build the first two number sets, $\mathbb{N}$ and $\mathbb{Z}$ , and see what the four basic operations do to them. Along the way we meet quotients, remainders, factors and primes, which keep coming back through the course.

1.1Counting and the natural numbers

Numbers first arose to record a count of objects: 1, 2, 3, 4, … For "7 stones" or "7 pencils", the count is 7.
We also need a number for "no objects at all". That number is 0.
Put together, these give the natural numbers.

Definition: natural numbers

The set of natural numbers is

\mathbb{N} = \{0, 1, 2, 3, 4, 5, \dots\}

In this course $\mathbb{N}$ includes 0. Sometimes $\mathbb{N}_0$ is written to stress that 0 is in. Some other books start $\mathbb{N}$ at 1, so always check the convention a book uses.

1.2The four operations, and where subtraction fails

The four arithmetic operations are addition, subtraction, multiplication and division. A natural question is: which of them always give a natural number when we start with natural numbers?

Operation	Example	Always a natural number?
Addition $+$	$5 + 2 = 7$	Yes
Multiplication $\times$	$3 \times 4 = 12$	Yes
Subtraction $-$	$5 - 6 = -1$	No: $-1$ is not in $\mathbb{N}$
Division $\div$	$19 \div 5$	No: 5 does not go into 19 exactly

Since $5 - 6$ is not a natural number, subtraction fails inside $\mathbb{N}$ . The fix is to extend the natural numbers with the negative numbers $-1, -2, -3, \dots$ .

1.3The integers

Definition: integers

The set of integers is

\mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}

Every natural number is an integer, and now subtraction always works: the difference of two integers is again an integer.

We picture the integers on a number line. Moving right the numbers increase; moving left they decrease.

Figure 1. The integers on the number line: the natural numbers (amber) plus the negatives (blue)

1.4Multiplication is repeated addition

$7 \times 4$ means: make 4 groups of 7. In general, multiplying $m$ by $n$ means adding $m$ to itself $n$ times:

m \times n = \underbrace{m + m + \cdots + m}_{n \text{ times}}

Figure 2. Multiplication as groups: 7 × 4 is four groups of 7

Notation

Three ways to write it

$m \times n$ , $m \cdot n$ , $mn$ all mean the same product.

Sign rules

Multiplying negative numbers

one negative: $-m \times n = -(m \cdot n)$

two negatives: $-m \times -n = m \cdot n$

1.5Exponentiation is repeated multiplication

Multiplying a number by itself again and again gets its own notation:

Expression	Written as	Read as
$m \times m$	$m^2$	"m squared"
$m \times m \times m$	$m^3$	"m cubed"
$\underbrace{m \times m \times \cdots \times m}_{k \text{ times}}$	$m^k$	"m to the power k"

Figure 3. Each operation is the one before it, repeated

Remember

Multiplication is repeated addition. Exponentiation is repeated multiplication.

Careful.

m^k

multiplies

m

by itself

k

times; it is not

m \times k

. For example

2^5 = 32

, whereas

2 \times 5 = 10

1.6Division is repeated subtraction

You have 20 mangoes to share among 5 friends. Give each friend one per round: after round 1 you have $20 - 5 = 15$ left, then $15 - 5 = 10$ , then $10 - 5 = 5$ , then $5 - 5 = 0$ . Four rounds, so $20 \div 5 = 4$ .

What if you start with only 19 mangoes? After 3 full rounds, 4 are left and you cannot run another round. The quotient of $19 \div 5$ is 3 and the remainder is 4.

Figure 4. Division as repeated subtraction, with and without a remainder

Definition: quotient, remainder and mod

When $a$ is divided by $b$ , the quotient is the number of full rounds of subtracting $b$ , and the remainder is what is left over (it is smaller than $b$ ). The modulo operator gives the remainder:

19 \bmod 5 = 4 \qquad 10 \bmod 3 = 1 \qquad 20 \bmod 5 = 0

Equivalently $a = b \times q + r$ with $0 \le r < b$ , where $q$ is the quotient and $r$ the remainder. Check: $19 = 5 \times 3 + 4$ .

Example 1Quotient and remainder

Find the quotient and remainder when 10 is divided by 3, and write the remainder using mod.

Solution

Subtract 3 repeatedly: $10 - 3 = 7$ , $7 - 3 = 4$ , $4 - 3 = 1$ .
Now $1 < 3$ , so no further round is possible. We made 3 full rounds.
Quotient = 3, remainder = 1. Check: $3 \times 3 + 1 = 10$ .

Answer: $10 \bmod 3 = 1$ .

1.7Factors and divisibility

Definition: divides, factor, multiple

$a$ divides $b$ if $b \bmod a = 0$ . We write $a \mid b$ . Then $a$ is a factor of $b$ , and $b$ is a multiple of $a$ ( $b$ is divisible by $a$ ).

Divides

Remainder is 0

$4 \mid 20,\; 7 \mid 63,\; 32 \mid 1024,\; 2 \mid 6,\; 5 \mid 10$

Does not divide

Remainder is not 0

$4 \nmid 19$ (since $19 \bmod 4 = 3$ ), $9 \nmid 100$ (since $100 \bmod 9 = 1$ )

Factors occur in pairs. If $a \mid b$ then $b = a \times c$ for some $c$ , and $c$ is a factor too. The factors of 12 are $\{1, 12\}, \{2, 6\}, \{3, 4\}$ . The only exception is a perfect square: the factors of 36 are $\{1, 36\}, \{2, 18\}, \{3, 12\}, \{4, 9\}, \{6\}$ , where 6 pairs with itself.

Figure 5. Factors come in pairs; a perfect square has one factor that pairs with itself

Note. Every non-zero integer

a

divides 0 (since

0 \bmod a = 0

), and 1 divides every integer. So every number

n > 1

has at least the two factors 1 and

n

1.8Prime numbers

Definition: prime number

A number $p$ is prime if it has exactly two factors, $\{1, p\}$ . 1 is not a prime: it has only one factor. The primes begin $2, 3, 5, 7, 11, 13, \dots$

The Sieve of Eratosthenes finds all primes up to a limit: start at 2, and each time you reach a number that has not been crossed out, it is prime, so remove all multiples of $p$ . Whatever survives is prime.

Figure 6. Sieve of Eratosthenes from 1 to 50: the 15 survivors are the primes

Why stop early? To test whether

n

is prime you only need to try primes

p

with

p^2 \le n

. If

n

had no prime factor up to

\sqrt{n}

, it could not have a larger one either, because factors come in pairs.

1.9Prime factorisation

Every number greater than 1 can be decomposed into prime factors, and this decomposition is unique (apart from the order of the factors). This is the prime factorisation of the number.

12 = 2 \times 2 \times 3 = 2^2 \times 3 \qquad 126 = 2 \times 3 \times 3 \times 7 = 2 \times 3^2 \times 7

Figure 7. Factor trees: keep splitting until every leaf is prime

Example 2Prime factorisation of 126

Write 126 as a product of primes.

Solution

126 is even, so divide by 2: $126 = 2 \times 63$ .
63 is not even. Its digits add to 9, so 3 divides it: $63 = 3 \times 21$ .
$21 = 3 \times 7$ , and 3 and 7 are both prime, so we stop.
Collect the leaves: $126 = 2 \times 3 \times 3 \times 7 = 2 \times 3^2 \times 7$ .

Example 3Using the sieve

Using the sieve, list the primes between 30 and 50.

Solution

Multiples of 2 remove all even numbers. Of the odd numbers 31 to 49, multiples of 3 remove 33, 39, 45; multiples of 5 remove 35 (and 45); multiples of 7 remove 49.
Survivors: $31, 37, 41, 43, 47$ .
Check one: 47 is not divisible by 2, 3, 5 or 7, and $7^2 = 49 > 47$ , so no larger prime needs testing.

Digit-sum shortcut

A number is divisible by 3 (or by 9) exactly when the sum of its digits is divisible by 3 (or by 9). For 63: $6 + 3 = 9$ , so both 3 and 9 divide 63.

1.10Going deeper: why each number set was built

Each new set exists because an operation failed in the one before. An operation is closed in a set when the answer always stays inside the set.

Operation	$\mathbb{N}$	$\mathbb{Z}$	$\mathbb{Q}$
Addition	closed	closed	closed
Subtraction	not closed	closed	closed
Multiplication	closed	closed	closed
Division (by non-zero)	not closed	not closed	closed

Quotient and remainder always satisfy $a = b \cdot q + r$ with $0 \le r < b$ . So the remainder is never as big as the divisor, and $b \mid a$ exactly when $r = 0$ .
Quick divisibility tests. By 2: the last digit is even. By 5: the last digit is 0 or 5. By 3 (or 9): the digit sum is divisible by 3 (or 9). Example: $1234$ has digit sum 10, so $1234 \bmod 9 = 1$ .
Is n prime? Try only the primes $p$ with $p^2 \le n$ . For 97: $10^2 > 97$ , so test 2, 3, 5, 7. None divides 97, so 97 is prime.
Listing factors. Go in pairs up to $\sqrt{n}$ : for 36 the pairs are $\{1, 36\}, \{2, 18\}, \{3, 12\}, \{4, 9\}$ and the self-pair $\{6\}$ , so 36 has 9 factors. A number has an odd number of factors exactly when it is a perfect square.
Extra shortcut (beyond the lecture). If $n = p^a q^b \cdots$ , then the number of factors is $(a + 1)(b + 1) \cdots$ . For $126 = 2 \cdot 3^2 \cdot 7$ this gives $2 \cdot 3 \cdot 2 = 12$ factors.

1.11LCM, Euclid's algorithm and divisibility tests

The notes so far cover the gcd and prime factorisation. Three more tools sit right next to them and appear constantly in exam questions: the LCM, Euclid's algorithm for finding a gcd without factorising, and the divisibility tests.

A. gcd and LCM from prime factorisations

The least common multiple $\operatorname{lcm}(a, b)$ is the smallest positive integer divisible by both $a$ and $b$ . Write each number as a product of prime powers. Then

$\gcd$ takes each prime to the smaller exponent (a prime missing from one number counts as exponent 0),
$\operatorname{lcm}$ takes each prime to the larger exponent.

Example: $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$ . So $\gcd = 2^1 \cdot 3^1 = 6$ and $\operatorname{lcm} = 2^2 \cdot 3^2 = 36$ . Notice $\gcd \cdot \operatorname{lcm} = 6 \cdot 36 = 216 = 12 \cdot 18$ .

Two numbers only

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b

This identity is for two numbers. For three numbers there is no such product rule: $\operatorname{lcm}(8, 12, 18)$ is found from the prime powers, $2^3 \cdot 3^2 = 72$ .
$a$ and $b$ are coprime when $\gcd(a, b) = 1$ (for example, any two consecutive integers). Then $\operatorname{lcm}(a, b) = ab$ : $\operatorname{lcm}(4, 9) = 36$ .
Any common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a, b)$ , and any common divisor is a divisor of $\gcd(a, b)$ .

B. Euclid's algorithm

Factorising big numbers is slow. Euclid's algorithm finds the gcd by repeated division with remainder:

\gcd(a, b) = \gcd(b,\ a \bmod b), \qquad \gcd(a, 0) = a

Why it works. If $a = qb + r$ , any number dividing both $a$ and $b$ also divides $r = a - qb$ , and any number dividing both $b$ and $r$ also divides $a = qb + r$ . So the pairs $(a, b)$ and $(b, r)$ have exactly the same common divisors, hence the same gcd.

Example: $\gcd(252, 105)$ .

252 = 2 \cdot 105 + 42, \qquad 105 = 2 \cdot 42 + 21, \qquad 42 = 2 \cdot 21 + 0

The last non-zero remainder is $21$ , so $\gcd(252, 105) = 21$ . Check with factorisations: $252 = 2^2 \cdot 3^2 \cdot 7$ , $105 = 3 \cdot 5 \cdot 7$ , common part $3 \cdot 7 = 21$ ✓. Then $\operatorname{lcm}(252, 105) = \dfrac{252 \cdot 105}{21} = 1260$ .

C. Divisibility tests

Divisor	Test
2, 5, 10	last digit is even / 0 or 5 / 0
4	the number formed by the last two digits is divisible by 4
8	the number formed by the last three digits is divisible by 8
3, 9	the sum of the digits is divisible by 3 / by 9
11	the alternating sum of the digits (from the right: $+, -, +, \dots$ ) is divisible by 11 (zero counts)

Example: $7524$ . Digit sum $7 + 5 + 2 + 4 = 18$ , divisible by 9 (and so by 3). Last two digits $24$ , divisible by 4. Alternating sum $4 - 2 + 5 - 7 = 0$ , so divisible by 11. Last three digits $524$ , and $524 / 8 = 65.5$ , so it is not divisible by 8. Indeed $7524 = 2^2 \cdot 3^2 \cdot 11 \cdot 19$ .

D. Counting divisors

If $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ , a divisor chooses an exponent from $0$ to $a_i$ for each prime, so the number of positive divisors is $(a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$ . For $360 = 2^3 \cdot 3^2 \cdot 5$ : $4 \cdot 3 \cdot 2 = 24$ divisors.

E. Word-problem translation

"Events repeating every $a$ , $b$ and $c$ minutes happen together again after..." $\to$ the lcm.
"Largest equal pieces / tiles / groups that fit both lengths exactly" $\to$ the gcd.

1.12Exam tips and common mistakes

Exam tips

Check any division with $a = bq + r$ before you write the answer.
$\mathbb{N}$ includes 0 in this course, and 1 is not prime. 2 is the only even prime.
Factors: list in pairs and stop at $\sqrt{n}$ so none is missed.

Common mistakes

Calling 1 a prime, or saying 0 is not in $\mathbb{N}$ (here it is).
Confusing $m^k$ with $m \times k$ : $2^5 = 32$ , not 10.
Writing a remainder equal to or larger than the divisor.
Forgetting that every number $n > 1$ has at least the factors 1 and $n$ .

Practice questions (graded-assignment style)

Q1Find the prime

Multiple Choice Question (MCQ): choose the one correct option.

Which of these numbers is prime?

Solution

Idea

A prime has exactly two factors, 1 and itself. Test small primes.

1 has only one factor, so it is not prime.
$51 = 3 \times 17$ and $57 = 3 \times 19$ , so both are composite.
59: not divisible by 2, 3, 5 or 7, and $8^2 = 64 > 59$ , so 59 is prime.
Answer: option 4.

Q2Remainder using digit sum

Numerical Answer Type (NAT).

Find $1234 \bmod 9$ .

Solution

Idea

A number leaves the same remainder mod 9 as its digit sum.

Digit sum $1 + 2 + 3 + 4 = 10$ , and $10 \bmod 9 = 1$ .
Check: $1234 = 9 \times 137 + 1$ .
Answer: 1

Q3Counting factors

Numerical Answer Type (NAT).

How many factors does 36 have?

Solution

Idea

Factors come in pairs, and a perfect square has one self-pair.

Pairs: $\{1, 36\}, \{2, 18\}, \{3, 12\}, \{4, 9\}$ , that is 8 factors.
The self-pair $\{6\}$ adds 1 more: $8 + 1 = 9$ .
Answer: 9

Q4Facts of this course

Multiple Select Question (MSQ): select all that apply.

Choose the correct statements.

0 \in \mathbb{N}

5 - 6 \in \mathbb{N}

1 is not a prime number.

a \mid b

then

b \bmod a = 0

Solution

Idea

Use the conventions of the course: $\mathbb{N}$ includes 0, and $a \mid b$ means remainder 0.

Option 1 is correct (this course includes 0).
Option 2 is wrong: $5 - 6 = -1$ is not natural.
Option 3 is correct: 1 has only one factor.
Option 4 is the definition of divides.
Answer: options 1, 3 and 4.

N1An LCM from a gcd

Numerical Answer Type (NAT).

Find $\operatorname{lcm}(84, 36)$ .

Solution

Idea

$\gcd \cdot \operatorname{lcm} = ab$ for two numbers.

$84 = 2^2 \cdot 3 \cdot 7$ and $36 = 2^2 \cdot 3^2$ . $\gcd = 2^2 \cdot 3 = 12$ .
$\operatorname{lcm} = \dfrac{84 \cdot 36}{12} = 252$ . Check with prime powers: $2^2 \cdot 3^2 \cdot 7 = 252$ ✓.
Answer: 252

N2Euclid's algorithm

Numerical Answer Type (NAT).

Use Euclid's algorithm to find $\gcd(252, 105)$ .

Solution

Idea

Replace $(a, b)$ by $(b, a \bmod b)$ until the remainder is $0$ .

$252 \bmod 105 = 42$ , so $\gcd(252, 105) = \gcd(105, 42)$ .
$105 \bmod 42 = 21$ , so it equals $\gcd(42, 21)$ .
$42 \bmod 21 = 0$ , so the answer is the last non-zero remainder, $21$ .
Answer: 21

N3Divisibility tests

Multiple Select Question (MSQ): select all that apply.

The number $7524$ is divisible by which of the following?

4

9

11

5

8

Solution

Idea

Apply the test for each divisor.

4 ✓ The last two digits $24$ are divisible by 4.
9 ✓ Digit sum $18$ is divisible by 9.
11 ✓ Alternating sum $4 - 2 + 5 - 7 = 0$ .
5 ✗ The last digit is 4, not 0 or 5.
8 ✗ The last three digits $524 = 8 \cdot 65 + 4$ .
Answer: options 1, 2 and 3.

N4Number of divisors

Numerical Answer Type (NAT).

How many positive divisors does $360$ have?

Solution

Idea

Factorise, add 1 to each exponent, multiply.

$360 = 2^3 \cdot 3^2 \cdot 5^1$ .
$(3 + 1)(2 + 1)(1 + 1) = 4 \cdot 3 \cdot 2 = 24$ .
Answer: 24

N5Three bells

Numerical Answer Type (NAT).

Three bells ring together at 9:00. After that they ring every 8, 12 and 18 minutes respectively. After how many minutes do they next ring together?

Solution

Idea

"Together again" means a common multiple; "next" means the least one.

$8 = 2^3$ , $12 = 2^2 \cdot 3$ , $18 = 2 \cdot 3^2$ . Take the larger exponent of each prime: $2^3 \cdot 3^2 = 72$ .
Check: $72 = 9 \cdot 8 = 6 \cdot 12 = 4 \cdot 18$ ✓, and no smaller number works (it must be a multiple of $8$ and of $9$ , so of $72$ ).
Answer: 72 (the next common ring is at 10:12).

Revision overview

Natural numbers ℕℕ = {0, 1, 2, 3, …}, includes 0
Numbers count objects; 0 is "none"
+ and × always stay inside ℕ

Integers ℤ5 − 6 is not natural
Add negatives: …, −2, −1, 0, 1, 2, …
Number line: right increases

Repeated operationsm × n: add m, n times
mᵏ: multiply m, k times
Division: subtract repeatedly

Natural Numbers & IntegersWeek 1 · Number system

Quotient & remainder19 ÷ 5: quotient 3, remainder 4
19 mod 5 = 4
a | b when b mod a = 0

FactorsFactors occur in pairs
Factors of 12: {1,12}, {2,6}, {3,4}
Perfect square: one self-pair (6 × 6)

PrimesExactly two factors: 1 and p
1 is not prime
Sieve: cross out multiples
Prime factorisation is unique

Revision: natural numbers and integers on one page

Next · Number system · Part 2 of 3Rational Numbers

Number system · Part 2 of 3

Rational Numbers

Division is the operation integers cannot always handle: $19 \div 5$ is not an integer. To fix this we extend the integers once more, to fractions. This topic covers rational numbers, their many representations, the reduced form, the greatest common divisor, and a new property called density.

2.1From division to fractions

We cannot represent $19 \div 5$ as an integer: 5 does not divide 19.
A fraction can: $19 \div 5 = \frac{19}{5} = 3\frac{4}{5}$ , which is the quotient 3 and the remainder 4 out of 5.

Definition: rational numbers

A rational number is a number of the form $\frac{p}{q}$ , where $p$ and $q$ are integers and $q \neq 0$ .

$p$ is the numerator and $q$ is the denominator.
The set of rational numbers is written $\mathbb{Q}$ .
Rationals extend the integers: every integer $m$ is the rational number $\frac{m}{1}$ .

Why $q \neq 0$ ? Dividing by zero is not defined, so a fraction with denominator 0 is not a number at all.

2.2The same number, many names

The representation of a rational number is not unique. Multiplying numerator and denominator by the same non-zero number gives another name for the same number:

\frac{3}{5} = \frac{6}{10} = \frac{30}{50} = \cdots \qquad \frac{1}{2} = \frac{2}{4} = \frac{10}{20} = \cdots

Figure 8. Three names for the same rational number

2.3Adding and comparing

Having many names is actually useful: to add, subtract or compare two fractions, rewrite both with a common denominator first.

\frac{3}{5} + \frac{3}{4} = \frac{12}{20} + \frac{15}{20} = \frac{27}{20} \qquad \frac{3}{5} < \frac{3}{4} \text{ because } \frac{12}{20} < \frac{15}{20}

Figure 9. Twentieths make 3/5 and 3/4 easy to add and compare

2.4Reduced form and the gcd

Definition: reduced form

$\frac{p}{q}$ is in reduced form when $p$ and $q$ have no common factors other than 1. For example, the reduced form of $\frac{18}{60}$ is $\frac{3}{10}$ .

Definition: greatest common divisor

The greatest common divisor $\gcd(p, q)$ of two non-zero integers is the greatest positive integer $k$ that divides both $p$ and $q$ . A fraction $\frac{p}{q}$ is in reduced form exactly when $\gcd(p, q) = 1$ .

To find the gcd, recall prime factorisation: $18 = 2 \cdot 3 \cdot 3$ and $60 = 2 \cdot 2 \cdot 3 \cdot 5$ . The common prime factors are $2 \cdot 3$ , so $\gcd(18, 60) = 6$ . (Later in the course you will see more efficient ways to find $\gcd(m, n)$ .)

Figure 10. The gcd is the product of the shared prime factors

Pair	gcd	Why
$\gcd(9, 12)$	3	Factors of 9: 1, 3, 9. Factors of 12: 1, 2, 3, 4, 6, 12. Largest common: 3
$\gcd(15, 45)$	15	15 divides 45, so 15 itself is the largest common divisor
$\gcd(0, q)$	$q$	0 is a multiple of every integer, so every divisor of $q$ divides 0 (here $q$ is a positive integer)
$\gcd(1, q)$	1	1 has no factors other than itself

Example 4Reducing a fraction

Write $\frac{18}{60}$ in reduced form.

Solution

Prime factorise: $18 = 2 \cdot 3 \cdot 3$ , $60 = 2 \cdot 2 \cdot 3 \cdot 5$ .
Common factors: $2 \cdot 3$ , so $\gcd(18, 60) = 6$ .
Divide top and bottom by the gcd: $\frac{18 \div 6}{60 \div 6} = \frac{3}{10}$ .
Check: $\gcd(3, 10) = 1$ , so $\frac{3}{10}$ is reduced.

2.5Density: integers are discrete, rationals are dense

Every integer has a next and a previous integer: for $m$ they are $m + 1$ and $m - 1$ . There is no integer between $m$ and $m + 1$ .

This is not possible for rationals. Between any two rationals we can always find another one. Suppose $\frac{m}{n} < \frac{p}{q}$ . Their average

\frac{1}{2}\left(\frac{m}{n} + \frac{p}{q}\right)

is again a rational number and lies between them. Repeat with the new pair and you get yet another rational, forever. So it makes no sense to talk about the "next" or "previous" rational.

Figure 11. No integer between m and m + 1, but always another rational in between

Remember

Rationals are dense; integers are discrete.

Example 5A rational in between

Find a rational number between $\frac{3}{5}$ and $\frac{3}{4}$ .

Solution

Common denominator: $\frac{3}{5} = \frac{12}{20}$ and $\frac{3}{4} = \frac{15}{20}$ .
Average: $\frac{1}{2}\left(\frac{12}{20} + \frac{15}{20}\right) = \frac{1}{2} \cdot \frac{27}{20} = \frac{27}{40}$ .
Check with denominator 40: $\frac{24}{40} < \frac{27}{40} < \frac{30}{40}$ . So $\frac{27}{40}$ lies between them.

2.6Going deeper: fractions, equality and decimals

Equality test. For positive denominators, $\frac{p}{q} = \frac{r}{s}$ exactly when $ps = qr$ . So $\frac{3}{5} = \frac{6}{10}$ because $3 \cdot 10 = 5 \cdot 6$ . The same cross-multiplication compares: $\frac{3}{5} < \frac{3}{4}$ because $3 \cdot 4 < 5 \cdot 3$ is $12 < 15$ .
Never add the denominators. $\frac{3}{5} + \frac{3}{4} \neq \frac{6}{9}$ . First rewrite with a common denominator: $\frac{12}{20} + \frac{15}{20} = \frac{27}{20}$ .
Reduced form is the standard name. Divide top and bottom by $\gcd(p, q)$ . Keep the denominator positive and put any minus sign on the numerator: $\frac{-6}{-9} = \frac{2}{3}$ , and $\frac{6}{-9} = \frac{-2}{3}$ .
Decimals (extra). A decimal is rational if it stops ( $0.75 = \frac{3}{4}$ ) or repeats ( $0.333\ldots = \frac{1}{3}$ ). Irrational decimals never stop and never repeat, as for $\pi$ .
Density has consequences. There is no smallest positive rational and no "next" rational, and there are infinitely many rationals between any two. Averaging two rationals gives a new one in between.
gcd facts to memorise. $\gcd(1, q) = 1$ , $\gcd(0, q) = q$ , and if $p \mid q$ then $\gcd(p, q) = p$ .

2.7Exam tips and common mistakes

Exam tips

Always reduce the final fraction and say that you checked $\gcd = 1$ .
To compare or add fractions, use a common denominator or cross-multiply.
For "find a rational between", use the average and verify with a common denominator.

Common mistakes

Adding numerators and denominators separately: $\frac{3}{5} + \frac{3}{4} = \frac{6}{9}$ is wrong.
Leaving a fraction unreduced, or with a zero denominator.
Believing a "next" rational exists after a given rational.
Treating $\frac{22}{7}$ as $\pi$ . It is only an approximation, and $\pi$ is irrational.

Practice questions (graded-assignment style)

Q1Add the fractions

Multiple Choice Question (MCQ): choose the one correct option.

What is $\frac{3}{5} + \frac{3}{4}$ ?

\frac{6}{9}

\frac{27}{20}

\frac{9}{20}

\frac{3}{10}

Solution

Idea

Use the common denominator 20.

$\frac{3}{5} = \frac{12}{20}$ and $\frac{3}{4} = \frac{15}{20}$ .
$\frac{12}{20} + \frac{15}{20} = \frac{27}{20}$ .
Option 1 wrongly adds the numerators and the denominators.
Answer: option 2.

Q2Find the gcd

Numerical Answer Type (NAT).

Find $\gcd(84, 36)$ .

Solution

Idea

Take the shared prime factors.

$84 = 2^2 \cdot 3 \cdot 7$ and $36 = 2^2 \cdot 3^2$ .
Common part: $2^2 \cdot 3 = 12$ .
Answer: 12

Q3Which is not rational?

Multiple Choice Question (MCQ): choose the one correct option.

Which of these numbers is not rational?

0.75

\sqrt{\frac{9}{16}}

\sqrt{7}

Solution

Idea

The square root of a non-negative integer is irrational unless the integer is a perfect square.

$0.75 = \frac{3}{4}$ is rational.
$\sqrt{\frac{9}{16}} = \frac{3}{4}$ is rational.
7 is an integer, hence rational.
7 is not a perfect square, so $\sqrt{7}$ is irrational.
Answer: option 4.

Q4Properties of rationals

Multiple Select Question (MSQ): select all that apply.

Choose the correct statements.

Between any two rationals there is another rational.

There is a smallest positive rational.

Every integer

m

is the rational number

\frac{m}{1}

The reduced form of

\frac{18}{60}

\frac{3}{10}

Solution

Idea

Rationals are dense and extend the integers.

Option 1: true, the average lies in between.
Option 2: false. Halving any positive rational gives a smaller positive rational.
Option 3: true by definition.
Option 4: true, since $\gcd(18, 60) = 6$ and $\gcd(3, 10) = 1$ .
Answer: options 1, 3 and 4.

Revision overview

Definitionℚ: numbers p/q with p, q integers
q ≠ 0; numerator p, denominator q
Extends ℤ: m = m/1

Many names3/5 = 6/10 = 30/50
Representation is not unique
Use a common denominator

Add and compare3/5 + 3/4 = 12/20 + 15/20 = 27/20
3/5 < 3/4 since 12/20 < 15/20

Rational NumbersWeek 1 · Number system

Reduced formp, q share no common factor
gcd(p, q) = 1
18/60 reduces to 3/10

gcdShared prime factors
gcd(18, 60) = 2 · 3 = 6
gcd(0, q) = q, gcd(1, q) = 1

DensityIntegers: next is m+1, previous m−1
Rationals: average lies between
No "next" rational exists

Revision: rational numbers on one page

Next · Number system · Part 3 of 3Real and Complex Numbers

Number system · Part 3 of 3

Real and Complex Numbers

The rationals are dense, so it is tempting to think they fill the whole number line. They do not. This topic shows a point the rationals miss, builds the real numbers $\mathbb{R}$ , and then goes one step further to the complex numbers $\mathbb{C}$ .

3.1Squares and square roots

Rationals are dense: between any two there is another. So, is every point on the number line a rational number? To answer this we need squares and square roots.

Square

Square of $m$

For an integer $m$ , its square is $m^2 = m \cdot m$ .

Square root

Square root of $m$

$\sqrt{m}$ is a number $r$ such that $r \cdot r = m$ .

Perfect square	1	4	9	16	25	36	49	64	…	256
Square root	1	2	3	4	5	6	7	8	…	16

What about integers that are not perfect squares, such as 2?

3.2Root 2 is irrational

$\sqrt{2}$ cannot be written as $\frac{p}{q}$ with integers $p, q$ .
Yet we can draw a line of length $\sqrt{2}$ : it is the diagonal of a square whose sides have length 1, because $1^2 + 1^2 = 2$ .
So $\sqrt{2}$ is a genuine point on the number line that is not rational. It is irrational.

Figure 12. The diagonal of a unit square lands exactly at √2 on the number line

Definition: irrational numbers

Numbers that cannot be written in the form $\frac{p}{q}$ with $p, q$ integers are called irrational. Simply: the numbers that are not rational. Examples: $\sqrt{2}, \sqrt{3}, \pi, e$ . Typical irrationals are square roots of integers that are not perfect squares.

Not every square root is irrational.

\sqrt{16} = 4

and

\sqrt{\frac{9}{16}} = \frac{3}{4}

are rational. The square root of a non-negative integer is irrational exactly when the integer is not a perfect square.

3.3The real numbers

Definition: real numbers

The real numbers $\mathbb{R}$ are all the rational numbers together with all the irrational numbers. Real numbers extend the rationals.

Some well-known irrationals: $\pi = 3.1415927\ldots$ and $e = 2.7182818\ldots$
Like the rationals, the reals are dense: if $r < r'$ , then $\frac{r + r'}{2}$ lies between $r$ and $r'$ .

Figure 13. Rationals (blue) and irrationals (amber) share the same number line

3.4Beyond the reals: complex numbers

Can we stop with the real numbers? What about $\sqrt{-1}$ ? For any real number $r$ , the square $r^2$ can never be negative, because of the law of signs for multiplication ( $(+)(+) = +$ and $(-)(-) = +$ ). So no real number squares to $-1$ .

Complex numbers

$\sqrt{-1}$ is a complex number. The complex numbers $\mathbb{C}$ extend the real numbers, just as each earlier set extended the one before.

3.5The whole family

Each new set was built to fix something the previous one could not do, and each one contains the one before it:

\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}

Figure 14. Every natural number is an integer, every integer is rational, every rational is real, and the complex numbers extend the reals

Set	Built to fix	Example of a new member
$\mathbb{N}$	Counting objects, including none	$0, 7$
$\mathbb{Z}$	$5 - 6$ is not natural	$-1$
$\mathbb{Q}$	$19 \div 5$ is not an integer	$\frac{19}{5}$
$\mathbb{R}$	$\sqrt{2}$ is not rational	$\sqrt{2}, \pi, e$
$\mathbb{C}$	No real number squares to $-1$	$\sqrt{-1}$

Example 6Smallest home of a number

For each number, name the smallest of $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ that contains it: $7,\ -3,\ \frac{6}{10},\ \sqrt{16},\ \sqrt{3},\ \pi,\ \sqrt{-1}$ .

Solution

Number	Reasoning	Smallest set
$7$	A count of objects	$\mathbb{N}$
$-3$	Negative, so not natural; but an integer	$\mathbb{Z}$
$\frac{6}{10}$	Reduces to $\frac{3}{5}$ , not an integer	$\mathbb{Q}$
$\sqrt{16}$	16 is a perfect square: $\sqrt{16} = 4$	$\mathbb{N}$
$\sqrt{3}$	3 is not a perfect square, so $\sqrt{3}$ is irrational	$\mathbb{R}$
$\pi$	A well-known irrational	$\mathbb{R}$
$\sqrt{-1}$	No real number squares to $-1$	$\mathbb{C}$

Example 7A real number in between

Find a real number between $\sqrt{2}$ and $\sqrt{3}$ , and say whether your answer is rational.

Solution

Use density: the average $\frac{\sqrt{2} + \sqrt{3}}{2}$ lies between them. Numerically $\frac{1.414\ldots + 1.732\ldots}{2} \approx 1.573$ .
A simpler choice also works: $\sqrt{2} \approx 1.414$ and $\sqrt{3} \approx 1.732$ , so $1.5 = \frac{3}{2}$ lies between them.
$\frac{3}{2}$ is rational, which shows that even between two irrationals there are rationals.

3.6Going deeper: rational or irrational?

Test for square roots. $\sqrt{n}$ for a non-negative integer $n$ : if $n$ is a perfect square it is an integer ( $\sqrt{49} = 7$ ); otherwise it is irrational ( $\sqrt{12}$ ). For a fraction, take the root of top and bottom: $\sqrt{\frac{25}{4}} = \frac{5}{2}$ .
Smallest set. To name the smallest set holding a number, try $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ in that order and stop at the first that fits. Simplify first: $\frac{6}{3} = 2 \in \mathbb{N}$ , and $\sqrt{16} = 4 \in \mathbb{N}$ .
Mixing rational and irrational (extra). A rational plus an irrational is irrational ( $1 + \sqrt{2}$ ). But two irrationals can give a rational: $\sqrt{2} \cdot \sqrt{2} = 2$ and $\sqrt{2} + (-\sqrt{2}) = 0$ .
Why $\sqrt{2}$ is irrational (optional proof). Suppose $\sqrt{2} = \frac{p}{q}$ in reduced form. Then $p^2 = 2q^2$ , so $p^2$ is even, hence $p$ is even, say $p = 2k$ . Then $4k^2 = 2q^2$ , so $q^2 = 2k^2$ and $q$ is even too. Both even contradicts $\gcd(p, q) = 1$ .
The chain only goes one way. $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$ . Every integer is rational, but not every rational is an integer.

3.7Absolute value, floor and ceiling, and arithmetic with complex numbers

A. Absolute value

The absolute value (or modulus) of a real number is its distance from $0$ : $|x| = x$ if $x \ge 0$ and $|x| = -x$ if $x < 0$ . So $|-5| = 5$ and $|x| \ge 0$ always.

$|ab| = |a||b|$ , but $|a + b| \le |a| + |b|$ (the triangle inequality; equality exactly when $a$ and $b$ do not have opposite signs). Example: $|3 + (-5)| = 2 \le 3 + 5 = 8$ .
$|x - a|$ is the distance between $x$ and $a$ . So $|x - a| < r$ means $a - r < x < a + r$ , the open interval $(a - r, a + r)$ , and $|x - a| \le r$ gives the closed interval $[a - r, a + r]$ .
$|x| > r$ means $x < -r$ or $x > r$ (two pieces, joined by union).

Example: $|2x - 1| \le 3 \iff -3 \le 2x - 1 \le 3 \iff -2 \le 2x \le 4 \iff -1 \le x \le 2$ , the interval $[-1, 2]$ . Its integer solutions are $-1, 0, 1, 2$ .

B. Floor and ceiling

$\lfloor x \rfloor$ is the greatest integer $\le x$ (round down), and $\lceil x \rceil$ is the least integer $\ge x$ (round up).

$x$	$\lfloor x \rfloor$	$\lceil x \rceil$
$2.7$	$2$	$3$
$-2.3$	$-3$	$-2$
$-3$	$-3$	$-3$

$\lfloor x \rfloor \le x < \lfloor x \rfloor + 1$ . For an integer $x$ , floor and ceiling both equal $x$ ; otherwise $\lceil x \rceil = \lfloor x \rfloor + 1$ .
For negative numbers, floor is not "drop the decimals": $\lfloor -2.3 \rfloor = -3$ , not $-2$ . Also $\lfloor -x \rfloor = -\lceil x \rceil$ .

C. Complex numbers: the arithmetic

A complex number is $z = a + bi$ with $a, b \in \mathbb{R}$ and $i^2 = -1$ . $a$ is the real part $\operatorname{Re}(z)$ and $b$ is the imaginary part $\operatorname{Im}(z)$ (a real number, without the $i$ ).

Add / subtract: real and imaginary parts separately. $(2 + 3i) + (1 - i) = 3 + 2i$ .
Multiply: expand and use $i^2 = -1$ : $(a + bi)(c + di) = (ac - bd) + (ad + bc)i$ . Example: $(2 + 3i)(1 - i) = 2 - 2i + 3i - 3i^2 = 2 + i + 3 = 5 + i$ .
Conjugate $\bar z = a - bi$ , and the modulus $|z| = \sqrt{a^2 + b^2}$ . They are linked by $z\bar z = a^2 + b^2 = |z|^2$ , a real number. Example: $(2 - i)(2 + i) = 4 + 1 = 5$ , and $|3 + 4i| = 5$ .
Divide: multiply top and bottom by the conjugate of the denominator. $\dfrac{3 + 4i}{1 - 2i} = \dfrac{(3 + 4i)(1 + 2i)}{(1 - 2i)(1 + 2i)} = \dfrac{3 + 6i + 4i + 8i^2}{5} = \dfrac{-5 + 10i}{5} = -1 + 2i$ .
Powers of $i$ repeat every four steps: $i, -1, -i, 1, i, \dots$ . So $i^n$ depends only on $n \bmod 4$ . $i^{23}$ : $23 = 4 \cdot 5 + 3$ , so $i^{23} = i^3 = -i$ .
Every real number is complex ( $b = 0$ ), so $\mathbb{R} \subset \mathbb{C}$ . Unlike the reals, complex numbers are not ordered: " $i > 0$ " and " $i < 0$ " both make no sense.

3.8Exam tips and common mistakes

Exam tips

Simplify the number first (cancel fractions, evaluate perfect-square roots), then pick the smallest set.
Remember that $\pi$ and $e$ are irrational, while $\frac{22}{7}$ is only an approximation of $\pi$ .
Always give a reason: "perfect square, so integer" or "not a perfect square, so irrational".

Common mistakes

Calling $\sqrt{16}$ or $\sqrt{\frac{9}{16}}$ irrational. They are $4$ and $\frac{3}{4}$ .
Saying every number with a square root sign is irrational, or that $0.333\ldots$ is irrational (it is $\frac{1}{3}$ ).
Writing the chain in the wrong direction, like $\mathbb{R} \subset \mathbb{Q}$ .
Claiming real numbers are not dense because they include irrationals. They are dense.

Practice questions (graded-assignment style)

Q1Smallest set

Multiple Choice Question (MCQ): choose the one correct option.

What is the smallest of $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ that contains $\sqrt{49}$ ?

\mathbb{N}

\mathbb{Z}

\mathbb{Q}

\mathbb{R}

Solution

Idea

Evaluate the root first.

49 is a perfect square, so $\sqrt{49} = 7$ .
7 is a count, so it already lies in $\mathbb{N}$ .
Answer: option 1.

Q2Irrational numbers

Multiple Select Question (MSQ): select all that apply.

Choose all the irrational numbers.

\sqrt{12}

\sqrt{\frac{9}{4}}

\pi

\frac{22}{7}

Solution

Idea

Simplify, then ask whether the number can be written as a ratio of integers.

$\sqrt{12}$ : 12 is not a perfect square, so it is irrational.
$\sqrt{\frac{9}{4}} = \frac{3}{2}$ is rational.
$\pi$ is a well-known irrational.
$\frac{22}{7}$ is a ratio of integers, so it is rational (only close to $\pi$ ).
Answer: options 1 and 3.

Q3The chain of sets

Multiple Choice Question (MCQ): choose the one correct option.

Which chain of sets is correct?

\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}

\mathbb{R} \subset \mathbb{Q} \subset \mathbb{Z} \subset \mathbb{N}

\mathbb{Z} \subset \mathbb{N} \subset \mathbb{Q} \subset \mathbb{R}

\mathbb{Q} \subset \mathbb{Z} \subset \mathbb{R} \subset \mathbb{C}

Solution

Idea

Each set extends the previous one.

Naturals sit inside integers, integers inside rationals, rationals inside reals, and reals inside complex numbers.
The other options reverse or skip a step.
Answer: option 1.

Q4Why complex numbers?

Multiple Choice Question (MCQ): choose the one correct option.

Why is $\sqrt{-1}$ not a real number?

It is irrational.

The square of a real number is never negative.

It is a fraction.

Real numbers are not dense.

Solution

Idea

Use the law of signs.

$(+)(+) = +$ and $(-)(-) = +$ , so $r^2 \ge 0$ for every real $r$ .
So no real number squares to $-1$ , and we need $\mathbb{C}$ .
Answer: option 2.

R1An absolute-value inequality

Numerical Answer Type (NAT).

How many integers $x$ satisfy $|2x - 1| \le 3$ ?

Solution

Idea

$|u| \le 3$ means $-3 \le u \le 3$ .

$-3 \le 2x - 1 \le 3 \Rightarrow -2 \le 2x \le 4 \Rightarrow -1 \le x \le 2$ .
Integers: $-1, 0, 1, 2$ . Check the endpoints: $|2(-1) - 1| = 3$ ✓ and $|2(2) - 1| = 3$ ✓; $x = 3$ gives $5$ ✗.
Answer: 4

R2Floor and ceiling of a negative number

Numerical Answer Type (NAT).

Find $\lfloor -2.3 \rfloor + \lceil -2.3 \rceil$ .

Solution

Idea

On the number line, floor goes left to the next integer and ceiling goes right.

$-2.3$ lies between $-3$ and $-2$ . Floor is the one on the left: $-3$ . Ceiling is the one on the right: $-2$ .
Sum $= -3 + (-2) = -5$ .
Answer: -5

R3Product of complex numbers

Numerical Answer Type (NAT).

If $(2 + 3i)(1 - i) = a + bi$ with $a, b$ real, find $a + b$ .

Solution

Idea

Expand and replace $i^2$ by $-1$ .

$(2 + 3i)(1 - i) = 2 - 2i + 3i - 3i^2 = 2 + i + 3 = 5 + i$ .
So $a = 5$ , $b = 1$ , and $a + b = 6$ .
Answer: 6

R4A power of $i$ and a quotient

Multiple Select Question (MSQ): select all that apply.

Choose the correct statements.

i^{23} = -i

\dfrac{3 + 4i}{1 - 2i} = -1 + 2i

|3 + 4i| = 7

(2 - i)(2 + i) = 5

Solution

Idea

Reduce the exponent modulo 4, use the conjugate for division, and remember $z\bar z = |z|^2$ .

1 ✓ $23 \bmod 4 = 3$ and $i^3 = -i$ .
2 ✓ $\dfrac{(3 + 4i)(1 + 2i)}{5} = \dfrac{-5 + 10i}{5} = -1 + 2i$ . Check: $(-1 + 2i)(1 - 2i) = -1 + 2i + 2i - 4i^2 = 3 + 4i$ ✓.
3 ✗ $|3 + 4i| = \sqrt{9 + 16} = 5$ , not $3 + 4$ .
4 ✓ $4 - i^2 = 5$ , real, equal to $|2 - i|^2$ .
Answer: options 1, 2 and 4.

Revision overview

Squares & rootsm² = m · m; √m = r with r · r = m
Perfect squares: 1, 4, 9, 16, …, 256

Irrationals√2 is not p/q
But √2 = diagonal of a unit square
Also √3, π = 3.14159…, e = 2.71828…

Real numbers ℝAll rationals + all irrationals
Dense: if r < s, (r + s)/2 is between
Real numbers extend rationals

Real & Complex NumbersWeek 1 · Number system

Complex numbers ℂr² is never negative for real r
√−1 is a complex number
Complex numbers extend reals

The familyℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ
Each set fixes a gap in the last

Revision: real and complex numbers on one page

Next · Sets · Part 1 of 3Sets: The Basics

Sets · Part 1 of 3

Sets: The Basics

With the number system in place, we step back and look at the idea that holds all those collections together: the set. This topic covers what a set is, how to describe one, when one set sits inside another, and how many subsets a set has.

4.1What is a set?

Definition: set

A set is a collection of (well-defined) items. The items in a set are called its elements.

Days of the week

$\{\text{Sun}, \text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}, \text{Sat}\}$

Factors of 24

$\{1, 2, 3, 4, 6, 8, 12, 24\}$

Primes below 15

$\{2, 3, 5, 7, 11, 13\}$

Sets may be finite (like the three above, or the months of a year) or infinite: the number sets $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ are all infinite, and so is the set of even natural numbers $\{0, 2, 4, 6, \dots\}$ .
There is no requirement that the members of a set have a uniform type. The set of objects in a painting, or in a room, is a perfectly good set.

4.2Order, duplicates and cardinality

Sets are unordered: $\{\text{Kohli}, \text{Dhoni}, \text{Pujara}\} = \{\text{Pujara}, \text{Kohli}, \text{Dhoni}\}$ .
Duplicates do not matter: $\{\text{Kohli}, \text{Dhoni}, \text{Pujara}, \text{Dhoni}\}$ is the same set again.

Figure 15. Three ways of writing one set

Definition: cardinality

The cardinality of a set $S$ , written $|S|$ , is the number of elements in $S$ . For finite sets, just count the items: $\{1, 2, 3, 4, 6, 8, 12, 24\}$ has cardinality 8, and $S = \{1, 2, 5, 7, 9, 300\}$ has cardinality 6.

What about infinite sets? Is

\mathbb{Q}

bigger than

\mathbb{Z}

? Is

\mathbb{R}

bigger than

\mathbb{Q}

? Counting does not work here. The tool for comparing sizes of sets without counting is a bijection, which appears in the chapter on types of functions.

4.3Describing sets and membership

Finite sets

List them explicitly

$\{\text{Kohli}, \text{Dhoni}, \text{Pujara}\}$

$\{1, 2, 3, 4, 6, 8, 12, 24\}$

Infinite sets

Cannot be listed out

$\mathbb{N} = \{0, 1, 2, \dots\}$ is a helpful picture, but the " $\dots$ " is not formal notation. Section 5.1 gives the formal way.

Careful

Not every collection of items is a set. For example, the collection of all sets is not a set. This is shown by Russell's paradox.

Notation: membership

$x \in X$ means " $x$ is an element of $X$ ", and $x \notin X$ means it is not. For example:

-5 \in \mathbb{Z} \qquad \sqrt{2} \notin \mathbb{Q}

4.4Subsets

Definition: subset

$X$ is a subset of $Y$ if every element of $X$ is also an element of $Y$ . Notation: $X \subseteq Y$ .

$\{\text{Kohli}, \text{Pujara}\} \subseteq \{\text{Kohli}, \text{Pujara}, \text{Dhoni}\}$
$\text{Primes} \subseteq \mathbb{N}$ , and $\mathbb{N} \subseteq \mathbb{Z},\ \mathbb{Z} \subseteq \mathbb{Q},\ \mathbb{Q} \subseteq \mathbb{R}$
Every set is a subset of itself: $X \subseteq X$ .
$X = Y$ if and only if $X \subseteq Y$ and $Y \subseteq X$ . This is how we prove two sets are equal.

Definition: proper subset

$X$ is a proper subset of $Y$ if $X \subseteq Y$ but $X \neq Y$ . Notation: $X \subset Y$ or $X \subsetneq Y$ . For example $\mathbb{N} \subsetneq \mathbb{Z},\ \mathbb{Z} \subsetneq \mathbb{Q},\ \mathbb{Q} \subsetneq \mathbb{R}$ .

Figure 16. Left: X is a proper subset of Y. Right: X and Y have the same elements, so they are equal

$\in$ versus $\subseteq$ .

\in

relates an element to a set;

\subseteq

relates a set to a set. For

X = \{a, b\}

a \in X

is true, but

a \subseteq X

is not (

a

is not a set);

\{a\} \subseteq X

is true, but

\{a\} \in X

is false.

4.5The empty set and the power set

Definition: empty set

The empty set has no elements. It is written $\emptyset$ . $\emptyset \subseteq X$ for every set $X$ : every element of $\emptyset$ is also in $X$ , simply because $\emptyset$ has no elements to check.

A set can contain other sets as elements. The most important example is the power set.

Definition: power set

The power set of $X$ is the set of all subsets of $X$ . For $X = \{a, b\}$ :

\text{Power set of } X = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}

A set with $n$ elements has $2^n$ subsets. Take $X = \{x_1, x_2, \dots, x_n\}$ . To build a subset, go through the elements one by one and either include or exclude each $x_i$ . That is 2 choices per element, so the number of subsets is

\underbrace{2 \cdot 2 \cdot 2 \cdots 2}_{n \text{ times}} = 2^n

Figure 17. Every path of include (+) / exclude (−) choices gives one subset of {a, b, c}

Figure 18. The 8 subsets of {a, b, c}, arranged by size

Notation. The power set of

X

is often written

\mathcal{P}(X)

, so

|\mathcal{P}(X)| = 2^{|X|}

. Note that

\emptyset \in \mathcal{P}(X)

and

\emptyset \subseteq X

, but

\emptyset \notin X

unless

X

itself has

\emptyset

as an element.

4.6Subsets and binary numbers

The include/exclude choice is exactly a bit. List the elements of $X = \{x_1, x_2, \dots, x_n\}$ in order and use an $n$ -bit binary number: digit $i$ says whether $x_i$ is included in the subset. With 3 bits the numbers are $000, 001, 010, 011, 100, 101, 110, 111$ , one for each subset.

Figure 19. For X = {a, b, c, d}: 0101 is {b, d}, 0000 is ∅, and 1111 is X

The same count, another way

There are $2^n$ different $n$ -bit binary numbers, and each one names exactly one subset. So a set with $n$ elements has $2^n$ subsets.

Example 8Power set of a 3-element set

List the power set of $X = \{a, b, c\}$ and check the count.

Solution

Size 0: $\emptyset$ .
Size 1: $\{a\}, \{b\}, \{c\}$ .
Size 2: $\{a, b\}, \{a, c\}, \{b, c\}$ .
Size 3: $\{a, b, c\}$ .
Total $1 + 3 + 3 + 1 = 8 = 2^3$ . The power set is $\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$ .

Example 9Counting subsets

A set $S$ has 5 elements. How many subsets does it have? How many of them are proper subsets?

Solution

Each of the 5 elements is either in or out: $2^5 = 32$ subsets.
A proper subset must not equal $S$ . Exactly one subset equals $S$ itself (all bits 1).
Proper subsets: $32 - 1 = 31$ . (This count includes $\emptyset$ .)

Example 10Subset or not?

Let $X = \{1, 2, 5, 7, 9, 300\}$ and $Y = \{0, 1, 2, 5, 7, 9, 40, 170, 300\}$ . Is $X \subseteq Y$ ? Is $X \subset Y$ ?

Solution

Check each element of $X$ : 1, 2, 5, 7, 9 and 300 all appear in $Y$ . So $X \subseteq Y$ .
$Y$ has elements not in $X$ (for example 0), so $X \neq Y$ .
Therefore $X$ is a proper subset: $X \subset Y$ .

4.7Going deeper: $\in$ versus $\subseteq$ , and sets inside sets

Most mistakes in this chapter come from mixing up elements and subsets. For $X = \{a, b\}$ :

Statement	True?	Reason
$a \in X$	true	a is an element of X
$\{a\} \subseteq X$	true	every element of {a} is in X
$a \subseteq X$	false	a is not a set
$\{a\} \in X$	false	the elements of X are a and b, not {a}
$\emptyset \subseteq X$	true	the empty set is a subset of every set
$\emptyset \in X$	false	X does not list $\emptyset$ as an element
$X \subseteq X$	true	every set is a subset of itself
$X \in X$	false	X is not one of its own elements

A set can contain sets. Let $Y = \{\emptyset, \{a\}\}$ . Its elements are $\emptyset$ and $\{a\}$ , so $|Y| = 2$ , $\emptyset \in Y$ is true, $\{a\} \in Y$ is true, but $a \in Y$ is false.
$\emptyset$ versus $\{\emptyset\}$ . $|\emptyset| = 0$ but $|\{\emptyset\}| = 1$ : it is a set holding one element, the empty set.
Cardinality ignores repeats. $\{1, 2, 2, 3, 3, 3\} = \{1, 2, 3\}$ , so its cardinality is 3.
Counting subsets. $n$ elements give $2^n$ subsets. Of these, $2^n - 1$ are proper (all except the set itself), and $2^{n-1}$ contain any one chosen element.

4.8Exam tips and common mistakes

Exam tips

Ask first: "is the left side an element or a set?" Use $\in$ for elements and $\subseteq$ for sets.
When counting subsets include both $\emptyset$ and the set itself.
To show $X = Y$ , prove $X \subseteq Y$ and $Y \subseteq X$ .

Common mistakes

Writing $a \subseteq X$ for an element, or $\{a\} \in X$ when $\{a\}$ is not listed in $X$ .
Forgetting that $\emptyset$ is a subset of every set, and so is in every power set.
Counting duplicates when finding cardinality.
Treating $\emptyset$ and $\{\emptyset\}$ as the same.

Practice questions (graded-assignment style)

Q1Cardinality

Numerical Answer Type (NAT).

What is the cardinality of $\{1, 2, 2, 3, 3, 3\}$ ?

Solution

Idea

Duplicates do not matter in a set.

The set is $\{1, 2, 3\}$ .
It has 3 distinct elements.
Answer: 3

Q2Proper subsets

Numerical Answer Type (NAT).

A set has 4 elements. How many proper subsets does it have?

Solution

Idea

Total subsets are $2^n$ ; remove the set itself.

Subsets: $2^4 = 16$ .
Only the set itself is not proper, so $16 - 1 = 15$ (this includes $\emptyset$ ).
Answer: 15

Q3Sets inside a set

Multiple Select Question (MSQ): select all that apply.

Let $Y = \{\emptyset, \{a\}\}$ . Choose the correct statements.

\emptyset \in Y

a \in Y

\{a\} \in Y

\{a\} \subseteq Y

Solution

Idea

List the elements of $Y$ first: they are $\emptyset$ and $\{a\}$ .

Option 1 is true: $\emptyset$ is listed.
Option 2 is false: $a$ alone is not listed.
Option 3 is true: $\{a\}$ is listed.
Option 4 is false: it would need $a \in Y$ .
Answer: options 1 and 3.

Q4Element or subset?

Multiple Choice Question (MCQ): choose the one correct option.

Let $X = \{a, b\}$ . Which statement is true?

a \subseteq X

\{a\} \in X

\{a\} \subseteq X

X \in X

Solution

Idea

$\in$ is for elements and $\subseteq$ is for sets.

$a$ is an element, not a set, so option 1 is false.
$X$ lists $a$ and $b$ , not $\{a\}$ , so option 2 is false.
Option 3 is true: $a \in X$ .
Option 4 is false.
Answer: option 3.

Q5Binary code of a subset

Multiple Choice Question (MCQ): choose the one correct option.

For $X = \{a, b, c, d\}$ the bit string $1010$ names which subset?

\{a, c\}

\{b, d\}

\{a, b\}

\{c, d\}

Solution

Idea

Bit i says whether the i-th element is included.

Bits 1 and 3 are 1, so $a$ and $c$ are included.
(Compare $0101$ , which is $\{b, d\}$ .)
Answer: option 1.

Revision overview

SetsA collection of items (elements)
Finite or infinite
Items need not be the same type

Order & duplicatesSets are unordered
Duplicates do not matter
Cardinality |S| = number of items

Describing setsFinite: list explicitly
Infinite: cannot list; "…" is informal
Not every collection is a set

Sets: The BasicsWeek 1 · Sets

Membership & subsetsx ∈ X: x is an element of X
X ⊆ Y: all of X is in Y
X = Y iff X ⊆ Y and Y ⊆ X

Empty & power set∅ has no elements; ∅ ⊆ every set
Power set = set of all subsets
n elements give 2ⁿ subsets

Binary viewBit i: is element i included?
0101 ↔ {b, d} for {a, b, c, d}
2ⁿ bit strings ↔ 2ⁿ subsets

Revision: the basics of sets on one page

Next · Sets · Part 2 of 3Building Sets and Set Operations

Sets · Part 2 of 3

Building Sets and Set Operations

Listing elements only works for small finite sets. This topic shows the formal way to build a set from an existing one, how to describe ranges of real numbers as intervals, and how to combine sets with union, intersection, difference and complement.

5.1Set comprehension (set-builder form)

To describe an infinite set formally, start from a set we already have and keep only the elements that satisfy a condition. For example, the subset of even integers is

\{x \mid x \in \mathbb{Z},\ x \bmod 2 = 0\}

Begin with an existing set, here $\mathbb{Z}$ .
Apply a condition to each element: $x \in \mathbb{Z}$ such that $x \bmod 2 = 0$ .
Collect all the elements that match the condition.

Definition: set comprehension

Set comprehension constructs a subset from an existing set such as $\mathbb{N}, \mathbb{Z}, \mathbb{R}$ by applying a filter to every element. It has three main components: a generator, a filter and a transformer.

Figure 20. Reading a comprehension: what to output | where elements come from, which ones to keep

Figure 21. The squares of the even integers, built step by step

Perfect squares

$\{m \mid m \in \mathbb{N},\ \sqrt{m} \in \mathbb{N}\}$

Rationals in reduced form

$\{\frac{p}{q} \mid p, q \in \mathbb{Z},\ q \neq 0,\ \gcd(p, q) = 1\}$

5.2Intervals

Comprehension also describes ranges of numbers. The integers from $-6$ to $6$ are $\{z \mid z \in \mathbb{Z},\ -6 \le z \le 6\}$ . For real numbers between 0 and 1 we must decide whether the endpoints are included, which gives four kinds of interval.

Figure 22. Square bracket: endpoint included. Round bracket: endpoint excluded

Name	Notation	Set comprehension	Endpoints
Closed interval	$[0, 1]$	$\{x \mid x \in \mathbb{R},\ 0 \le x \le 1\}$	both included
Open interval	$(0, 1)$	$\{x \mid x \in \mathbb{R},\ 0 < x < 1\}$	both excluded
Left open	$(0, 1]$	$\{x \mid x \in \mathbb{R},\ 0 < x \le 1\}$	only 1 included
Right open	$[0, 1)$	$\{x \mid x \in \mathbb{R},\ 0 \le x < 1\}$	only 0 included

Infinite ends. For unbounded ranges we write

\infty

with a round bracket, never a square one, since

\infty

is not a real number you can include. For example

[0, \infty)

is the set of non-negative reals.

5.3Union, intersection and difference

Operation	Meaning	Notation	Example
Union	combine $X$ and $Y$	$X \cup Y$	$\{a, b, c\} \cup \{c, d, e\} = \{a, b, c, d, e\}$
Intersection	elements common to $X$ and $Y$	$X \cap Y$	$\{a, b, c, d\} \cap \{a, d, e, f\} = \{a, d\}$
Set difference	elements in $X$ that are not in $Y$	$X - Y$ or $X \setminus Y$	$\{a, b, c, d\} - \{a, d, e, f\} = \{b, c\}$

In a union, an element that is in both sets (like

c

above) is written once, because duplicates do not matter.

5.4Complement

Definition: complement

The complement of $X$ is the set of elements not in $X$ , written $\overline{X}$ or $X^c$ . It only makes sense relative to a larger set, called the universe $U$ : $X^c = U - X$ .

Inside $\mathbb{N}$ , the complement of the set of primes is the set of composite numbers, together with 0 and 1 (which are neither prime nor composite).
Inside $\mathbb{Z}$ , the complement of the even integers is the odd integers.

Figure 23. The four operations as shaded regions (U is the universe)

Example 11All four operations

Let $U = \{a, b, c, d, e, f, g, h\}$ , $X = \{a, b, c, d\}$ and $Y = \{a, d, e, f\}$ . Find $X \cup Y$ , $X \cap Y$ , $X - Y$ , $Y - X$ and $X^c$ .

Solution

Figure 24. Place each element in its region first; every answer can then be read off

Set	Read from the diagram	Answer
$X \cup Y$	everything inside either circle	$\{a, b, c, d, e, f\}$
$X \cap Y$	the middle region	$\{a, d\}$
$X - Y$	the left-only region	$\{b, c\}$
$Y - X$	the right-only region	$\{e, f\}$
$X^c$	everything in $U$ outside the $X$ circle	$\{e, f, g, h\}$

Notice $X - Y \neq Y - X$ : set difference depends on the order.

Example 12Intervals with comprehension

Write "the real numbers from $-1$ to 2, including $-1$ but not 2" as an interval and as a set comprehension. Is 2 in it? Is $-1$ ?

Solution

$-1$ is included (square bracket) and 2 is excluded (round bracket): $[-1, 2)$ .
As a comprehension: $\{r \mid r \in \mathbb{R},\ -1 \le r < 2\}$ .
$-1 \in [-1, 2)$ because $-1 \le -1$ . But $2 \notin [-1, 2)$ because $2 < 2$ is false.

5.5Going deeper: reading comprehensions and intervals

Read a comprehension like a loop. For $\{x^2 \mid x \in \mathbb{Z},\ x \bmod 2 = 0\}$ : take each $x$ from $\mathbb{Z}$ , keep it if $x$ is even, then output $x^2$ . Result: $\{0, 4, 16, 36, \dots\}$ .
The filter acts before the transform. $\{x^2 \mid x \in \{1, 2, 3, 4\},\ x > 2\} = \{9, 16\}$ , because only 3 and 4 pass the filter and are then squared.
Interval algebra. Draw both intervals on a number line and watch the endpoints.

Expression	Result	Why
$[0, 2) \cup [1, 3]$	$[0, 3]$	together they cover 0 up to 3, both ends included
$[0, 2) \cap [1, 3]$	$[1, 2)$	1 is in both; 2 is excluded from the first
$[0, 3] - (1, 2)$	$[0, 1] \cup [2, 3]$	removing the open middle keeps 1 and 2
complement of $[0, 1)$ in $\mathbb{R}$	$(-\infty, 0) \cup [1, \infty)$	everything outside; 1 is now included

Difference as intersection. $X - Y = X \cap Y^c$ : "in $X$ and not in $Y$ ". And $X - Y \neq Y - X$ in general.
Words to symbols. "or" means union, "and" means intersection, "not in" means difference or complement.

5.6Exam tips and common mistakes

Exam tips

Draw a quick number line for interval questions and mark open and closed ends.
Place each element of the universe in its region first, then read off every answer.
For a complement, always say which universe $U$ you are using.

Common mistakes

Using a square bracket next to $\infty$ . It is always $(\ldots, \infty)$ .
Confusing $\cup$ (or) with $\cap$ (and).
Assuming $X - Y = Y - X$ .
Writing a complement with no universe.

Practice questions (graded-assignment style)

Q1Intersect intervals

Multiple Choice Question (MCQ): choose the one correct option.

What is $[1, 5) \cap (3, 8]$ ?

[3, 5)

(3, 5)

(3, 5]

[1, 8]

Solution

Idea

Take the larger left end and the smaller right end, and keep each end only if both intervals keep it.

$x$ must satisfy $1 \le x < 5$ and $3 < x \le 8$ , so $3 < x < 5$ .
Neither end is included: the answer is the open interval (3, 5).
Answer: option 2.

Q2Size of a comprehension

Numerical Answer Type (NAT).

How many elements does $\{x^2 \mid x \in \mathbb{Z},\ -3 \le x \le 3\}$ have?

Solution

Idea

List the squares, and remember that duplicates count once.

$x = -3, \dots, 3$ gives $9, 4, 1, 0, 1, 4, 9$ .
As a set this is $\{0, 1, 4, 9\}$ , which has 4 elements.
Answer: 4

Q3Set operations

Multiple Select Question (MSQ): select all that apply.

Let $U = \{1, \dots, 8\}$ , $X = \{1, 2, 3, 4\}$ and $Y = \{3, 4, 5, 6\}$ . Choose the correct statements.

X \cap Y = \{3, 4\}

X - Y = \{1, 2\}

Y - X = \{1, 2\}

X^c = \{5, 6\}

Solution

Idea

Place each element in its region first.

Options 1 and 2 are correct.
Option 3: $Y - X = \{5, 6\}$ .
Option 4: $X^c = U - X = \{5, 6, 7, 8\}$ .
Answer: options 1 and 2.

Q4Read the interval

Multiple Choice Question (MCQ): choose the one correct option.

Which set is $[0, 1)$ ?

\{x \in \mathbb{R} \mid 0 < x \le 1\}

\{x \in \mathbb{R} \mid 0 \le x < 1\}

\{x \in \mathbb{R} \mid 0 < x < 1\}

\{x \in \mathbb{R} \mid 0 \le x \le 1\}

Solution

Idea

Square bracket includes the end, round excludes it.

0 is included and 1 is excluded.
That is $0 \le x < 1$ .
Answer: option 2.

Revision overview

Set comprehension{ x | x ∈ ℤ, x mod 2 = 0 }
Begin with an existing set
Filter, then collect

Three partsGenerator: where elements come from
Filter: which ones to keep
Transform: modify kept ones

Intervals[0, 1] closed: ends included
(0, 1) open: ends excluded
(0, 1] left open, [0, 1) right open

Building Sets & OperationsWeek 1 · Sets

Union & intersectionX ∪ Y: in X or Y
X ∩ Y: in both
Shared elements written once

DifferenceX − Y = X \ Y: in X, not Y
{a,b,c,d} − {a,d,e,f} = {b,c}
X − Y ≠ Y − X in general

ComplementXᶜ: elements not in X
Relative to a universe U
Primes in ℕ → composites, 0, 1

Revision: building and combining sets on one page

Next · Sets · Part 3 of 3Sets in Action

Sets · Part 3 of 3

Sets in Action

This topic puts set comprehension to work on a set of examples, and then uses Venn diagrams to solve counting problems. The aim is fluency: reading and writing comprehensions quickly, and picking the right region of a Venn diagram.

6.1Generator, filter, transform: more examples

Set	Set comprehension	Generator	Filter	Transform
Squares of even integers	$\{x^2 \mid x \in \mathbb{Z},\ x \bmod 2 = 0\}$	$x \in \mathbb{Z}$	$x \bmod 2 = 0$	$x^2$
Rationals in reduced form	$\{\frac{p}{q} \mid \frac{p}{q} \in \mathbb{Q},\ \gcd(p, q) = 1\}$	$\frac{p}{q} \in \mathbb{Q}$	$\gcd(p, q) = 1$	none
Reals in $[-1, 2)$	$\{r \mid r \in \mathbb{R},\ -1 \le r < 2\}$	$r \in \mathbb{R}$	$-1 \le r < 2$	none
Cubes of first 5 naturals	$\{n^3 \mid n \in \{0, 1, 2, 3, 4\}\}$	$n \in \{0, \dots, 4\}$	none	$n^3$

A comprehension does not need all three parts. With no filter, every generated element is kept; with no transform, kept elements are output unchanged.

Example 13Cubes of the first 500 natural numbers

Use set comprehension to describe the set of cubes of the first 500 natural numbers, in a readable way.

Solution

Listing the generator is clumsy: $Y = \{n^3 \mid n \in \{0, 1, 2, 3, \dots, 498, 499\}\}$ .
First use comprehension to define the first 500 natural numbers: $X = \{n \mid n \in \mathbb{N},\ n < 500\}$ .
Now generate from $X$ : $Y = \{n^3 \mid n \in X\}$ . This is the more readable version.
Check the small case: with $\{0, 1, 2, 3, 4\}$ as generator we get $\{0, 1, 8, 27, 64\}$ .

6.2Perfect squares, three ways

Integers whose square root is also an integer: $\{z \mid z \in \mathbb{Z},\ \sqrt{z} \in \mathbb{Z}\}$ .
All squares are non-negative, so this is the same as $\{n \mid n \in \mathbb{N},\ \sqrt{n} \in \mathbb{N}\}$ (a filter).
Alternatively, generate all the perfect squares directly: $\{n^2 \mid n \in \mathbb{N}\}$ (a transform).

Figure 25. Filtering ℕ and transforming ℕ reach the same set

Extending the definition to rationals

$\frac{9}{16} = \left(\frac{3}{4}\right)^2$ is a square of a rational, but $\frac{1}{2} \neq \left(\frac{p}{q}\right)^2$ for any $p, q$ . The squares of rationals are $\{q \mid q \in \mathbb{Q},\ \sqrt{q} \in \mathbb{Q}\}$ or, generating them, $\{q^2 \mid q \in \mathbb{Q}\}$ .

6.3Counting with Venn diagrams

When two sets overlap, adding their sizes counts the overlap twice. Subtracting it once gives the size of the union:

n(P \cup B) = n(P) + n(B) - n(P \cap B)

Here $n(X)$ is the number of elements of $X$ (the same as $|X|$ ). A Venn diagram splits the class into four regions: P only, both, B only, and neither. Fill in the region you know best (usually "both") first, then work outwards.

Regions add up. With a universe

U

(the whole class):

n(U) = n(P \text{ only}) + n(\text{both}) + n(B \text{ only}) + n(\text{neither})

, and

n(\text{neither}) = n(U) - n(P \cup B)

Example 14How many students in the class?

In a class, 30 students took Physics, 25 took Biology, 10 took both, and 5 took neither. How many students are there in the class?

Solution

Figure 26. Start from the middle: 10 took both

Draw sets for Physics ( $P$ ) and Biology ( $B$ ). 10 students are in $P \cap B$ .
This leaves $30 - 10 = 20$ students in $P \setminus B$ (took Physics but not Biology).
Likewise $25 - 10 = 15$ students in $B \setminus P$ (took Biology but not Physics).
5 students are outside $P \cup B$ : in the class but took neither.
Class strength: $20 + 10 + 15 + 5 = 50$ .

Example 15Biology but not Physics

In a class of 55 students, 32 took Physics, 11 took both Physics and Biology, and 7 took neither. How many took Biology but not Physics?

Solution

Figure 27. The unknown region is B only

Physics only: $32 - 11 = 21$ .
Let $x$ = number who took Biology but not Physics. The four regions add up to the class: $55 = x + 11 + 21 + 7$ .
So $55 = x + 39$ , giving $x = 55 - 39 = 16$ .
16 students took Biology but not Physics.

Example 16Both subjects

In a class of 60 students, 35 took Physics, 30 took Biology, and 10 took neither. How many took both Physics and Biology?

Solution

Figure 28. Here the middle is the unknown, so use the formula

Students who took at least one subject: $n(P \cup B) = 60 - 10 = 50$ .
$n(P) = 35$ and $n(B) = 30$ , so $n(P) + n(B) = 35 + 30 = 65$ .
From $n(P \cup B) = n(P) + n(B) - n(P \cap B)$ : $50 = 65 - n(P \cap B)$ .
Thus $n(P \cap B) = 65 - 50 = 15$ . (Then Physics only = 20 and Biology only = 15; check: $20 + 15 + 15 + 10 = 60$ .)

6.4Summary

Set notation is a useful way to concisely describe collections of objects.
Set comprehension combines generators, filters and transformations to produce new sets from old.
Venn diagrams are useful to work out problems involving sets.

6.5Going deeper: a method for Venn problems

Every two-set counting problem uses the same four regions. Follow this order:

Write the total $n(U)$ , the two set sizes, the overlap $n(P \cap B)$ and the "neither" count, marking which ones are unknown.
Find the union: $n(P \cup B) = n(U) - n(\text{neither})$ .
Use $n(P \cup B) = n(P) + n(B) - n(P \cap B)$ to find whichever of the three is missing.
Fill the regions: P only $= n(P) - n(\text{both})$ , B only $= n(B) - n(\text{both})$ .
Check that the four regions add up to the total.

Question wording	Formula
At least one subject	$n(P \cup B)$
Both subjects	$n(P \cap B)$
Only Physics	$n(P) - n(P \cap B)$
Exactly one subject	$n(P) + n(B) - 2\,n(P \cap B)$
At most one subject	$n(U) - n(P \cap B)$
Neither	$n(U) - n(P \cup B)$

Filter or generate. The perfect squares can be written by filtering $\{n \in \mathbb{N} \mid \sqrt{n} \in \mathbb{N}\}$ or by generating $\{n^2 \mid n \in \mathbb{N}\}$ . Both give $\{0, 1, 4, 9, \dots\}$ .

6.6Laws of set operations, De Morgan's laws and counting with three sets

The operations $\cup$ , $\cap$ , $-$ and complement obey a short list of laws. Knowing them lets you simplify a set expression instead of testing it element by element.

A. The laws (for subsets of a universal set $U$ )

Law	Statement
Commutative	$A \cup B = B \cup A$ , $A \cap B = B \cap A$
Associative	$(A \cup B) \cup C = A \cup (B \cup C)$ , same for $\cap$
Distributive	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Identity and domination	$A \cup \emptyset = A$ , $A \cap U = A$ , $A \cup U = U$ , $A \cap \emptyset = \emptyset$
Complement	$A \cup A^c = U$ , $A \cap A^c = \emptyset$ , $(A^c)^c = A$
De Morgan	$(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$
Difference	$A - B = A \cap B^c$
Subset equivalences	$A \subseteq B \iff A \cup B = B \iff A \cap B = A \iff B^c \subseteq A^c$

De Morgan in words. "Not (in $A$ or in $B$ )" means "not in $A$ and not in $B$ ". "Not (in $A$ and in $B$ )" means "not in $A$ or not in $B$ ". The complement swaps $\cup$ and $\cap$ .

Proof of the first law. $x \in (A \cup B)^c \iff x \notin A \cup B \iff (x \notin A \text{ and } x \notin B) \iff x \in A^c \cap B^c$ . $\blacksquare$

Numeric check. $U = \{1, \dots, 10\}$ , $A = \{1, 2, 3, 4\}$ , $B = \{3, 4, 5, 6\}$ . Then $A \cup B = \{1, \dots, 6\}$ , so $(A \cup B)^c = \{7, 8, 9, 10\}$ . Also $A^c = \{5, \dots, 10\}$ and $B^c = \{1, 2, 7, 8, 9, 10\}$ , so $A^c \cap B^c = \{7, 8, 9, 10\}$ ✓.

B. Symmetric difference

$A \triangle B$ is the set of elements in exactly one of $A$ and $B$ : $A \triangle B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$ . Its size is

|A \triangle B| = |A| + |B| - 2|A \cap B|

(the overlap is removed from both). For $A$ and $B$ above: $A \triangle B = \{1, 2, 5, 6\}$ , and $4 + 4 - 2 \cdot 2 = 4$ ✓.

C. Counting with three sets

Inclusion–exclusion for three sets

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Add the singles, subtract the pairwise overlaps (each pair was counted twice), and add back the triple overlap (it was added three times and subtracted three times, so it vanished).

Example. Of 100 students, 60 take Maths (M), 50 Physics (P), 40 Chemistry (C); 30 take M and P, 20 take M and C, 15 take P and C, and 10 take all three.

At least one subject: $60 + 50 + 40 - 30 - 20 - 15 + 10 = 95$ . So $100 - 95 = 5$ take none.
Only Maths: $60 - 30 - 20 + 10 = 20$ . Only Physics: $50 - 30 - 15 + 10 = 15$ . Only Chemistry: $40 - 20 - 15 + 10 = 15$ . Exactly one subject: $20 + 15 + 15 = 50$ .
Exactly two subjects: $(30 - 10) + (20 - 10) + (15 - 10) = 35$ . All three: $10$ .
Check: $50 + 35 + 10 + 5 = 100$ ✓.

"At least" versus "exactly". The pair counts

|M \cap P|

etc. include the students who take all three. To get "exactly two", subtract the triple count from each pair first.

6.7Exam tips and common mistakes

Exam tips

Always draw the diagram, even when the formula looks easy.
Start from the region you know best, usually "both".
Finish by checking that all four regions sum to the class strength.

Common mistakes

Treating $n(P)$ as "Physics only". It includes the students who took both.
Adding $n(P) + n(B)$ and forgetting to subtract the overlap, so the middle is counted twice.
Forgetting the "neither" region when computing the class total.

Practice questions (graded-assignment style)

Q1Both subjects

Numerical Answer Type (NAT).

In a class of 80, 50 took Physics, 45 took Biology and 15 took neither. How many took both?

Solution

Idea

Find the union first.

$n(P \cup B) = 80 - 15 = 65$ .
$65 = 50 + 45 - n(P \cap B)$ , so $n(P \cap B) = 95 - 65 = 30$ .
Answer: 30

Q2Exactly one subject

Numerical Answer Type (NAT).

In a class of 40, 22 took Maths, 18 took Computer Science and 8 took both. How many took exactly one of the two?

Solution

Idea

Remove the overlap from each side.

Maths only: $22 - 8 = 14$ . CS only: $18 - 8 = 10$ .
Exactly one: $14 + 10 = 24$ .
(Neither would be $40 - (14 + 8 + 10) = 8$ .)
Answer: 24

Q3The union formula

Multiple Choice Question (MCQ): choose the one correct option.

Which formula gives $n(P \cup B)$ ?

n(P) + n(B)

n(P) + n(B) - n(P \cap B)

n(P) \cdot n(B)

n(P) - n(B)

Solution

Idea

Adding both sizes counts the overlap twice.

Subtract the overlap once to count it once.
Answer: option 2.

Q4Equal sets

Multiple Choice Question (MCQ): choose the one correct option.

Which set equals $\{n^2 \mid n \in \mathbb{N}\}$ ?

\{n \in \mathbb{N} \mid \sqrt{n} \in \mathbb{N}\}

\{2n \mid n \in \mathbb{N}\}

\{n^3 \mid n \in \mathbb{N}\}

\{n \in \mathbb{N} \mid n > 0\}

Solution

Idea

Squares can be generated or filtered.

A natural number has a natural square root exactly when it is a perfect square.
Options 2, 3 and 4 give evens, cubes and positives.
Answer: option 1.

S1De Morgan

Multiple Choice Question (MCQ): choose the one correct option.

Which set equals $(A \cup B)^c$ ?

A^c \cup B^c

A^c \cap B^c

A^c - B^c

(A \cap B)^c

Solution

Idea

Not in the union means in neither set.

$x \notin A \cup B$ means $x \notin A$ and $x \notin B$ , i.e. $x \in A^c \cap B^c$ .
Option 1 is $(A \cap B)^c$ , the other De Morgan law, which equals option 4. Check with $A = \{1\}$ , $B = \{2\}$ , $U = \{1, 2, 3\}$ : $(A \cup B)^c = \{3\}$ , while $A^c \cup B^c = \{1, 2, 3\}$ .
Answer: option 2.

S2Students taking none of three subjects

Numerical Answer Type (NAT).

Of 100 students, 60 take Maths, 50 Physics and 40 Chemistry; 30 take Maths and Physics, 20 take Maths and Chemistry, 15 take Physics and Chemistry, and 10 take all three. How many take none of the three?

Solution

Idea

Count the union by inclusion–exclusion, then subtract from the total.

$|M \cup P \cup C| = 60 + 50 + 40 - 30 - 20 - 15 + 10 = 95$ .
None $= 100 - 95 = 5$ .
Answer: 5

S3Exactly one subject

Numerical Answer Type (NAT).

In the same class, how many students take exactly one of the three subjects?

Solution

Idea

For "only Maths", remove from 60 everyone who also takes Physics or Chemistry, and add back the triple overlap that was removed twice.

Only Maths: $60 - 30 - 20 + 10 = 20$ .
Only Physics: $50 - 30 - 15 + 10 = 15$ . Only Chemistry: $40 - 20 - 15 + 10 = 15$ .
Total $= 20 + 15 + 15 = 50$ . Check: exactly two $= 20 + 10 + 5 = 35$ , all three $= 10$ , none $= 5$ ; $50 + 35 + 10 + 5 = 100$ ✓.
Answer: 50

S4True or false: set identities

Multiple Select Question (MSQ): select all that apply.

Choose the correct statements for subsets $A, B, C$ of a universal set $U$ .

A - B = A \cap B^c

(A \cap B)^c = A^c \cap B^c

A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

A \subseteq B

if and only if

B^c \subseteq A^c

|A \triangle B| = |A| + |B| - |A \cap B|

Solution

Idea

Match each with the laws, and test a false-looking one on a tiny example.

1 ✓ $x \in A - B$ means $x \in A$ and $x \notin B$ .
2 ✗ De Morgan gives $(A \cap B)^c = A^c \cup B^c$ . With $A = \{1\}$ , $B = \{2\}$ , $U = \{1, 2\}$ : $(A \cap B)^c = U$ , but $A^c \cap B^c = \{2\} \cap \{1\} = \emptyset$ .
3 ✓ The second distributive law.
4 ✓ The contrapositive form: anything outside $B$ is outside $A$ .
5 ✗ It is $|A| + |B| - 2|A \cap B|$ ; the formula in the option is $|A \cup B|$ .
Answer: options 1, 3 and 4.

S5Size of a symmetric difference

Numerical Answer Type (NAT).

$A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$ . Find $|A \triangle B|$ .

Solution

Idea

Elements in exactly one of the two sets.

$A \cap B = \{3, 4\}$ , so $|A \cap B| = 2$ . $|A \triangle B| = 4 + 4 - 2 \cdot 2 = 4$ .
Direct: $A - B = \{1, 2\}$ and $B - A = \{5, 6\}$ , so $A \triangle B = \{1, 2, 5, 6\}$ ✓.
Answer: 4

Revision overview

Comprehension practiceSquares of evens: {x² | x ∈ ℤ, x mod 2 = 0}
Reals in [−1, 2): −1 ≤ r < 2
Not every part is needed

Readable definitionsX = {n | n ∈ ℕ, n < 500}
Y = {n³ | n ∈ X}
Name a set, then reuse it

Perfect squaresFilter: {n | √n ∈ ℕ}
Generate: {n² | n ∈ ℕ}
Rationals: 9/16 = (3/4)², but not 1/2

Sets in ActionWeek 1 · Sets

Venn regionsP only, both, B only, neither
Fill "both" first, work outwards
All four regions add up to the total

Union formulan(P ∪ B) = n(P) + n(B) − n(P ∩ B)
Overlap is counted twice otherwise
Neither = total − n(P ∪ B)

Revision: set examples and counting on one page

Next · Relations · Part 1 of 2Relations

Relations · Part 1 of 2

Relations

Sets on their own just collect objects. To talk about how objects are connected (one number dividing another, a student taking a course, a point lying on a circle) we pair elements up. Pairs come from the Cartesian product, and a relation is simply a chosen collection of pairs.

7.1Cartesian product

Definition: Cartesian product

The Cartesian product of sets $A$ and $B$ is the set of all ordered pairs with the first element from $A$ and the second from $B$ :

A \times B = \{(a, b) \mid a \in A,\ b \in B\}

Pair up elements from $A$ and $B$ : if $A = \{0, 1\}$ and $B = \{2, 3\}$ , then $A \times B = \{(0, 2), (0, 3), (1, 2), (1, 3)\}$ .
In a pair, the order is important: $(0, 1) \neq (1, 0)$ .
For sets of numbers, visualise the product as two-dimensional space: $\mathbb{N} \times \mathbb{N}$ is a grid of points.
For finite sets, $|A \times B| = |A| \cdot |B|$ : each of the $|A|$ choices of first entry pairs with each of the $|B|$ choices of the second.

Figure 29. A × B for A = {a, b} and B = {1, 2, 3}: six ordered pairs

7.2Binary relations

A relation selects some pairs from the Cartesian product. The natural way to do that is to combine the Cartesian product with set comprehension:

\{(m, n) \mid (m, n) \in \mathbb{N} \times \mathbb{N},\ n = m + 1\} = \{(0, 1), (1, 2), (2, 3), \dots, (17, 18), \dots\}

\{(d, n) \mid (d, n) \in \mathbb{N} \times \mathbb{N},\ d \mid n\} = \{(1, 1), \dots, (2, 82), \dots, (14, 56), \dots\}

Definition: binary relation

A binary relation from $A$ to $B$ is a subset of the Cartesian product: $R \subseteq A \times B$ . If $(a, b) \in R$ we also write $a\,R\,b$ and say " $a$ is related to $b$ ".

Figure 30. Two relations on ℕ × ℕ, seen as chosen points of the grid

With $A = \{a, b\}$ and $B = \{1, 2, 3\}$ , each of these is a relation from $A$ to $B$ , because each is a subset of $A \times B$ :

Relation	Pairs	Note
$R_1$	$\{(a, 1), (b, 2), (b, 3)\}$	$b$ is related to two elements
$R_2$	$\{(a, 2), (b, 1)\}$
$R_3$	$\{(b, 3)\}$	$a$ is related to nothing
$R_4$	$\{(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)\}$	all of $A \times B$

Figure 31. A relation drawn as arrows from A to B

Two extreme relations. The empty set

\emptyset

is a relation (nothing is related), and

A \times B

itself is a relation (everything is related). A relation is any subset, so there are

2^{|A| \cdot |B|}

relations from

A

B

when both are finite.

7.3More relations

Points at distance 5 from $(0, 0)$ . The distance from $(0, 0)$ to $(a, b)$ is $\sqrt{a^2 + b^2}$ , so the relation is

\{(a, b) \mid (a, b) \in \mathbb{R} \times \mathbb{R},\ \sqrt{a^2 + b^2} = 5\} = \{(0, 5), (5, 0), (3, 4), (-3, -4), \dots\}

Figure 32. The related pairs form a circle with centre (0, 0)

Rationals in reduced form. This set is a subset of $\mathbb{Q}$ : $\{\frac{p}{q} \mid (p, q) \in \mathbb{Z} \times \mathbb{Z},\ q \neq 0,\ \gcd(p, q) = 1\}$ . But it is also a relation on $\mathbb{Z} \times \mathbb{Z}$ : $\{(p, q) \mid (p, q) \in \mathbb{Z} \times \mathbb{Z},\ \gcd(p, q) = 1\}$ .

7.4Beyond binary relations

We can take Cartesian products of more than two sets. A product of $n$ sets generates $n$ -tuples: $(x_1, x_2, \dots, x_n) \in X_1 \times X_2 \times \cdots \times X_n$ , and a relation can pick out some of them.

Pythagorean triples

A relation on three sets

The square on the hypotenuse is the sum of the squares on the other two sides:

\{(a, b, c) \mid (a, b, c) \in \mathbb{N}^3,\ a, b, c > 0,\ a^2 + b^2 = c^2\}

Corners of squares

A relation on four sets

A corner is a point $(x, y) \in \mathbb{R} \times \mathbb{R}$ . Four points $((x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4))$ are related if they are the four corners of a square:

Sq \subseteq \mathbb{R}^2 \times \mathbb{R}^2 \times \mathbb{R}^2 \times \mathbb{R}^2

Figure 33. Two members of the relation Sq

Example 17Cartesian product and order

Let $A = \{0, 1\}$ and $B = \{2, 3\}$ . List $A \times B$ and $B \times A$ . Are they equal? Is $(1, 0) \in A \times B$ ?

Solution

Pair each element of $A$ with each element of $B$ : $A \times B = \{(0, 2), (0, 3), (1, 2), (1, 3)\}$ , which has $2 \times 2 = 4$ pairs.
Swap roles: $B \times A = \{(2, 0), (2, 1), (3, 0), (3, 1)\}$ .
No pair appears in both lists, because order matters. So $A \times B \neq B \times A$ .
$(1, 0) \notin A \times B$ : its second entry 0 is not in $B$ .

Example 18Testing membership in a relation

Which of $(3, 4, 5)$ , $(5, 12, 13)$ , $(2, 3, 4)$ are Pythagorean triples? Which of $(3, -4)$ , $(4, 4)$ , $(-5, 0)$ are at distance 5 from the origin?

Solution

Tuple	Check	In the relation?
$(3, 4, 5)$	$9 + 16 = 25 = 5^2$	Yes
$(5, 12, 13)$	$25 + 144 = 169 = 13^2$	Yes
$(2, 3, 4)$	$4 + 9 = 13 \neq 16$	No
$(3, -4)$	$\sqrt{9 + 16} = \sqrt{25} = 5$	Yes
$(4, 4)$	$\sqrt{16 + 16} = \sqrt{32} \neq 5$	No
$(-5, 0)$	$\sqrt{25 + 0} = 5$	Yes

7.5Going deeper: counting pairs and relations

Three views of one relation. A list of pairs, arrows from $A$ to $B$ , and chosen points of a grid describe the same subset of $A \times B$ .
Counting. $|A \times B| = |A| \cdot |B|$ . A relation is any subset of $A \times B$ , so there are $2^{|A| \cdot |B|}$ relations from $A$ to $B$ . For $|A| = 2$ and $|B| = 3$ that is $2^6 = 64$ .
Relations on one set. A relation on $A$ is a subset of $A \times A$ . With $|A| = 3$ there are $2^9 = 512$ of them.
Order matters in a pair, not in a set. $(1, 2) \neq (2, 1)$ but $\{1, 2\} = \{2, 1\}$ . A pair may repeat an element: $(a, a)$ is allowed.
Testing a pair. To see if $(a, b)$ is in a relation, first check that $a$ and $b$ belong to the right sets, then plug into the condition (for example $n = m + 1$ or $\sqrt{a^2 + b^2} = 5$ ).
Also relations. $\emptyset$ and $A \times B$ itself are both relations.

7.6Exam tips and common mistakes

Exam tips

First check the coordinates against the sets, then test the condition.
Count pairs with $|A| \cdot |B|$ , and count relations with $2^{|A||B|}$ .
Write pairs with parentheses and sets with braces.

Common mistakes

Assuming $A \times B = B \times A$ .
Writing $(b, a)$ when the relation says $(a, b)$ .
Mixing up the number of pairs, $|A||B|$ , with the number of relations, $2^{|A||B|}$ .
Forgetting that the empty relation counts.

Practice questions (graded-assignment style)

Q1Size of a product

Numerical Answer Type (NAT).

$A = \{1, 2, 3\}$ and $B = \{x, y\}$ . What is $|A \times B|$ ?

Solution

Idea

Multiply the sizes.

$|A| = 3$ and $|B| = 2$ , so $|A \times B| = 3 \cdot 2 = 6$ .
Answer: 6

Q2Number of relations

Numerical Answer Type (NAT).

How many relations are there from $A$ to $B$ when $|A| = 2$ and $|B| = 3$ ?

Solution

Idea

A relation is any subset of A × B.

$|A \times B| = 6$ .
Each of the 6 pairs is in or out: $2^6 = 64$ subsets, so 64 relations.
Answer: 64

Q3Members of A × B

Multiple Select Question (MSQ): select all that apply.

Let $A = \{0, 1\}$ and $B = \{2, 3\}$ . Which pairs belong to $A \times B$ ?

(0, 3)

(3, 0)

(1, 2)

(1, 1)

Solution

Idea

The first entry must be from A and the second from B.

$(0, 3)$ : 0 is in A, 3 is in B, yes.
$(3, 0)$ : 3 is not in A, no.
$(1, 2)$ : yes.
$(1, 1)$ : 1 is not in B, no.
Answer: options 1 and 3.

Q4A relation by rule

Multiple Choice Question (MCQ): choose the one correct option.

The relation $\{(a, b) \mid b = a + 1\}$ on $\mathbb{N}$ . Which pair belongs to it?

(4, 3)

(3, 4)

(3, 3)

(5, 7)

Solution

Idea

Put the pair into the condition.

$(3, 4)$ : $4 = 3 + 1$ , yes.
$(4, 3)$ : $3 \neq 5$ ; $(3, 3)$ : $3 \neq 4$ ; $(5, 7)$ : $7 \neq 6$ .
Answer: option 2.

Revision overview

Cartesian productA × B = {(a, b) | a ∈ A, b ∈ B}
Order matters: (0, 1) ≠ (1, 0)
|A × B| = |A| · |B|

Binary relationR ⊆ A × B: some chosen pairs
Notation (a, b) ∈ R or aRb
Product + comprehension

Examples on ℕ × ℕn = m + 1: (0,1), (1,2), …
d divides n: (2, 82), (14, 56)
Visualise as points of a grid

RelationsWeek 1 · Relations

Geometric relations√(a² + b²) = 5: a circle
gcd(p, q) = 1 on ℤ × ℤ

Beyond binaryn sets give n-tuples
Pythagorean triples ⊆ ℕ × ℕ × ℕ
Corners of squares: 4-tuples of points

Revision: relations on one page

Next · Relations · Part 2 of 2Types of Relations

Relations · Part 2 of 2

Types of Relations

Most interesting relations connect a set to itself: $R \subseteq A \times A$ . Such relations can have special properties, and one combination of properties, the equivalence relation, groups the elements of a set into classes.

8.1The identity relation

Definition: identity relation

The identity relation on $A$ relates each element to itself and nothing else:

I = \{(a, b) \mid (a, b) \in A \times A,\ a = b\} = \{(a, a) \mid a \in A\}

For $S = \{1, 2, 3, 4\}$ the identity relation is $\{(1, 1), (2, 2), (3, 3), (4, 4)\}$ .

8.2Reflexive relations

Definition: reflexive

A relation $R \subseteq A \times A$ is reflexive if $I \subseteq R$ : for every $x \in A$ , $(x, x) \in R$ .

$\{(a, b) \mid (a, b) \in \mathbb{N} \times \mathbb{N},\ a, b > 0,\ a \mid b\}$ is reflexive, since $a \mid a$ for all $a > 0$ .
On $S = \{1, 2, 3, 4\}$ : $R_1 = \{(1, 1), (2, 2), (3, 3), (4, 4)\}$ (the identity) and $R_3 = \{(1, 1), (2, 2), (3, 3), (4, 4), (2, 4), (4, 1)\}$ are reflexive. $R_2 = \{(1, 1), (2, 3), (2, 2), (4, 4), (3, 4)\}$ is not, because $(3, 3) \notin R_2$ .

8.3Symmetric relations

Definition: symmetric

$R$ is symmetric if $(a, b) \in R$ if and only if $(b, a) \in R$ : every pair comes with its reverse.

$\{(a, b) \mid \gcd(a, b) = 1\}$ and $\{(a, b) \mid |a - b| = 2\}$ on $\mathbb{N} \times \mathbb{N}$ are symmetric: swapping $a$ and $b$ does not change the condition.
$\{(1, 2), (2, 1), (3, 4), (4, 3), (2, 2)\}$ and $\{(1, 2), (2, 3), (2, 1), (3, 2), (4, 3), (3, 4)\}$ are symmetric. $\{(2, 1), (1, 2), (3, 4), (2, 4), (4, 2)\}$ is not: $(3, 4)$ is in it but $(4, 3)$ is not.

8.4Transitive relations

Definition: transitive

$R$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$ , also $(a, c) \in R$ .

$\{(a, b) \mid a \mid b\}$ on $\mathbb{N} \times \mathbb{N}$ is transitive: if $a \mid b$ and $b \mid c$ then $a \mid c$ .
$\{(a, b) \mid (a, b) \in \mathbb{R} \times \mathbb{R},\ a < b\}$ is transitive: if $a < b$ and $b < c$ then $a < c$ .
On $\{1, 2, 3, 4\}$ : $\{(1, 2), (2, 3), (1, 3)\}$ , $\{(1, 4)\}$ and $\{(1, 3), (1, 4)\}$ are transitive. $\{(1, 2), (2, 1), (1, 1), (2, 3)\}$ is not: $(1, 2)$ and $(2, 3)$ are in it, but $(1, 3)$ is not.

Vacuous truth.

\{(1, 4)\}

has no chain

(a, b), (b, c)

at all, so there is nothing that could fail. A condition with no cases to check is automatically true.

8.5Antisymmetric relations

Definition: antisymmetric

$R$ is antisymmetric if whenever $(a, b) \in R$ and $a \neq b$ , then $(b, a) \notin R$ : no two different elements are related both ways.

$\{(a, b) \mid (a, b) \in \mathbb{R} \times \mathbb{R},\ a < b\}$ : if $a < b$ then $b \not< a$ .
$M \subseteq P \times P$ relating mothers to children: if $(p, c) \in M$ then $(c, p) \notin M$ .

Not opposites. "Symmetric" and "antisymmetric" are not opposites. The identity relation is both;

\{(1, 2), (2, 1), (2, 3)\}

is neither (it has the two-way pair

1 \leftrightarrow 2

, so not antisymmetric, but

(2, 3)

has no return, so not symmetric).

Figure 34. Arrow diagrams on S = {1, 2, 3, 4}: a loop is a pair (x, x)

8.6Equivalence relations

Definition: equivalence relation

A relation that is reflexive, symmetric and transitive is an equivalence relation.

Same remainder modulo 5. $7 \bmod 5 = 2$ and $22 \bmod 5 = 2$ . If $a \bmod 5 = b \bmod 5$ , then $b - a$ is a multiple of 5. So define

\mathbb{Z} \bmod 5 = \{(a, b) \mid a, b \in \mathbb{Z},\ (b - a) \bmod 5 = 0\}

Reflexive: $a - a = 0$ is a multiple of 5.
Symmetric: if $b - a$ is a multiple of 5, so is $a - b = -(b - a)$ .
Transitive: if $b - a$ and $c - b$ are multiples of 5, so is their sum $c - a$ .

This relation divides the integers into 5 groups, based on the remainder when divided by 5.

Figure 35. Same remainder modulo 5 splits ℤ into five classes

Partitions and classes

An equivalence relation partitions a set: every element lands in exactly one group, and the groups do not overlap. The groups of equivalent elements are called equivalence classes.

Measuring time. A clock displays hours modulo 12. 2:00 am is equivalent to 2:00 pm, and 4 hours after 9 o\'clock the clock shows 1.

Figure 36. A clock works with equivalence classes of hours modulo 12

On $S = \{1, 2, 3, 4\}$ , $R_1 = \{(1, 1), (2, 2), (3, 3), (4, 4), (2, 3), (3, 2), (4, 1), (1, 4)\}$ is an equivalence relation. Its classes are $\{1, 4\}$ and $\{2, 3\}$ .

Figure 37. The equivalence relation R₁ splits S into two classes

Figure 38. The checklist for any relation on a set

Example 19Match the relations with their properties

On $S = \{1, 2, 3\}$ , match each relation with a property: reflexive, symmetric, transitive, equivalence.

$R_1 = \{(1, 3), (3, 2), (1, 1), (2, 3), (3, 1)\}$
$R_2 = \{(1, 1), (2, 3), (3, 2), (2, 2), (3, 3)\}$
$R_3 = \{(3, 1), (1, 1), (2, 1), (2, 3), (3, 3), (2, 2)\}$
$R_4 = \{(3, 2), (3, 1), (2, 1)\}$

Solution

	Reflexive	Symmetric	Transitive	Match
$R_1$	No: no (2,2)	Yes: (1,3)↔(3,1), (3,2)↔(2,3)	No: (1,3), (3,2) but no (1,2)	Symmetric
$R_2$	Yes: (1,1), (2,2), (3,3)	Yes: (2,3)↔(3,2)	Yes: (2,3), (3,2) give (2,2) ✓	Equivalence
$R_3$	Yes: (1,1), (2,2), (3,3)	No: (3,1) but no (1,3)	Yes: (2,3), (3,1) give (2,1) ✓	Reflexive
$R_4$	No: no loops	No: (3,2) but no (2,3)	Yes: (3,2), (2,1) give (3,1) ✓	Transitive

$R_2$ is reflexive, symmetric and transitive, so it is the equivalence relation (classes $\{1\}$ and $\{2, 3\}$ ). $R_3$ is reflexive (and also transitive), and $R_4$ is only transitive.

Example 20A transitivity trap

On $S = \{1, 2, 3, 4\}$ , is $R = \{(2, 4), (1, 2), (1, 4), (4, 1), (1, 1), (2, 1)\}$ transitive?

Solution

Many chains work: $(1, 2), (2, 4)$ gives $(1, 4)$ ✓; $(2, 4), (4, 1)$ gives $(2, 1)$ ✓; $(1, 4), (4, 1)$ gives $(1, 1)$ ✓.
But take $(4, 1) \in R$ and $(1, 2) \in R$ . Transitivity needs $(4, 2)$ .
$(4, 2) \notin R$ , so $R$ is not transitive. (Also $(4, 1), (1, 4)$ would need $(4, 4)$ , which is missing too.)
Lesson: check every chain, including ones that start from the second element of a two-way pair.

BonusSymmetric, antisymmetric, both or neither?

On $S = \{1, 2, 3\}$ , classify each relation as symmetric and/or antisymmetric: $A_1 = \{(1, 1), (2, 2)\}$ , $A_2 = \{(1, 2), (2, 1)\}$ , $A_3 = \{(1, 2), (2, 3)\}$ , $A_4 = \{(1, 2), (2, 1), (2, 3)\}$ .

Solution

	Symmetric?	Antisymmetric?	Verdict
$A_1$	Yes: only loops	Yes: no pair of different elements	both
$A_2$	Yes	No: (1,2) and (2,1)	symmetric only
$A_3$	No: (1,2) has no (2,1)	Yes	antisymmetric only
$A_4$	No: (2,3) has no (3,2)	No: (1,2) and (2,1)	neither

8.7Summary of relations

Property	Condition	Example	Non-example
Reflexive	$\text{every } (x, x) \in R$	$a \mid b$ on positive naturals	$a < b$
Symmetric	$(a, b) \in R \Rightarrow (b, a) \in R$	$\|a - b\| = 2$	$a < b$
Transitive	$(a, b), (b, c) \in R \Rightarrow (a, c) \in R$	$a \mid b,\ a < b$	$\{(1, 2), (2, 1), (1, 1), (2, 3)\}$
Antisymmetric	$(a, b) \in R,\ a \neq b \Rightarrow (b, a) \notin R$	$a < b$ , "mother of"	$\|a - b\| = 2$
Equivalence	reflexive + symmetric + transitive	same remainder mod 5	$a \mid b$

Cartesian products generate $n$ -tuples from $n$ sets.
A relation picks out a subset of a Cartesian product.
Properties of relations: reflexive, symmetric, transitive, antisymmetric.
An equivalence relation partitions a set.

8.8Going deeper: checking properties systematically

Reflexive: go through every element of $S$ , even those that never appear in a pair, and look for its loop $(x, x)$ . One missing loop is enough to fail.
Symmetric: for each pair $(a, b)$ look for $(b, a)$ . Loops $(x, x)$ are their own reverse, so they never cause a failure.
Transitive: for each pair $(a, b)$ and each pair starting at $b$ , check that $(a, c)$ is present. Include chains through loops and chains that start from the second element of a two-way pair.
Antisymmetric: look for two-way pairs $(a, b), (b, a)$ with $a \neq b$ . If you find one, it fails.
Proving versus disproving. To prove a property you need a general argument. To disprove it a single counterexample is enough.

Properties of common relations

Relation	Reflexive	Symmetric	Transitive	Antisymmetric	Equivalence?
$a = b$	yes	yes	yes	yes	equivalence
$a \le b$	yes	no	yes	yes	none
$a < b$	no	no	yes	yes	none
$a \mid b$ (positive)	yes	no	yes	yes	none
$\|a - b\| = 2$	no	yes	no	no	none
same remainder mod 5	yes	yes	yes	no	equivalence

Reflexive and symmetric do not give transitive. On $\{1, 2, 3\}$ , $\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}$ is reflexive and symmetric, but $(1, 2), (2, 3)$ need $(1, 3)$ , which is missing.
Classes. "Same remainder mod $n$ " splits $\mathbb{Z}$ into exactly $n$ classes, which do not overlap and together cover $\mathbb{Z}$ .

8.9Exam tips and common mistakes

Exam tips

Check all four properties for every relation in a table, one at a time.
Always quote the exact missing pair when a property fails.
For an equivalence relation, finish by listing the classes.

Common mistakes

Treating "symmetric" and "antisymmetric" as opposites. The identity is both, and some relations are neither.
Missing a loop for an element that appears in no pair.
Checking only the obvious chains for transitivity.
Assuming reflexive plus symmetric is enough for an equivalence.

Practice questions (graded-assignment style)

Q1Classify a relation

Multiple Choice Question (MCQ): choose the one correct option.

On $S = \{1, 2, 3\}$ let $R = \{(1, 1), (2, 2)\}$ . Which statement is true?

R

is reflexive.

R

is not reflexive, but it is symmetric, transitive and antisymmetric.

R

is an equivalence relation.

R

is not symmetric.

Solution

Idea

Reflexive needs a loop for every element of $S$ , including 3.

$(3, 3) \notin R$ , so $R$ is not reflexive (options 1 and 3 are false).
The only pairs are loops, so $R$ is symmetric, antisymmetric and transitive.
Answer: option 2.

Q2Less than

Multiple Select Question (MSQ): select all that apply.

Consider $\{(a, b) \mid a < b\}$ on $\mathbb{R}$ . Choose the correct statements.

Reflexive

Symmetric

Transitive

Antisymmetric

Solution

Idea

Test each property with a number or two.

Reflexive: $a < a$ is false.
Symmetric: $1 < 2$ but $2 < 1$ is false.
Transitive: $a < b$ and $b < c$ give $a < c$ .
Antisymmetric: $a < b$ means $b < a$ fails.
Answer: options 3 and 4.

Q3Number of classes

Numerical Answer Type (NAT).

How many equivalence classes does "same remainder mod 7" create on $\mathbb{Z}$ ?

Solution

Idea

One class for each possible remainder.

Remainders are $0, 1, \dots, 6$ , which is 7 values.
Answer: 7

Q4Why not an equivalence?

Multiple Choice Question (MCQ): choose the one correct option.

On $\{1, 2, 3\}$ , $R = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}$ . Why is $R$ not an equivalence relation?

It is not reflexive.

It is not symmetric.

It is not transitive:

(1, 2), (2, 3) \in R

but

(1, 3) \notin R

It is an equivalence relation.

Solution

Idea

Check every chain.

All three loops are present, so it is reflexive.
Every pair has its reverse, so it is symmetric.
The chain $1 \to 2 \to 3$ needs $(1, 3)$ , so it is not transitive.
Answer: option 3.

Revision overview

Identity & reflexiveI = {(a, a) | a ∈ A}
Reflexive: I ⊆ R
Example: a | b on positive ℕ

Symmetric(a, b) ∈ R iff (b, a) ∈ R
gcd(a, b) = 1, |a − b| = 2

Transitive(a,b), (b,c) ⇒ (a,c)
Divides; less than
Check every chain

Types of RelationsWeek 1 · Relations

Antisymmetrica ≠ b: never both ways
Less than; mother of
Not the opposite of symmetric

EquivalenceReflexive + symmetric + transitive
Same remainder mod 5
Clock: hours mod 12

PartitionsEquivalence splits a set
Groups = equivalence classes
mod 5 gives 5 classes

Revision: types of relations on one page

Next · Functions · Part 1 of 2Functions

Functions · Part 1 of 2

Functions

A function is the most important kind of relation in data science: a rule that turns each input into exactly one output. This topic defines functions, the sets around them (domain, codomain, range), and how a function is drawn as a graph.

9.1A rule to map inputs to outputs

Convert $x$ to $x^2$ . The rule is $x \mapsto x^2$ .
Give the rule a name: $\text{sq}(x) = x^2$ . The input $x$ is a parameter.

Figure 39. The function sq turns each input into its square

9.2Domain, codomain and range

A rule alone is not enough: we need to specify the input and output sets.

Term	Meaning	For sq
Domain	the input set	$\text{domain}(\text{sq}) = \mathbb{R}$
Codomain	the output set of possible values	$\text{codomain}(\text{sq}) = \mathbb{R}$
Range	the actual values that the output can take	$\text{range}(\text{sq}) = \mathbb{R}_{\ge 0} = \{r \mid r \in \mathbb{R},\ r \ge 0\}$

Notation

$f : X \to Y$ means $f$ is a function from $X$ to $Y$ : the domain of $f$ is $X$ and the codomain is $Y$ . The range is

\text{range}(f) = \{y \mid y \in Y,\ y = f(x) \text{ for some } x \in X\}

The range is always a subset of the codomain.

Figure 40. The range sits inside the codomain

9.3Functions as relations

We can associate a relation $R_f$ with each function $f$ : the set of all (input, output) pairs.

R_{\text{sq}} = \{(x, y) \mid x, y \in \mathbb{R},\ y = x^2\} \qquad R_f \subseteq \text{domain}(f) \times \text{range}(f)

For $R_{\text{sq}}$ we also use the additional notation $y = x^2$ . Not every relation comes from a function. $R_f$ has two special properties:

Property 1

Defined on the entire domain

For each $x \in \text{domain}(f)$ , there is a pair $(x, y) \in R_f$ . No input is left without an output.

Property 2

Single valued

For each $x \in \text{domain}(f)$ , there is exactly one $y \in \text{codomain}(f)$ with $(x, y) \in R_f$ .

Definition: function

A function is a relation in which each element of $X$ is paired with exactly one element of $Y$ . In a function there cannot be two pairs with the same first element.

Figure 41. Left: every input has exactly one arrow. Right: input 3 has two arrows

Drawing $f$ as a graph is plotting $R_f$ : each pair $(x, f(x))$ becomes a point.

Figure 42. The graph of sq is the parabola y = x², the picture of R_sq

Vertical line test. Because a function gives exactly one output per input, a graph is the graph of a function exactly when every vertical line meets it at most once (and at least once, over the domain).

9.4Lines

$f(x) = 3.5x + 5.7$ is a straight line. 3.5 is the slope and 5.7 is the intercept: the value where the line crosses the $y$ -axis, when $x = 0$ . Changing the slope and intercept produces different lines:

f(x) = 3.5x - 1.2 \qquad f(x) = 2x + 5.7 \qquad f(x) = -4.5x + 2.5

Figure 43. Changing slope and intercept moves and tilts the line

In all these cases

Domain $= \mathbb{R}$ , and codomain $=$ range $= \mathbb{R}$ : every real number is the output for some input.

9.5More functions: the square root

Consider $x \mapsto \sqrt{x}$ . Is this even a function? $5^2 = (-5)^2 = 25$ , so " $\sqrt{25}$ " gives two options, 5 and $-5$ . A function must give exactly one output, so by convention we take the positive square root: $\sqrt{25} = 5$ .

What is the domain? It depends on the codomain. Negative numbers do not have real square roots.

Codomain

\mathbb{R}

Domain is $\mathbb{R}_{\ge 0}$

Only $x \ge 0$ has a real square root, so the domain is $[0, \infty)$ .

Codomain

\mathbb{C}

Domain is $\mathbb{R}$

If the codomain is the set $\mathbb{C}$ of complex numbers, every real number has a square root, e.g. $\sqrt{-1}$ .

Figure 44. y = √x uses only the positive root and starts at x = 0

Example 21Domain of the square root

If the codomain is $\mathbb{R}$ , find the domain of $f(x) = \sqrt{x}$ .

Solution

$\sqrt{x}$ must be a real number. If $x < 0$ , no real $r$ has $r^2 = x$ , because a real square is never negative.
If $x \ge 0$ , the positive root exists and is unique by convention.
So $\sqrt{x}$ is well defined only if $x \ge 0$ : the domain is $[0, \infty)$ .

Example 22Is it a function?

Let $X = \{1, 2, 3, 4\}$ , $Y = \{a, b, c, d\}$ . Decide whether each relation is a function from $X$ to $Y$ : $F = \{(1, b), (2, c), (3, a), (4, c)\}$ , $G = \{(1, b), (2, c), (3, a), (3, d), (4, c)\}$ , $H = \{(1, a), (2, b), (4, d)\}$ .

Solution

Relation	Defined on all of X?	Single valued?	Function?
$F$	Yes: 1, 2, 3, 4 all used	Yes	Yes (2 and 4 sharing c is allowed)
$G$	Yes	No: 3 maps to a and d	No
$H$	No: 3 has no output	Yes	No

Example 23Reading a line

For $f(x) = 3.5x + 5.7$ , find $f(0)$ , $f(2)$ and the input $x$ with $f(x) = 0$ .

Solution

$f(0) = 3.5 \cdot 0 + 5.7 = 5.7$ : the intercept, where the line crosses the $y$ -axis.
$f(2) = 3.5 \cdot 2 + 5.7 = 7 + 5.7 = 12.7$ .
$3.5x + 5.7 = 0$ gives $x = -\frac{5.7}{3.5} = -\frac{57}{35} \approx -1.63$ . Any real output is reachable, which is why range $=$ codomain $= \mathbb{R}$ .

9.6Going deeper: is it a function, and what are its sets?

Two checks for a function. (1) Every element of the domain has an arrow. (2) Each has exactly one. Several inputs may share one output (many-to-one is fine), but one input may not have two outputs.
Finding a natural domain. Remove inputs that break the rule: division by zero, or the square root of a negative number (when the codomain is $\mathbb{R}$ ). So $\frac{1}{x}$ has domain $\mathbb{R} - \{0\}$ , and $\sqrt{x - 2}$ has domain $[2, \infty)$ .
Finding the range. Solve $y = f(x)$ for $x$ and see which $y$ allow a solution in the domain. For $f(x) = x^2 + 3$ , $x^2 \ge 0$ gives $y \ge 3$ , so the range is $[3, \infty)$ .
Evaluating. Replace $x$ everywhere by the input: for $f(x) = 2x^2 - 3$ , $f(-2) = 2 \cdot 4 - 3 = 5$ .
Lines. The slope of $f(x) = mx + c$ is the change in $y$ per unit of $x$ . Through two points: $m = \frac{y_2 - y_1}{x_2 - x_1}$ . A line with $m \neq 0$ has range $\mathbb{R}$ .
How many functions? Each of the $|X|$ inputs independently picks one of $|Y|$ outputs, so there are $|Y|^{|X|}$ functions from $X$ to $Y$ .

9.7Exam tips and common mistakes

Exam tips

State the domain, codomain and range as sets, not as words.
The range is a subset of the codomain, and often a proper subset.
To test a graph use the vertical line test; to test pairs use "one arrow per input".

Common mistakes

Assuming range equals codomain. For $x^2 : \mathbb{R} \to \mathbb{R}$ the range is only $[0, \infty)$ .
Calling a relation a function when one input has two outputs, or when an input has none.
Giving $\pm$ for $\sqrt{x}$ . By convention it is the positive root.
Mixing up domain (inputs) and range (outputs).

Practice questions (graded-assignment style)

Q1Which is a function?

Multiple Choice Question (MCQ): choose the one correct option.

Let $X = \{1, 2, 3\}$ and $Y = \{a, b\}$ . Which relation is a function from $X$ to $Y$ ?

\{(1, a), (2, b)\}

\{(1, a), (1, b), (2, a), (3, b)\}

\{(1, a), (2, a), (3, b)\}

\{(1, a), (2, b), (3, a), (3, b)\}

Solution

Idea

Every input needs exactly one arrow.

Option 1: input 3 has no output.
Option 2: input 1 has two outputs.
Option 3: each of 1, 2, 3 has exactly one output (1 and 2 sharing a is allowed).
Option 4: input 3 has two outputs.
Answer: option 3.

Q2Evaluate

Numerical Answer Type (NAT).

If $f(x) = 2x^2 - 3$ , find $f(-2)$ .

Solution

Idea

Substitute and follow the order of operations.

$(-2)^2 = 4$ .
$2 \cdot 4 - 3 = 8 - 3 = 5$ .
Answer: 5

Q3Range and codomain

Multiple Select Question (MSQ): select all that apply.

Let $f : \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2 + 3$ . Choose the correct statements.

The range of

f

[3, \infty)

The range equals the codomain.

f(2) = f(-2)

The domain is

\mathbb{R}

Solution

Idea

Since $x^2 \ge 0$ , the output is at least 3.

Option 1 is true.
Option 2 is false: for example $0$ is in $\mathbb{R}$ but never an output.
Option 3 is true: both give 7.
Option 4 is true by the definition of f.
Answer: options 1, 3 and 4.

Q4Domain of a root

Multiple Choice Question (MCQ): choose the one correct option.

With codomain $\mathbb{R}$ , what is the domain of $f(x) = \sqrt{x - 2}$ ?

\mathbb{R}

(2, \infty)

[2, \infty)

(-\infty, 2]

Solution

Idea

The expression under the root must be $\ge 0$ .

$x - 2 \ge 0$ gives $x \ge 2$ .
At $x = 2$ the value is $\sqrt{0} = 0$ , so 2 is included.
Answer: option 3.

Q5Count the functions

Numerical Answer Type (NAT).

How many functions are there from a 3-element set $X$ to a 2-element set $Y$ ?

Solution

Idea

Each input picks an output independently.

Each of 3 inputs has 2 choices: $2 \cdot 2 \cdot 2 = 2^3 = 8$ .
Answer: 8

Revision overview

A ruleMaps inputs to outputs
sq(x) = x²; x is a parameter

Three setsDomain: input set
Codomain: possible outputs
Range: outputs that occur ⊆ codomain

Function as relationR_f = {(x, f(x))}
Defined on the entire domain
Single valued: exactly one y

FunctionsWeek 1 · Functions

GraphsGraph of f = plot of R_f
y = x²: a parabola, range ≥ 0

Linesf(x) = 3.5x + 5.7
Slope 3.5, intercept 5.7
Domain = codomain = range = ℝ

Square rootPositive root by convention
Codomain ℝ: domain x ≥ 0
Codomain ℂ: domain ℝ

Revision: functions on one page

Next · Functions · Part 2 of 2Types of Functions

Functions · Part 2 of 2

Types of Functions

Functions are classified by how their arrows land in the codomain. Do different inputs always give different outputs? Is every possible output actually reached? The answers give injective, surjective and bijective functions, and bijections let us compare the sizes of sets without counting.

10.1Injective (one-one)

Definition: injective

$f$ is injective (one-one) if different inputs produce different outputs: if $x_1 \neq x_2$ then $f(x_1) \neq f(x_2)$ . Equivalently, each element of $X$ maps to a distinct element of $Y$ .

To prove injectivity it is often easier to use the contrapositive: if $f(x_1) = f(x_2)$ then $x_1 = x_2$ .

Injective

$f(x) = 3x + 5$

If $3x_1 + 5 = 3x_2 + 5$ then $x_1 = x_2$ . So different inputs never share an output.

Not injective

$f(x) = 7x^2$

For any $a$ , $f(a) = f(-a)$ . For example $f(2) = f(-2) = 28$ .

10.2Surjective (onto)

Definition: surjective

$f$ is surjective (onto) if the range is the codomain: for every $y \in \text{codomain}(f)$ , there is an $x \in \text{domain}(f)$ such that $f(x) = y$ .

Function	Codomain	Range	Surjective?
$f(x) = -7x + 10$	$\mathbb{R}$	$\mathbb{R}$ (solve $x = \frac{10 - y}{7}$ )	Yes
$f(x) = 5x^2 + 3$	$\mathbb{R}$	$[3, \infty)$ since $x^2 \ge 0$	No
$f(x) = 7\sqrt{x}$	$\mathbb{R}$	$[0, \infty)$	No

Surjectivity depends on the codomain you choose.

f(x) = x^2

is not onto

\mathbb{R}

, but the same rule is onto

[0, \infty)

. Injectivity, by contrast, does not depend on the codomain.

10.3Bijective (one-to-one correspondence)

Definition: bijective

$f$ is bijective if it is a 1-1 correspondence between domain and codomain:

Every $x \in \text{domain}(f)$ maps to a distinct $y \in \text{codomain}(f)$ .
Every $y \in \text{codomain}(f)$ has a unique pre-image $x \in \text{domain}(f)$ such that $y = f(x)$ .

Figure 45. The four combinations of injective and surjective

Theorem

A function is bijective if and only if it is injective and surjective.

Bijective $\Rightarrow$ injective and surjective. This follows directly from the definition: distinct outputs is injectivity, and every $y$ having a pre-image is surjectivity.
Injective and surjective $\Rightarrow$ bijective. Injectivity guarantees that $f$ satisfies the first condition of a bijection (distinct outputs).
Surjectivity says every $y \in \text{codomain}(f)$ has a pre-image. Injectivity guarantees this pre-image is unique, which is the second condition.

Figure 46. Two questions decide the type of any function

10.4Bijections and cardinality

For finite sets we can count the items. But what if we have two large sacks filled with marbles? Do we need to count the marbles in each sack? No: pull out marbles in pairs, one from each sack, and see whether both sacks become empty simultaneously. If they do, the pairing is a bijection between the marbles in the two sacks.

Figure 47. A bijection compares sizes without counting

Key idea

A bijection establishes that the domain and codomain have the same cardinality. This is how we compare the sizes of infinite sets.

For infinite sets. How many lines are there? Every (non-vertical) line $y = mx + c$ is determined uniquely by the pair $(m, c)$ , and vice versa. So the number of such lines is the same as the cardinality of $\mathbb{R} \times \mathbb{R}$ .

Also, for every pair of points $(x_1, y_1)$ and $(x_2, y_2)$ there is a unique line through both points. Does this show that $(\mathbb{R} \times \mathbb{R}) \times (\mathbb{R} \times \mathbb{R}) = \mathbb{R}^2 \times \mathbb{R}^2$ has the same cardinality as $\mathbb{R} \times \mathbb{R}$ ? Not this way: the correspondence (pair of points $\to$ line) is not a bijection, because many pairs of points describe the same line.

Figure 48. Lines match pairs (m, c) one-to-one, but not pairs of points

A careful reading. The argument above only shows that this particular correspondence is not a bijection, so it proves nothing either way about the two sizes. (In fact

\mathbb{R}^2 \times \mathbb{R}^2

and

\mathbb{R} \times \mathbb{R}

do have the same cardinality, but that needs a different argument, beyond this course.) Do not read "No" as "they have different sizes".

Example 24Range and surjectivity of x²

Suppose $f : \mathbb{R} \to \mathbb{R}$ is defined as $f(x) = x^2$ . Find the range of $f$ and check whether $f$ is surjective. Is it injective?

Solution

A real square is never negative, and every $y \ge 0$ is reached by $x = \sqrt{y}$ . So the range is $[0, \infty)$ .
The codomain is $\mathbb{R}$ but the range is $[0, \infty)$ . Since codomain $\neq$ range (for example $-1$ is never an output), $f$ is not surjective.
$f(3) = f(-3) = 9$ , so $f$ is not injective either. It is the "neither" case.

Example 25Proving a bijection

Show that $f : \mathbb{R} \to \mathbb{R}$ , $f(x) = 3x + 5$ is a bijection.

Solution

Injective: suppose $f(x_1) = f(x_2)$ . Then $3x_1 + 5 = 3x_2 + 5$ , so $3x_1 = 3x_2$ and $x_1 = x_2$ . Equal outputs force equal inputs.
Surjective: take any $y \in \mathbb{R}$ . Solve $3x + 5 = y$ : $x = \frac{y - 5}{3}$ , which is a real number. Check: $f\!\left(\frac{y - 5}{3}\right) = (y - 5) + 5 = y$ .
Injective and surjective, so by the theorem $f$ is bijective.

Example 26Classify these functions

All have domain and codomain $\mathbb{R}$ unless stated: $3x + 5$ , $7x^2$ , $-7x + 10$ , $5x^2 + 3$ , and $7\sqrt{x}$ (domain $[0, \infty)$ ).

Solution

Function	Injective?	Surjective?	Type
$3x + 5$	Yes	Yes	Bijective
$7x^2$	No: $f(a) = f(-a)$	No: range $[0, \infty)$	Neither
$-7x + 10$	Yes: a line with slope $\neq 0$	Yes	Bijective
$5x^2 + 3$	No: $f(1) = f(-1) = 8$	No: range $[3, \infty)$	Neither
$7\sqrt{x}$	Yes: bigger $x$ gives bigger $\sqrt{x}$	No: range $[0, \infty)$	Injective only

10.5Summary

A function is given by a rule mapping inputs to outputs.
Define the domain, codomain and range.
Associate a relation $R_f$ with each function $f$ .
Properties of functions: injective (one-one), surjective (onto).
Bijections: injective and surjective.
A bijection establishes that domain and codomain have the same cardinality.

10.6Going deeper: injective, surjective and the sizes of sets

Two questions. (1) Can two different inputs share an output? If never, $f$ is injective. (2) Is every codomain element hit? If yes, $f$ is surjective. Both yes means bijective.
Graph tests. If every horizontal line meets the graph at most once, $f$ is injective. If every horizontal line through the codomain meets it at least once, $f$ is surjective.
Finite sets and sizes. Injective needs $|X| \le |Y|$ . Surjective needs $|X| \ge |Y|$ . Bijective needs $|X| = |Y|$ . If $|X| = |Y|$ is finite, then injective, surjective and bijective all mean the same thing.
Repairing a function. Shrink the codomain to the range to make it onto, and restrict the domain to make it one-one. For example $x^2$ on $\mathbb{R} \to \mathbb{R}$ is neither, but $x^2$ on $[0, \infty) \to [0, \infty)$ is bijective.
Proof templates. Injective: assume $f(x_1) = f(x_2)$ and show $x_1 = x_2$ . Surjective: take any $y$ , solve for $x$ and check $x$ lies in the domain. To disprove, give one counterexample.
Infinite sets. The map $n \mapsto 2n$ is a bijection from $\mathbb{N}$ to the even naturals. So these two sets have the same cardinality, even though the evens form a proper subset.
Lines. $f(x) = mx + c$ with $m \neq 0$ is a bijection $\mathbb{R} \to \mathbb{R}$ , with inverse $x = \frac{y - c}{m}$ .

10.7Composition and inverse of functions

A. Composition

If $g : X \to Y$ and $f : Y \to Z$ , the composition $f \circ g : X \to Z$ is "first $g$ , then $f$ ":

(f \circ g)(x) = f\big(g(x)\big)

The output of $g$ must be a legal input for $f$ : the codomain of $g$ must fit inside the domain of $f$ .
Order matters. For $f(x) = 2x + 3$ and $g(x) = x^2$ : $(f \circ g)(x) = 2x^2 + 3$ but $(g \circ f)(x) = (2x + 3)^2 = 4x^2 + 12x + 9$ . At $x = 2$ : $(f \circ g)(2) = 11$ while $(g \circ f)(2) = 49$ .
Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$ . The identity function $\operatorname{id}(x) = x$ satisfies $f \circ \operatorname{id} = \operatorname{id} \circ f = f$ .

Fact	Why
$f, g$ injective $\Rightarrow$ $f \circ g$ injective	$f(g(x_1)) = f(g(x_2)) \Rightarrow g(x_1) = g(x_2) \Rightarrow x_1 = x_2$ .
$f, g$ surjective $\Rightarrow$ $f \circ g$ surjective	Every $z$ is $f(y)$ for some $y$ , and every $y$ is $g(x)$ for some $x$ .
$f \circ g$ injective $\Rightarrow$ $g$ injective	If $g(x_1) = g(x_2)$ then $f(g(x_1)) = f(g(x_2))$ , so $x_1 = x_2$ . (The inner function.)
$f \circ g$ surjective $\Rightarrow$ $f$ surjective	Every $z$ is $f(\text{something})$ . (The outer function.)

B. The inverse function

A function $f : X \to Y$ has an inverse $f^{-1} : Y \to X$ exactly when $f$ is a bijection. Then $f^{-1}(f(x)) = x$ for all $x \in X$ and $f(f^{-1}(y)) = y$ for all $y \in Y$ . Injective is needed so each $y$ comes from only one $x$ ; surjective is needed so every $y$ comes from some $x$ .

How to find it: write $y = f(x)$ , solve for $x$ in terms of $y$ , then rename. For $f(x) = 2x + 3$ : $x = \dfrac{y - 3}{2}$ , so $f^{-1}(y) = \dfrac{y - 3}{2}$ .
$f(x) = \dfrac{2x + 1}{x - 3}$ (for $x \neq 3$ , onto $\mathbb{R} - \{2\}$ ): $y(x - 3) = 2x + 1 \Rightarrow x(y - 2) = 3y + 1 \Rightarrow x = \dfrac{3y + 1}{y - 2}$ , so $f^{-1}(y) = \dfrac{3y + 1}{y - 2}$ . Check: $f(5) = \tfrac{11}{2}$ and $f^{-1}(\tfrac{11}{2}) = \dfrac{33/2 + 1}{11/2 - 2} = \dfrac{35/2}{7/2} = 5$ ✓.
$f(x) = x^2$ on $\mathbb{R}$ has no inverse (not injective: $f(2) = f(-2)$ ). Restrict to $[0, \infty) \to [0, \infty)$ and it becomes a bijection with inverse $\sqrt{y}$ .
$(f \circ g)^{-1} = g^{-1} \circ f^{-1}$ : undo the last step first.

C. The inverse image is not the inverse function

For any function $f : X \to Y$ and $S \subseteq Y$ , the inverse image $f^{-1}(S) = \{x \in X : f(x) \in S\}$ is always defined, even when $f$ has no inverse function. For $f(x) = x^2$ on $\mathbb{R}$ : $f^{-1}(\{4, 9\}) = \{-3, -2, 2, 3\}$ , which has $4$ elements, while $f^{-1}(\{-1\}) = \emptyset$ .

10.8Exam tips and common mistakes

Exam tips

For "classify the function" answer two questions in a table: injective? surjective?
Say which codomain you assume: surjectivity depends on it, injectivity does not.
For proofs, follow the templates; for disproofs, give one explicit counterexample.

Common mistakes

Calling $x^2 : \mathbb{R} \to \mathbb{R}$ onto. Negative numbers are never outputs.
Saying $7\sqrt{x}$ is bijective onto $\mathbb{R}$ . Its range is only $[0, \infty)$ .
Confusing the two words: injective is about distinct outputs, surjective is about covering the codomain.
Concluding "different sizes" from a map that is not a bijection (it only shows that map fails).

Practice questions (graded-assignment style)

Q1Classify x squared

Multiple Choice Question (MCQ): choose the one correct option.

The function $f : \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2$ is

injective but not surjective

surjective but not injective

bijective

neither injective nor surjective

Solution

Idea

Check both questions.

Not injective: $f(3) = f(-3) = 9$ .
Not surjective: the range is $[0, \infty)$ , so $-1$ is never an output.
Answer: option 4.

Q2Bijections

Multiple Select Question (MSQ): select all that apply.

Which of these functions $\mathbb{R} \to \mathbb{R}$ are bijections?

f(x) = 2x - 7

f(x) = x^2 + 1

f(x) = -x + 4

f(x) = 5x^2

Solution

Idea

Lines with non-zero slope are bijections; parabolas are not.

$2x - 7$ and $-x + 4$ are lines with slope $\neq 0$ , hence bijective.
$x^2 + 1$ and $5x^2$ fail injectivity ( $f(a) = f(-a)$ ) and surjectivity.
Answer: options 1 and 3.

Q3Sizes of sets

Multiple Choice Question (MCQ): choose the one correct option.

$f : X \to Y$ with $|X| = 3$ and $|Y| = 5$ . Which statement is possible?

f

is surjective.

f

is injective.

f

is bijective.

None of these.

Solution

Idea

Compare the sizes.

Surjective needs $|X| \ge |Y|$ , but $3 < 5$ . Bijective needs equal sizes.
Injective needs $|X| \le |Y|$ , which holds, and such a function exists (map 3 elements to 3 different elements).
Answer: option 2.

Q4Pre-image

Numerical Answer Type (NAT).

For $f(x) = 3x + 5$ on $\mathbb{R}$ , find the input $x$ with $f(x) = 14$ .

Solution

Idea

Solve the equation, using that f is a bijection so the answer is unique.

$3x + 5 = 14$ gives $3x = 9$ , so $x = 3$ .
Check: $3 \cdot 3 + 5 = 14$ .
Answer: 3

F1Composition at a point

Numerical Answer Type (NAT).

$f(x) = 2x + 3$ and $g(x) = x^2$ . Find $(f \circ g)(2)$ .

Solution

Idea

$f \circ g$ means apply $g$ first.

$g(2) = 4$ , then $f(4) = 2 \cdot 4 + 3 = 11$ .
(The other order would give $g(f(2)) = g(7) = 49$ , a different number.)
Answer: 11

F2Finding an inverse and evaluating it

Numerical Answer Type (NAT).

$f(x) = \dfrac{2x + 1}{x - 3}$ (defined for $x \neq 3$ , taking every real value except $2$ ). Find $f^{-1}(5)$ .

Solution

Idea

Solving $y = f(x)$ for $x$ gives $f^{-1}$ . Alternatively, $f^{-1}(5)$ is the $x$ with $f(x) = 5$ .

$\dfrac{2x + 1}{x - 3} = 5 \Rightarrow 2x + 1 = 5x - 15 \Rightarrow 16 = 3x \Rightarrow x = \dfrac{16}{3}$ .
Check with the formula $f^{-1}(y) = \dfrac{3y + 1}{y - 2}$ : $\dfrac{16}{3}$ ✓. And $f\left(\tfrac{16}{3}\right) = \dfrac{32/3 + 1}{16/3 - 3} = \dfrac{35/3}{7/3} = 5$ ✓.
Answer: 16/3 (about 5.33)

F3Composition and injectivity or surjectivity

Multiple Select Question (MSQ): select all that apply.

$f$ and $g$ are functions such that $f \circ g$ is defined. Choose the correct statements.

f \circ g = g \circ f

always.

f

and

g

are injective, then

f \circ g

is injective.

f \circ g

is injective, then

g

is injective.

f \circ g

is surjective, then

g

is surjective.

f

and

g

are bijections, then

(f \circ g)^{-1} = g^{-1} \circ f^{-1}

Solution

Idea

The inner function $g$ carries injectivity; the outer function $f$ carries surjectivity.

1 ✗ $f(x) = 2x + 3$ , $g(x) = x^2$ give $11$ and $49$ at $x = 2$ .
2 ✓ Injective maps compose to an injective map.
3 ✓ $g(x_1) = g(x_2) \Rightarrow f(g(x_1)) = f(g(x_2)) \Rightarrow x_1 = x_2$ .
4 ✗ Surjectivity of $f \circ g$ forces $f$ to be surjective, not $g$ . Example: $g : \{1\} \to \{1, 2\}$ , $g(1) = 1$ , and $f : \{1, 2\} \to \{7\}$ , $f(1) = f(2) = 7$ . Then $f \circ g : \{1\} \to \{7\}$ is surjective but $g$ misses $2$ .
5 ✓ Undo the last step first.
Answer: options 2, 3 and 5.

F4An inverse image

Numerical Answer Type (NAT).

$f : \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2$ . How many elements does $f^{-1}(\{4, 9\})$ have?

Solution

Idea

The inverse image of a set is every $x$ that $f$ sends into the set. It exists even though $f$ has no inverse function.

$x^2 = 4 \Rightarrow x = \pm 2$ and $x^2 = 9 \Rightarrow x = \pm 3$ .
$f^{-1}(\{4, 9\}) = \{-3, -2, 2, 3\}$ , which has 4 elements.
Answer: 4

Revision overview

Injective (one-one)x₁ ≠ x₂ ⇒ f(x₁) ≠ f(x₂)
3x + 5 yes; 7x² no

Surjective (onto)Range = codomain
−7x + 10 yes
5x² + 3, 7√x no (codomain ℝ)

Bijective1-1 correspondence
Unique pre-image for every y
Bijective ⇔ injective + surjective

Types of FunctionsWeek 1 · Functions

CardinalityBijection ⇒ same cardinality
Marbles: pair them off
Lines y = mx + c ↔ ℝ × ℝ

Watch outPairs of points → lines is many-to-one
So it is not a bijection
Codomain choice changes "onto"

Revision: types of functions on one page

Next · All topicsWeek 1 Summary Sheet

All topics

Week 1 Summary Sheet

Everything from Week 1 on one sheet, for a last-minute revision.

Number system

$\mathbb{N} = \{0, 1, 2, \dots\}$ , $\mathbb{Z} = \{\dots, -1, 0, 1, \dots\}$
$\mathbb{Q} = \{p/q : p, q \in \mathbb{Z},\ q \neq 0\}$ ; reduced form when $\gcd(p, q) = 1$
$\mathbb{R}$ = rationals + irrationals ( $\sqrt{2}, \pi, e$ ); $\sqrt{-1} \in \mathbb{C}$
$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$

Arithmetic facts

$m \times n$ = repeated addition; $m^k$ = repeated multiplication
$a \bmod b$ = remainder; $a \mid b \iff b \bmod a = 0$
Prime: exactly two factors; 1 is not prime
Prime factorisation is unique: $126 = 2 \cdot 3^2 \cdot 7$

Sets

Unordered, no duplicates; $|S|$ = cardinality
$X \subseteq Y$ : all of $X$ in $Y$ ; $X = Y \iff X \subseteq Y,\ Y \subseteq X$
$\emptyset \subseteq X$ ; $n$ elements give $2^n$ subsets
Comprehension: $\{\text{transform} \mid \text{generate},\ \text{filter}\}$

Relations and functions

$A \times B = \{(a, b) \mid a \in A,\ b \in B\}$ ; relation $R \subseteq A \times B$
Equivalence = reflexive + symmetric + transitive; partitions the set
Function: each input has exactly one output; range ⊆ codomain
Bijective $\iff$ injective + surjective

Set operations at a glance

Operation	Notation	Contains	With $X = \{A, B, C, D\}$ , $Y = \{A, D, E, F\}$
Union	$X \cup Y$	elements in X or Y	$\{A, B, C, D, E, F\}$
Intersection	$X \cap Y$	elements in both	$\{A, D\}$
Difference	$X - Y,\ X \setminus Y$	in X, not in Y	$\{B, C\}$
Complement	$\overline{X},\ X^c$	in U, not in X	$U - X$
Counting	$n(X \cup Y)$	$n(X) + n(Y) - n(X \cap Y)$	$4 + 4 - 2 = 6$

Intervals

	$[a, b]$	$(a, b)$	$(a, b]$	$[a, b)$
Condition	$a \le x \le b$	$a < x < b$	$a < x \le b$	$a \le x < b$
Name	closed	open	left open	right open

Relation properties and function types

Relation on S

Property	Test
Reflexive	$(x, x) \in R$ for all x
Symmetric	$(a, b) \Rightarrow (b, a)$
Transitive	$(a, b), (b, c) \Rightarrow (a, c)$
Antisymmetric	$a \neq b$ : not both ways

Function

f : X \to Y

Type	Test
Injective	$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$
Surjective	range = codomain
Bijective	both
Domain of $\sqrt{x}$	$[0, \infty)$ when codomain is $\mathbb{R}$

Decision tree for function types

Figure 49. Classify any function with two questions

Five things to remember

1. $\mathbb{N}$ includes 0 in this course. 2. Rationals and reals are dense; integers are discrete. 3. A set with $n$ elements has $2^n$ subsets. 4. Check transitivity on every chain. 5. Whether a function is onto depends on the codomain you choose.

Exam tips: last-minute checklist

$\mathbb{N}$ includes 0; 1 is not prime
Check divisions with $a = bq + r$
Say $\in$ for elements and $\subseteq$ for sets
Count: subsets $2^n$ , pairs $|A||B|$ , relations $2^{|A||B|}$ , functions $|Y|^{|X|}$
Check transitivity on every chain
State the codomain before deciding surjective
Draw the Venn diagram first

Do not

Call $\sqrt{16}$ irrational
Add numerators and denominators separately
Treat $\emptyset$ and $\{\emptyset\}$ as equal
Use a square bracket with $\infty$
Say symmetric and antisymmetric are opposites
Call $x^2 : \mathbb{R} \to \mathbb{R}$ onto
Assume $X - Y = Y - X$

Counting formulas

What to count	Formula
Subsets of an $n$ -element set	$2^n$ (proper: $2^n - 1$ )
Pairs in $A \times B$	$\|A\| \cdot \|B\|$
Relations from $A$ to $B$	$2^{\|A\| \cdot \|B\|}$
Functions from $X$ to $Y$	$\|Y\|^{\|X\|}$
Union of two sets	$n(P) + n(B) - n(P \cap B)$
Classes of "same remainder mod $n$ "	$n$

Mathematics forData Science 1

Chapters

Natural Numbers and Integers

1.1Counting and the natural numbers

1.2The four operations, and where subtraction fails

1.3The integers

1.4Multiplication is repeated addition

Three ways to write it

Multiplying negative numbers

1.5Exponentiation is repeated multiplication

1.6Division is repeated subtraction

1.7Factors and divisibility

Remainder is 0

Remainder is not 0

1.8Prime numbers

1.9Prime factorisation

1.10Going deeper: why each number set was built

1.11LCM, Euclid's algorithm and divisibility tests

A. gcd and LCM from prime factorisations

B. Euclid's algorithm

C. Divisibility tests

D. Counting divisors

E. Word-problem translation

1.12Exam tips and common mistakes

Practice questions (graded-assignment style)

Rational Numbers

2.1From division to fractions

2.2The same number, many names

2.3Adding and comparing

2.4Reduced form and the gcd

2.5Density: integers are discrete, rationals are dense

2.6Going deeper: fractions, equality and decimals

2.7Exam tips and common mistakes

Practice questions (graded-assignment style)

Real and Complex Numbers

3.1Squares and square roots

Square of mmm

Square root of mmm

3.2Root 2 is irrational

3.3The real numbers

3.4Beyond the reals: complex numbers

3.5The whole family

3.6Going deeper: rational or irrational?

3.7Absolute value, floor and ceiling, and arithmetic with complex numbers

A. Absolute value

B. Floor and ceiling

C. Complex numbers: the arithmetic

3.8Exam tips and common mistakes

Practice questions (graded-assignment style)

Sets: The Basics

4.1What is a set?

4.2Order, duplicates and cardinality

4.3Describing sets and membership

List them explicitly

Cannot be listed out

4.4Subsets

4.5The empty set and the power set

4.6Subsets and binary numbers

4.7Going deeper: ∈\in∈ versus ⊆\subseteq⊆, and sets inside sets

4.8Exam tips and common mistakes

Practice questions (graded-assignment style)

Building Sets and Set Operations

5.1Set comprehension (set-builder form)

5.2Intervals

5.3Union, intersection and difference

5.4Complement

5.5Going deeper: reading comprehensions and intervals

5.6Exam tips and common mistakes

Practice questions (graded-assignment style)

Sets in Action

6.1Generator, filter, transform: more examples

6.2Perfect squares, three ways

6.3Counting with Venn diagrams

6.4Summary

6.5Going deeper: a method for Venn problems

6.6Laws of set operations, De Morgan's laws and counting with three sets

A. The laws (for subsets of a universal set UUU)

B. Symmetric difference

C. Counting with three sets

6.7Exam tips and common mistakes

Mathematics for
Data Science 1

Square of $m$

Square root of $m$

4.7Going deeper: $\in$ versus $\subseteq$ , and sets inside sets

A. The laws (for subsets of a universal set $U$ )

Domain is $\mathbb{R}_{\ge 0}$

Domain is $\mathbb{R}$

$f(x) = 3x + 5$

$f(x) = 7x^2$