Relations and Functions
Types of Relations
Whenever two objects are connected by a rule — "is the brother of", "is less than", "leaves the same remainder as" — mathematics records that connection as a relation. Formally, a relation is built on top of the Cartesian product.
Cartesian product and relation
For two non-empty sets $A$ and $B$, the Cartesian product is the set of all ordered pairs $A \times B = \{(a,b) : a \in A,\ b \in B\}$. A relation $R$ from $A$ to $B$ is any subset $R \subseteq A \times B$. We write $a\,R\,b$ (read "$a$ is related to $b$") when $(a,b) \in R$.
When $A = B$, we call $R$ a relation on $A$. If $A$ has $n$ elements then $A \times A$ has $n^2$ ordered pairs, so there are $2^{n^2}$ possible relations on $A$ — a relation is simply a choice of which pairs to keep.
Two extreme cases
- Empty relation: $R = \varnothing$. No element is related to any other. Example: on $A=\{1,2,3\}$, the rule $a\,R\,b \iff a - b = 7$ gives the empty relation.
- Universal relation: $R = A \times A$. Every element is related to every element. Example: on the set of all students of a class, "has the same nationality as" may be universal.
The empty and universal relations are sometimes called trivial relations.
The three building-block properties
Let $R$ be a relation on a set $A$. We test it against three properties:
| Property | Condition (for all elements) | Plain meaning |
|---|---|---|
| Reflexive | $(a,a)\in R \ \ \forall a\in A$ | Every element relates to itself. |
| Symmetric | $(a,b)\in R \Rightarrow (b,a)\in R$ | If $a$ relates to $b$, then $b$ relates to $a$. |
| Transitive | $(a,b)\in R \text{ and } (b,c)\in R \Rightarrow (a,c)\in R$ | Relations "chain" together. |
A single missing pair is enough to break a property. To disprove reflexivity, symmetry, or transitivity you only need one counter-example; to prove it you must argue for all elements.
Equivalence relations — the star of the chapter
A relation that is reflexive, symmetric and transitive at the same time is called an equivalence relation. Equivalence relations are how mathematics says "these things behave the same for our purpose": congruent triangles, parallel lines, integers with the same remainder.
An equivalence relation slices the set into non-overlapping pieces called equivalence classes. The class of an element $a$ is $[a] = \{x \in A : x\,R\,a\}$. Two classes are either identical or completely disjoint, and together they cover all of $A$ — this is called a partition. The most important Class-12 example is congruence modulo $n$ on $\mathbb{Z}$: $a \equiv b \pmod{n} \iff n \mid (a-b)$, whose classes are the remainder sets $\{[0],[1],\dots,[n-1]\}$.
Reflexive: For every real $a$, $a \le a$ is true, so $(a,a)\in R$. Yes.
Symmetric: Take $a=2,\ b=5$. Then $2 \le 5$ so $(2,5)\in R$, but $5 \le 2$ is false, so $(5,2)\notin R$. One counter-example is enough — not symmetric.
Transitive: If $a \le b$ and $b \le c$ then $a \le c$. Yes.
Conclusion: $R$ is reflexive and transitive but not symmetric, hence not an equivalence relation. (It is in fact a partial order.)
Reflexive: $a-a = 0$ and $3 \mid 0$, so $a\,R\,a$ for every $a$. Yes.
Symmetric: If $3\mid(a-b)$ then $a-b = 3k$ for some integer $k$, so $b-a = 3(-k)$, hence $3\mid(b-a)$. Yes.
Transitive: If $3\mid(a-b)$ and $3\mid(b-c)$, write $a-b=3k,\ b-c=3m$. Adding, $a-c = 3(k+m)$, so $3\mid(a-c)$. Yes.
All three hold, so $R$ is an equivalence relation. The classes are grouped by remainder on division by $3$:
- $[0]=\{\dots,-3,0,3,6,\dots\}$
- $[1]=\{\dots,-2,1,4,7,\dots\}$
- $[2]=\{\dots,-1,2,5,8,\dots\}$
These three disjoint classes partition $\mathbb{Z}$.
Reflexive: $(1,1),(2,2),(3,3)$ are all present. Yes.
Symmetric: The only "off-diagonal" pairs are $(1,2)$ and $(2,1)$, and both are present. Yes.
Transitive: Check chains. $(1,2)$ and $(2,1)$ give us $(1,1)$ — present. $(2,1)$ and $(1,2)$ give $(2,2)$ — present. No chain forces a missing pair. Yes.
$R$ is reflexive, symmetric and transitive, so it is an equivalence relation. Its classes are $\{1,2\}$ and $\{3\}$.
$a+b$ is even exactly when $a$ and $b$ have the same parity (both odd or both even).
Reflexive: $a+a=2a$ is always even. Yes.
Symmetric: $a+b=b+a$, so parity is unchanged. Yes.
Transitive: If $a,b$ share parity and $b,c$ share parity, then $a,c$ share parity. Yes.
So $R$ is an equivalence relation. The classes are the odd numbers $[1]=\{1,3\}$ and the even numbers $[2]=\{2,4\}$.
- A relation on $A$ is any subset of $A\times A$; with $|A|=n$ there are $2^{n^2}$ possible relations.
- Empty relation = $\varnothing$; universal relation = $A\times A$.
- Reflexive: $(a,a)\in R$ for all $a$. Symmetric: $(a,b)\Rightarrow(b,a)$. Transitive: $(a,b),(b,c)\Rightarrow(a,c)$.
- To disprove a property, one counter-example suffices; to prove it, argue for all elements.
- Equivalence relation = reflexive + symmetric + transitive; it partitions $A$ into disjoint equivalence classes.
- Congruence mod $n$ on $\mathbb{Z}$ is the model equivalence relation, with classes $[0],[1],\dots,[n-1]$.
One-One and Onto Functions
A function $f : A \to B$ is a special relation that assigns to every element of the domain $A$ exactly one element of the codomain $B$. Two demands must both hold: nothing in $A$ is left unmapped, and nothing in $A$ maps to two different outputs. In Class 12 we classify functions by how they fill the codomain.
One-one (injective) functions
$f$ is one-one (injective) if different inputs always give different outputs:
$$f(x_1)=f(x_2) \ \Rightarrow\ x_1=x_2 \qquad\text{equivalently}\qquad x_1 \ne x_2 \Rightarrow f(x_1)\ne f(x_2).$$
Graphically, a function of a real variable is one-one when no horizontal line meets its graph more than once (the horizontal-line test). A handy shortcut: a function that is strictly increasing or strictly decreasing on its whole domain is automatically one-one.
Onto (surjective) functions
$f$ is onto (surjective) if every element of the codomain is actually hit — that is, the range equals the codomain:
$$\forall\, y \in B,\ \exists\, x \in A \text{ such that } f(x)=y, \qquad \text{i.e. } \operatorname{Range}(f) = B.$$
Onto-ness depends on the chosen codomain. The same formula can be onto or not depending on whether $B$ is $\mathbb{R}$, $[0,\infty)$, $\mathbb{N}$, and so on. So always read the codomain carefully.
Bijective functions
$f$ is bijective if it is both one-one and onto. A bijection pairs up the two sets perfectly — each input has a unique output and each output has a unique pre-image. Only bijections are invertible (the subject of the next page).
| Type | Test | Counting (finite sets, $|A|=|B|=n$) |
|---|---|---|
| One-one | $f(x_1)=f(x_2)\Rightarrow x_1=x_2$ | $n!$ injective maps |
| Onto | $\operatorname{Range}=B$ | $n!$ surjective maps |
| Bijective | one-one and onto | $n!$ bijections |
Useful fact: when $A$ and $B$ are finite and of equal size, a function is one-one if and only if it is onto. This shortcut fails for infinite sets — for example $f:\mathbb{N}\to\mathbb{N},\ f(x)=2x$ is one-one but not onto.
How to prove it in an exam
- One-one: assume $f(x_1)=f(x_2)$ and algebraically force $x_1=x_2$.
- Onto: take an arbitrary $y\in B$, solve $f(x)=y$ for $x$, and check that this $x$ lies in $A$.
- To disprove: give one explicit counter-example.
One-one: Suppose $f(x_1)=f(x_2)$. Then $2x_1+3 = 2x_2+3 \Rightarrow 2x_1=2x_2 \Rightarrow x_1=x_2$. So $f$ is one-one.
Onto: Take any $y\in\mathbb{R}$. Solve $2x+3=y \Rightarrow x=\dfrac{y-3}{2}$, which is a real number, so it lies in the domain $\mathbb{R}$ and $f(x)=y$. Hence $f$ is onto.
Being one-one and onto, $f$ is bijective.
One-one? $f(-2)=4=f(2)$ but $-2\ne 2$, so $f$ is not one-one.
Onto? Outputs are squares, so $f(x)\ge 0$ always. A negative codomain value such as $y=-1$ has no pre-image. So $f$ is not onto.
Note: If we shrink both sides — restrict to $f:[0,\infty)\to[0,\infty)$ — then $f(x)=x^2$ becomes bijective. Domain and codomain are part of the function.
One-one: For natural numbers, $x_1^2=x_2^2$ with $x_1,x_2>0$ forces $x_1=x_2$. So it is one-one.
Onto: The value $y=3\in\mathbb{N}$ is not a perfect square, so no natural $x$ gives $f(x)=3$. Not onto.
Thus $f$ is one-one but not onto — a reminder that the finite "one-one $\Leftrightarrow$ onto" shortcut does not apply to infinite sets.
One-one: $x^3$ is strictly increasing on $\mathbb{R}$ (if $x_1 Onto: For any $y\in\mathbb{R}$, the real number $x=y^{1/3}$ satisfies $f(x)=y$. Onto. Hence $f$ is bijective.
- One-one (injective): $f(x_1)=f(x_2)\Rightarrow x_1=x_2$ — passes the horizontal-line test.
- Onto (surjective): range $=$ codomain; depends on which codomain is chosen.
- Bijective: one-one and onto; only bijections are invertible.
- Strictly increasing or strictly decreasing $\Rightarrow$ one-one.
- For finite sets of equal size, one-one $\iff$ onto; this fails for infinite sets (e.g. $f(x)=2x$ on $\mathbb{N}$).
- Prove one-one by algebra; prove onto by solving $f(x)=y$ and checking $x$ is in the domain.
Composition and Invertible Functions
Once we have functions we can chain them and, when they are bijective, reverse them. These two ideas — composition and inverse — are the practical payoff of one-one and onto.
Composition of functions
Given $f:A\to B$ and $g:B\to C$, the composite $g\circ f : A \to C$ is defined by
$$(g\circ f)(x) = g\big(f(x)\big).$$
You apply $f$ first, then feed the result into $g$. For the composite to make sense, the range of $f$ must sit inside the domain of $g$. Two key facts:
- Not commutative: in general $g\circ f \ne f\circ g$.
- Associative: $h\circ(g\circ f) = (h\circ g)\circ f$, so we can drop the brackets.
The identity function $I_A(x)=x$ acts as a "do nothing" map: $f\circ I_A = f = I_B \circ f$.
Invertible functions
A function $f:A\to B$ is invertible if there is a function $g:B\to A$ that undoes it:
$$g\circ f = I_A \quad\text{and}\quad f\circ g = I_B.$$
Such a $g$ is unique; we call it the inverse and write $f^{-1}$. The central theorem of this chapter:
$f$ is invertible $\iff$ $f$ is bijective (one-one and onto).
This is why we spent the previous page classifying functions: only a bijection can be inverted. Note $f^{-1}$ is the inverse function, not the reciprocal $1/f$.
Properties of the inverse
- $(f^{-1})^{-1} = f$ — inverting twice returns the original.
- $f^{-1}\big(f(x)\big)=x$ and $f\big(f^{-1}(y)\big)=y$.
- Reversal law: if $f$ and $g$ are bijections, then $(g\circ f)^{-1} = f^{-1}\circ g^{-1}$ ("socks and shoes": undo in reverse order).
Finding an inverse — the method
- Confirm $f$ is bijective (so the inverse exists).
- Write $y=f(x)$.
- Solve the equation for $x$ in terms of $y$.
- Swap symbols to express $f^{-1}(y)$ (or rename $y$ as $x$).
$(g\circ f)(x) = g(f(x)) = g(2x+1) = (2x+1)^2 = 4x^2+4x+1$.
$(f\circ g)(x) = f(g(x)) = f(x^2) = 2x^2+1$.
At $x=1$: $(g\circ f)(1)=9$ while $(f\circ g)(1)=3$. They disagree, confirming composition is not commutative.
From the previous page, $f(x)=2x+3$ is bijective, so it is invertible.
Put $y=2x+3$. Solve for $x$: $x=\dfrac{y-3}{2}$. Therefore
$$f^{-1}(y)=\frac{y-3}{2}, \qquad \text{or} \qquad f^{-1}(x)=\frac{x-3}{2}.$$
Check: $f^{-1}(f(x)) = \dfrac{(2x+3)-3}{2} = x$. Correct.
Put $y=\dfrac{x}{x-2}$. Then $y(x-2)=x \Rightarrow yx-2y = x \Rightarrow yx - x = 2y \Rightarrow x(y-1)=2y$.
So $x=\dfrac{2y}{y-1}$ (valid since $y\ne 1$). Hence
$$f^{-1}(x)=\frac{2x}{x-1}.$$
Check at a point: $f(0)=\dfrac{0}{-2}=0$ and $f^{-1}(0)=\dfrac{0}{-1}=0$. Consistent.
First, $(g\circ f)(x)=g(x+1)=3(x+1)=3x+3$. Inverting: set $y=3x+3 \Rightarrow x=\dfrac{y-3}{3}$, so $(g\circ f)^{-1}(x)=\dfrac{x-3}{3}$.
Next, $f^{-1}(x)=x-1$ and $g^{-1}(x)=\dfrac{x}{3}$. Then $(f^{-1}\circ g^{-1})(x)=f^{-1}\!\left(\dfrac{x}{3}\right)=\dfrac{x}{3}-1=\dfrac{x-3}{3}$.
Both sides equal $\dfrac{x-3}{3}$, so the reversal law holds.
- Composition: $(g\circ f)(x)=g(f(x))$ — apply $f$ first, then $g$.
- Composition is associative but not commutative: usually $g\circ f \ne f\circ g$.
- Identity function $I(x)=x$ satisfies $f\circ I = I\circ f = f$.
- $f$ is invertible $\iff$ bijective; the inverse $f^{-1}$ is unique.
- $(f^{-1})^{-1}=f$ and reversal law $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$.
- To find $f^{-1}$: set $y=f(x)$, solve for $x$, then rename.