Chapter 1 · Sets, Relations and Functions

1.1 Sets and Relations

A set is a well-defined collection; a relation is a set of ordered pairs. From these two ideas come union, intersection and complement with their laws, the power set with its $2^n$ members, counting with $n(A\cup B)=n(A)+n(B)-n(A\cap B)$, and the reflexive, symmetric and transitive properties that make an equivalence relation.

A coaching centre has 60 students. 32 of them play cricket, 28 play football and 25 play hockey; some play two games and a few play all three. How many play none? You cannot add $32+28+25$ — the students who play two games would be counted twice. To count correctly you need to talk about collections of students and how they overlap: who is in this group and that one, who is in this one or that one, who is not in it. That is the language of sets. Now sort the same students into teams by the rule "is in the same batch as". Everyone is in the same batch as themselves; if Asha is with Ravi then Ravi is with Asha; if Asha is with Ravi and Ravi with Meera, then Asha is with Meera. Those three facts are exactly what make the rule split the students into separate, non-overlapping batches. Rules like this are called relations.

Sets and relations are the grammar of all of JEE Main mathematics: the domain of a function, the solution set of an inequality, an event in probability and a locus in coordinate geometry are all sets. In this section we build that grammar from the beginning — how to describe a set, its subsets and its power set, the operations of union, intersection and complement and the laws they obey, how to count the elements of a union, Cartesian products and relations, and finally the special properties (reflexive, symmetric, transitive) that make an equivalence relation. Direct questions on this unit in the paper are usually quick marks for a well-prepared candidate: counting with Venn diagrams, counting relations, and testing the three properties.

Sets, Subsets and the Power Set

📘 Definition 1.1 — Set, element and the two ways of writing a set

A set is a well-defined collection of distinct objects, called its elements (or members). "Well-defined" means that for every object we can decide, without opinion, whether it belongs to the collection. We write $a\in A$ if $a$ is an element of $A$, and $a\notin A$ if it is not.

Roster form lists the elements inside braces: $\{2,3,5,7\}$. Order and repetition do not matter, so $\{1,2,2,3\}=\{3,1,2\}$. Set-builder form describes the elements by a property: $\{x : x \text{ is a prime number less than } 10\}$, read "the set of all $x$ such that $x$ is a prime less than $10$".

"The good students of a class" is not a set — "good" is an opinion. "The students of the class who scored above 80" is a set. We use standard letters for the number sets that appear throughout the course: $\mathbb{N}=\{1,2,3,\dots\}$ (natural numbers, starting at $1$), $\mathbb{Z}=\{\dots,-2,-1,0,1,2,\dots\}$ (integers), $\mathbb{Q}$ (rationals $\tfrac pq$ with $p,q\in\mathbb{Z}$, $q\ne0$) and $\mathbb{R}$ (real numbers).

📘 Definition 1.2 — Empty, finite, infinite and equal sets

The empty set $\phi=\{\ \}$ has no elements. A set with exactly one element is a singleton. A set is finite if it is empty or its elements can be counted with the count coming to an end; then $n(A)$ denotes the number of its (distinct) elements. Otherwise the set is infinite. Two sets are equal, $A=B$, if they have exactly the same elements.

📘 Definition 1.3 — Subset, proper subset, universal set and intervals

$A$ is a subset of $B$, written $A\subseteq B$, if every element of $A$ is also an element of $B$. If in addition $A\ne B$, then $A$ is a proper subset of $B$, written $A\subset B$. In any discussion, the set that contains all the objects under consideration is the universal set $U$; every set in that discussion is a subset of $U$.

Important subsets of $\mathbb{R}$ are the intervals: for $a\lt b$, $\ (a,b)=\{x: a\lt x\lt b\}$ (open), $\ [a,b]=\{x:a\le x\le b\}$ (closed), and the half-open $[a,b)$, $(a,b]$; also $(a,\infty)=\{x:x\gt a\}$ and so on.

📐 Theorem 1.1 — Facts about subsets

For any sets $A$, $B$, $C$:

  1. $\phi\subseteq A$ and $A\subseteq A$.
  2. $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.
  3. If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.
  4. If $n(A)=n$, then $A$ has exactly $2^n$ subsets, of which $2^n-1$ are proper subsets.

Why (1)? To show $\phi\subseteq A$ we would have to find an element of $\phi$ that is not in $A$ — and $\phi$ has no elements at all, so there is nothing to check. Part (2) is the standard way to prove two sets equal: show each is contained in the other. Proof of (4). Build a subset of $A=\{a_1,\dots,a_n\}$ by going through the elements one at a time and deciding "in" or "out". There are $2$ choices for $a_1$, then $2$ for $a_2$, …, $2$ for $a_n$, and every sequence of choices gives a different subset. So there are $2\times2\times\dots\times2=2^n$ subsets. Exactly one of them is $A$ itself (all "in"), so $2^n-1$ are proper. $\blacksquare$

📘 Definition 1.4 — Power set

The power set of $A$, written $P(A)$, is the set of all subsets of $A$. By Theorem 1.1(4), if $n(A)=n$ then $n\big(P(A)\big)=2^n$. The elements of $P(A)$ are sets: $X\in P(A)$ means exactly $X\subseteq A$.

