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$. The set of first co-ordinates that actually appear is the domain of $R$, and the set of second co-ordinates is its range; the whole of $B$ is the co-domain.
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.
Special types of relations
A few relations are important enough to be named outright. Let $A$ be a non-empty set.
- Empty (void) relation: $R = \varnothing \subseteq A \times A$. 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, since no such pair exists.
- Universal relation: $R = A \times A$. Every element is related to every element. Example: on the set of all students of a class, "has age difference less than $100$ years" is universal.
- Identity relation: $I_A = \{(a,a) : a \in A\}$ — each element is related to itself and to nothing else. On $A=\{1,2,3\}$, $I_A=\{(1,1),(2,2),(3,3)\}$.
The empty and universal relations are the two extremes, and are together called trivial relations. Do not confuse the identity relation with a merely reflexive one: the identity relation contains only the diagonal pairs, whereas a reflexive relation must contain the diagonal but may contain more besides.
The three building-block properties
Let $R$ be a relation on a set $A$. We test it against three properties:
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. A useful subtlety: on a small set a property can hold vacuously — if there are no pairs $(a,b)$ to begin with, symmetry and transitivity are automatically satisfied, so the empty relation is symmetric and transitive (but not reflexive unless $A=\varnothing$).
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. The standard exam task is to verify all three properties in turn — one line each — and only then declare $R$ an equivalence relation.
Equivalence classes and partitions
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\}.$$
Three facts make equivalence classes so useful: (i) every element lies in some class, since $a \in [a]$ by reflexivity; (ii) two classes are either identical or completely disjoint — if $[a]$ and $[b]$ share even one element then $[a]=[b]$; and (iii) together the classes cover all of $A$. A family of non-empty, pairwise-disjoint subsets whose union is $A$ is called a partition of $A$. So every equivalence relation produces a partition, and conversely every partition defines an equivalence relation ("same block") — the two ideas are really one idea wearing two hats.
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]\}$ — exactly $n$ of them. For instance, the relation $a\,R\,b \iff 5\mid(a-b)$ splits $\mathbb{Z}$ into the five classes $[0],[1],[2],[3],[4]$ according to the remainder on division by $5$.
Let $R$ be the relation on $\mathbb{R}$ defined by $a\,R\,b \iff a \le b$. Check whether $R$ is reflexive, symmetric and transitive.
Solution
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.)
Answer: reflexive and transitive but not symmetric, hence not an equivalence relation.
Show that the relation $R$ on the set of integers $\mathbb{Z}$ given by $a\,R\,b \iff 3 \mid (a-b)$ (i.e. $a-b$ is divisible by $3$) is an equivalence relation, and describe its equivalence classes.
Solution
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\}$
Answer: $R$ is an equivalence relation with three disjoint classes that partition $\mathbb{Z}$.
On $A=\{1,2,3\}$, let $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$. Is $R$ reflexive, symmetric, transitive?
Solution
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.
Answer: $R$ is reflexive, symmetric and transitive, so it is an equivalence relation. Its classes are $\{1,2\}$ and $\{3\}$.
Define $R$ on $A=\{1,2,3,4\}$ by $a\,R\,b \iff a+b$ is even. Determine the type of relation and its equivalence classes (if any).
Solution
$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.
Answer: $R$ is an equivalence relation. The classes are the odd numbers $[1]=\{1,3\}$ and the even numbers $[2]=\{2,4\}$.
On $A=\{1,2,3\}$, identify the empty relation, the universal relation and the identity relation, and state $n(A\times A)$ and the total number of relations possible on $A$.
Solution
$A\times A$ has $3\times 3 = 9$ ordered pairs, so $n(A\times A)=9$.
Empty relation: $R=\varnothing$ — no pairs at all, e.g. "$a\,R\,b \iff a-b=10$".
Universal relation: $R=A\times A$ — all nine pairs, e.g. "$a\,R\,b \iff |a-b|<5$".
Identity relation: $I_A=\{(1,1),(2,2),(3,3)\}$ — only the diagonal.
Each of the $9$ pairs is independently in or out of a relation, so the number of relations on $A$ is $2^{9}=512$.
Answer: $\varnothing$, $A\times A$ and $\{(1,1),(2,2),(3,3)\}$ respectively; $n(A\times A)=9$ and there are $\mathbf{512}$ relations in all.
On $A=\{1,2,3\}$, let $R=\{(1,1),(2,2),(3,3),(1,2),(2,3)\}$. Test all three properties. Is $R$ an equivalence relation? If not, name the smallest pairs that would need to be added.
Solution
Reflexive: $(1,1),(2,2),(3,3)$ are all present. Yes.
Symmetric: $(1,2)\in R$ but $(2,1)\notin R$. Not symmetric.
Transitive: $(1,2)$ and $(2,3)$ are present, but $(1,3)\notin R$. Not transitive.
Since symmetry and transitivity both fail, $R$ is not an equivalence relation. To repair it we would need $(2,1),(3,2)$ for symmetry and then $(1,3),(3,1)$ for transitivity — which forces every pair, i.e. the whole of $A\times A$.
Answer: $R$ is reflexive only; it is not an equivalence relation, and completing it to one gives the universal relation $A\times A$.
Show that the relation "is congruent to" on the set of all triangles in a plane is an equivalence relation.
Solution
Let $T_1,T_2,T_3$ be triangles and $\cong$ denote congruence.
Reflexive: Every triangle is congruent to itself, $T_1\cong T_1$. Yes.
Symmetric: If $T_1\cong T_2$ then the same correspondence gives $T_2\cong T_1$. Yes.
Transitive: If $T_1\cong T_2$ and $T_2\cong T_3$, then matching corresponding sides and angles gives $T_1\cong T_3$. Yes.
Answer: Congruence is reflexive, symmetric and transitive, so it is an equivalence relation; its classes group together all mutually-congruent triangles.
Let $A=\{1,2,3,4,5\}$ and define $R$ on $A$ by $a\,R\,b \iff |a-b|$ is even. Prove $R$ is an equivalence relation and list its equivalence classes.
Solution
$|a-b|$ is even exactly when $a$ and $b$ have the same parity.
Reflexive: $|a-a|=0$ is even, so $a\,R\,a$. Yes.
Symmetric: $|a-b|=|b-a|$, so $a\,R\,b \Rightarrow b\,R\,a$. Yes.
Transitive: If $a,b$ share parity and $b,c$ share parity then $a,c$ share parity, so $|a-c|$ is even. Yes.
The classes are the odd elements and the even elements of $A$:
- $[1]=\{1,3,5\}$
- $[2]=\{2,4\}$
Answer: $R$ is an equivalence relation with two classes, $\{1,3,5\}$ and $\{2,4\}$, which partition $A$.
Let $A=\{1,2,3,4,5,6\}$ and $R=\{(a,b): b=a+1\}$ (i.e. $a\,R\,b \iff b$ is the successor of $a$). Examine $R$ for reflexivity, symmetry and transitivity.
Solution
In roster form, $R=\{(1,2),(2,3),(3,4),(4,5),(5,6)\}$.
Reflexive: $(1,1)\notin R$ (we never have $a=a+1$). Not reflexive.
Symmetric: $(1,2)\in R$ but $(2,1)\notin R$. Not symmetric.
Transitive: $(1,2)$ and $(2,3)$ are present, but $(1,3)\notin R$. Not transitive.
Answer: $R$ is neither reflexive nor symmetric nor transitive, so it is far from an equivalence relation.
Let $A=\{1,2,3,\dots,12\}$ and $R$ on $A$ be $a\,R\,b \iff 4 \mid (a-b)$. Show $R$ is an equivalence relation and find the equivalence class $[2]$.
Solution
Reflexive: $4\mid(a-a)=0$, so $a\,R\,a$. Yes.
Symmetric: $4\mid(a-b)\Rightarrow 4\mid(b-a)$, since $b-a=-(a-b)$. Yes.
Transitive: $4\mid(a-b)$ and $4\mid(b-c)$ give $4\mid\big((a-b)+(b-c)\big)=4\mid(a-c)$. Yes.
So $R$ is an equivalence relation, with classes by remainder mod $4$. The class of $2$ contains every element of $A$ leaving remainder $2$ on division by $4$:
$$[2]=\{2,6,10\}.$$
Answer: $R$ is an equivalence relation and $[2]=\{2,6,10\}$.