Chapter 2 · Relations and Functions

2.2 Relations

A relation from $A$ to $B$ is simply a subset of $A\times B$ — the pairs that are linked. Its domain, range and codomain say where the links start and end, and there are $2^{pq}$ relations in all.

A school's records link students to the clubs they have joined. Asha is in Music and Robotics, Bilal is in Debate, and Chen has not joined any club yet. Out of all the possible (student, club) pairs — the Cartesian product of the set of students and the set of clubs — only some are actually linked. That chosen collection of pairs is the relation "is a member of".

Relations are everywhere: "is the mother of" in a family, "is a factor of" among numbers, "has a direct flight to" among cities, "is less than" among real numbers. In each case we start with a product $A\times B$ and select the pairs we care about. This section turns that idea into a definition, introduces the vocabulary — domain, range, codomain — and shows three ways to describe a relation. It also answers a counting question: how many different relations can there be between two finite sets?

Relations as Subsets of a Product

📘 Definition 2.4 — Relation

Let $A$ and $B$ be non-empty sets. A relation $R$ from $A$ to $B$ is any subset of $A\times B$: $$R\subset A\times B.$$ If $(a,b)\in R$ we say "$a$ is related to $b$", and sometimes write $a\,R\,b$; then $b$ is called an image of $a$, and $a$ a pre-image of $b$. A relation from $A$ to $A$ itself is called a relation on $A$.

The pairs of a relation are usually chosen by a rule connecting the two components — "$b=a+1$", "$a$ divides $b$" — but the definition does not insist on a rule: any subset of $A\times B$ counts, even $\phi$ (the empty relation, nothing linked) and the whole of $A\times B$ (the universal relation, everything linked). A relation can be described in three ways:

roster form — list the pairs, e.g. $R=\{(1,2),(2,3),(3,4)\}$;
set-builder form — give the rule, e.g. $R=\{(a,b) : a\in A,\ b\in B,\ b=a+1\}$;
arrow diagram — draw $A$ and $B$ as two ovals and an arrow from $a$ to $b$ for every pair $(a,b)\in R$.

📘 Definition 2.5 — Domain, codomain and range

Let $R$ be a relation from $A$ to $B$.

The domain of $R$ is the set of all first components of the pairs in $R$: $\{a : (a,b)\in R \text{ for some } b\}$.
The range of $R$ is the set of all second components: $\{b : (a,b)\in R \text{ for some } a\}$.
The whole set $B$ is called the codomain of $R$.

Always: domain $\subset A$, and range $\subset$ codomain $=B$.

✏️ Example 1 — From a rule to roster form

Let $A=\{1,2,3,4,5,6\}$ and let $R$ be the relation on $A$ given by $R=\{(a,b) : a,b\in A,\ b=a+1\}$. Write $R$ in roster form, find its domain, range and codomain, and describe its arrow diagram.

💡 Show solution▶

Method Go through $a=1,2,\dots,6$ and ask which $b\in A$ satisfies the rule. For $a=6$, $b=7\notin A$, so $6$ has no image.

Roster $R=\{(1,2),(2,3),(3,4),(4,5),(5,6)\}$.

Domain, range Domain $=\{1,2,3,4,5\}$; range $=\{2,3,4,5,6\}$; codomain $=A=\{1,2,3,4,5,6\}$. Note that $6$ is not in the domain and $1$ is not in the range.

Arrows Five arrows: $1\to2$, $2\to3$, $3\to4$, $4\to5$, $5\to6$; no arrow leaves $6$ and none arrives at $1$.

✏️ Example 2 — A relation where some elements are left out

Let $A=\{1,2,3,4\}$, $B=\{5,6,8\}$ and $R=\{(x,y) : x\in A,\ y\in B,\ x+y \text{ is prime}\}$. Find $R$, its domain and its range.

💡 Show solution▶

Test all pairs $A\times B$ has $4\times3=12$ pairs. The sums are: with $x=1$: $6,7,9$; with $x=2$: $7,8,10$; with $x=3$: $8,9,11$; with $x=4$: $9,10,12$.

