Relations — The Three Properties and Equivalence

A relation $R$ from a set $A$ to itself is any subset of $A \times A$; $(a, b) \in R$ is written $aRb$. On a set with $n$ elements there are $2^{n^2}$ possible relations — the two extremes being the empty relation (no pair related) and the universal relation (every pair related). Everything the board asks about relations comes down to three properties, each with a precise test:

1. Reflexive: $(a, a) \in R$ for every $a \in A$. One missing diagonal pair breaks it.
2. Symmetric: whenever $(a, b) \in R$, also $(b, a) \in R$. Test every pair; one one-way pair breaks it.
3. Transitive: whenever $(a, b) \in R$ and $(b, c) \in R$, also $(a, c) \in R$. The chains must close.

A relation with all three properties is an equivalence relation — the chapter's central definition, and the single most-asked proof in board papers.

How to write the proof for full marks: take arbitrary elements, verify each property from the defining condition (never from a few examples), and state the conclusion. For "divisible by" conditions the three checks almost write themselves: $a - a = 0$ is divisible by anything (reflexive); if $k$ divides $a - b$ it divides $b - a = -(a-b)$ (symmetric); if $k$ divides $a - b$ and $b - c$ it divides their sum $a - c$ (transitive).

Equivalence classes

An equivalence relation slices $A$ into disjoint equivalence classes: $[a] = \{x \in A : xRa\}$, the set of everything related to $a$. Two facts carry the marks:

1. Classes are either identical or disjoint — they partition the set.
2. $[a] = [b]$ exactly when $aRb$.

Standard specimen: on $\mathbb{Z}$, $aRb$ iff $3$ divides $a - b$ gives exactly three classes $[0], [1], [2]$ — the possible remainders. With "$\vert a - b \vert$ is even", the two classes are the odds and the evens: all odd numbers are related to each other, all evens to each other, and never across.

Frequent one-mark traps: symmetric-and-transitive does not force reflexive (the element might relate to nothing at all); the smallest equivalence relation containing a given pair $(1, 2)$ on $\{1, 2, 3\}$ needs exactly the diagonal plus $(1,2)$ and $(2,1)$ — five pairs; and a relation can be reflexive and transitive without being symmetric ($a \leq b$ is the standing example).

Worked Examples — Relations

Example 1 — A relation with none of the properties

Check the three properties for $R = \{(a, b) : b = a + 1\}$ on $A = \{1, 2, 3, 4, 5, 6\}$.

Step 1 — reflexive? $(1, 1)$ would need $1 = 1 + 1$ — false. Not reflexive.

Step 2 — symmetric? $(1, 2) \in R$ but $(2, 1)$ would need $1 = 3$ — false. Not symmetric.

Step 3 — transitive? $(1, 2)$ and $(2, 3)$ are in $R$, but $(1, 3)$ would need $3 = 2$ — false. Not transitive.

Answer: neither reflexive, nor symmetric, nor transitive — one concrete failing pair is a complete disproof for each property.

Example 2 — The divisibility template, in full

Show that $R$ on $\mathbb{Z}$, defined by $aRb$ iff $2$ divides $a - b$, is an equivalence relation, and find its equivalence classes.

Step 1 — reflexive: $a - a = 0 = 2 \cdot 0$, divisible by $2$. ✓

Step 2 — symmetric: if $a - b = 2k$ then $b - a = 2(-k)$, still divisible. ✓

Step 3 — transitive: if $a - b = 2k$ and $b - c = 2m$, then $a - c = (a-b) + (b-c) = 2(k+m)$. ✓

Step 4 — the classes: $[0] = \{\ldots, -4, -2, 0, 2, 4, \ldots\}$ (evens) and $[1] = \{\ldots, -3, -1, 1, 3, \ldots\}$ (odds).

Answer: an equivalence relation with exactly two classes — evens and odds. This add-the-differences trick is the whole transitivity proof for every divisibility relation.

Example 3 — Counting classes for mod 3

For $R$ on $\mathbb{Z}$ with $aRb$ iff $3$ divides $a - b$, list the equivalence classes.

Step 1 — the proof pattern: identical to Example 2 with $3$ in place of $2$ — equivalence confirmed.

Step 2 — classes by remainder: every integer leaves remainder $0$, $1$ or $2$ on division by $3$, and two integers are related exactly when their remainders match.