✏️ Example 1 — Writing sets, and counting subsets
(a) Write $A=\{x\in\mathbb{Z}: x^2\lt10\}$ and $B=\{x\in\mathbb{R}: x^2-5x+6=0\}$ in roster form. Is $B$ equal to $C=\{x\in\mathbb{N}: x \text{ is prime and } x \text{ divides } 6\}$? (b) Write $\{1,4,9,16,25\}$ in set-builder form. (c) List $P(\{a,b,c\})$. Is $a\in P(\{a,b,c\})$? Is $\{a\}\in P(\{a,b,c\})$? (d) How many subsets of $\{1,2,\dots,8\}$ contain both $1$ and $2$ but not $3$? (e) Find $n\big(P(P(\phi))\big)$.
Find (d) before you open the solution:
(a) $x^2\lt10$ for the integers $-3,\dots,3$ (since $3^2=9\lt10$ but $4^2=16$), so $A=\{-3,-2,-1,0,1,2,3\}$. $x^2-5x+6=(x-2)(x-3)=0$ gives $B=\{2,3\}$. The primes dividing $6$ are $2$ and $3$, so $C=\{2,3\}=B$: different descriptions, same elements, equal sets.
(b) $\{n^2 : n\in\mathbb{N},\ n\le5\}$ (or $\{x: x=n^2,\ n\in\mathbb{N},\ 1\le n\le5\}$).
(c) $P(\{a,b,c\})=\{\phi,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$ — $2^3=8$ elements. $a\notin P(\{a,b,c\})$ ($a$ is not a set of the list), but $\{a\}\in P(\{a,b,c\})$ because $\{a\}\subseteq\{a,b,c\}$.
(d) $1$ and $2$ must be in and $3$ must be out; each of the remaining five elements $4,\dots,8$ is free: $2^5=32$ subsets.
(e) $P(\phi)=\{\phi\}$ has one element, so $P(P(\phi))=\{\phi,\{\phi\}\}$ has $2^1=2$ elements.
Check (d) by a smaller case: subsets of $\{1,2,3,4\}$ containing $1,2$ but not $3$ are $\{1,2\}$ and $\{1,2,4\}$ — $2^1=2$ ✓.

Let $A=\{1,\{2\},3\}$. Which statement is true?

Union, Intersection, Complement and their Laws

New sets are made from old ones by three basic operations. Picture them in a Venn diagram: the universal set $U$ as a rectangle, each set as a circle inside it.

📘 Definition 1.5 — Operations on sets

Let $A$, $B$ be subsets of a universal set $U$.

  • Union: $A\cup B=\{x: x\in A \text{ or } x\in B\}$ (or both).
  • Intersection: $A\cap B=\{x: x\in A \text{ and } x\in B\}$. If $A\cap B=\phi$, the sets are disjoint.
  • Difference: $A-B=\{x: x\in A \text{ and } x\notin B\}$.
  • Complement: $A'=U-A=\{x\in U: x\notin A\}$ (also written $A^c$).
  • Symmetric difference: $A\,\Delta\,B=(A-B)\cup(B-A)$, the elements in exactly one of the two sets.

For example, with $U=\{1,2,\dots,8\}$, $A=\{1,2,3,4\}$ and $B=\{3,4,5,6\}$: $A\cup B=\{1,\dots,6\}$, $A\cap B=\{3,4\}$, $A-B=\{1,2\}$, $B-A=\{5,6\}$, $A\,\Delta\,B=\{1,2,5,6\}$ and $A'=\{5,6,7,8\}$. These operations obey a set of laws that look very like the laws of ordinary algebra — with a few surprises.

📐 Theorem 1.2 — Laws of the algebra of sets

For all subsets $A$, $B$, $C$ of a universal set $U$:

Idempotent$A\cup A=A,\quad A\cap A=A$
Identity$A\cup\phi=A,\quad A\cap U=A$
Domination$A\cup U=U,\quad A\cap\phi=\phi$
Commutative$A\cup B=B\cup A,\quad A\cap B=B\cap A$
Associative$(A\cup B)\cup C=A\cup(B\cup C)$
$(A\cap B)\cap C=A\cap(B\cap C)$
Distributive$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
Complement$A\cup A'=U,\ \ A\cap A'=\phi,\ \ (A')'=A$
$\phi'=U,\ \ U'=\phi$
De Morgan's laws$(A\cup B)'=A'\cap B'$
$(A\cap B)'=A'\cup B'$
Difference and absorption$A-B=A\cap B'$
$A\cup(A\cap B)=A,\ \ A\cap(A\cup B)=A$

Each law is proved by chasing an element: take an arbitrary $x$ and show that it belongs to the left side exactly when it belongs to the right side (Theorem 1.1(2)). De Morgan's first law:

$$\begin{aligned}x\in(A\cup B)'&\iff x\notin A\cup B\iff x\notin A\ \text{and}\ x\notin B\\&\iff x\in A'\ \text{and}\ x\in B'\iff x\in A'\cap B'.\end{aligned}$$

"Not (in $A$ or in $B$)" is the same as "not in $A$ and not in $B$": complementing swaps $\cup$ and $\cap$. The distributive law $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$: $x$ is in the left side $\iff$ $x\in A$ and ($x\in B$ or $x\in C$) $\iff$ ($x\in A$ and $x\in B$) or ($x\in A$ and $x\in C$) $\iff$ $x$ is in the right side. $\blacksquare$ Notice the surprise: unlike numbers, where $a+bc\ne(a+b)(a+c)$, both distributive laws hold for sets.

✏️ Example 2 — Proving and simplifying with the laws
Using the laws of Theorem 1.2, (a) show that $(A-B)\cup(A\cap B)=A$; (b) simplify $(A\cup B)\cap(A\cup B')$; (c) prove that $A-(B\cup C)=(A-B)\cap(A-C)$.
(a) $(A-B)\cup(A\cap B)=(A\cap B')\cup(A\cap B)=A\cap(B'\cup B)=A\cap U=A$ (difference law, distributive law read backwards, complement law, identity law). Every element of $A$ is either outside $B$ or inside it.
(b) By the first distributive law (with $A$ taken out): $(A\cup B)\cap(A\cup B')=A\cup(B\cap B')=A\cup\phi=A$.
(c) $A-(B\cup C)=A\cap(B\cup C)'=A\cap(B'\cap C')$ by De Morgan. Since $A=A\cap A$, this is $(A\cap B')\cap(A\cap C')=(A-B)\cap(A-C)$ (associative and commutative laws). $\blacksquare$
Check Test (c) with $A=\{1,2,3,4\}$, $B=\{1\}$, $C=\{2\}$: left side $\{3,4\}$; $A-B=\{2,3,4\}$, $A-C=\{1,3,4\}$, intersection $\{3,4\}$ ✓. A check with numbers cannot prove a law, but one failure would disprove it.

The next result is the most-used counting tool of this unit. It answers the question in the opening paragraph.

📐 Theorem 1.3 — Counting the elements of a union

For finite sets $A$, $B$, $C$ (subsets of a finite universal set $U$):

$$n(A\cup B)=n(A)+n(B)-n(A\cap B),$$ $$n(A-B)=n(A)-n(A\cap B),\qquad n(A')=n(U)-n(A),$$ $$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C).$$

In particular $n(A\cup B)=n(A)+n(B)$ exactly when $A$ and $B$ are disjoint.

Proof. In $n(A)+n(B)$ every element of $A\cap B$ is counted twice and every other element of $A\cup B$ once; subtracting $n(A\cap B)$ corrects this. For three sets, look at an element lying in exactly $k$ of the sets $A,B,C$. On the right-hand side it is counted $k$ times in the first bracket, subtracted once for each pair of sets it lies in, and added back if $k=3$. For $k=1$: $1$. For $k=2$: $2-1=1$. For $k=3$: $3-3+1=1$. So every element of the union is counted exactly once. $\blacksquare$ This alternate "add, subtract, add back" pattern is called the principle of inclusion–exclusion; we meet it again when counting onto functions in Section 1.2.

A classmate claims that $A-(B\cap C)=(A-B)\cap(A-C)$ for all sets — it "looks like" Example 2(c). Before using the lab, predict: is the claim true?

Choose A − (B ∩ C) on the left and (A − B) ∩ (A − C) on the right. The left diagram shades three regions of $A$ (in $A$ only, in $A\cap B$ only, in $A\cap C$ only); the right diagram shades only "in $A$ only". With the starting numbers the readouts are $n(\text{left})=9$ and $n(\text{right})=6$, and the lab reports that the two sides differ on two regions. The correct law is $A-(B\cap C)=(A-B)\cup(A-C)$ — De Morgan again: complementing $B\cap C$ turns $\cap$ into $\cup$. Choose that right side and the shadings agree on all eight regions.
Interactive 1 — Venn Lab: Is it a Law?

Three circles $A$, $B$, $C$ split the universal set into eight regions. Choose a set expression for each side: the left diagram shades the first, the right diagram the second. Two expressions are equal for all sets exactly when they shade the same regions. The numbers are how many elements each region holds — press 🎲 for new ones and watch $n(\cdot)$ follow Theorem 1.3. Press Play to tour famous laws and famous non-laws.

$n(\text{left})$—
$n(\text{right})$—
regions where they differ—
✏️ Example 3 — The three-games survey
Of the 60 students in the opening paragraph, 32 play cricket ($C$), 28 football ($F$) and 25 hockey ($H$); 12 play cricket and football, 10 cricket and hockey, 9 football and hockey, and 4 play all three. How many students play (a) at least one of the games, (b) none, (c) exactly one, (d) exactly two?
Find (c), the number who play exactly one game:
(a) Theorem 1.3: $n(C\cup F\cup H)=32+28+25-12-10-9+4=58$.
(b) $n\big((C\cup F\cup H)'\big)=60-58=2$.
Fill from the centre All three: $4$. Exactly $C$ and $F$: $12-4=8$; exactly $C$ and $H$: $10-4=6$; exactly $F$ and $H$: $9-4=5$. Only $C$: $32-8-6-4=14$; only $F$: $28-8-5-4=11$; only $H$: $25-6-5-4=10$.
(c), (d) Exactly one: $14+11+10=35$. Exactly two: $8+6+5=19$.
Check $35+19+4=58$ ✓, the answer to (a). ⏱ A quick formula: exactly two $=\sum n(X\cap Y)-3\,n(C\cap F\cap H)=31-12=19$.

$n(U)=50$, $n(A)=30$, $n(B)=25$ and $n(A'\cap B')=5$. Then $n(A\cap B)$ is

Ordered Pairs, Cartesian Products and Relations

In a set the order of elements does not matter. To record a connection from one object to another — "Asha is the sister of Ravi", "$3$ is less than $5$" — we need pairs in which order does matter.

📘 Definition 1.6 — Ordered pair and Cartesian product

An ordered pair $(a,b)$ has a first entry $a$ and a second entry $b$; two ordered pairs are equal, $(a,b)=(c,d)$, if and only if $a=c$ and $b=d$. The Cartesian product of sets $A$ and $B$ is the set of all ordered pairs with first entry from $A$ and second from $B$:

$$A\times B=\{(a,b): a\in A,\ b\in B\}.$$

Similarly $A\times B\times C=\{(a,b,c): a\in A,\ b\in B,\ c\in C\}$. The plane of coordinate geometry is $\mathbb{R}\times\mathbb{R}=\mathbb{R}^2$.

📘 Definition 1.7 — Relation, domain, range and inverse

A relation $R$ from a set $A$ to a set $B$ is any subset of $A\times B$. If $(a,b)\in R$ we say "$a$ is related to $b$" and write $a\,R\,b$. The domain of $R$ is the set of first entries of its pairs, the range is the set of second entries, and $B$ is called the codomain. A relation from $A$ to $A$ is called a relation on $A$. The inverse relation is $R^{-1}=\{(b,a):(a,b)\in R\}$, a relation from $B$ to $A$.

📐 Theorem 1.4 — Counting pairs and relations

If $n(A)=m$ and $n(B)=n$, then

$$n(A\times B)=mn\qquad\text{and the number of relations from } A \text{ to } B \text{ is } 2^{mn}.$$

The product distributes over union and intersection: $A\times(B\cup C)=(A\times B)\cup(A\times C)$, $\ A\times(B\cap C)=(A\times B)\cap(A\times C)$, and $(A\times B)\cap(C\times D)=(A\cap C)\times(B\cap D)$.

Proof. Each of the $m$ choices of first entry combines with each of the $n$ choices of second entry, giving $mn$ pairs. A relation is a subset of $A\times B$, so by Theorem 1.1(4) there are $2^{mn}$ of them — including the empty relation $\phi$ and the whole of $A\times B$. For the intersection law: $(x,y)\in(A\times B)\cap(C\times D)$ $\iff$ $x\in A$, $y\in B$, $x\in C$ and $y\in D$ $\iff$ $x\in A\cap C$ and $y\in B\cap D$. $\blacksquare$ Note that $A\times B\ne B\times A$ in general: $(1,a)$ is not the same pair as $(a,1)$.

✏️ Example 4 — Products and relations
(a) Let $A=\{1,2,3\}$ and $B=\{p,q\}$. Write $A\times B$, find the number of relations from $A$ to $B$, and find how many of them contain the pair $(1,p)$. (b) On $A=\{1,2,3,4,5,6\}$ let $R=\{(a,b): b=a+3\}$. Write $R$ in roster form, find its domain and range, and write $R^{-1}$. (c) $A\times B$ has $6$ elements, three of which are $(x,1)$, $(y,2)$ and $(z,1)$, where $x$, $y$, $z$ are distinct. Find $A$, $B$ and the other three elements.
(a) $A\times B=\{(1,p),(1,q),(2,p),(2,q),(3,p),(3,q)\}$, $6$ pairs, so there are $2^6=64$ relations. Those containing $(1,p)$: that pair is forced in, the other $5$ pairs are free: $2^5=32$.
(b) $R=\{(1,4),(2,5),(3,6)\}$ (for $a\ge4$, $a+3\gt6$ is not in $A$). Domain $\{1,2,3\}$, range $\{4,5,6\}$, codomain $A$. $R^{-1}=\{(4,1),(5,2),(6,3)\}=\{(a,b): b=a-3\}$.
(c) First entries $x,y,z$ lie in $A$ and second entries $1,2$ lie in $B$, so $n(A)\ge3$ and $n(B)\ge2$. Since $n(A)\,n(B)=6$, $A=\{x,y,z\}$ and $B=\{1,2\}$. The remaining pairs are $(x,2)$, $(y,1)$, $(z,2)$.
Check (a) $64=2^{3\times2}$, and exactly half of all relations contain any given pair: $32$ ✓.

If $n(A)=3$ and $n(B)=4$, the number of non-empty relations from $A$ to $B$ is

Types of Relations and Equivalence Relations

From now on $R$ is a relation on a single set $A$. A relation on a small set can be drawn in two useful ways: as an arrow diagram (an arrow from $a$ to $b$ for each pair $(a,b)$, a loop for $(a,a)$) and as a relation matrix (a grid with a filled cell in row $a$, column $b$ when $(a,b)\in R$). Each property below has a picture in both.

📘 Definition 1.8 — Types of relations on a set $A$
  • The empty relation $\phi$ relates nothing; the universal relation $A\times A$ relates everything; the identity relation is $I_A=\{(a,a): a\in A\}$.
  • $R$ is reflexive if $(a,a)\in R$ for every $a\in A$ — a loop at every point; the whole diagonal of the matrix filled.
  • $R$ is symmetric if $(a,b)\in R\Rightarrow(b,a)\in R$ — every arrow has a return arrow; the matrix is symmetric about its diagonal.
  • $R$ is transitive if $(a,b)\in R$ and $(b,c)\in R\Rightarrow(a,c)\in R$ — every two-step path has a one-step shortcut.
  • $R$ is antisymmetric if $(a,b)\in R$ and $(b,a)\in R\Rightarrow a=b$ — no two different points have arrows both ways.

To show a property holds you must argue for all elements; to show it fails one counterexample is enough. Watch the quantifiers: "reflexive" demands a loop at every element of $A$, while "symmetric" and "transitive" are conditional — they make demands only when certain pairs are present. So the empty relation on a non-empty set is symmetric and transitive (there is nothing to check) but not reflexive.

📘 Definition 1.9 — Equivalence relation and equivalence class

A relation on $A$ that is reflexive, symmetric and transitive is an equivalence relation. For $a\in A$, the equivalence class of $a$ is the set of all elements related to $a$:

$$[a]=\{x\in A:\ x\,R\,a\}.$$

"Has the same remainder on division by $3$" on $\mathbb{Z}$, "is parallel to" on the lines of a plane (taking each line parallel to itself) and "has the same birthday as" on the people in a room are all equivalence relations: each says that two objects are the same in one chosen respect. Such a relation chops the set into groups.

📐 Theorem 1.5 — Equivalence classes form a partition

Let $R$ be an equivalence relation on a non-empty set $A$. Then

  1. $a\in[a]$ for every $a$, so every element lies in some class;
  2. $a\,R\,b$ if and only if $[a]=[b]$;
  3. any two classes are either equal or disjoint.

So the distinct classes split $A$ into non-empty, non-overlapping pieces whose union is $A$ (a partition of $A$). Conversely, every partition of $A$ comes from exactly one equivalence relation: "is in the same piece as".

Proof. (1) is reflexivity. (2) Suppose $a\,R\,b$. If $x\in[a]$ then $x\,R\,a$ and $a\,R\,b$, so $x\,R\,b$ by transitivity: $[a]\subseteq[b]$. By symmetry $b\,R\,a$, and the same argument gives $[b]\subseteq[a]$; so $[a]=[b]$. Conversely if $[a]=[b]$ then $a\in[a]=[b]$, i.e. $a\,R\,b$. (3) If $[a]$ and $[b]$ share an element $x$, then $x\,R\,a$ and $x\,R\,b$; by symmetry and transitivity $a\,R\,b$, so $[a]=[b]$ by (2). $\blacksquare$ A consequence used constantly in JEE Main: counting equivalence relations on a finite set is the same as counting its partitions. On $\{1,2,3\}$ the partitions are $\{1,2,3\}$; $\{1,2\},\{3\}$; $\{1,3\},\{2\}$; $\{2,3\},\{1\}$; $\{1\},\{2\},\{3\}$ — so there are exactly $5$ equivalence relations.

📐 Theorem 1.6 — Counting relations on an $n$-element set

On a set with $n$ elements there are

$$2^{n^2}\ \text{relations},\quad 2^{n^2-n}\ \text{reflexive},\quad 2^{n(n+1)/2}\ \text{symmetric},\quad 2^{n(n-1)/2}\ \text{reflexive and symmetric},$$

and $2^n\cdot3^{n(n-1)/2}$ antisymmetric relations.

Proof. Think of the $n\times n$ relation matrix: $n$ diagonal cells and $n^2-n$ off-diagonal cells, which pair up into $\tfrac{n(n-1)}{2}$ mirror pairs $\{(a,b),(b,a)\}$. Reflexive: the diagonal is forced full; the $n^2-n$ other cells are free. Symmetric: each diagonal cell is free ($n$ choices of in/out) and each mirror pair is either both in or both out ($\tfrac{n(n-1)}2$ choices): $2^{n+n(n-1)/2}=2^{n(n+1)/2}$. Reflexive and symmetric: diagonal forced, mirror pairs free: $2^{n(n-1)/2}$. Antisymmetric: diagonal cells free ($2$ ways each), and each mirror pair has $3$ allowed states — neither, only $(a,b)$, only $(b,a)$. $\blacksquare$ There is no simple formula for the number of transitive relations; questions on transitivity are settled by checking pairs.

✏️ Example 5 — Testing the three properties
Decide which of the properties reflexive, symmetric, transitive hold. (a) On $\mathbb{Z}$: $a\,R\,b$ if $a-b$ is divisible by $3$; also describe the equivalence classes. (b) On $\mathbb{R}$: $a\,S\,b$ if $a\le b^2$. (c) On $\mathbb{N}$: $a\,T\,b$ if $a$ divides $b$.
(a) Reflexive: $a-a=0=3\cdot0$. Symmetric: if $a-b=3k$ then $b-a=3(-k)$. Transitive: if $a-b=3k$ and $b-c=3l$ then $a-c=3(k+l)$. So $R$ is an equivalence relation. Its classes are $[0]=\{\dots,-3,0,3,6,\dots\}$, $[1]=\{\dots,-2,1,4,\dots\}$, $[2]=\{\dots,-1,2,5,\dots\}$ — the integers sorted by remainder; three classes that partition $\mathbb{Z}$.
(b) Not reflexive: $\tfrac12\le\left(\tfrac12\right)^2=\tfrac14$ is false. Not symmetric: $1\le2^2$ but $2\le1^2$ is false. Not transitive: $3\le2^2$ and $2\le(1.5)^2=2.25$, but $3\le(1.5)^2$ is false. So $S$ has none of the three properties.
(c) Reflexive ($a=1\cdot a$) and transitive (if $b=ka$ and $c=lb$ then $c=(kl)a$), but not symmetric ($2$ divides $4$, $4$ does not divide $2$). It is antisymmetric: if $a\mid b$ and $b\mid a$ in $\mathbb{N}$ then $a=b$.
Check In (b), all three counterexamples use simple numbers and each takes one line — that is what a JEE answer needs. For a "holds" claim a proof for all elements is needed, as in (a).

On $A=\{1,2,3,4,5\}$ start from $R=\{(1,2),(2,3),(4,5)\}$. What is the number of ordered pairs in the smallest equivalence relation on $A$ that contains $R$?

Choose the preset chain with $n=5$ and press Play. The lab adds $5$ reflexive loops (green), then $3$ return arrows $(2,1),(3,2),(5,4)$ (blue), then $2$ shortcuts $(1,3),(3,1)$ (red) — $10$ added pairs — and stops at $13$ pairs with classes $\{1,2,3\}$ and $\{4,5\}$. A class with $k$ elements contributes $k^2$ pairs (every element related to every element of its class), so $3^2+2^2=13$. $10$ is the number of pairs added, and $25$ would relate everything to everything.
Interactive 2 — Relation Lab: Close it to an Equivalence

The matrix (left) has a filled cell in row $a$, column $b$ when $(a,b)\in R$; the arrow diagram (right) shows the same relation. Click cells to build your own relation, or choose a preset. The readouts test the three properties and name a pair that breaks each one. Press Play and the lab turns $R$ into the smallest equivalence relation containing it, one pair at a time: missing loops (green), missing return arrows (blue), then missing shortcuts (red), until the classes appear.

pairs in $R$—
reflexive?—
symmetric?—
transitive?—
✏️ Example 6 — Hard example: the smallest equivalence relation, and counting
(a) Let $A=\{1,2,3,4\}$ and $R=\{(1,2),(2,3)\}$. Find the minimum number of ordered pairs that must be added to $R$ to make it an equivalence relation on $A$, and the resulting classes. (b) How many equivalence relations on $\{1,2,3\}$ contain the pair $(1,2)$? (c) How many relations on $\{1,2,3,4\}$ are reflexive and symmetric?
Find the number of pairs to be added in (a):
Reflexive Add $(1,1),(2,2),(3,3),(4,4)$: $4$ pairs. ($4$ must be included even though it appears in no pair of $R$.)
Symmetric Add $(2,1),(3,2)$: $2$ pairs.
Transitive $(1,2),(2,3)$ force $(1,3)$, and $(3,2),(2,1)$ force $(3,1)$: $2$ pairs. Now $1,2,3$ are all related to one another and the relation is an equivalence. Total added: $4+2+2=8$; the relation has $10$ pairs and classes $\{1,2,3\}$, $\{4\}$.
⏱ Shortcut The classes must be $\{1,2,3\}$ and $\{4\}$ (anything linked by a chain of pairs lands in one class). Pairs $=3^2+1^2=10$; added $=10-2=8$.
(b) Equivalence relations correspond to partitions (Theorem 1.5). Partitions of $\{1,2,3\}$ with $1$ and $2$ in the same piece: $\{1,2,3\}$ and $\{1,2\},\{3\}$. Answer: $2$.
(c) Theorem 1.6 with $n=4$: $2^{n(n-1)/2}=2^6=64$.
⚠️ JEE Main traps

1. $\in$ versus $\subseteq$, and $\phi$ versus $\{\phi\}$. $a\in A$ is about an element; $\{a\}\subseteq A$ is about a set. $\phi$ has no elements, while $\{\phi\}$ has one, so $n(P(\phi))=1$ and $n(P(P(\phi)))=2$.

2. "At least one", "exactly one", "none". Theorem 1.3 gives "at least one" (the union). "Exactly one" needs the Venn diagram filled from the centre outwards; "none" is $n(U)$ minus the union. Read which one the question asks for.

3. Reflexive means every element. $\{(1,1),(2,2)\}$ on $\{1,2,3\}$ is not reflexive. An element that appears in no pair still needs its loop.

4. Transitivity is easy to get wrong both ways. $\{(1,2)\}$ is transitive (no two-step path exists to check), but $\{(1,2),(2,1)\}$ is not: the path $1\to2\to1$ demands $(1,1)$. And "symmetric + transitive $\Rightarrow$ reflexive" is false: the empty relation is a counterexample.

5. Counting slips. Relations from an $m$-set to an $n$-set: $2^{mn}$, not $mn$ (that is $n(A\times B)$) and not $n^m$ (that is functions). On an $n$-set: reflexive $2^{n^2-n}$, symmetric $2^{n(n+1)/2}$ — check with $n=1$ ($2^0=1$ and $2^1=2$).

On $A=\{1,2,3\}$, the relation $R=\{(1,1),(2,2),(3,3),$ $(1,2),(2,1),(2,3),(3,2)\}$ is

Exercises

$\mathbb{N}=\{1,2,3,\dots\}$ throughout. Give reasons: for a property that holds, an argument for all elements; for one that fails, a counterexample.

I
Sets, subsets and power sets.
  • 1 Write $\{x\in\mathbb{Z}: -2\le x\lt3\}$ in roster form.
  • 2 Write $\{x\in\mathbb{N}: x^2-3x-10=0\}$ in roster form.
  • 3 Write $\{3,6,9,12,15\}$ in set-builder form.
  • 4 Which of these sets are empty? (a) $\{x\in\mathbb{N}: 2\lt x\lt3\}$ (b) $\{x\in\mathbb{R}: x^2=-4\}$ (c) $\{0\}$ (d) $\{x\in\mathbb{Z}: x^2=4\}$.
  • 5 How many subsets and how many proper subsets does $\{a,b,c,d,e\}$ have?
  • 6 If $n\big(P(A)\big)=256$, find $n(A)$.
  • 7 How many subsets of $\{1,2,\dots,9\}$ contain at least one even number?
  • 8 A set $A$ has $3$ more elements than a set $B$, and $A$ has $56$ more subsets than $B$. Find $n(A)$.
  • 9 True or false: (a) $\phi\in\{\phi\}$ (b) $\phi\subseteq\{\phi\}$ (c) $\{1\}\in\{1,2\}$ (d) $\{1,2\}\subseteq\{1,\{1,2\}\}$.
1 $\{-2,-1,0,1,2\}$ ($3$ is excluded by the strict inequality).
2 $(x-5)(x+2)=0$ gives $x=5$ or $x=-2$; only $5\in\mathbb{N}$: the set is $\{5\}$.
3 $\{3n: n\in\mathbb{N},\ n\le5\}$.
4 (a) and (b) are empty. $\{0\}$ has one element; (d) is $\{-2,2\}$.
5 $2^5=32$ subsets, $31$ proper subsets.
6 $2^n=256=2^8$: $n(A)=8$.
7 All subsets minus those with no even number (subsets of $\{1,3,5,7,9\}$): $2^9-2^5=512-32=480$.
8 With $n(A)=m$: $2^m-2^{m-3}=2^{m-3}(8-1)=56$, so $2^{m-3}=8$ and $m=6$ (and $n(B)=3$).
9 (a) True — $\phi$ is the one element of $\{\phi\}$. (b) True — $\phi$ is a subset of every set. (c) False — the elements are $1$ and $2$; $\{1\}\subseteq\{1,2\}$ would be true. (d) False — $2\notin\{1,\{1,2\}\}$ (but $\{1,2\}\in\{1,\{1,2\}\}$).
II
Operations, laws and counting. In parts 1–3, $U=\{1,2,\dots,10\}$, $A=\{1,2,3,4,5\}$, $B=\{2,4,6,8\}$, $C=\{3,4,5,6\}$.
  • 1 Find $A\cup B$, $A\cap C$, $A-B$ and $B'$.
  • 2 Verify De Morgan's law $(A\cup B)'=A'\cap B'$ for these sets.
  • 3 Find $A\,\Delta\,C$.
  • 4 Simplify $(A\cap B)\cup(A\cap B')$ for any sets $A$, $B$.
  • 5 Simplify $A\cap(A'\cup B)$.
  • 6 Prove that $A-(A-B)=A\cap B$.
  • 7 If $n(A)=40$, $n(B)=26$ and $n(A\cup B)=54$, find $n(A\cap B)$ and $n(A-B)$.
  • 8 In a group of $80$ people, $50$ speak Hindi and $45$ speak English, and everyone speaks at least one of the two. How many speak both? How many speak English only?
  • 9 Of $200$ students, $120$ take Mathematics, $90$ Physics and $70$ Chemistry; $40$ take Mathematics and Physics, $30$ Physics and Chemistry, $50$ Mathematics and Chemistry, and $20$ take none of the three. How many take all three, and how many take exactly one?
1 $A\cup B=\{1,2,3,4,5,6,8\}$, $A\cap C=\{3,4,5\}$, $A-B=\{1,3,5\}$, $B'=\{1,3,5,7,9,10\}$.
2 $(A\cup B)'=\{7,9,10\}$. $A'=\{6,7,8,9,10\}$, $B'=\{1,3,5,7,9,10\}$, so $A'\cap B'=\{7,9,10\}$ ✓.
3 $A-C=\{1,2\}$, $C-A=\{6\}$: $A\,\Delta\,C=\{1,2,6\}$.
4 $A\cap(B\cup B')=A\cap U=A$.
5 $(A\cap A')\cup(A\cap B)=\phi\cup(A\cap B)=A\cap B$.
6 $A-(A-B)=A\cap(A\cap B')'=A\cap(A'\cup B)=A\cap B$ (De Morgan, then part 5).
7 $n(A\cap B)=40+26-54=12$; $n(A-B)=40-12=28$.
8 $80=50+45-n(H\cap E)$, so $15$ speak both; English only $=45-15=30$.
9 $n(M\cup P\cup C)=200-20=180=120+90+70-40-30-50+x$, so $x=20$ take all three. Only $M$: $120-40-50+20=50$; only $P$: $90-40-30+20=40$; only $C$: $70-30-50+20=10$; exactly one: $100$. (Check: exactly two $=20+10+30=60$, and $100+60+20=180$ ✓.)
III
Cartesian products and relations.
  • 1 For $A=\{1,2\}$ and $B=\{x,y,z\}$, write $A\times B$. How many elements has $B\times A$? Is $A\times B=B\times A$?
  • 2 If $(2a-1,\ b+3)=(5,\ 1)$, find $a$ and $b$.
  • 3 $A\times A$ has $9$ elements, two of which are $(-1,0)$ and $(0,1)$. Find $A$.
  • 4 Prove that $A\times(B\cap C)=(A\times B)\cap(A\times C)$.
  • 5 If $n(A)=4$ and $n(B)=3$, find the number of relations from $A$ to $B$, and the number that contain a given pair $(a_1,b_1)$.
  • 6 On $A=\{1,2,3,4,5,6\}$ let $R=\{(a,b): b=2a\}$. Write $R$ and $R^{-1}$ in roster form and give the domain and range of $R$.
  • 7 $R=\{(x,y): x,y\in\mathbb{Z},\ x^2+y^2=25\}$. How many ordered pairs does $R$ contain? Find its domain.
  • 8 For $A=\{1,2,3\}$, $B=\{3,4\}$, $C=\{4,5,6\}$, find $n\big((A\times B)\cap(A\times C)\big)$.
1 $A\times B=\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}$. $n(B\times A)=6$ too, but $A\times B\ne B\times A$: $(1,x)\in A\times B$ while $(1,x)\notin B\times A$.
2 $2a-1=5$ and $b+3=1$: $a=3$, $b=-2$.
3 $n(A)^2=9$ gives $n(A)=3$; the entries $-1,0,1$ all lie in $A$, so $A=\{-1,0,1\}$.
4 $(x,y)\in A\times(B\cap C)\iff x\in A$ and $y\in B$ and $y\in C\iff(x,y)\in A\times B$ and $(x,y)\in A\times C$. $\blacksquare$
5 $n(A\times B)=12$: $2^{12}=4096$ relations; with $(a_1,b_1)$ forced in, $2^{11}=2048$.
6 $R=\{(1,2),(2,4),(3,6)\}$, $R^{-1}=\{(2,1),(4,2),(6,3)\}$; domain $\{1,2,3\}$, range $\{2,4,6\}$.
7 The integer points on the circle $x^2+y^2=25$: $(\pm5,0)$, $(0,\pm5)$, $(\pm3,\pm4)$, $(\pm4,\pm3)$ — $4+4+4=12$ pairs. Domain $\{-5,-4,-3,0,3,4,5\}$.
8 By Theorem 1.4 it is $A\times(B\cap C)=A\times\{4\}$, with $3$ elements.
IV
Types of relations and equivalence relations.
  • 1 On $\{1,2,3\}$, is $R_1=\{(1,1),(2,2),(3,3),(1,2)\}$ reflexive, symmetric, transitive?
  • 2 On $\{1,2,3\}$, test $R_2=\{(1,2),(2,1)\}$.
  • 3 On $\{1,2,3\}$, test $R_3=\{(1,1)\}$. What does it show about "symmetric and transitive"?
  • 4 On $\mathbb{Z}$, $a\,R\,b$ if $a-b$ is even. Show that $R$ is an equivalence relation and find its classes.
  • 5 On the set of lines in a plane: (a) $l\,R\,m$ if $l$ is parallel to $m$ (each line counted as parallel to itself); (b) $l\,S\,m$ if $l$ is perpendicular to $m$. Test both, and describe the class of the line $y=2x$ under $R$.
  • 6 On $\mathbb{R}$, $a\,R\,b$ if $|a-b|\le1$. Test the three properties.
  • 7 On a set with $4$ elements, how many relations are reflexive? Symmetric? Both reflexive and symmetric?
  • 8 An equivalence relation on $\{1,2,3,4,5,6\}$ has classes $\{1,4\}$, $\{2,5\}$, $\{3,6\}$. How many ordered pairs does it contain? Describe it by a rule.
  • 9 How many equivalence relations are there on $\{a,b,c\}$?
  • 10 Prove: if $R$ on $A$ is symmetric and transitive, and every element of $A$ is related to at least one element, then $R$ is reflexive.
1 Reflexive: yes. Symmetric: no ($(1,2)$ but not $(2,1)$). Transitive: yes — the only paths are $1\to1\to2$ and $1\to2\to2$, whose shortcut $(1,2)$ is present. (It is also antisymmetric.)
2 Symmetric only: not reflexive (no loops), not transitive ($1\to2\to1$ needs $(1,1)$).
3 Symmetric and transitive, but not reflexive ($(2,2)$ missing). So symmetric + transitive does not imply reflexive — unless every element is related to something (part 10).
4 $a-a=0$ is even; if $a-b$ is even so is $b-a$; if $a-b$ and $b-c$ are even, so is their sum $a-c$. Two classes: the even integers and the odd integers.
5 (a) Equivalence relation; the class of $y=2x$ is the family of all lines $y=2x+c$, $c\in\mathbb{R}$ (all lines of slope $2$). (b) Symmetric only: a line is not perpendicular to itself, and $l\perp m$, $m\perp n$ give $l\parallel n$, not $l\perp n$.
6 Reflexive ($|a-a|=0$) and symmetric ($|a-b|=|b-a|$), not transitive: $|0-1|\le1$, $|1-2|\le1$ but $|0-2|=2$.
7 $n=4$: reflexive $2^{12}=4096$, symmetric $2^{10}=1024$, both $2^6=64$.
8 Three classes of size $2$: $3\times2^2=12$ pairs. Rule: $a\,R\,b$ if $a-b$ is divisible by $3$.
9 One per partition of $\{a,b,c\}$: $\{a,b,c\}$; three ways to split off one element; all singletons — $1+3+1=5$.
10 Take $a\in A$; by hypothesis $a\,R\,b$ for some $b$. By symmetry $b\,R\,a$, and by transitivity ($a\,R\,b$, $b\,R\,a$) we get $a\,R\,a$. $\blacksquare$
🎯 Exam corner JEE Main · MCQJEE Main · Numerical

E1. JEE Main · MCQ Let $A=\{x\in\mathbb{Z}: |x-2|\lt3\}$ and $B=\{x\in\mathbb{N}: x^2-5x\le0\}$. Then $n\big((A\cup B)\times(A\cap B)\big)$ is (A) $20$ (B) $24$ (C) $30$ (D) $25$

Sets $|x-2|\lt3\iff-1\lt x\lt5$: $A=\{0,1,2,3,4\}$. $x(x-5)\le0\iff0\le x\le5$, and $x\in\mathbb{N}$: $B=\{1,2,3,4,5\}$.
Count $A\cup B=\{0,1,\dots,5\}$ has $6$ elements, $A\cap B=\{1,2,3,4\}$ has $4$; by Theorem 1.4 the product has $6\times4$ elements.
Answer (B) $24$.
⏱ Shortcut (D) is $n(A)\,n(B)$; (A) forgets that $0\in\mathbb{Z}$ belongs to $A$. Write both sets out — it takes ten seconds.

E2. JEE Main · Numerical In a survey of $1000$ adults, $840$ use UPI, $750$ use a debit card and $610$ use cash every week. Find the least possible number of adults who use all three. Give the answer to the nearest integer.

Complements Non-users: $n(A')=160$, $n(B')=250$, $n(C')=390$. By De Morgan, the adults who miss at least one method form $A'\cup B'\cup C'=(A\cap B\cap C)'$.
Bound $n(A'\cup B'\cup C')\le160+250+390=800$, so $n(A\cap B\cap C)\ge1000-800=200$.
Attained If the three groups of non-users are disjoint (possible, since $800\le1000$), exactly $200$ use all three.
Answer $200$.
⏱ Shortcut Least $n(A\cap B\cap C)=n(A)+n(B)+n(C)-2\,n(U)$ when this is positive: $2200-2000=200$.

E3. JEE Main · MCQ The relation $R=\{(a,b)\in\mathbb{R}\times\mathbb{R}: ab+4\gt0\}$ on $\mathbb{R}$ is (A) an equivalence relation (B) reflexive and transitive but not symmetric (C) reflexive and symmetric but not transitive (D) symmetric and transitive but not reflexive

Reflexive $a\cdot a+4=a^2+4\gt0$ for every real $a$ ✓.
Symmetric $ab+4=ba+4$ ✓.
Transitive? $(3,-1)$: $-3+4=1\gt0$ ✓; $(-1,-3)$: $3+4\gt0$ ✓; but $(3,-3)$: $-9+4\lt0$ ✗. Not transitive.
Answer (C).
⏱ Shortcut Look for a "bridge" element: a small negative $b$ relates to a large positive $a$ and to a large negative $c$, while $a$ and $c$ are not related.

E4. JEE Main · Numerical Let $A=\{1,2,3,4,5,6\}$ and $R=\{(1,3),(3,5),(2,4)\}$. Find the number of ordered pairs in the smallest equivalence relation on $A$ that contains $R$. Give the answer to the nearest integer.

Classes $1\sim3\sim5$ are linked, $2\sim4$ are linked, and $6$ is linked to nothing: classes $\{1,3,5\}$, $\{2,4\}$, $\{6\}$ (Theorem 1.5).
Pairs Each class of size $k$ gives $k^2$ pairs: $9+4+1$.
Answer $14$.
⏱ Shortcut Forgetting $(6,6)$ gives $13$ — the most common wrong answer. Reflexivity covers every element of $A$.

E5. JEE Main · MCQ The number of relations on $\{a,b,c\}$ that are symmetric but not reflexive is (A) $56$ (B) $64$ (C) $8$ (D) $48$

Symmetric $2^{n(n+1)/2}=2^6=64$ (Theorem 1.6, $n=3$).
Remove the reflexive ones Reflexive and symmetric: $2^{n(n-1)/2}=2^3=8$.
Answer (A) $64-8=56$.
⏱ Shortcut "Not reflexive" means "at least one loop missing": the diagonal has $2^3-1=7$ allowed states and the $3$ mirror pairs $2^3$: $7\times8=56$.

E6. JEE Main · Numerical Find the number of equivalence relations on $\{1,2,3,4\}$ that contain the pair $(1,2)$. Give the answer to the nearest integer.

Partitions An equivalence relation containing $(1,2)$ is a partition with $1$ and $2$ in the same piece. Glue $1$ and $2$ into one object $X$ and partition $\{X,3,4\}$.
Count Partitions of a $3$-element set: one piece ($1$), a pair and a single ($3$), three singles ($1$): $5$. (They are $\{1,2,3,4\}$; $\{1,2,3\},\{4\}$; $\{1,2,4\},\{3\}$; $\{1,2\},\{3,4\}$; $\{1,2\},\{3\},\{4\}$.)
Answer $5$.
🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. Hospitals, banks and exam boards must decide when two records describe the same person. Is "these two records are similar enough" an equivalence relation — and what goes wrong when it is not?

Why it matters. Record linkage (de-duplication) is used to merge patient files, detect duplicate exam registrations and link census data. Matching software compares names with a tolerance for typing errors. If the matching rule were an equivalence relation, its classes would be the people. Real rules are reflexive and symmetric but often not transitive, so long chains of small differences can join records of different people.

What to do.

  1. Write a list of about 12 surnames with realistic typing variants, for example Sharma, Sarma, Sharman, Karma, Verma, Varma, Rao, Rai, Ray, Roy, Raj, Ram.
  2. Define $x\,R\,y$ if $y$ can be obtained from $x$ by changing, inserting or deleting at most one letter. Build the relation matrix (a spreadsheet grid of 0s and 1s).
  3. Check reflexivity and symmetry. Then hunt for transitivity failures: triples with $x\,R\,y$, $y\,R\,z$ but not $x\,R\,z$. List every one you find.
  4. Form the smallest equivalence relation containing $R$ (follow chains, as in Interactive 2). Which classes now contain names that obviously belong to different families?

Tools: Paper or a spreadsheet; optionally a few lines of Python to compute the matrix and the classes.

Hand in: Your matrix, the list of transitivity failures, the classes of the closure, and three sentences on whether you would trust the closure to merge records automatically.

Going further. Change the tolerance to "at most two letters". Do the classes grow or shrink? Real systems add a second test (date of birth, address) before merging. Why does using two independent tests reduce false merges?

Instructor note: "within distance $d$" relations are tolerance relations — always reflexive and symmetric, generally not transitive. With the list above, chains such as Rao–Rai–Ram–Raj and Sharma–Sarma–Karma appear quickly, and the closure merges names that differ in two or more letters. This is exactly the "single-linkage chaining" problem of clustering, and a good place to discuss why Theorem 1.5 needs transitivity.

🧪 Self-check quiz

0/5 correct

Q1. How many subsets of $A=\{1,2,3\}$ contain the element $1$?

Q2. For subsets $A$, $B$ of $U$, the set $(A\cup B)'$ is equal to

Q3. If $n(A)=5$ and $n(B)=3$, the number of relations from $A$ to $B$ is

Q4. On $\{1,2,3\}$, the relation $\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ is

Q5. On $A=\{1,2,\dots,12\}$, $a\,R\,b$ if $a-b$ is divisible by $4$. The equivalence class $[3]$ is