Relations and Functions | Computer Science Fundamentals

Introduction

Relations and functions are fundamental concepts that describe connections between objects. They bridge set theory with practical applications like databases, graphs, and mappings in programming.

Learning Objectives

By the end of this reading, you will be able to:

Define and represent binary relations
Identify properties of relations (reflexive, symmetric, transitive)
Understand equivalence relations and partial orders
Distinguish functions from general relations
Apply function concepts (injection, surjection, bijection)

1. Binary Relations

A binary relation R from set A to set B is a subset of A × B.

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

Example

Let A = {1, 2, 3} and B = {a, b}

R = {(1, a), (2, a), (2, b), (3, b)}

This means: 1Ra, 2Ra, 2Rb, 3Rb

Relation on a Set

A relation on set A is a relation from A to A (a subset of A × A).

Example: "Less than" on {1, 2, 3} R = {(1, 2), (1, 3), (2, 3)}

Representing Relations

As a set of pairs: R = {(1, 2), (2, 3), (3, 1)}

As a matrix: For relation R on A = {1, 2, 3}

    1  2  3
  ┌─────────┐
1 │ 0  1  0 │    Entry (i,j) = 1 if iRj
2 │ 0  0  1 │
3 │ 1  0  0 │
  └─────────┘

As a directed graph:

    1 → 2
    ↑   ↓
    └── 3

2. Properties of Relations

Let R be a relation on set A.

Reflexive

R is reflexive if ∀a ∈ A: aRa

Every element is related to itself.

Examples:

≤ on integers (x ≤ x for all x) ✓
< on integers (x < x is false) ✗
"has same birthday as" ✓

Irreflexive

R is irreflexive if ∀a ∈ A: ¬(aRa)

No element is related to itself.

Example: < on integers (x < x is never true) ✓

Symmetric

R is symmetric if ∀a,b ∈ A: aRb → bRa

Examples:

"is sibling of" ✓
"is parent of" ✗
= (equality) ✓

Antisymmetric

R is antisymmetric if ∀a,b ∈ A: (aRb ∧ bRa) → a = b

Examples:

≤ on integers (if x ≤ y and y ≤ x, then x = y) ✓
"is ancestor of" ✓
⊆ on sets ✓

Transitive

R is transitive if ∀a,b,c ∈ A: (aRb ∧ bRc) → aRc

Examples:

< on integers (if x < y and y < z, then x < z) ✓
"is ancestor of" ✓
"is friend of" ✗ (typically)

3. Equivalence Relations

An equivalence relation is reflexive, symmetric, and transitive.

Examples of Equivalence Relations

Equality (=): The quintessential equivalence relation
Congruence modulo n: a ≡ b (mod n) if n divides (a - b)
- 7 ≡ 2 (mod 5) because 5 divides (7 - 2)
Same length: Strings of equal length

Equivalence Classes

For equivalence relation R on A, the equivalence class of element a is:

[a] = {x ∈ A | xRa}

Properties:

Every element belongs to exactly one equivalence class
Equivalence classes partition the set (divide it into non-overlapping parts)

Example: Congruence mod 3 on integers

[0] = {..., -6, -3, 0, 3, 6, 9, ...}
[1] = {..., -5, -2, 1, 4, 7, 10, ...}
[2] = {..., -4, -1, 2, 5, 8, 11, ...}

Partitions

A partition of set A is a collection of non-empty, disjoint subsets whose union is A.

Theorem: Every equivalence relation induces a partition, and every partition induces an equivalence relation.

4. Partial Orders

A partial order is reflexive, antisymmetric, and transitive.

A set with a partial order is called a partially ordered set or poset.

Examples

≤ on integers: Standard ordering
⊆ on sets: Set inclusion
- {1} ⊆ {1, 2} ⊆ {1, 2, 3}
Divides relation: a | b if a divides b
- 2 | 4, 4 | 12, so 2 | 12

Hasse Diagrams

Hasse diagrams visualize partial orders compactly:

Remove reflexive loops
Remove transitive edges
Place "larger" elements higher

Example: Divisibility on {1, 2, 3, 4, 6, 12}

Total Orders

A partial order is a total order if every pair of elements is comparable: ∀a,b ∈ A: aRb ∨ bRa

Example: ≤ on integers is total (we can compare any two integers) Counterexample: ⊆ on sets is not total ({1,2} and {2,3} are incomparable)

5. Functions

A function f from A to B (written f: A → B) is a relation where each element of A is related to exactly one element of B.

A is the domain
B is the codomain
f(a) is the image of a
The range is {f(a) | a ∈ A} ⊆ B

Function Notation

f: A → B defined by f(x) = expression

Example: f: ℝ → ℝ defined by f(x) = x²

Well-Defined Functions

A function must:

Be defined for all elements in the domain
Map each input to exactly one output

Not a function: f(x) = ±√x (multiple outputs) Not a function: f: ℝ → ℝ, f(x) = 1/x (undefined at x = 0)

6. Types of Functions

Injection (One-to-One)

A function f is injective if different inputs give different outputs: ∀a,b ∈ A: f(a) = f(b) → a = b

Example: f(x) = 2x is injective Counterexample: f(x) = x² is not injective (f(2) = f(-2) = 4)

Surjection (Onto)

