Relations and Functions

If A and B are two non-empty sets, a relation R from A to B is simply a subset of the Cartesian product A × B. So R ⊆ A × B, and if (a, b) ∈ R we write a R b, read as "a is related to b". The set of first elements of the ordered pairs in R is called the domain of R, and the set of second elements is called the range of R.

When A = B, we simply say R is a relation on the set A, and R ⊆ A × A. Two special relations on any set A are worth naming: the empty relation R = ∅ (no element of A is related to any element), and the universal relation R = A × A (every element is related to every element, including itself).

To study relations in general, we classify them using three key properties:

• Reflexive: R is reflexive if (a, a) ∈ R for every a ∈ A.
• Symmetric: R is symmetric if (a, b) ∈ R ⟹ (b, a) ∈ R for all a, b ∈ A.
• Transitive: R is transitive if (a, b) ∈ R and (b, c) ∈ R ⟹ (a, c) ∈ R for all a, b, c ∈ A.

Worked Example: Let A = {1, 2, 3, 4} and let R = {(a, b) : a divides b}. Check whether R is reflexive, symmetric and transitive.

Reflexive: every natural number divides itself, so (a, a) ∈ R for all a ∈ A. Hence R is reflexive.

Symmetric: (1, 2) ∈ R because 1 divides 2, but (2, 1) ∉ R because 2 does not divide 1. So R is not symmetric.

Transitive: suppose (a, b) ∈ R and (b, c) ∈ R, i.e., a divides b and b divides c. Then a must divide c as well (since b = ka and c = mb = mka for integers k, m). So (a, c) ∈ R, and R is transitive.

Conclusion: R is reflexive and transitive, but not symmetric.

A relation R on a set A is called an equivalence relation if it is simultaneously reflexive, symmetric and transitive. Equivalence relations are important because they behave like "sameness" — they group elements of A into non-overlapping clusters called equivalence classes.

For a ∈ A, the equivalence class of a, denoted [a], is defined as [a] = {x ∈ A : (x, a) ∈ R}, i.e., the set of all elements related to a. A fundamental fact is that any two equivalence classes are either identical or completely disjoint, and the union of all distinct equivalence classes is the whole set A. This means an equivalence relation always partitions A into disjoint, non-empty subsets.

Worked Example: Let R be the relation on the set of integers Z defined by a R b if and only if (a − b) is divisible by 3 (congruence modulo 3). Show R is an equivalence relation and list its equivalence classes.

Reflexive: a − a = 0, and 3 divides 0, so (a, a) ∈ R for every a. R is reflexive.

Symmetric: if (a − b) is divisible by 3, say a − b = 3k, then b − a = 3(−k), which is also divisible by 3. So (b, a) ∈ R. R is symmetric.

Transitive: if a − b = 3k and b − c = 3m, adding gives a − c = 3(k + m), which is divisible by 3. So R is transitive.

Hence R is an equivalence relation. Every integer leaves remainder 0, 1 or 2 on division by 3, so there are exactly three equivalence classes:

• [0] = {..., −6, −3, 0, 3, 6, ...} (multiples of 3)
• [1] = {..., −5, −2, 1, 4, 7, ...}
• [2] = {..., −4, −1, 2, 5, 8, ...}

These three classes are disjoint and their union is all of Z, exactly as the partition property predicts.

A function f : A → B assigns to every element of A exactly one element of B. Two important properties describe how efficiently f uses its codomain:

• One-one (injective): f is one-one if distinct elements of A always have distinct images in B, i.e., f(x₁) = f(x₂) ⟹ x₁ = x₂ (equivalently, x₁ ≠ x₂ ⟹ f(x₁) ≠ f(x₂)).
• Onto (surjective): f is onto if every element of B is the image of at least one element of A, i.e., for every y ∈ B there exists some x ∈ A such that f(x) = y. In other words, Range(f) = B.

Worked Example 1: Let f : R → R be defined by f(x) = 2x + 3. Show f is one-one and onto.

One-one: assume f(x₁) = f(x₂). Then 2x₁ + 3 = 2x₂ + 3, so 2x₁ = 2x₂, giving x₁ = x₂. Hence f is one-one.

Onto: let y ∈ R be any real number. We need x ∈ R with f(x) = y, i.e., 2x + 3 = y, so x = (y − 3)/2, which is a real number for every real y. Hence every y ∈ R has a pre-image, so f is onto.

Worked Example 2: Let f : R → R be defined by f(x) = x². Show f is neither one-one nor onto.

