Unit 1 CLO 1 6 lecture hours

Functions & Relations

Sets are just collections. A relation is a set of "if–then" rules connecting two sets. A function is a relation where each input gets exactly one output. This unit is the language for everything else in the course.

On this page
  1. Cartesian product
  2. Relations & the four special types
  3. Reflexive, symmetric, transitive
  4. Equivalence relation & equivalence classes
  5. Functions & function types
  6. CS functions: floor, ceiling, boolean, exponential, piecewise
  7. Recursion & recursive algorithms
  8. Solution of a homogeneous recurrence
  9. Self-check

1. Cartesian Product

The Cartesian product of two sets A and B is every possible ordered pair you can build by taking one thing from A and one thing from B.

Definition A × B = { (a, b) : a ∈ A and b ∈ B }
Example — build it by hand

Let A = {1, 2, 3} and B = {a, b}. Pick from A first, then from B. Write A outside, B inside:

A × B = { (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) }
|A × B| = 3 × 2 = 6  →  "3 outside, 2 inside, 6 pairs."
A (rows) ↓   /   B (columns) → a b 1 2 3 (1, a)(1, b) (2, a)(2, b) (3, a)(3, b) 6 pairs
Fill the row for 1, then the row for 2, then the row for 3. Every cell of the grid becomes one pair.
Tricks
  • Order matters. (1, a) and (a, 1) are different pairs. So |A × B| = |B × A| = |A| · |B|, but the sets are not the same unless A = B.
  • "Outside × inside." Say it out loud: "|A| outside, |B| inside, answer = multiply."

2. Relations and the Four Special Types

A binary relation from A to B is any subset of A × B. It is simply a list of arrows.

A relation R from A to B R ⊆ A × B

The four special relations you must recognise instantly

RelationDefinitionEasy way to remember
IdentityR = {(a,a) : a ∈ A} — every element relates to itself and nothing elseDiagonal lines only
UniversalR = A × B — every single possible pair is in RThe whole grid, fully filled
Void (empty)R = ∅ — no pairs at allAn empty grid
BinaryAny relation that links exactly two sets A and B (i.e. any subset of A × B)"Bi" = 2 boxes. It's the umbrella term
IDENTITY {(a,a),(b,b),(c,c)} a b c each element loops to itself R = A × A UNIVERSAL A × B — all 9 pairs a b c 1 2 3 the grid is completely full R = A × B VOID no pairs whatsoever a b c 1 2 3 ∅ not a single arrow drawn R = ∅ BINARY any R ⊆ A × B a b c 1 2 3 "bi" = links exactly two sets the umbrella term
Same two sets, four completely different relations. The only difference is which arrows you draw.
Trick

I U V B — Identity (straight lines), Universal (all lines), Void (zero lines), Binary (the family that contains all the others).

3. Reflexive, Symmetric, Transitive

These three words describe properties a relation may or may not have. A relation on a single set A (A to itself) can be checked by looking at the arrows.

REFLEXIVE ✓ every node has a loop a b c a b c every single element loops back SYMMETRIC ✓ every arrow has a twin a b c a b c a→b and b→a, or neither NOT SYMMETRIC ✗ a→b exists, b→a missing a b c a b c a is "less than" b → not symmetric
Reflexive = "selfie" (loops). Symmetric = "mirror" (paired arrows). Transitive = "chain" (a→b→c forces a→c).
TRANSITIVE — the chain rule a b c a R b b R c a R c — REQUIRED the red arrow is the one students forget. Without it, the relation is NOT transitive. Example that works: "is less than" — 1<2 and 2<3, so 1<3 ✓
Transitivity is the only property where you must add a pair. Reflexive adds loops, symmetric adds twins, transitive adds the long arrow.
Quick definitions to copy into your notes
R on A is… reflexive   ⇔  ∀a ∈ A : (a, a) ∈ R
symmetric   ⇔  ∀a, b ∈ A : (a, b) ∈ R ⇒ (b, a) ∈ R
transitive ⇔ ∀a, b, c ∈ A : (a, b) ∈ R ∧ (b, c) ∈ R ⇒ (a, c) ∈ R
antisymmetric ⇔ ∀a ≠ b : (a, b) ∈ R ⇒ (b, a) ∉ R
Tricks
  • "Reflexive" rhymes with "reflect" — you see yourself. "Symmetric" = "symmetry" — a mirror. "Transitive" = "transit" — you pass through b to get from a to c.
  • Loop test for reflexive: count the elements in A. Count the loops in the diagram. Equal numbers? Reflexive. (Faster than checking one by one.)
  • Antisymmetric is the opposite of symmetric but weaker: it only forbids a two-way pair. "≤" is antisymmetric; "<" is not symmetric and not antisymmetric.
  • Fewer pairs = easier to check. If a relation has 3 or fewer pairs, just write them out. If it has more, look for a pattern.