Keep the primes $7$ (twice) and $11$: $R=\{(1,6),(2,5),(3,8)\}$.

Answer Domain $=\{1,2,3\}$ — the element $4$ of $A$ has no image. Range $=\{5,6,8\}=B$.

✏️ Example 3 — Relations on infinite sets

(a) $R=\{(x,y) : x,y\in\mathbb{N},\ x+2y=10\}$. Write $R$ in roster form and find its domain and range.
(b) $S=\{(x,x^2) : x \text{ is a prime number less than } 10\}$. Write $S$ in roster form and find its domain and range.

💡 Show solution▶

(a) Solve for x $x=10-2y$, and we need $x\ge1$: $y=1,2,3,4$ give $x=8,6,4,2$; $y=5$ gives $x=0\notin\mathbb{N}$.

(a) Answer $R=\{(8,1),(6,2),(4,3),(2,4)\}$; domain $\{2,4,6,8\}$, range $\{1,2,3,4\}$. Although $\mathbb{N}\times\mathbb{N}$ is infinite, this relation is finite.

(b) The primes below $10$ are $2,3,5,7$, so $S=\{(2,4),(3,9),(5,25),(7,49)\}$; domain $\{2,3,5,7\}$, range $\{4,9,25,49\}$.

The grid is $A\times B$ with $A=\{1,2,3,4\}$ (rows) and $B=\{1,\dots,6\}$ (columns). A relation is any choice of cells. Press ▶ to watch rules choose their pairs, or pick "my own" and click cells to build a relation yourself. The arrow diagram, domain and range update as you go — and the last readout previews Section 2.3: is every element of $A$ sent to exactly one element of $B$?

Relation:

$R$—

domain—

range—

$n(R)$—

function from $A$ to $B$?—

⚠️ Common mistakes with relations

1. Range is not codomain. The codomain is the whole of $B$; the range is only the part of $B$ actually reached. In Example 1 the codomain contains $1$ but the range does not.

2. Domain need not be all of $A$. An element of $A$ with no arrow (like $4$ in Example 2) is simply not in the domain.

3. Direction matters. A relation from $A$ to $B$ is a subset of $A\times B$, so its pairs have the $A$-element first. $(5,2)$ cannot be in a relation from $\{1,2,3\}$ to $\{4,5,6\}$.

4. Check the sets the rule lives in. In Example 3(a), $y=5$ gives $x=0$, which is rejected because $0\notin\mathbb{N}$. Forgetting the set produces extra pairs.

How Many Relations Are There?

Choosing a relation from $A$ to $B$ means choosing a subset of $A\times B$. For each pair we make an independent yes/no decision: put it in, or leave it out.

📐 Theorem 2.3 — Number of relations

If $A$ and $B$ are finite sets with $n(A)=p$ and $n(B)=q$, then the number of relations from $A$ to $B$ is $$2^{pq}.$$ In particular, the number of relations on a set with $n$ elements is $2^{n^2}$.

Proof. By Theorem 2.1, $A\times B$ has $pq$ pairs. A relation is fixed by deciding, for each of these $pq$ pairs, whether it is in $R$ or not: $2$ choices for the first pair, $2$ for the second, and so on, giving $2\times2\times\cdots\times2=2^{pq}$ choices (the multiplication principle you saw in Section 1.2, Example 2, and will meet properly in Chapter 6). Different choices give different subsets, so these are $2^{pq}$ different relations — including the empty relation and the universal relation $A\times B$. $\blacksquare$

✏️ Example 4 — Counting relations

Let $A=\{1,2\}$ and $B=\{a,b\}$. (a) How many relations are there from $A$ to $B$? (b) How many of them have exactly one pair? (c) How many have domain equal to $A$?

💡 Show solution▶

(a) $pq=2\times2=4$ pairs, so $2^4=16$ relations.

(b) A one-pair relation is $\{(x,y)\}$ for one of the $4$ pairs of $A\times B$: $\{(1,a)\},\{(1,b)\},\{(2,a)\},\{(2,b)\}$ — four relations.