Not one-one: f(2) = 4 and f(−2) = 4, so two distinct inputs (2 and −2) give the same output. Hence f is not one-one.

Not onto: since x² ≥ 0 for every real x, no negative real number (e.g., −1) is ever the image of any x ∈ R. So Range(f) = [0, ∞) ≠ R, and f is not onto.

A function f : A → B that is both one-one and onto is called a bijective function, or simply a bijection. Bijections set up a perfect one-to-one pairing between every element of A and every element of B — nothing in B is left out, and nothing in B is repeated. A useful consequence is that if A and B are finite sets and a bijection f : A → B exists, then A and B must have the same number of elements.

Counting functions between finite sets is a common application. Suppose |A| = m and |B| = n.

• The total number of functions from A to B is nᵐ, since each of the m elements of A can independently be mapped to any of the n elements of B.
• The number of one-one functions (injections) from A to B, when m ≤ n, is ⁿPₘ = n! / (n − m)!, since the images of the m elements must all be distinct, chosen in order from n available elements.
• When m = n, every one-one function from A to B is automatically onto too (and vice-versa), so the number of bijections from a set with n elements to itself is simply n!.

Worked Example: Let A = {a, b, c} (3 elements) and B = {1, 2, 3, 4, 5} (5 elements). Find the number of one-one functions from A to B, and the number of bijections from A to A.

Number of one-one functions from A to B: here m = 3, n = 5, so the count is ⁵P₃ = 5! / (5 − 3)! = 5 × 4 × 3 = 60.

Number of bijections from A to A: here A has 3 elements, so the count is 3! = 3 × 2 × 1 = 6.

Given two functions f : A → B and g : B → C, their composition g∘f : A → C is defined by (g∘f)(x) = g(f(x)) for every x ∈ A. In words: first apply f to x to land in B, then apply g to that result to land in C. Note that g∘f is only defined when the codomain of f matches (or is contained in) the domain of g.

Composition of functions is associative: if f : A → B, g : B → C and h : C → D, then (h∘g)∘f = h∘(g∘f). However, composition is not commutative in general — g∘f and f∘g can be completely different functions, and one may not even be defined when the other is.

Worked Example: Let f(x) = 2x + 1 and g(x) = x² − 2, both functions R → R. Find g∘f and f∘g, and check whether they are equal.

(g∘f)(x) = g(f(x)) = g(2x + 1) = (2x + 1)² − 2 = 4x² + 4x + 1 − 2 = 4x² + 4x − 1.

(f∘g)(x) = f(g(x)) = f(x² − 2) = 2(x² − 2) + 1 = 2x² − 4 + 1 = 2x² − 3.

Clearly 4x² + 4x − 1 ≠ 2x² − 3 as functions (for instance, at x = 0 the first gives −1 while the second gives −3). So g∘f ≠ f∘g here, confirming that composition of functions does not commute in general.

Two useful facts connect composition with the properties from earlier sections: if both f and g are one-one, then g∘f is one-one; and if both f and g are onto, then g∘f is onto.

A function f : A → B is called invertible if there exists a function g : B → A such that g∘f = I_A (the identity function on A) and f∘g = I_B (the identity function on B). Such a g, if it exists, is unique and is called the inverse of f, written f⁻¹.

The central theorem of this topic is: f is invertible if and only if f is bijective (both one-one and onto). This makes intuitive sense — to reverse f uniquely, every output must come from exactly one input (one-one), and every element of B must actually be reached so the inverse is defined everywhere on B (onto).

Worked Example: Let f : R → R be defined by f(x) = 3x − 4. Show f is invertible and find f⁻¹.

One-one: if f(x₁) = f(x₂), then 3x₁ − 4 = 3x₂ − 4, so 3x₁ = 3x₂, giving x₁ = x₂. Hence f is one-one.

Onto: for any y ∈ R, we need x with 3x − 4 = y, i.e., x = (y + 4)/3, which is always a real number. So f is onto.

Since f is bijective, it is invertible. To find f⁻¹, set y = 3x − 4 and solve for x: x = (y + 4)/3. Swapping the roles of the variable, f⁻¹(x) = (x + 4)/3.

Verification: f(f⁻¹(x)) = 3 × [(x + 4)/3] − 4 = (x + 4) − 4 = x, and f⁻¹(f(x)) = [(3x − 4) + 4]/3 = 3x/3 = x. Both checks confirm the inverse is correct.