4. Equivalence Relation & Equivalence Classes

An equivalence relation is one that is ALL THREE of reflexive + symmetric + transitive

When a relation is an equivalence relation, the set A splits up neatly into groups of elements that are "related to each other". These groups are called equivalence classes, written A/a ("A over a").

"has the same remainder when divided by 2" on A = {0,…,7} A [0] = {0,2,4,6} 0 2 4 6 even numbers [1] = {1,3,5,7} 1 3 5 7 odd numbers
Two equivalence classes, and they cover A with no leftovers and no overlap. That is the point of an equivalence relation.
What you must remember

Classes are disjoint (no element in two classes) and their union is A (nothing left out). If you draw classes that overlap, your relation was not transitive.

5. Functions: The Special Relation

f : A → B is a function if for every a ∈ A there is exactly one b ∈ B with f(a) = b
✓ THIS IS A FUNCTION each input → one output a b c 1 2 3 b and c share output 2 — that is fine ✗ NOT A FUNCTION a has two outputs a b c 1 2 3 one input, two outputs → it is a relation only
The left diagram is a function even though two arrows land on the same place. The right one is not, because one arrow leaves from the same place twice.

Types of functions

TypeWhat it meansCondition
One-one / InjectiveDifferent inputs give different outputsf(x₁)=f(x₂) ⇒ x₁=x₂
Onto / SurjectiveEvery output is used at least onceRange = codomain
BijectiveOne-one and ontoHas an inverse function
ConstantAll outputs equal one fixed valuef(x)=c for all x
IdentityReturns the input unchangedf(x)=x
Trick — the injection test

Draw a vertical line anywhere on the graph.

  • Line hits the curve once everywhere → injective (one-one). This is the "vertical line test".
  • Line misses some part of the range → not onto.
  • Line hits some values twice → not one-one.

For a finite set: if |A| = |B|, then one-one automatically means onto (bijective). One of the two conditions is free — saves you marks.

6. Functions for Computer Science

Floor and Ceiling

Round a number to an integer ⌊x⌋ = floor(x) = largest integer ≤ x   (round down)
⌈x⌉ = ceiling(x) = smallest integer ≥ x   (round up)
CEILING  ceils up FLOOR  floors down 012 345 6 x = 1.5 ceiling gives 2 floor gives 1
At x = 1.5 the floor drops to 1 and the ceiling rises to 2.
Trick

Floor = down to the floor. Ceiling = up to the ceiling. The symbols are arrows: ⌊  ⌋ open at the top (stuff can go up = round up), ⌈  ⌉ open at the bottom (stuff falls down = round down). Draw them as a "cup" and a "hat".

For negatives, always test with a small example: ⌊−1.5⌋ = −2 (not −1!) and ⌈−1.5⌉ = −1.

Example — floor & ceiling calculations
⌊3.7⌋ = 3    ⌈3.2⌉ = 4    ⌊5⌋ = ⌈5⌉ = 5
⌊−0.2⌋ = −1    ⌈−0.2⌉ = 0    ⌊−4⌋ = −4

The general trick for negatives: the floor is always ≤ x, the ceiling is always ≥ x. Check your answer against that.

Boolean Function

A Boolean function works on inputs that are only 0 (False) or 1 (True) — the same values used in logic and in every computer's binary arithmetic.

