Week 6  ·  9 July 2025

Functions & Relations

Sets, Cartesian Products, and Beyond

1 Sets & Power Sets Recap
2 Cartesian Products
3 What is a Function?
4 Injective & Surjective Functions
5 Composition & Inverse
6 Functions as Relations
§1

Sets & Power Sets Recap

A quick review of Week 5 — you'll need this for Cartesian products and functions.

Sets — the Core Vocabulary
Definition A set is an unordered collection of distinct objects called elements. We write a ∈ A to mean "a is an element of A".
Examples A = {1, 2, 3}
B = {cat, dog, fish}
ℕ = {0, 1, 2, 3, …}
Subset A ⊆ B means every element of A is also in B.

A ⊂ B means A ⊆ B and A ≠ B (proper subset).
Key Difference ∈ vs ⊆
2 ∈ {1,2,3} ✓ (element)
{2} ⊆ {1,2,3} ✓ (subset)
{2} ∈ {1,2,3} ✗ (set is not listed as element)
Set Operations (Reminder) A ∪ B = union (elements in A or B)  |  A ∩ B = intersection (elements in A and B)  |  A \ B = difference (in A but not B)  |  Ā = complement
The Power Set
Definition The power set 𝒫(A) of a set A is the set of all subsets of A.
Equivalently: X ∈ 𝒫(A)  ⟺  X ⊆ A
Worked Example Let A = {1, 2}. List all subsets:

∅    {1}    {2}    {1,2}

So 𝒫(A) = { ∅, {1}, {2}, {1,2} } and |𝒫(A)| = 4 = 2²
Key Pattern If |A| = n then |𝒫(A)| = 2ⁿ. Each element is either included or not → 2 choices per element.
Let A = {a, b, c}. How many elements does 𝒫(A) have?
§2

Cartesian Products

Pairing elements from two or more sets — the foundation of functions and relations.

Cartesian Product: Definition
Definition The Cartesian product of sets A and B is:
A × B = { (a, b) : a ∈ A and b ∈ B }

Each element is an ordered pair. Order matters: (a,b) ≠ (b,a) in general.
Worked Example Let A = {1, 2}, B = {x, y, z}.

A × B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) }

|A × B| = |A| × |B| = 2 × 3 = 6
Real-World Example A deck of playing cards = {A,2,…,K} × {♠,♥,♦,♣}. Each card is an ordered pair (value, suit) → 13 × 4 = 52 cards.
Cartesian Product: Extension & Practice
n-fold Cartesian Product A₁ × A₂ × … × Aₙ = { (a₁, a₂, …, aₙ) : aᵢ ∈ Aᵢ }
Elements are called n-tuples. The size is |A₁| × |A₂| × … × |Aₙ|.
Car Registration Plates 3 letters followed by 3 digits.
Let L = {A, B, …, Z} (26 letters), D = {0, 1, …, 9} (10 digits).

Plates = L × L × L × D × D × D
Total plates = 26³ × 10³ = 17,576 × 1,000 = 17,576,000
Let A = {0,1} and B = {a,b,c}. What is |B × A|?
§3

Functions

Functions assign exactly one output to each input — a precise version of what you already know from algebra.

What is a Function?
Definition A function f : A → B is a rule that assigns to each element of A exactly one element of B.

• Domain: the set A (all inputs)
• Codomain: the set B (all possible outputs)
• Range: { f(x) : x ∈ A } ⊆ B (outputs actually produced)
Valid Function Every element of A maps to exactly one element of B. A B a b c 1 2 3
NOT a Function An element of A maps to two outputs — this breaks the rule! A B a b ✗
Functions: Domain, Codomain, Range
Example 1 — Capital Letters & Loops Define f : {A,B,…,Z} → ℕ where f(letter) = number of closed loops.

f(A) = 1    f(B) = 2    f(C) = 0    f(O) = 1    f(Q) = 1

