Why Every Roll Number Must Belong to Exactly One Student

A relation pairs elements of sets; a function is a special relation that gives every input exactly one output. Class 12 asks sharper questions: does a relation behave like equality, and does a function lose or miss any values?

This part covers reflexive, symmetric and transitive relations, equivalence relations, one-one and onto functions, and bijections and counting.

**A relation $R$ on a set $A$ is reflexive if every element is related to itself, symmetric if $(a,b)\in R$ always forces $(b,a)\in R$, and transitive if $(a,b)$ and $(b,c)$ in $R$ always force $(a,c)\in R$ — and each property must hold in every case.

Definitions for a relation $R$ on $A$:

- Reflexive** — $(a,a)\in R$ for every $a\in A$
- Symmetric — $(a_1,a_2)\in R\Rightarrow (a_2,a_1)\in R$
- Transitive — $(a_1,a_2)\in R$ and $(a_2,a_3)\in R\Rightarrow (a_1,a_3)\in R$

Worked example 1. On $A=\{1,2,3\}$, let $R=\{(1,1),(2,2),(3,3),(1,2)\}$.

- Reflexive: $(1,1),(2,2),(3,3)$ are all present — yes
- Symmetric: $(1,2)\in R$ but $(2,1)\notin R$ — no
- Transitive: the chains $(1,1),(1,2)$ and $(1,2),(2,2)$ both give $(1,2)\in R$ — yes

An everyday example. The relation is a sibling of among students of a school is symmetric — if Ravi is a sibling of Meena, Meena is a sibling of Ravi — but not reflexive, since no one is their own sibling.

The substance. One counterexample disproves a property, but proving it needs an argument that covers every element.

A relation is an equivalence relation when it is reflexive, symmetric and transitive together, and it splits the set into disjoint equivalence classes, each containing elements related to one another.

Worked example — divisibility by 2. On $\mathbb{Z}$, let $R=\{(a,b):2\text{ divides }a-b\}$.

- Reflexive: $a-a=0=2\times 0$
- Symmetric: if $a-b=2k$, then $b-a=2(-k)$
- Transitive: if $a-b=2k$ and $b-c=2m$, then $a-c=2(k+m)$

So $R$ is an equivalence relation, with two classes:

$$[0]=\{\dots ,-4,-2,0,2,4,\dots \}[1]=\{\dots ,-3,-1,1,3,5,\dots \}$$

They are disjoint, and together they make up $\mathbb{Z}$ — a partition of the integers.

An everyday example. Grouping students by their section is an equivalence relation: everyone is in their own section, the relation works both ways, and chains stay within one section.

The substance. Every equivalence relation produces a partition, and every partition defines an equivalence relation.

**A function $f:A\to B$ is one-one if different inputs always give different outputs, shown by proving that $f(x_1)=f(x_2)$ forces $x_1=x_2$, and onto if every element of $B$ is an output, shown by solving $f(x)=y$ for an $x$ in $A$.

Definitions:

- One-one (injective)** — $f(x_1)=f(x_2)\Rightarrow x_1=x_2$
- Onto (surjective) — every $y\in B$ equals $f(x)$ for some $x\in A$; equivalently, range = co-domain

Worked example 1. $f:\mathbb{R}\to \mathbb{R}$, $f(x)=2x+3$.

$$f(x_1)=f(x_2)\Rightarrow 2x_1+3=2x_2+3\Rightarrow x_1=x_2\text{(one-one)}$$

$$y=2x+3\Rightarrow x=\frac{y-3}{2}\in \mathbb{R}\text{ for every real }y\text{(onto)}$$

Worked example 2. $f:\mathbb{R}\to \mathbb{R}$, $f(x)=x^2$.

- $f(-2)=f(2)=4$, so it is not one-one
- No real $x$ gives $x^2=-1$, so it is not onto

Changing the sets changes the answer. $g:\mathbb{N}\to \mathbb{N}$, $g(x)=x^2$ is one-one, because natural numbers are positive, but not onto, because $2$ is not a perfect square.

An everyday example. Giving each student in a class a different roll number is a one-one function from students to roll numbers.

The substance. Whether a function is onto depends on the chosen co-domain, not only on its formula.

**A bijection is a function that is both one-one and onto, pairing every element of $A$ with exactly one element of $B$; between finite sets of sizes $m$ and $n$, one-one functions exist only when $m\le n$, and bijections exist only when $m=n$, numbering $n!$.

Counting functions from $A$ with $m$ elements to $B$ with $n$ elements:

- All functions**: $n^m$
- One-one functions when $m\le n$: $n(n-1)\cdots (n-m+1)=\frac{n!}{(n-m)!}$
- Bijections when $m=n$: $n!$

Worked example — counting. $A=\{1,2,3\}$ and $B=\{a,b,c,d\}$.

$$\text{all functions}=4^3=64\text{one-one functions}=4\times 3\times 2=24$$

There are no onto functions, because $3$ inputs cannot cover $4$ outputs.

Same finite set. For $f:A\to A$ with $A$ finite, one-one and onto are equivalent — either one implies the other.

An everyday example. **Assigning $5$ students to $5$ lockers, one each**, is a bijection, and there are $5!=120$ ways to do it.

The substance. That equivalence fails for infinite sets — $f(x)=2x$ on $\mathbb{N}$ is one-one but not onto.