Example — AND, OR, NOT, XOR AND(x,y) = x·y     OR(x,y) = x+y     NOT(x) = 1−x     XOR(x,y) = x+y−2xy
BOOLEAN GATES AND flat left, round right AND(x,y) = x·y OR curved back, pointy front OR(x,y) = x+y NOT triangle then bubble NOT(x) = 1 − x x y AND OR XOR 0 0000 0 1011 1 0011 1 1110 XOR = 1 only when the inputs differ
AND is a squarish D, OR is a shield, NOT is a bubble on the end of a line.
Trick

AND needs both (multiplication, so one zero kills it). OR needs one (addition, so one is enough). XOR needs a difference — output 1 exactly when the inputs are different.

Exponential Function

Growth f(x) = aˣ   where a > 0, a ≠ 1
x y 0 a > 1   GROWTH 2⁶, e⁶, 3⁶ 0 < a < 1   DECAY (1/2)⁶, 0.9⁶ a = 1  : the flat line y = 1  (excluded — that is linear) Every exponential curve passes through (0, 1) because a⁰ = 1. It never touches the x-axis: y > 0 always, and the domain is all real x.
Every exponential curve passes through (0, 1) — that single point answers "which side does it decay?" instantly.
Trick

All exponentials pass through (0, 1) because a⁰ = 1. So:

  • a > 1 → rises to the right (explosive) → 2ˣ, 3ˣ, eˣ, 10ˣ
  • 0 < a < 1 → falls to the right (decays) → ½ˣ, 0.9ˣ
  • a = 1 → flat line y = 1 (never used, it is linear not exponential)

Two facts worth memorising: a⁰ = 1, a⁻ⁿ = 1/aⁿ, and the domain/range of aˣ is all real x, and y > 0 always (it never touches 0).

Piecewise Function

A function built from several small formulas, each used on a different part of the input. Like a traffic light: different colour for different times.