(c) Domain $=A$ means both $1$ and $2$ have at least one image. The images of $1$ form a non-empty subset of $B$: $\{a\}$, $\{b\}$ or $\{a,b\}$ — $3$ choices; likewise $3$ for $2$. Total $3\times3=9$.

Check The other $16-9=7$ relations miss $1$ or $2$: $4$ have no arrow from $1$, $4$ have none from $2$, and $1$ (the empty relation) has neither, so $4+4-1=7$ ✓.

✏️ Example 5 — Working backwards from a count

(a) There are $4096$ relations from $A$ to $B$, and $n(A)=3$. Find $n(B)$.
(b) There are $512$ relations from $A$ to $B$. List the possible pairs $\big(n(A),n(B)\big)$.

💡 Show solution▶

(a) $4096=2^{12}$, so $pq=12$ with $p=3$: $n(B)=4$.

(b) $512=2^9$, so $pq=9$. With $p,q\ge1$ whole numbers: $(1,9)$, $(3,3)$ or $(9,1)$.

Check $2^{3\cdot4}=2^{12}=4096$ ✓ and $2^{3\cdot3}=512$ ✓.

Exercises

Roster form, domain and range.

1 $A=\{1,2,3,4,5\}$, $R=\{(a,b) : a,b\in A,\ b=a+2\}$. Write $R$ in roster form and find its domain and range.
2 $R=\{(x,x^3) : x\in\{-1,0,1,2\}\}$. Write $R$ in roster form; find its domain and range.
3 $R=\{(x,y) : x,y\in\mathbb{N},\ x+y=6\}$. Write $R$ in roster form; find its domain and range.
4 $A=\{2,3,5\}$, $B=\{4,6,9,10\}$, $R=\{(a,b) : a\in A,\ b\in B,\ a \text{ divides } b\}$. Write $R$, its domain and its range.
5 $R=\{(x,y) : x,y\in\mathbb{Z},\ y=x^2,\ -2\le x\le2\}$. Write $R$, its domain and its range.
6 $A=\{1,2,3,4,5\}$, $R=\{(x,y) : x,y\in A,\ y=x-1\}$. Write $R$ and find its domain and range.
7 Write $R=\{(1,1),(2,4),(3,9),(4,16)\}$ in set-builder form.
8 Write $R=\{(1,3),(2,6),(3,9),(4,12)\}$ in set-builder form.
9 Draw the arrow diagram of the relation in part 4. Which element of $B$ receives two arrows?

💡 Show solutions▶

1 $R=\{(1,3),(2,4),(3,5)\}$; domain $\{1,2,3\}$; range $\{3,4,5\}$.

2 $R=\{(-1,-1),(0,0),(1,1),(2,8)\}$; domain $\{-1,0,1,2\}$; range $\{-1,0,1,8\}$.

3 $R=\{(1,5),(2,4),(3,3),(4,2),(5,1)\}$; domain and range both $\{1,2,3,4,5\}$.

4 $R=\{(2,4),(2,6),(2,10),(3,6),(3,9),(5,10)\}$; domain $\{2,3,5\}$; range $\{4,6,9,10\}$.

5 $R=\{(-2,4),(-1,1),(0,0),(1,1),(2,4)\}$; domain $\{-2,-1,0,1,2\}$; range $\{0,1,4\}$.

6 $R=\{(2,1),(3,2),(4,3),(5,4)\}$; domain $\{2,3,4,5\}$; range $\{1,2,3,4\}$.

7 $R=\{(x,y) : x\in\{1,2,3,4\},\ y=x^2\}$.

8 $R=\{(x,y) : x\in\{1,2,3,4\},\ y=3x\}$.

9 Arrows $2\to4$, $2\to6$, $2\to10$, $3\to6$, $3\to9$, $5\to10$. Both $6$ (from $2$ and $3$) and $10$ (from $2$ and $5$) receive two arrows.

Counting relations.

