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
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).
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.
$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.
For any sets $A$, $B$, $C$:
- $\phi\subseteq A$ and $A\subseteq A$.
- $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.
- If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.
- 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$
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$.
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.
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.
For all subsets $A$, $B$, $C$ of a universal set $U$:
$(A\cap B)\cap C=A\cap(B\cap C)$
$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
$\phi'=U,\ \ U'=\phi$
$(A\cap B)'=A'\cup 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.
The next result is the most-used counting tool of this unit. It answers the question in the opening paragraph.
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?
$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.
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$.
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$.
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)$.
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.
- 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.
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.
Let $R$ be an equivalence relation on a non-empty set $A$. Then
- $a\in[a]$ for every $a$, so every element lies in some class;
- $a\,R\,b$ if and only if $[a]=[b]$;
- 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.
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.
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$?
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.
- 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 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 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 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.
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$
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.
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
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.
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$
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.
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.
- 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.
- 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).
- 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.
- 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?
🧪 Self-check quiz
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