Example f(x) = { −x, if x < 0
         { x², if 0 ≤ x < 3
         { x − 1, if x ≥ 3 }
y x 0 2 4 -2 -3 123 y = -x  (x < 0) y = x²/2  (0 ≤ x < 2) y = x  (x ≥ 2) ○ open dot = this branch does NOT take the boundary ● solid dot = this branch DOES take it only one branch may own a boundary value
Always mark the boundary points: solid dot if that branch owns the point, open dot if it does not.
Marks lost here
  • Forgetting the open circle at a boundary where the value is excluded.
  • Using ≤ in two branches at the same point — only one branch may own a boundary value.

7. Recursion

A recursive definition describes something in terms of a smaller version of itself. It always has two parts: a base case (where it stops) and a recursive step.

RECURSION = BIG CALLS A SMALLER CALL…UNTIL THE BASE CASE fact(5) fact(4) fact(3) fact(2) fact(1) = 1 unwind going back BASE CASE — recursion stops here
Always draw the call stack going down to smaller numbers, then compute back up.

Factorial

n! = n × (n−1) × (n−2) × … × 2 × 1 n! = n · (n−1)!   for n > 1   |   base case: 0! = 1! = 1
Example — trace 5!

Method 1 (unwrap):

5! = 5·4! = 5·4·3! = 5·4·3·2! = 5·4·3·2·1! = 5·4·3·2·1
    = 120

Method 2 (unwinding back up):

1! = 1
2! = 2·1 = 2
3! = 3·2 = 6
4! = 4·6 = 24
5! = 5·24 = 120
5! = 120

Fibonacci

Each term = sum of the two before it F₀ = 0,  F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂   for n ≥ 2
011 235 81321 34 F₀F₁F₂ F₃F₄F₅ F₆F₇F₈ F₉ Start 0, 1 — then just keep ADDING the two before. That is the whole algorithm.
Nothing to memorise. Write 0, 1 and the arrow of adding the previous two is a free 2 marks.
Example — compute F₇ recursively
F₇ = F₆ + F₅
  = (F₅ + F₄) + F₅
  = ((F₄ + F₃) + F₄) + F₅
  = (((F₃ + F₂) + F₃) + F₄) + F₅
  = (((F₂ + F₁) + F₂) + F₃) + F₄ + F₅
  = (((F₁ + F₀) + F₁) + F₂) + F₃ + F₄ + F₅
  = ((1 + 0) + 1) + 1 + 2 + 3 + 5 = 13
F₇ = 13
Trick

For any recursion question: write the base case, then write the "smaller" version in a column beside each step until you hit the base case, then compute the column back up. Marks are awarded for the base case even if you make an arithmetic slip.

Note the growth: Fibonacci roughly triples every 2 steps (F ≈ 1.618ⁿ) while factorial is far worse (n! ≈ (n/e)ⁿ). That is why real programs use loops, not naive recursion — but for your exam, recursion is the required method.

8. Solution of a Homogeneous Recurrence

A homogeneous linear recurrence is an equation that only mentions the sequence itself — no extra "forcing" term like 3ⁿ or 5.

General form aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ   (no standalone term)

The standard method: try an answer of the form aₙ = rⁿ, substitute, solve for r, and use those roots to build the answer.

Step 1 — the characteristic equation Substitute aₙ = rⁿ into aₙ = c₁aₙ₋₁ + c₂aₙ₋₂:
rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻²   ÷  divide by rⁿ⁻²:   r² = c₁r + c₂
If the roots are…General solutionShape
Two distinct roots r₁, r₂aₙ = A·r₁ⁿ + B·r₂ⁿSum of two exponentials
One repeated root r (twice)aₙ = (A + Bn)·rⁿOne exponential times a straight line
Complex roots r = ρe±iθaₙ = ρⁿ(A cos nθ + B sin nθ)Oscillates, amplitude grows/shrinks by ρⁿ
Example — aₙ = 3aₙ₋₁ − 2aₙ₋₂, with a₀ = 1, a₁ = 4

Step 1 · characteristic equation. Try aₙ = rⁿ:

r² = 3r − 2   →   r² − 3r + 2 = 0

Step 2 · factorise.

(r − 1)(r − 2) = 0   →   r₁ = 1, r₂ = 2

Two distinct roots, so use the first row: aₙ = A·1ⁿ + B·2ⁿ.

Step 3 · use the initial values to find A and B.

n = 0:  a₀ = A + B = 1
n = 1:  a₁ = A + 2B = 4
         →  subtract: B = 3, so A = 1 − 3 = −2

Step 4 · write the answer.

aₙ = −2 + 3·2ⁿ
aₙ = 3·2ⁿ − 2.  Quick check: a₀ = 3−2 = 1 ✓  a₁ = 6−2 = 4 ✓
Tricks for recurrences
  • Always check your final answer in the original recurrence. Put your closed form back in and see if a₂, a₃ match. 30 seconds, saves a whole answer.
  • Factorial is a homogeneous recurrence in disguise: n! = 1·(n−1)!. Roots: the characteristic equation is r = 1 — a single repeated root, but the exact answer n! is not of the exponential form, so use the definition instead. If a question asks for the "solution of the homogeneous relation" for factorial, they mean the recurrence form.
  • Fibonacci is homogeneous too: Fₙ = Fₙ₋₁ + Fₙ₋₂ gives r² = r + 1, roots (1±√5)/2, and the Binet formula. In the exam they usually just want the recursive answer.
  • Write the constants as A, B, C… in the order the roots are listed. Mixing up A and B is the most common arithmetic slip.

Self-check

Open to see the answers

1. A = {1,2,3,4}, B = {x, y}. List A × B and give |A × B|.

A × B = {(1,x),(1,y),(2,x),(2,y),(3,x),(3,y),(4,x),(4,y)}
|A × B| = 4 × 2 = 8  — 4 rows of 2.

2. Is the relation R = {(1,1),(1,2),(2,1)} on A = {1,2} reflexive, symmetric, transitive? Is it an equivalence relation?

Reflexive? (2,2) is missing → No.
Symmetric? (1,2) present and (2,1) present → Yes.
Transitive? (1,1) and (1,2) are in R, so (1,2) must be in R ✓; (1,2) and (2,1) in R so (1,1) ✓; (2,1) and (1,1) in R so (2,1) ✓ → Yes.
Equivalence relation? Needs all three. Reflexive fails → No.

3. Find ⌊−2.5⌋, ⌈−2.5⌉, ⌊7.999⌋.

⌊−2.5⌋ = −3 (largest integer ≤ −2.5)
⌈−2.5⌉ = −2 (smallest integer ≥ −2.5)
⌊7.999⌋ = 7
← BackOverview