Answer: three classes — $[0] = \{\ldots, -3, 0, 3, 6, \ldots\}$, $[1] = \{\ldots, -2, 1, 4, 7, \ldots\}$, $[2] = \{\ldots, -1, 2, 5, 8, \ldots\}$. In general, mod $n$ gives exactly $n$ classes.

Example 4 — Reflexive and transitive but not symmetric

Check the properties of $R = \{(a, b) : a \leq b\}$ on $\mathbb{R}$.

Step 1 — reflexive: $a \leq a$ always. ✓

Step 2 — symmetric? $2 \leq 3$ but $3 \leq 2$ is false. ✗

Step 3 — transitive: $a \leq b$ and $b \leq c$ chain to $a \leq c$. ✓

Answer: reflexive and transitive, not symmetric — the standard counterexample showing the three properties are genuinely independent.

Example 5 — The smallest equivalence relation containing a pair

Find the smallest equivalence relation on $\{1, 2, 3\}$ containing $(1, 2)$.

Step 1 — what is forced: reflexivity demands $(1,1), (2,2), (3,3)$; symmetry demands $(2,1)$ to partner the given $(1,2)$.

Step 2 — check nothing more is forced: transitivity on $\{(1,2), (2,1)\}$ requires $(1,1)$ and $(2,2)$ — already present. The element $3$ stays in its own class.

Answer: $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ — exactly $5$ pairs. Adding any pair involving $3$ would be a larger equivalence relation, not the smallest.

Functions — One-One, Onto, Bijective

A function $f : A \to B$ assigns exactly one output in $B$ to each input in $A$. The chapter classifies functions by two independent questions:

One-one (injective): different inputs give different outputs. Working test: assume $f(x_1) = f(x_2)$ and derive $x_1 = x_2$ by algebra. Disproof: exhibit two distinct inputs with equal outputs — one pair is enough.

Onto (surjective): every element of the codomain $B$ is hit. Working test: take an arbitrary $y \in B$, solve $f(x) = y$ for $x$, and check the solution lies in $A$. Disproof: name one element of $B$ with no preimage.

Bijective = one-one and onto — the gold standard, because bijective is exactly what makes a function invertible.

The domain matters as much as the formula. $f(x) = x^2$ is not one-one on $\mathbb{R}$ (since $f(-1) = f(1)$) but is one-one on $\mathbb{N}$; it is not onto $\mathbb{R}$ (no negative value is hit) but is onto $[0, \infty)$ if the codomain says so. Every injectivity/surjectivity verdict must quote the domain and codomain — answers that ignore them lose marks even when the algebra is right.

Composition and Invertibility

Composition: $(g \circ f)(x) = g(f(x))$ — apply $f$ first, then $g$. Order matters: in general $g \circ f \neq f \circ g$, and showing this with a concrete pair is itself a board question. Composition is associative, and composing with the identity function changes nothing.

Invertible function: $f : A \to B$ is invertible if there is a $g : B \to A$ with $g \circ f = I_A$ and $f \circ g = I_B$; then $g = f^{-1}$, and it is unique.

$$\boxed{\;f \text{ is invertible} \iff f \text{ is bijective}\;}$$

Finding $f^{-1}$, the three-line routine: set $y = f(x)$, solve for $x$ in terms of $y$, and declare $f^{-1}(y)$ to be that expression. Always finish by verifying one composition — $f^{-1}(f(x)) = x$ — because the verification line is where the presentation mark lives.

Useful closing facts: the composition of two bijections is a bijection, $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ (order reverses, exactly like matrix inverses), and if $f \circ f = I$ the function is its own inverse — a pattern the board likes to hide inside rational functions.

Worked Examples — Functions

Example 6 — A full bijectivity proof

Show that $f : \mathbb{R} \to \mathbb{R}$, $f(x) = 4x + 3$, is bijective.

Step 1 — one-one: suppose $f(x_1) = f(x_2)$: then $4x_1 + 3 = 4x_2 + 3$, so $4x_1 = 4x_2$ and $x_1 = x_2$. ✓

Step 2 — onto: take any $y \in \mathbb{R}$ and solve $4x + 3 = y$: $x = \frac{y - 3}{4}$, which is a real number, and $f\left(\frac{y-3}{4}\right) = y$. ✓

Answer: bijective. Every non-constant linear function $ax + b$ ($a \neq 0$) passes both tests by exactly this algebra.

Example 7 — When the domain changes the verdict

Discuss whether $f(x) = x^2$ is one-one and onto (i) as $f : \mathbb{R} \to \mathbb{R}$, (ii) as $f : \mathbb{N} \to \mathbb{N}$.