A function f: A → B is surjective if every element of B is mapped to: ∀b ∈ B: ∃a ∈ A: f(a) = b

Example: f: ℝ → ℝ≥0, f(x) = x² is surjective Counterexample: f: ℝ → ℝ, f(x) = x² is not surjective (negative numbers not reached)

Bijection (One-to-One and Onto)

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

Bijections establish a one-to-one correspondence between sets.

Example: f: ℝ → ℝ, f(x) = 2x + 1

Key property: Bijections have inverses.

Visual Summary

Injection:          Surjection:         Bijection:
A     B             A     B             A     B
●──→●              ●──┬─→●             ●──→●
●──→●              ●──┘                ●──→●
●──→●              ●────→●             ●──→●
    ●              ●──┬─→●
(unused in B)      (some share target) (perfect pairing)

7. Function Composition

If f: A → B and g: B → C, the composition g ∘ f: A → C is: (g ∘ f)(x) = g(f(x))

Example:

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

Note: g ∘ f ≠ f ∘ g in general (composition is not commutative)

Properties

Composition is associative: (h ∘ g) ∘ f = h ∘ (g ∘ f)
If f and g are injective, g ∘ f is injective
If f and g are surjective, g ∘ f is surjective
If f and g are bijective, g ∘ f is bijective

8. Inverse Functions

If f: A → B is bijective, its inverse f⁻¹: B → A satisfies:

f⁻¹(f(a)) = a for all a ∈ A
f(f⁻¹(b)) = b for all b ∈ B

Example:

f(x) = 2x + 1
f⁻¹(x) = (x - 1)/2

Verification: f⁻¹(f(x)) = f⁻¹(2x + 1) = ((2x + 1) - 1)/2 = x ✓

9. Application to Computer Science

Relations in Databases

-- Relations are tables
-- Each table is a subset of a Cartesian product

CREATE TABLE enrollments (
    student_id INT,
    course_id INT,
    PRIMARY KEY (student_id, course_id)
);

-- This represents a relation between Students and Courses

Functions in Programming

# Pure functions - same input always gives same output
def add(a, b):
    return a + b

# Injection example - hash functions try to be injective
def simple_hash(s):
    return sum(ord(c) for c in s)

# But they're not always injective (collisions)
# simple_hash("ab") == simple_hash("ba")  # Both equal 195

# Bijection - encryption/decryption
def caesar_encrypt(text, shift):
    return ''.join(chr((ord(c) - 97 + shift) % 26 + 97) for c in text.lower())

def caesar_decrypt(text, shift):
    return caesar_encrypt(text, -shift)

Equivalence Classes in Practice

# Grouping by equivalence class
students = [
    {"name": "Alice", "grade": "A"},
    {"name": "Bob", "grade": "B"},
    {"name": "Carol", "grade": "A"},
    {"name": "Dave", "grade": "B"},
]

# Group by grade (equivalence relation: same grade)
from collections import defaultdict
by_grade = defaultdict(list)
for s in students:
    by_grade[s["grade"]].append(s["name"])

# Result: {"A": ["Alice", "Carol"], "B": ["Bob", "Dave"]}

Function Composition

# Composing functions
def double(x):
    return x * 2

def increment(x):
    return x + 1

def compose(f, g):
    return lambda x: f(g(x))

double_then_increment = compose(increment, double)
increment_then_double = compose(double, increment)

print(double_then_increment(5))  # 11 (5*2 + 1)
print(increment_then_double(5))  # 12 ((5+1) * 2)

Partial Orders in Dependencies

# Task dependencies form a partial order
# Task A must complete before Task B means A ≤ B

tasks = {
    "compile": [],
    "link": ["compile"],
    "test": ["link"],
    "deploy": ["test"],
    "docs": ["compile"]  # Can run in parallel with link, test
}

# Topological sort gives a valid execution order
# respecting the partial order

Exercises

Basic

For A = {1, 2, 3}, determine which properties hold for:
- R₁ = {(1,1), (2,2), (3,3), (1,2)}
- R₂ = {(1,2), (2,1), (2,3), (3,2)}
Let f: ℝ → ℝ. Determine if each is injective, surjective, both, or neither:
- f(x) = x³
- f(x) = eˣ
- f(x) = sin(x)
Find the inverse of f(x) = 3x - 7

Intermediate

Prove that "has the same remainder when divided by 5" is an equivalence relation on ℤ. List the equivalence classes.
For f(x) = x² and g(x) = √x, find:
- (f ∘ g)(x)
- (g ∘ f)(x)
- Are these equal? Explain.
Prove: If f: A → B is bijective, then f⁻¹ is also bijective.

Advanced

Prove: A relation R is an equivalence relation if and only if R is the kernel of some function (where aRb iff f(a) = f(b)).
Let A = {1, 2, ..., n}. How many:
- Relations on A exist?
- Reflexive relations on A exist?
- Symmetric relations on A exist?
Prove: The composition of two bijections is a bijection.

Summary

Relations are subsets of Cartesian products
Key properties: reflexive, symmetric, antisymmetric, transitive
Equivalence relations partition sets into equivalence classes
Partial orders define hierarchical structures
Functions map each input to exactly one output
Injective: one-to-one; Surjective: onto; Bijective: both
Bijections have inverses

Next Reading

Combinatorics →