1 $n(A)=2$ and $n(B)=3$. How many relations are there from $A$ to $B$?
2 How many relations are there on the set $\{a,b\}$?
3 The number of relations from $A$ to $B$ is $4096$ and $n(B)=6$. Find $n(A)$.
4 $A=\{1,2\}$, $B=\{3,4\}$. List all relations from $A$ to $B$ with exactly three pairs.
5 How many relations are there from $\{1,2,3\}$ to $\{x\}$? List those whose domain is $\{1,2,3\}$.
6 How many relations are there on a set with $3$ elements?
7 $n(A)=2$, $n(B)=3$. How many relations from $A$ to $B$ have domain equal to $A$?

💡 Show solutions▶

1 $2^{2\cdot3}=2^6=64$.

2 $2^{2\cdot2}=16$.

3 $4096=2^{12}$, so $6\,n(A)=12$ and $n(A)=2$.

4 Leave out one of the four pairs of $A\times B$: $\{(1,4),(2,3),(2,4)\}$, $\{(1,3),(2,3),(2,4)\}$, $\{(1,3),(1,4),(2,4)\}$, $\{(1,3),(1,4),(2,3)\}$ — four relations.

5 $2^{3\cdot1}=8$. Only one has domain $\{1,2,3\}$: $\{(1,x),(2,x),(3,x)\}$.

6 $2^{3^2}=2^9=512$.

7 Each element of $A$ needs a non-empty set of images: $2^3-1=7$ choices each, so $7\times7=49$.

III

Relations given by equations.

1 $R=\{(x,y) : x,y\in\mathbb{N},\ 2x+y=12\}$. Find $R$, its domain and range.
2 $R=\{(x,y) : x,y\in\mathbb{Z},\ x^2+y^2=25\}$. Find $n(R)$, the domain and the range.
3 $R=\{(x,x+5) : x\in\{0,1,2,3,4,5\}\}$. Find its domain and range.
4 $A=\{1,2,\dots,10\}$, $R=\{(a,b) : a,b\in A,\ b=a^2\}$. Find $R$, its domain and range.
5 Is $R=\{(1,2),(2,3),(3,4)\}$ a relation from $\{1,2,3\}$ to $\{2,3,4\}$? A relation on $\{1,2,3\}$? Explain.
6 $R=\{(x,x+1) : x\in\{1,2,3\}\}$ is regarded as a relation from $A=\{1,2,3\}$ to $B=\{1,2,3,4,5\}$. State its codomain and range, and explain why they differ.

Check: plot the pairs of the relations in parts 1, 2 and 4 as points of the plane

Part:

$n(R)$—

domain—

range—

💡 Show solutions▶

1 $y=12-2x\ge1$ needs $x\le5$: $R=\{(1,10),(2,8),(3,6),(4,4),(5,2)\}$; domain $\{1,2,3,4,5\}$; range $\{2,4,6,8,10\}$.

2 Integer solutions: $(\pm5,0)$, $(0,\pm5)$, $(\pm3,\pm4)$, $(\pm4,\pm3)$, so $n(R)=2+2+4+4=12$. Domain $=$ range $=\{-5,-4,-3,0,3,4,5\}$.

3 Domain $\{0,1,2,3,4,5\}$; range $\{5,6,7,8,9,10\}$.

4 $b=a^2\le10$ needs $a\le3$: $R=\{(1,1),(2,4),(3,9)\}$; domain $\{1,2,3\}$; range $\{1,4,9\}$.

5 Yes: every pair lies in $\{1,2,3\}\times\{2,3,4\}$. Not a relation on $\{1,2,3\}$, because $(3,4)\notin\{1,2,3\}\times\{1,2,3\}$ (as $4\notin\{1,2,3\}$).

6 Codomain $B=\{1,2,3,4,5\}$; range $\{2,3,4\}$. The codomain is the set we chose to aim at; the range is the part actually reached — $1$ and $5$ are never images.

Relations in context.