Step 1 — case (i), one-one? $f(-1) = 1 = f(1)$ with $-1 \neq 1$ — not one-one.

Step 2 — case (i), onto? $-1$ has no preimage (squares are never negative) — not onto.

Step 3 — case (ii), one-one? for natural numbers, $x_1^2 = x_2^2$ forces $x_1 = x_2$ (both positive) — one-one. ✓

Step 4 — case (ii), onto? $2$ is not a perfect square, so no natural $x$ has $x^2 = 2$ — not onto.

Answer: (i) neither; (ii) one-one but not onto. Same formula, different verdicts — the domain and codomain are part of the function.

Example 8 — One-one but not onto

Show that $f : \mathbb{N} \to \mathbb{N}$, $f(n) = n + 1$, is one-one but not onto.

Step 1 — one-one: $n_1 + 1 = n_2 + 1$ gives $n_1 = n_2$. ✓

Step 2 — onto? the element $1$ of the codomain would need $n + 1 = 1$, i.e. $n = 0$ — not a natural number. ✗

Answer: one-one, not onto — the shift leaves $1$ uncovered. (The same map on $\mathbb{Z}$ is onto: infinite sets behave differently from finite ones.)

Example 9 — A cubic bijection

Show that $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$, is bijective.

Step 1 — one-one: $x_1^3 = x_2^3$ gives $x_1^3 - x_2^3 = (x_1 - x_2)(x_1^2 + x_1x_2 + x_2^2) = 0$; the second factor is positive unless both are zero, so $x_1 = x_2$. ✓

Step 2 — onto: for any real $y$, $x = y^{1/3}$ is real and $f(x) = y$. ✓

Answer: bijective, with $f^{-1}(y) = y^{1/3}$ — contrast with $x^2$, where the even power destroys injectivity.

Worked Examples — Composition and Inverse

Example 10 — Order matters in composition

For $f(x) = \cos x$ and $g(x) = 3x^2$, find $g \circ f$ and $f \circ g$ and show they differ.

Step 1 — $g \circ f$: $g(f(x)) = 3\cos^2 x$.

Step 2 — $f \circ g$: $f(g(x)) = \cos(3x^2)$.

Step 3 — one test value: at $x = 0$: $g(f(0)) = 3$ while $f(g(0)) = \cos 0 = 1$.

Answer: $g \circ f \neq f \circ g$ — a single differing value is a complete proof.

Example 11 — Find the inverse and verify

Show that $f : \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$, is invertible and find $f^{-1}$.

Step 1 — bijective: linear with nonzero slope — one-one and onto by the Example 6 algebra.

Step 2 — solve $y = 2x + 3$: $x = \frac{y - 3}{2}$, so $f^{-1}(y) = \frac{y - 3}{2}$.

Step 3 — verify: $f^{-1}(f(x)) = \frac{(2x + 3) - 3}{2} = x$ ✓ and $f(f^{-1}(y)) = 2\cdot\frac{y-3}{2} + 3 = y$ ✓.

Answer: $f^{-1}(x) = \frac{x - 3}{2}$ — always close with the verification line.

Example 12 — A function that is its own inverse

Let $f(x) = \dfrac{4x + 3}{6x - 4}$, $x \neq \dfrac{2}{3}$. Show that $(f \circ f)(x) = x$. What is $f^{-1}$?

Step 1 — compute $f(f(x))$: $$f(f(x)) = \frac{4\cdot\frac{4x+3}{6x-4} + 3}{6\cdot\frac{4x+3}{6x-4} - 4} = \frac{4(4x+3) + 3(6x-4)}{6(4x+3) - 4(6x-4)} = \frac{16x + 12 + 18x - 12}{24x + 18 - 24x + 16} = \frac{34x}{34} = x$$

Step 2 — conclude: $f \circ f$ is the identity, so $f$ is invertible with $$f^{-1} = f$$

Answer: the function is its own inverse — multiply through by the common denominator and the collapse is three lines.

Example 13 — Composition, numerically

For $f(x) = x^2$ and $g(x) = x + 1$, evaluate $(f \circ g)(2)$ and $(g \circ f)(2)$.

Step 1 — $(f \circ g)(2)$: $g(2) = 3$, then $f(3) = 9$.

Step 2 — $(g \circ f)(2)$: $f(2) = 4$, then $g(4) = 5$.

Answer: $9$ and $5$ — read compositions inside-out, always applying the nearer function to the input first.