Relations and Functions

RELATIONS AND FUNCTIONS — COMPREHENSIVE CHAPTER NOTES

INTRODUCTION TO RELATIONS

**Definition:** A **relation R from set A to set B** is an arbitrary subset of the Cartesian product A × B.

If (a, b) ∈ R, we say "a is related to b under R" and write **a R b**

A relation in a set A is a subset of A × A

Two extreme relations exist: empty relation φ and universal relation A × A

Functions are special kinds of relations (covered in section 1.3)

**Key Points:**

The mathematical definition of relation abstracts from real-world recognisable connections

Relations provide the foundational framework for understanding functions

Every function is a relation, but not every relation is a function

---

EMPTY AND UNIVERSAL RELATIONS

**Definition 1: Empty Relation**

A relation R in set A is **empty** if R = φ ⊂ A × A, meaning no element of A is related to any element of A.

**Definition 2: Universal Relation**

A relation R in set A is **universal** if R = A × A, meaning every element of A is related to every element of A.

Both are called **trivial relations**.

**Example:** Let A be the set of all students in a boys school.

R = {(a,b) : a is sister of b} is empty (boys school has no sisters among students)

R′ = {(a,b) : height difference < 3 meters} is universal (any two students differ by less than 3 meters)

---

REFLEXIVE RELATIONS

**Definition:** A relation R in a set A is **reflexive** if **(a, a) ∈ R for every a ∈ A**.

In other words, every element must be related to itself.

**Testing for Reflexivity:**

Check if (a,a) is in the relation for ALL elements a ∈ A

If even one element fails this condition, R is not reflexive

**Examples:**

R = {(x,y) : x ≤ y} in ℝ is reflexive because x ≤ x for all x ∈ ℝ

R = {(x,y) : x = y} in any set is reflexive

R = {(x,y) : x > y} in ℤ is NOT reflexive because no integer is greater than itself

---

SYMMETRIC RELATIONS

**Definition:** A relation R in a set A is **symmetric** if **(a₁, a₂) ∈ R implies (a₂, a₁) ∈ R for all a₁, a₂ ∈ A**.

If one element is related to another, the reverse relation must also hold.

**Testing for Symmetry:**

For every ordered pair (a,b) in R, check if (b,a) is also in R

If one pair lacks its reverse, R is not symmetric

**Examples:**

R = {(x,y) : x = y} is symmetric because if x = y then y = x

R = {(x,y) : x ≤ y} in ℝ is NOT symmetric (e.g., 2 ≤ 3 but 3 ≤ 2 is false)

R = {(L₁,L₂) : L₁ ⊥ L₂} (perpendicular lines) is symmetric (if L₁ ⊥ L₂ then L₂ ⊥ L₁)

---

TRANSITIVE RELATIONS

**Definition:** A relation R in a set A is **transitive** if **(a₁, a₂) ∈ R and (a₂, a₃) ∈ R implies (a₁, a₃) ∈ R for all a₁, a₂, a₃ ∈ A**.

The relation "chains" through intermediate elements.

**Testing for Transitivity:**

Whenever you have a path a₁ → a₂ → a₃, check if a₁ → a₃ exists

If any path lacks its endpoint connection, R is not transitive

**Examples:**

R = {(x,y) : x ≤ y} in ℝ is transitive (if x ≤ y and y ≤ z then x ≤ z)

R = {(x,y) : x = y} is transitive (if x = y and y = z then x = z)

R = {(L₁,L₂) : L₁ ⊥ L₂} is NOT transitive (if L₁ ⊥ L₂ and L₂ ⊥ L₃, then L₁ ∥ L₃, not L₁ ⊥ L₃)

---

EQUIVALENCE RELATIONS

**Definition 4:** A relation R in a set A is an **equivalence relation** if it is **simultaneously reflexive, symmetric, and transitive**.

**Fundamental Property:** An equivalence relation partitions a set into disjoint **equivalence classes**.

**Equivalence Class:** For an element a ∈ A, the equivalence class [a] is the set of all elements related to a:

**[a] = {x ∈ A : x R a}**

**Properties of Equivalence Relations:**

All elements within an equivalence class are mutually related

No element from one class relates to elements of another class

All equivalence classes are pairwise disjoint

The union of all equivalence classes equals the original set A

**Example:** R = {(a,b) : 2 divides (a-b)} in ℤ

*Proof of equivalence:*

**Reflexive:** 2 divides (a-a) = 0 for all a ∈ ℤ ✓

**Symmetric:** If 2|(a-b), then 2|-(a-b) = (b-a), so 2|(b-a) ✓

**Transitive:** If 2|(a-b) and 2|(b-c), then (a-b) and (b-c) are both even, so (a-c) = (a-b) + (b-c) is even, thus 2|(a-c) ✓

**Equivalence Classes:** [0] = {all even integers}, [1] = {all odd integers}

**Worked Example:** In set A = {1,2,3,4,5,6,7}, define R = {(a,b) : both a and b are odd or both are even}

*Testing:*

Reflexive: (a,a) ∈ R since a and a have same parity ✓

Symmetric: If a,b have same parity, so do b,a ✓

Transitive: If a,b have same parity AND b,c have same parity, then a,c have same parity ✓

**Equivalence classes:** [1] = {1,3,5,7} (all odd), [2] = {2,4,6} (all even)