1 Family. In a family, Anita is the mother of Ravi and of Meena, and Meena is the mother of Arjun. Let $F=\{\text{Anita},\text{Ravi},\text{Meena},\text{Arjun}\}$ and $R$ = "is the mother of" on $F$. Write $R$ in roster form, with its domain and range.
2 Clubs. Asha is in Music and Robotics, Bilal is in Debate, and Chen is in no club. Write the relation "is a member of" from the set of students to $\{\text{Music},\text{Robotics},\text{Debate}\}$, with its domain and range.
3 Factors. On $A=\{1,2,3,4,5,6\}$ let $R=\{(a,b) : a\ne b,\ a \text{ is a factor of } b\}$. Write $R$ in roster form; find $n(R)$, its domain and its range.
4 Timetable. In an exam week, Maths is on Monday, Physics and English are on Tuesday, and Chemistry is on Wednesday. Write the relation "is held on" from subjects to days. Does every subject have exactly one day? Does every day have exactly one subject?

💡 Show solutions▶

1 $R=\{(\text{Anita},\text{Ravi}),(\text{Anita},\text{Meena}),(\text{Meena},\text{Arjun})\}$; domain $\{\text{Anita},\text{Meena}\}$ (the mothers); range $\{\text{Ravi},\text{Meena},\text{Arjun}\}$.

2 $R=\{(\text{Asha},\text{Music}),(\text{Asha},\text{Robotics}),(\text{Bilal},\text{Debate})\}$; domain $\{\text{Asha},\text{Bilal}\}$ — Chen is not in the domain; range $\{\text{Music},\text{Robotics},\text{Debate}\}$.

3 $R=\{(1,2),(1,3),(1,4),(1,5),(1,6),(2,4),(2,6),(3,6)\}$; $n(R)=8$; domain $\{1,2,3\}$; range $\{2,3,4,5,6\}$.

4 $\{(\text{Maths},\text{Mon}),(\text{Physics},\text{Tue}),(\text{English},\text{Tue}),(\text{Chemistry},\text{Wed})\}$. Every subject has exactly one day (this relation will be called a function in Section 2.3); Tuesday has two subjects, so the reverse is not true.

🎯 Exam corner Board · 1 markBoard · 2 marksBoard · 3 marksJEE MainJEE Advanced

How this is examined: Board papers give a relation by a rule and ask for its roster form, domain and range (2–3 marks, sometimes with an arrow diagram), or ask for a range or a count of relations as a 1-mark question. JEE uses $2^{pq}$ in counting questions and relations defined by equations on $\mathbb{Z}$.

E1. Board · 1 mark Let $R=\{(1,2),(2,3),(1,3)\}$ be a relation on $A=\{1,2,3\}$. The range of $R$ is (A) $\{1,2\}$ (B) $\{2,3\}$ (C) $\{1,2,3\}$ (D) $\{3\}$

💡 Show solution▶

Idea The range is the set of second components: $2,3,3$.

Trap (A) is the domain; (C) is the codomain.

Answer (B).

E2. Board · 2 marks Let $R=\{(x,y) : x,y\in\mathbb{N},\ x+3y=12\}$. Write $R$ in roster form and find its domain and range.

💡 Show solution▶

Solve $x=12-3y\ge1$ needs $y\le3$: $y=1,2,3$ give $x=9,6,3$. ($y=4$ gives $x=0\notin\mathbb{N}$.) (1 mark)

Answer $R=\{(9,1),(6,2),(3,3)\}$; domain $\{3,6,9\}$; range $\{1,2,3\}$. (1 mark)

E3. Board · 3 marks Let $A=\{2,3,4,8,9\}$ and $R=\{(a,b) : a,b\in A,\ a\ne b,\ a \text{ divides } b\}$. (i) Write $R$ in roster form. (ii) Find its domain and range. (iii) Draw its arrow diagram.

💡 Show solution▶

(i) $2$ divides $4$ and $8$; $3$ divides $9$; $4$ divides $8$; $8$ and $9$ divide no other element. $R=\{(2,4),(2,8),(3,9),(4,8)\}$. (1 mark)

(ii) Domain $\{2,3,4\}$; range $\{4,8,9\}$. (1 mark)

Answer (iii) Two copies of $A$ side by side with arrows $2\to4$, $2\to8$, $3\to9$, $4\to8$. (1 mark)