Range = {0, 1, 2} (only these values appear, even though codomain is all of ℕ)
Example 2 — Subsets and Cardinality Let X = {1,2,3,4}. Define g : 𝒫(X) → {0,1,2,3,4} by g(A) = |A|.

g(∅) = 0    g({1,3}) = 2    g({1,2,3,4}) = 4
Domain: all 16 subsets of X.   Range: {0, 1, 2, 3, 4}
For the letter-loops function above, what is the range?
§4

Injective & Surjective Functions

Two key properties that describe how a function maps its domain to its codomain.

Injective (One-to-One) Functions
Definition f : A → B is injective (one-to-one) if different inputs always give different outputs:
x ≠ y  ⟹  f(x) ≠ f(y)   (equivalently: f(x) = f(y) ⟹ x = y)

Intuition: No two arrows from A land on the same element in B.

A B a b c 1 2 3 4 ✓ Injective
Each input maps to a
different output
A B a b c 1 2 3 ✗ NOT Injective
Two inputs (a,b) land
on the same output (1)
Surjective (Onto) Functions
Definition f : A → B is surjective (onto) if every element of B is hit by at least one element of A:
∀ y ∈ B, ∃ x ∈ A such that f(x) = y

Intuition: No element in B is left without an arrow pointing to it. Range = Codomain.

A B ✓ Surjective
Every element of B
is reached
A B ? ✗ NOT Surjective
Bottom element of B
is never reached
Let f : ℝ → ℝ be defined by f(x) = x². Is f surjective?
Bijective Functions
Definition A function is bijective (a bijection or one-to-one correspondence) if it is both injective and surjective.
PropertyMeaning
Injectiveno two inputs share an output
Surjectiveevery output is reached
Bijectiveboth — perfect pairing
Why Bijections Matter A bijection f : A → B tells us |A| = |B|. This is how mathematicians compare the sizes of infinite sets!
Example f : {1,2,3} → {a,b,c}
f(1)=a, f(2)=b, f(3)=c

✓ Injective — all outputs distinct
✓ Surjective — all of B is covered
✓ Bijective

Non-example: f(x) = x² on ℝ is neither injective (f(2)=f(−2)) nor surjective.
§5

Composition & Inverse

Chaining functions together, and undoing them.

Function Composition
Definition Given f : A → B and g : B → C, the composition is:
(g ∘ f) : A → C    defined by    (g ∘ f)(x) = g(f(x))

Read "g after f" — first apply f, then apply g.
Worked Example Let f(x) = 2x + 1 and g(x) = x², both from ℝ → ℝ.

(g ∘ f)(x) = g(f(x)) = g(2x+1) = (2x+1)²
(f ∘ g)(x) = f(g(x)) = f(x²) = 2x² + 1

Note: In general g ∘ f ≠ f ∘ g — composition is not commutative!
A B C f g g ∘ f
Let f(x) = x + 3 and g(x) = 2x. What is (g ∘ f)(5)?
Inverse Functions
Definition Let f : A → B. A function g : B → A is the inverse of f if:
g ∘ f = id_A    and    f ∘ g = id_B
where id_A(x) = x for all x ∈ A. We write g = f⁻¹.
Example f : ℝ → ℝ,   f(x) = 3x − 1

To find f⁻¹, solve y = 3x − 1 for x:
x = (y + 1) / 3

So f⁻¹(y) = (y + 1) / 3

Check: f(f⁻¹(y)) = 3·(y+1)/3 − 1 = y ✓
Key Theorem A function has an inverse if and only if it is bijective.

• Not injective → two inputs share an output, so the inverse can't be a function (which output to go back to?)
• Not surjective → some outputs in B have no pre-image, so the inverse is undefined there.
§6

Functions as Relations

Connecting functions back to Cartesian products — a deeper, more abstract view.

Binary Relations
Definition A (binary) relation R between sets A and B is any subset of A × B:
R ⊆ A × B