No element of {1,3,5,7} is related to any element of {2,4,6}.

---

ONE-ONE FUNCTIONS (INJECTIVE)

**Definition 5:** A function f : X → Y is **one-one (or injective)** if the images of distinct elements of X under f are distinct.

**Formally:** For all x₁, x₂ ∈ X: **f(x₁) = f(x₂) ⟹ x₁ = x₂**

**Alternative Testing Method:** If f(x₁) = f(x₂), you must be able to conclude x₁ = x₂.

**Graphical Check:** A function is one-one if every horizontal line intersects its graph at most once.

**Examples:**

f : ℝ → ℝ, f(x) = 2x is one-one [if 2x₁ = 2x₂ then x₁ = x₂]

f : ℕ → ℕ, f(x) = 2x is one-one [if 2x₁ = 2x₂ then x₁ = x₂]

f : ℝ → ℝ, f(x) = x² is NOT one-one [f(-1) = f(1) = 1 but -1 ≠ 1]

**Worked Example:** f : ℝ* → ℝ*, f(x) = 1/x

Assume f(x₁) = f(x₂). Then 1/x₁ = 1/x₂ ⟹ x₁ = x₂. Therefore f is one-one. ✓

---

ONTO FUNCTIONS (SURJECTIVE)

**Definition 6:** A function f : X → Y is **onto (or surjective)** if every element of Y is the image of at least one element of X.

**Formally:** For every y ∈ Y, **there exists x ∈ X such that f(x) = y**

**Key Remark:** f is onto if and only if **Range of f = Co-domain Y**

**Testing for Onto:**

Take an arbitrary element y from the co-domain

Try to find at least one x in the domain such that f(x) = y

If successful for all y, then f is onto

**Examples:**

f : ℝ → ℝ, f(x) = 2x is onto [for any y ∈ ℝ, choose x = y/2, then f(x) = y]

f : ℕ → ℕ, f(x) = 2x is NOT onto [odd numbers like 1,3,5 are never reached]

f : ℝ → ℝ, f(x) = x² is NOT onto [negative numbers like -1 cannot be images since x² ≥ 0]

**Worked Example:** f : ℕ → ℕ defined by f(1) = f(2) = 1 and f(x) = x-1 for x > 2

For any y ∈ ℕ:

If y = 1: f(1) = 1 ✓

If y > 1: f(y+1) = (y+1) - 1 = y ✓

So every natural number is the image of some natural number. Therefore f is onto. ✓

---

BIJECTIVE FUNCTIONS

**Definition 7:** A function f : X → Y is **bijective (one-one and onto)** if it is both one-one AND onto.

**Properties:**

Every element of X maps to a unique element of Y (one-one)

Every element of Y is mapped to by some element of X (onto)

There is a perfect "pairing" between X and Y

**Worked Example:** f : ℝ → ℝ, f(x) = 2x

*One-one:* f(x₁) = f(x₂) ⟹ 2x₁ = 2x₂ ⟹ x₁ = x₂ ✓

*Onto:* For any y ∈ ℝ, choose x = y/2 ∈ ℝ. Then f(y/2) = 2(y/2) = y ✓

Therefore f is bijective.

---

FINITE SET PROPERTY

**Important Theorem:** For a finite set X:

A one-one function f : X → X is necessarily **onto**

An onto function f : X → X is necessarily **one-one**

This means for finite sets, one-one ⟺ onto ⟺ bijective.

**Why Different for Infinite Sets:**

f : ℕ → ℕ, f(x) = 2x is one-one but NOT onto (Example 8)

f : ℕ → ℕ with f(1)=f(2)=1, f(x)=x-1 (x>2) is onto but NOT one-one (Example 10)

**Proof Sketch for Finite Set:** If f : X → X (|X| = n) is one-one, then n distinct domain elements map to n distinct range elements. Since co-domain has only n elements, range must equal co-domain, so f is onto.

---

COMMON MISTAKES TO AVOID

1. **Confusing Reflexivity:** R is reflexive only if (a,a) ∈ R for EVERY a ∈ A, not just some

2. **Symmetry Error:** Check both directions—if (a,b) ∈ R then (b,a) must be in R

3. **Transitivity Chain:** Requires: if (a,b) and (b,c) both in R, then (a,c) must be in R

4. **One-One vs Onto:** One-one means no two different inputs give same output; onto means every output is reached

5. **Domain vs Co-domain:** Range (actual outputs) may differ from co-domain (permitted outputs); a function is onto only when these equal

6. **Equivalence Class Partition:** Equivalence classes are pairwise disjoint AND their union is the entire set

---

EXAM QUICK-CHECK CHECKLIST

For a relation R in set A:

✓ Reflexive? Test: (a,a) ∈ R for ALL a

✓ Symmetric? Test: (a,b) ∈ R ⟹ (b,a) ∈ R

✓ Transitive? Test: (a,b) ∈ R and (b,c) ∈ R ⟹ (a,c) ∈ R

✓ Equivalence? If all three above properties hold

For a function f : X → Y:

✓ One-one? Test: f(x₁) = f(x₂) ⟹ x₁ = x₂

✓ Onto? Test: For every y in Y, ∃x in X such that f(x) = y

✓ Bijective? Both one-one AND onto simultaneously