E4. JEE Main If $n(A)=3$ and $n(B)=2$, the number of relations from $A$ to $B$ containing at least two ordered pairs is (A) $57$ (B) $58$ (C) $63$ (D) $64$

💡 Show solution▶

Total $n(A\times B)=6$, so there are $2^6=64$ relations.

Remove Those with fewer than two pairs: the empty relation ($1$) and the one-pair relations ($6$).

Trap (C) removes only the empty relation; (B) removes only the six one-pair relations.

Answer (A) $64-1-6=57$.

E5. JEE Main Numerical value. Let $A=\{1,2,3\}$ and $B=\{a,b\}$. Find the number of relations from $A$ to $B$ whose domain is $A$.

💡 Show solution▶

Idea Each of $1,2,3$ must have a non-empty set of images, chosen independently from the $2^2-1=3$ non-empty subsets of $B$.

Answer $3^3=27$. ⏱ Fast route: $(2^{q}-1)^{p}$ with $p=3$, $q=2$.

E6. JEE Advanced One or more options correct. Let $R=\{(x,y) : x,y\in\mathbb{Z},\ x^2+y^2=50\}$. Then (A) $R$ has exactly $12$ elements (B) the domain of $R$ has exactly $6$ elements (C) $0$ belongs to the domain of $R$ (D) the range of $R$ is different from its domain

💡 Show solution▶

Solve Squares up to $50$: $0,1,4,9,16,25,36,49$. Pairs adding to $50$: $1+49$, $49+1$, $25+25$. So $|x|,|y|\in\{1,7\}$ or both $5$.

List $(\pm1,\pm7)$, $(\pm7,\pm1)$, $(\pm5,\pm5)$: $4+4+4=12$ pairs. Domain $=\{-7,-5,-1,1,5,7\}$, six elements; $0$ is not in it ($50$ is not a perfect square). The rule is symmetric in $x$ and $y$, so range $=$ domain.

Answer (A), (B).

🔬 Research–Teaching NexusMini project · about 45 minutes

Research question. In a small real network — who has whose phone number saved, or who follows whom in a class group — how "dense" is the relation, and how many links are mutual?

Why it matters. Social networks, citation databases and transport maps are stored as relations: sets of ordered pairs. Network scientists measure them by the fraction of possible pairs that are present, $n(R)/n(A\times A)$, and by how often a link $(a,b)$ comes with its reverse $(b,a)$. The same measurements are used to study the spread of rumours and of infections.

What to do.

With permission, take $6$ to $8$ classmates as the set $A$. For each ordered pair $(a,b)$ with $a\ne b$, record whether $a$ has $b$'s number saved (or follows $b$).
Write the relation in roster form and draw its arrow diagram (or a grid of $A\times A$ with ticks).
Find $n(R)$, the domain and the range. Is anyone outside the domain (saves nobody) or outside the range (saved by nobody)?
Compute the density $n(R)/\big(n(A)\,(n(A)-1)\big)$ and count the mutual pairs.

Tools: Paper grid or a spreadsheet (one row and one column per person)

Hand in: The grid, the arrow diagram, the four numbers, and a short paragraph comparing your network with a partner's.

Going further. How many different "who-saves-whom" relations are possible on your set (pairs with $a\ne b$ only)? Use the idea of Theorem 2.3: each of the $n(n-1)$ allowed pairs is in or out.

Instructor note: keep the data anonymous (use letters, not names) and voluntary. The count in "going further" is $2^{n(n-1)}$ — for $n=8$ it is $2^{56}$, a striking illustration of how fast $2^{pq}$ grows.

🧪 Self-check quiz

0/5 correct

Q1. A relation from $A$ to $B$ is

Q2. The range of $R=\{(1,4),(2,5),(3,4)\}$ is

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

Q4. The domain of $R=\{(x,y) : x,y\in\mathbb{N},\ x+y=4\}$ is

Q5. For every relation from $A$ to $B$,

← 2.1 Cartesian Products of Sets 2.3 Functions and Their Graphs →