We write a R b (or (a,b) ∈ R) to mean "a is related to b".
Familiar Relations
  • ≤ on ℤ: R = {(a,b) : a ≤ b} — e.g. (2,5) ∈ R but (5,2) ∉ R
  • Divisibility: R = {(a,b) : a divides b} — e.g. (3,12) ∈ R
  • "Is a friend of" on people — a social network is literally this!
How Many Relations Exist? The set of all relations between A and B is 𝒫(A × B) — the power set of the Cartesian product. If |A|=2, |B|=3 then |A×B|=6, so there are 2⁶ = 64 possible relations between A and B.
Functions as Special Relations

Every function is a relation, but with extra rules.

Function as a Relation A function f : A → B can be represented as a relation (set of ordered pairs):
R_f = { (x, f(x)) : x ∈ A } ⊆ A × B

This relation satisfies two special conditions:
1. Total: every x ∈ A appears as a first element in some pair
2. Functional: no x ∈ A appears with two different second elements
Concrete Example Let f : 𝒫({a,b}) → {0,1,2} where f(S) = |S|.

R_f = { (∅, 0), ({a}, 1), ({b}, 1), ({a,b}, 2) }

This is a subset of 𝒫({a,b}) × {0,1,2}. ✓ Total (all subsets listed) ✓ Functional (each subset has exactly one size)
The Bridge A relation R ⊆ A × B is a function exactly when it is total and functional. Relations that are NOT functions: like ≤ — the number 2 relates to 3, 4, 5, … (multiple outputs).
Relations vs Functions — Check Your Understanding
Quick Summary
  • Every function is a relation, but not every relation is a function.
  • A relation R ⊆ A × B is a function iff each a ∈ A appears exactly once as a first element.
  • The set of all relations between A and B is 𝒫(A × B).
Which of these subsets of {1,2} × {a,b,c} represents a function from {1,2} to {a,b,c}?
How many relations exist between A = {0,1} and B = {x,y}?
Pólya's Problem-Solving Framework

Use this every time you tackle an unfamiliar problem!

① Understand the Problem
  • What are you being asked?
  • Do you understand every word?
  • Can you draw a picture or diagram?
  • Is there enough information?
② Devise a Plan
  • Try small cases first
  • Look for a pattern
  • Work backwards from the answer
  • Reduce to a known problem
③ Carry Out the Plan
  • Execute methodically
  • Check each step
  • Be willing to revise the plan
④ Look Back
  • Does the answer make sense?
  • Can you verify it another way?
  • What did you learn from this problem?
  • Can the method generalise?
Practice Problem Find the domain and range of the function that assigns to each pair of positive integers its first element. Is it injective? Surjective?
Domain: ℤ⁺ × ℤ⁺ (pairs of positive integers).   Range: ℤ⁺ (every positive integer is the first of some pair).   Injective? No — (1,1) and (1,2) both map to 1.   Surjective? Yes — for any n ∈ ℤ⁺, the pair (n,1) maps to n.
Week 6 Summary
What We Covered
  • Power sets: 𝒫(A), |𝒫(A)| = 2ⁿ
  • Cartesian products: ordered pairs/tuples
  • Functions: domain, codomain, range
  • Injective: no two inputs → same output
  • Surjective: every output is reached
  • Bijective: both; has an inverse
  • Composition: (g∘f)(x) = g(f(x))
  • Inverse: exists iff bijective
  • Relations: subsets of A×B; functions are special relations
Next Week
  • Finishing off functions and relations
  • More on the written assessment (choosing & designing your project)
  • Introduction to Recursion & Induction
To Prepare
  • Read Rosen Ch. 2.3 (Functions)
  • Try: Rosen 2.3 exercises 1–10
  • Think about your written project topic
Questions? Email: cue.nguyen@jcu.edu.au  ·  Subject: MA2211 or MA2011 in the title
Use ← → arrow keys or click buttons to navigate