Mathematical Proof/Relations

Introduction

Intuitively, relation associates pairs of objects based on some rules and properties. That is, relation suggests some kinds of relationship or connection between two objects. Take marriage as an example. In the marriage registry, there is a record in which the names of husbands are associated with the names of their corresponding wives, to keep track of the marriages. The entries in the record can be interpreted as ordered pairs $(a,b)$, where $a$ is the husband, while $b$ is the wife.

Expressing it mathematically, let $M$ and $W$ be the set of all men and women respectively. Then, the Cartesian product $M\times W=\{(a,b):a\in M{\text{ and }}b\in W\}$ consists of all pairs of people (first and second coordinate is a man and woman respectively). After that, we know that the record in the marriage registry, $R$, is a subset of $M\times W$. If a man and a woman form an ordered pair in $R$, say $(m,w)$, then it means they are married. Then, it is natural to say that $m$ is related to $w$. In other words, if we find that $(m,w)\in R$, then it means that they are related by this relation $R$. Also, knowing what $R$ exactly is (we have the record from the marriage registry) is the same as knowing all the husband and wife relationship.

Thus, it is natural to define the set $R$ as a relation. Let us formally define relation below.

Terminologies

Definition. (Relation) A relation $R$ from a set $A$ to a set $B$ is a subset of $A\times B$, i.e., $R\subseteq A\times B$. In particular, when $A=B$, we say that $R$ is a relation on $A$, and we have $R\subseteq A\times A$. If $(a,b)\in R$, then we say that $a$ is related to $b$ by $R$, and write $aRb$. On the other hand, if $(a,b)\notin R$, then we say that $a$ is not related to $b$ by $R$, and write $a\not Rb$.

Example. Let $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Since the set $R$ is a subset of $A\times B$, $R$ defines a relation from set $A$ to set $B$. Also, in this relation, $a$ is related to 1, $b$ is related to 1 and 2, $c$ is related to 3. Thus, we have $aR1,bR1,bR2$ and $cR3$. But, we have, say $a\not R2$ or $d\not R4$, since $(a,2),(d,4)\notin R$.

Exercise.

(a) Suggest a set $S$ that is not a relation from set $A$ to set $B$.

(b) Suggest a set $T$ that is a relation from set $A$ to set $R$.

Solution

(a) $S=\{(a,5)\}$ ($(a,5)\notin A\times B$, so $S$ is not a subset of $A\times B$).

(b) $T=\left\{{\big (}a,(a,1){\big )}\right\}$.

Exercise. Let $A$ and $B$ be two nonempty sets. Are $\varnothing$ and $A\times B$ relations from $A$ to $B$? Describe the relationships meant by these two sets.

Solution

Both $\varnothing$ and $A\times B$ are relations from $A$ to $B$ since both are subsets of $A\times B$.

For $\varnothing$, it means nothing is related, i.e., there is no relationship between elements in $A$ and elements in $B$.

For $A\times B$, it means everything is related, i.e., every element in $A$ is related to every element in $B$.

Example. Let $H$ be a set of all human beings. Then, $R=\{(a,b):a{\text{ is the son of }}b\}$. Then, $R$ is a subset of $H\times H$, and defines the relation for son and (father or mother).

Example. The concept of "less than" defines a relation on $\mathbb {R}$. To be more precise, the relation corresponding to this concept is $R=\{(a,b):a<b\}\subseteq \mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}$. For instance, $1R2$ but $2\not R1$.

Example. The congruence of integers defines a relation on $\mathbb {Z}$. To be more precise, the corresponding relation is $R=\{(a,b):a\equiv b{\pmod {n}}\}\subseteq \mathbb {Z} \times \mathbb {Z}$ ($n\in \mathbb {N}$ with $n\geq 2$). For example, when $n=3$, then $2R5$ but $1\not R3$.

Exercise. Consider the relation on $\mathbb {R}$, corresponding the concept of "equal to": $R=\{(x,y):x=y\}\subseteq \mathbb {R} ^{2}$.

(a) Sketch $R$ in the Cartesian coordinate system.

(b) Consider also the relations $S,T$ on $\mathbb {R}$ corresponding the concept of "less than" and "greater than" respectively. Sketch also $S$ and $T$ in the graph in (a).

Solution

(a) and (b):

        y
        |    y=x     
########|#####/%%%
########|####/%%%% 
########|###/%%%%%
########|##/%%%%%%
########|#/%%%%%%%
########|/%%%%%%%%
--------*--------- x
#######/|%%%%%%%%% 
######/%|%%%%%%%%%
#####/%%|%%%%%%%%%
####/%%%|%%%%%%%%%
###/%%%%|%%%%%%%%%

*----*
|####|
|####| : y>x (relation T)
*----*

*----*
|%%%%|
|%%%%| : y<x (relation S)
*----*

Remark.

• The sets $R,S,T$ give a partition of $\mathbb {R}$. As we will see, there is a close relationship between the concept of relation and the concept of partition.

Example. Let $A=\{1,2\}$. Define a relation on ${\mathcal {P}}(A)$, $R=\{(S,T)\in {\mathcal {P}}(A)\times {\mathcal {P}}(A):S\subseteq T\}$. Express $R$ by listing method.

Solution. First, we have ${\mathcal {P}}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$. So,

$$R=\{(\varnothing ,\varnothing ),(\varnothing ,\{1\}),(\varnothing ,\{2\}),(\varnothing ,\{1,2\}),(\{1\},\{1\}),(\{1\},\{1,2\}),(\{2\},\{2\}),(\{2\},\{1,2\}),(\{1,2\},\{1,2\})\}.$$

Exercise. Let $A=\{1,2\}$ and $B=\{3,4\}$. Consider a relation $R$ on $A\times B$ defined by

$$(a,b)R(c,d){\text{ if }}a+d=b+c.$$

Express $R$ by listing method.

Solution

First, $A\times B=\{(1,3),(1,4),(2,3),(2,4)\}$. So,

$$R=\{{\big (}(1,3),(1,3){\big )}{\big (}(1,3),(2,4){\big )},{\big (}(1,4),(1,4){\big )},{\big (}(2,3),(2,3){\big )},{\big (}(2,4),(1,3){\big )},{\big (}(2,4),(2,4){\big )}\}.$$

Definition. (Domain and range) Let $R$ be a relation from a set $A$ to a set $B$. The domain of $R$, denoted by $\operatorname {dom} R$ is the subset of $A$ defined by

$$\operatorname {dom} R=\{a\in A:(a,b)\in R{\text{ for some }}b\in B\}.$$

The range of $R$, denoted by $\operatorname {ran} R$, is the subset of $B$ defined by

$$\operatorname {ran} R=\{b\in B:(a,b)\in R{\text{ for some }}a\in A\}.$$

Remark.

• You may have learnt about the domain and range for functions. Using the same terminologies for both relations and functions is indeed not a coincidence. This is because a function is actually a relation. That is, a function is indeed just a special case of relation.

Example. Let $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Then, $\operatorname {dom} R=\{a,b,c\}=A$ and $\operatorname {ran} R=\{1,2,3\}$.

Example. Consider the relation $R$ on $\mathbb {Z}$: $R=\{(a,b):a{\text{ and }}b{\text{ are both even}}\}$. Then, $\operatorname {dom} R$ is the set of all even numbers, and $\operatorname {ran} R$ is the set of all even numbers also.

Exercise. Consider the relation $R$ on $\mathbb {Z}$: $R=\{(a,b):a{\text{ and }}b{\text{ are of different parity}}\}$. Find $\operatorname {dom} R$ and $\operatorname {ran} R$.

Solution

$\operatorname {dom} R=\mathbb {Z}$ and $\operatorname {ran} R=\mathbb {Z}$.

Definition. (Inverse relation) Let $R$ be a relation from a set $A$ to a set $B$. The inverse relation $R^{-1}$ from $B$ to $A$ is

$$R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$$

Remark.

• Again, you may have learnt a similar concept (and also a similar notation) for functions: inverse functions. Indeed, inverse functions can be defined as the inverse relation of a function, provided that the inverse relation is also a function.
• We can see that the inverse relation is obtained by "reversing" the order of elements in every ordered pair in the original relation.
• When $R$ is empty, then the inverse relation $R^{-1}$ is also empty since there is no ordered pair in the empty set.

Example. Let $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Then, the inverse relation $R^{-1}$ is $\{(1,a),(1,b),(2,b),(3,c)\}$.

Exercise. Construct an example of sets $A,B$ and a nonempty relation $R$ from set $A$ to set $B$ such that $R=R^{-1}$.

Solution

Take $A=B=\{1\}$, and $R=\{(1,1)\}$. Then, $R^{-1}=\{(1,1)\}=R$.

Reflexive, symmetric and transitive relations

After introducing the terminologies related to relations, we will study three properties for a relation defined on a set.

Definition. (Reflexive, symmetric and transitive) Let $A$ be a set and $R$ be a relation defined on $A$. Then,

• $R$ is reflexive if $xRx$ for every $x\in A$.
• $R$ is symmetric if for every $x,y\in A$, $xRy\implies yRx$.
• $R$ is transitive if for every $x,y,z\in A$, $(xR{\color {darkgreen}y}{\text{ and }}{\color {darkgreen}y}Rz)\implies xRz$.

Exercise. Let $A$ be a set and $R$ be a relation defined on $A$. Write down the meaning of (i) $R$ is not reflexive; (ii) $R$ is not symmetric; (iii) $R$ is not transitive.

Solution

(i) There exists $x\in A$ such that $x\not Rx$.

(ii) There exist $x,y\in A$ such that $xRy$ but $y\not Rx$.

(iii) There exist $x,y,z\in A$ such that $xRy$ and $yRz$, but $x\not Rz$.

Example. Let $A=\{1,2\}$, and let a relation defined on $A$ be

$$R=\{(1,1),(2,2),(1,2)\}.$$

Then, $R$ is reflexive since $(1,1),(2,2)\in R$. But $R$ is not symmetric since $(1,2)\in R$ but $(2,1)\notin R$.

Exercise. Is $R$ transitive? Explain why.

Solution

$R$ is transitive since

• $1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$;
• $1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$.

(There are no more ordered pairs $(x,{\color {darkgreen}y})$ and $({\color {darkgreen}y},z)$ in the relation $R$, satisfying $(x,y)\in R$ and $(y,z)\in R$.)

Example. The congruence of integers

$$R=\{(a,b):a\equiv b{\pmod {n}}\}$$

defines a relation on $\mathbb {Z}$ ($n\in \mathbb {N}$ with $n\geq 2$). Prove that $R$ is a reflexive, symmetric and transitive.

Proof.

Reflexive: For every $x\in \mathbb {Z}$, $x\equiv x{\pmod {n}}$. So, $xRx$ for every $x\in \mathbb {Z}$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies x\equiv y{\pmod {n}}\implies x-y=kn\implies y-x=(-k)n\implies y\equiv x{\pmod {n}}\implies yRx$ where $k$ is some integer.

Transitive: For every $x,y,z\in \mathbb {Z}$,

$${\begin{aligned}xRy{\text{ and }}yRz&\implies x-y=kn{\text{ and }}y-z=k'n{\text{ for some }}k,k'\in \mathbb {Z} \\&\implies x-z=(x-y)+(y-z)=(k+k')n\\&\implies xRz.&(k+k'\in \mathbb {Z} )\end{aligned}}$$

$\Box$

Exercise. Which of the properties, reflexive, symmetric and transitive, does each of the following relations possesses? Prove your answer.

(a) $R=\{(x,y)\in \mathbb {R} ^{2}:x\leq y\}$.

(b) $R=\{(x,y)\in \mathbb {R} ^{2}:x<y\}$.

(c) $R=\{(x,y)\in \mathbb {Z} \times \mathbb {Z} :xy>0\}$.

Solution

(a) $R$ is reflexive, not symmetric, and transitive.

Proof.

Reflexive: For every $x\in \mathbb {R}$, $x\leq x$. So, $xRx$.

Not symmetric: Take $x=1$ and $y=2$. Then, $1\leq 2$, so $xRy$. However, $2>1$. So, $y\not Rx$.

Transitive: For every $x,y,z\in \mathbb {R}$, $xRy{\text{ and }}yRz\implies x\leq y{\text{ and }}y\leq z{\text{ and }}x\leq z\implies xRz$ (this actually follows from the property of "$\leq$").

$\Box$

(b) $R$ is not reflexive, not symmetric, and transitive.

Proof.

Reflexive: Take $x=1$. Then, 1 is not less than 1 itself. Hence, $1\not R1$.

Not symmetric: Take $x=1$ and $y=2$. Then, $1<2$, so $xRy$. However, $2>1$. So, $y\not Rx$.

Transitive: For every $x,y,z\in \mathbb {R}$, $xRy{\text{ and }}yRz\implies x<y{\text{ and }}y<z{\text{ and }}x<z\implies xRz$ (this actually follows from the property of "$<$").

$\Box$

(c) $R$ is reflexive, symmetric and not transitive.

Proof.

Reflexive: For every $x\in \mathbb {Z}$,

Case 1: $x\geq 0$. Then, $x(x)\geq 0$. So, $xRx$.

Case 2: $x<0$. Then, $x(x)>0$. So, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies xy\geq 0\implies yx=xy\geq 0\implies yRx$.

Not transitive: Take $x=1,y=0$ and $z=-1$. Then, $xy=0$ and $yz=0$. So, $xRy$ and $yRz$. However, since $xy=-1<0$, $x\not Rz$.

$\Box$

Exercise. Let $R$ be a relation on a set $A$. Prove or disprove that

(a) if $R$ is reflexive, then $R^{-1}$ is reflexive;

(b) if $R$ is symmetric, then $R^{-1}$ is symmetric;

(c) if $R$ is transitive, then $R^{-1}$ is transitive.

Equivalence relations and equivalence classes

After studying the three properties that a relation on a set can possess, let us focus on those relations that possess all three properties.

Definition. (Equivalence relation) Let $A$ be a set. A relation $R$ defined on $A$ is an equivalence relation if it is reflexive, symmetric and transitive.

Remark.

• To show that a relation is not an equivalence relation (i.e., to disprove that the relation is an equivalence relation), it suffices to show any one of the following: (i) it is not reflexive; (ii) it is not symmetric; (iii) it is not transitive, by considering the negation of the above definition.

Example. Let $A=\{1,2\}$. Also let a relation defined on $A$ be

$$R=\{(1,1),(2,2),(1,2),(2,1)\}.$$

Prove or disprove that $R$ is an equivalence relation.

Proof.

Reflexive: Since $(1,1),(2,2)\in R$, $R$ is reflexive.

Symmetric: Since $(1,1)\in R\implies (1,1)\in R$, $(2,2)\in R\implies (2,2)\in R$, $(1,2)\in R\implies (2,1)\in R$, and $(2,1)\in R\implies (1,2)\in R$, $R$ is symmetric.

Transitive: Since for every $x,y,z\in A$, $xRy{\text{ and }}yRz\implies xRz$, $R$ is transitive.

$\Box$

Exercise. Give another equivalence relation that is defined on $A$.

Solution

$R=\{(1,1),(2,2)\}$. It can be shown to be reflexive, symmetric and transitive.

Example. Since the congruence of integers defines a reflexive, symmetric and transitive relation, it defines an equivalence relation on $\mathbb {Z}$.

Suppose $R$ is an equivalence relation on a set $A$. Intuitively, for elements that are related by $R$, they are quite "closely related". Thus, when we consider the set consisting elements that are related to a given element of set A, the elements inside the set are "closely related", so the set, in some sense, forms a "group" of elements that are "relatives". It then appears that we can classify the elements of set $A$ into different such "groups", according to an equivalence relation. As we will see, this is roughly the case. Hence, such "group" is quite important. Now, let us formally define what the "group" is:

Definition. (Equivalence class)

A graph that illustrates equivalence classes. The whole circle in the set on which the relation is defined, and when there is a line connecting two dots, it means the two dots (representing elements in the set) are related by the equivalence relation.

Let $R$ be an equivalence relation defined on a set $A$. For every $a\in A$, the set

$$[a]=\{x\in A:xRa\}$$

consisting of all elements in $A$ that are related to $a$, is called an (equivalence) class of $a$ by $R$.

Example. Let $A=\{1,2,3,4\}$, and let a relation defined on $A$ be

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

This relation $R$ can be shown to be an equivalence relation. The equivalence classes are given by

$$[1]=\{1,2,3\},[2]=\{1,2,3\},[3]=\{1,2,3\},[4]=\{4\}.$$

Since $[1]=[2]=[3]$, there are only two distinct equivalence classes. Graphically, the situation looks like:

*----------**
|  .  .   / |
| 2   3  /  |
|  .    /.  |
| 1    /  4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]    [4]
=[3]

Exercise. Construct an equivalence relation $R$ on $A$ such that the equivalence classes are given by

$$[1]=\{1,2\},[2]=\{1,2\},[3]=\{3,4\},[4]=\{3,4\}.$$

Solution

$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)$. Graphically, the situation looks like:

*---*-------*
|  .| .     |
| 2 | 3     |
|  .\    .  |
| 1  \    4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]  [3]=[4]

Example. (Integers modulo $n$) Recall that the congruence of integers defines an equivalence relation $R$ on $\mathbb {Z}$. Using this equivalence relation, we can define the equivalence class $[a]$ for every $a\in \mathbb {Z}$, as follows:

• $$[0]=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=\{\dotsc ,-2n,-n,0,n,2n,\dotsc \}$$
• $$[1]=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=\{\dotsc ,-2n+1,-n+1,1,n+1,2n+1,\dotsc \}$$
• ...
• $$[n-1]=\{x\in \mathbb {Z} :xR(n-1)\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=\{\dotsc ,-2n+(n-1),-n+(n-1),n-1,n+(n-1),2n+(n-1),\dotsc \}=\{\dotsc ,-2n-1,-n-1,-1,2n-1,\dotsc \}$$
• $$[n]=\{x\in \mathbb {Z} :xRn\}=\{x\in \mathbb {Z} :x\equiv n{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=[0]$$
• $$[n+1]=\{x\in \mathbb {Z} :xR(n+1)\}=\{x\in \mathbb {Z} :x\equiv n+1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=[1]$$

We can observe that starting from $[n]$, the classes are not distinct from the previous classes. Indeed, if we consider the classes "backward":

• $[-1]=\{x\in \mathbb {Z} :xR(-1)\}=\{x\in \mathbb {Z} :x\equiv -1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=[n-1]$
• $[-2]=\{x\in \mathbb {Z} :xR(-2)\}=\{x\in \mathbb {Z} :x\equiv -2{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-2{\pmod {n}}\}=[n-2]$
• ...

They also do not give new classes.

Hence, we conclude that there are only $n$ distinct equivalence classes, namely $[0],[1],\dotsc ,[n-1]$. Usually, the set of these equivalence classes, $\{[0],[1],\dotsc ,[n-1]\}$, is denoted by $\mathbb {Z} _{n}$, and is called integers modulo $n$. Notice that $\mathbb {Z} _{n}$ is a finite set itself, but each of its elements is an infinite set.

Remark.

• We can illustrate the equivalence classes as follows (each column is an equivalence class, and the whole table is $\mathbb {Z}$):

*----*----*---...---*-----*
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
|-n  |-n+1|         |-2n-1|
| 0  | 1  |  ....   | n-1 |
| n  |n+1 |         |2n-1 |
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
*----*----*---...---*-----*

• When we consider integers modulo $m$ and integers modulo $n$ ($m\neq n$) together, there may be some ambiguities for the elements. For example, $\mathbb {Z} _{2}=\{[0],[1]\}$ and $\mathbb {Z} _{3}=\{[0],[1],[2]\}$. However, for instance, the "$[0]$" in $\mathbb {Z} _{2}$ and the "$[0]$" in $\mathbb {Z} _{3}$ are different. One of them contains all even numbers, another contains all multiples of 3.

• To avoid such ambiguities, we may add a subscript to the classes. For instance, we may write $\mathbb {Z} _{2}=\{[0]_{2},[1]_{2}\}$ and $\mathbb {Z} _{3}=\{[0]_{3},[1]_{3},[2]_{3}\}$.

Exercise. A relation $R$ on $\mathbb {Z}$ is defined by

$$aRb{\text{ if }}3a+b\equiv 0{\pmod {4}}.$$

(a) Prove that $R$ is an equivalence relation.

(b) Express each of the equivalence classes by $R$ $[0]_{R},[1]_{R},[2]_{R},[3]_{R}$ in terms of $[0]_{4},[1]_{4},[2]_{4},[3]_{4}$ (Hint: use the symmetric property of $R$).

Solution

(a)

Proof.

Reflexive: For every $x\in \mathbb {Z}$, since $3x+x=4x\equiv 0{\pmod {4}}$, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, since $xRy\implies 3x+y\equiv 0{\pmod {4}}\implies 9x+3y\equiv 0{\pmod {4}}\implies 9x-8x+3y\equiv \underbrace {-8x} _{\text{multiple of 4}}\equiv 0{\pmod {4}}\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$,

$${\begin{aligned}xRy{\text{ and }}yRz&\implies 3x+y\equiv 0{\pmod {4}}{\text{ and }}3y+z\equiv 0{\pmod {4}}\\&\implies (3x+y)+(3y+z)\equiv 0{\pmod {4}}\\&\implies 3x+z+4y\equiv 0{\pmod {4}}\\&\implies 3x+z\equiv -4y\equiv 0{\pmod {4}}\\&\implies xRz.\end{aligned}}$$

$\Box$

(b)

$$[0]_{R}=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :0Rx\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {4}}\}=[0]_{4}.$$

(By the symmetric property of $R$, $xR0\implies 0Rx$. Also, $0Rx\implies xR0$. So, $xR0\iff 0Rx$.)

$$[1]_{R}=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :1Rx\}=\{x\in \mathbb {Z} :3+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :4+x\equiv 1{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {4}}\}=[1]_{4}.$$

$$[2]_{R}=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :2Rx\}=\{x\in \mathbb {Z} :6+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :8+x\equiv 2{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 2{\pmod {4}}\}=[2]_{4}.$$

$$[3]_{R}=\{x\in \mathbb {Z} :xR3\}=\{x\in \mathbb {Z} :3Rx\}=\{x\in \mathbb {Z} :9+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :12+x\equiv 3{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 3{\pmod {4}}\}=[3]_{4}.$$

Properties of equivalence classes

In this section, we will discuss some properties of equivalence classes. In particular, we will address these two questions:

1. When are two equivalence classes equal?
2. Can two different equivalence classes contain a common element?

The answer to question 1 is given by the following theorem.

Theorem. Let $R$ be an equivalence relation defined on a set $A$. For every $a,b\in A$,

$$[a]=[b]{\text{ if and only if }}aRb.$$

Proof. "$\Rightarrow$" direction: Assume $[a]=[b]$. Since $R$ is an equivalence relation, and in particular, is reflexive, we have $aRa$. Thus, we have by definition $a\in [a]$. Then, since $[a]=[b]$ by assumption, we have $a\in [b]$.

"$\Leftarrow$" direction: Assume $aRb$. First, for every $x\in A$,

$${\begin{aligned}x\in [a]&\implies xRa&({\text{definition}})\\&\implies xRb&(aRb{\text{ and }}{\text{transitivity of }}R)\\&\implies x\in [b].&({\text{definition}})\\\end{aligned}}$$

So, $[a]\subseteq [b]$.

On the other hand, first, since $aRb$ by assumption, we have $bRa$ by the symmetry of $R$. Now, For every $y\in A$,

$${\begin{aligned}y\in [b]&\implies yRb&({\text{definition}})\\&\implies yRa&(bRa{\text{ and transitivity of }}R)\\&\implies y\in [a].&({\text{definition}})\\\end{aligned}}$$

So, $[b]\subseteq [a]$.

Hence, $[a]=[b]$.

$\Box$

Remark.

• From this theorem, we know that "$aRb$" is the necessary and sufficient condition for "$[a]=[b]$". Also, we have $[a]\neq [b]$ if and only if $a\not Rb$.

Now, let us consider the question 2. The answer to question 2 is, indeed, "No". The following corollary justifies this answer:

Corollary. Let $R$ be an equivalence relation defined on a nonempty set $A$. For every $a,b\in A$,

$$[a]\neq [b]{\text{ if and only if }}[a]\cap [b]=\varnothing .$$

Proof. "$\Leftarrow$" direction:

$${\begin{aligned}{}[a]\cap [b]=\varnothing &\implies [a]{\text{ and }}[b]{\text{ have distinct elements}}&([a]{\text{ and }}[b]{\text{ are nonempty}})\\&\implies [a]\neq [b].\end{aligned}}$$

($[a]$ and $[b]$ are nonempty since $R$ is reflexive. So they must contain, at least, $a$ and $b$ respectively.)

"$\Rightarrow$" direction: We use proof by contrapositive.

$${\begin{aligned}{}[a]\cap [b]\neq \varnothing &\implies \exists x\in [a]\cap [b]\\&\implies xRa{\text{ and }}xRb\\&\implies aRx{\text{ and }}xRb&(R{\text{ is symmetric}})\\&\implies aRb&(R{\text{ is transitive}})\\&\implies [a]=[b].&({\text{above theorem}})\\\end{aligned}}$$

$\Box$

Remark.

• From this result, we know that two equivalence classes are either equal or disjoint (since they are either equal or not equal). Hence, it is impossible for two different equivalence classes to contain a common element.

Now we have reached a key point in studying equivalence relations (and it is probably the major reason for studying equivalence relations at all): using equivalence relation on a set to construct a partition of that set, and vice versa. Before discussing it, let us define partition of a set:

Definition. (Partition) A partition of a nonempty set $A$ is a set of nonempty subset(s) of $A$ with the property that every element of $A$ belongs to exactly one of the subset(s). In other words, $P$ is a collection of pairwise disjoint and nonempty subset(s) of $A$ whose union is $A$.

Example. Let $A=\{1,2,3\}$. Then, a partition of $A$ is $\{\{1\},\{2\},\{3\}\}$. Another one is $\{\{1,2\},\{3\}\}$. However, $\{\{1,2\},\{2,3\}\}$ is not a partition of $A$ since $\{1,2\}$ and $\{2,3\}$ are not disjoint (or the element "2" belongs to two sets). Also, $\{\{1\},\{3\}\}$ is not a partition of $A$ since the union of $\{1\}$ and $\{3\}$ is not the entire set $A$ (or the element "2" does not belong to any of the sets inside the partition).

Exercise. Is $\{\{1,2,3\}\}$ a partition of $A$?

Solution

Yes, since every element of $A$ belongs to exactly one of the set inside the partition, namely the set $\{1,2,3\}$.

Example. Let $A=\{1,2,3,4\}$, and let a relation defined on $A$ be

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

Recall that the two distinct equivalence classes are given by

$$[1]=\{1,2,3\},[4]=\{4\}.$$

We can see that every element of $A$ belongs to exactly one of these equivalence classes. Hence, the set $\{[1],[4]\}=\{\{1,2,3\},\{4\}\}$ gives a partition of $A$.

Also, we can define another equivalence relation $R$ on $A$ such that the two distinct equivalence classes are given by

$$[1]=\{1,2\},[3]=\{3,4\}.$$

We can also see that every element of $A$ belongs to exactly one of these equivalence classes. hence, the set $\{[1],[3]\}=\{\{1,2\},\{3,4\}\}$.

Example. Recall that the congruence of integers defines an equivalence relation $R$ on $\mathbb {Z}$. Also, there are $n$ distinct equivalence classes: $[0],[1],\dotsc ,[n-1]$. By Euclid's division lemma, every integer belongs to exactly one of these $n$ equivalence classes. Thus, the integers modulo $n$

$$\mathbb {Z} _{n}=\{[0],[1],\dotsc ,[n-1]\}$$

gives a partition on $\mathbb {Z}$.

We can observe from the previous examples that equivalence relation of a set can be used to give a partition of that set. The following theorem suggests that, in general, an equivalence relation on a set $A$ can be used to give a partition of that set.

Theorem. Let $R$ be an equivalence relation defined on a nonempty set $A$. Then the set of all distinct equivalence classes by $R$ is a partition of $A$.

Proof. It suffices to show that every element of $A$ belongs to exactly one of the distinct equivalence classes.

For every $x\in A$, since $R$ is reflexive, we have $x\in [x]$. From this, we can ensure that every element of $A$ belongs to at least one of the distinct classes. It now remains to show that every element of $A$ also belongs to at most one of the distinct classes.

Assume that $x$ also belongs to the class $[y]$. Then, we have $xRy$. Since $R$ is an equivalence relation, it means $[x]=[y]$ by a previous theorem. Thus, any two equivalence classes to which $x$ belongs are equal. This means every element of $A$ cannot belong to more than one of the distinct classes.

Hence, every $x$ in $A$ belongs to exactly one of the distinct classes, and thus the set of all distinct equivalence classes by $R$ gives a partition of $A$.

$\Box$

The following theorem suggests the converse of the above theorem is also true. To be more precise, we can use a partition of a set to construct an equivalence relation on that set. Before introducing the theorem, let us make some intuitive guesses on how to construct the equivalence relation in this way. First, from the previous theorem, roughly speaking, using an equivalence relation on a set, we can create several "groups" of elements in different classes, in which the elements are "relatives".

Now, given a partition of a set, it means we have several "groups" of elements. Such "grouping" intuitively indicates the elements inside the group are "relatives" in some sense. So, intuitively, a relation that relates the "relatives" seems to make the relation quite "close", and hence an equivalence relation.

The following theorem formalizes this intuition:

Theorem. Let $P$ be a partition of a nonempty set $A$. Define a relation $R$ on $A$ by

$$xRy{\text{ if there exists }}S\in P{\text{ such that }}x,y\in S.$$

Then, the relation $R$ is an equivalence relation on the set $A$.

Proof. It suffices to prove that $R$ defined in this way is reflexive, symmetric, and transitive.

Reflexive: By the definition of partition, for every $x\in A$, $x$ belongs to exactly one of $S\in P$, so there exists $S\in P$ such that $x\in S$. Hence, $xRx$.

Symmetric: For every $x,y\in A$,

$${\begin{aligned}xRy&\implies \exists S\in P,x,y\in S\\&\implies \exists S\in P,y,x\in S\\&\implies yRx.\end{aligned}}$$

Transitive: For every $x,y,z\in A$, assume $xRy$ and $yRz$. Then, there exist $S,T\in P$ such that $x,{\color {blue}y\in S}$ and ${\color {blue}y},z{\color {blue}\in T}$. But by the definition of partition, $y$ belongs to exactly one of the set in the partition $P$. So, we have $S=T$. Hence, there exists a set $S$ ($=T$) such that $x,z\in S$, and thus $xRz$.

$\Box$

Example. Let $R$ be a relation defined on $\mathbb {Z}$ by

$$aRb{\text{ if }}|a|=|b|.$$

(a) Prove that $R$ is an equivalence relation.

(b) Determine all distinct equivalence classes by $R$ and hence give a partition on $\mathbb {Z}$.

Solution.

(a)

Proof. Reflexive: For every $x\in \mathbb {Z}$, $|x|=|x|$. So, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies |x|=|y|\implies |y|=|x|\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$, $xRy{\text{ and }}yRz\implies |x|=|y|{\text{ and }}|y|=|z|\implies |x|=|z|\implies xRz$.

$\Box$

(b) First, some equivalence classes are

$${\begin{aligned}{}[0]&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :|x|=0\}=\{0\},\\{}[1]&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :|x|=1\}=\{-1,1\},\\{}[2]&=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :|x|=2\}=\{-2,2\},\dotsc \\\end{aligned}}$$

So, all distinct equivalence classes are $[0],[1],[2],\dotsc$ ($-1\in [1]$, so $[-1]$ is not distinct from them, etc.). Hence, a partition on $A$ is

$$\{[0],[1],[2],\dotsc \}=\{[n]:n{\text{ is a nonnegative integer}}\}$$

(that is, every integer belongs to exactly one of $[0],[1],[2],\dotsc$.)

Exercise. Let $R$ be a relation defined on $\mathbb {Z}$ by

$$aRb{\text{ if }}a+b{\text{ is even}}.$$

(a) Prove that $R$ is an equivalence relation.

(b) Determine all distinct equivalence classes by $R$, and hence give a partition on $\mathbb {Z}$.

Solution

(a)

Proof. Reflexive: For every $x\in \mathbb {Z}$, since $x+x=2x$ is even, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies x+y{\text{ is even}}\implies y+x=x+y{\text{ is even}}\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$,

$${\begin{aligned}xRy{\text{ and }}yRz&\implies x+y{\text{ is even}}{\text{ and }}y+z{\text{ is even}}\\&\implies (x+y)+(y+z)=x+2y+z{\text{ is even}}\\&\implies x+2y+z-2y{\text{ is even}}&(-2y{\text{ is even}})\\&\implies x+z{\text{ is even}}\\&\implies xRz.\\\end{aligned}}$$

$\Box$

(b) First, some equivalence classes are

$${\begin{aligned}{}[0]_{R}&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x{\text{ is even}}\}=[0]_{2},\\{}[1]_{R}&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x+1{\text{ is even}}\}=\{x\in \mathbb {Z} :x{\text{ is odd}}\}=[1]_{2}.\\\end{aligned}}$$

Since every integer belongs to exactly one of $[0]_{2}$ and $[1]_{2}$ (i.e., all other equivalence classes are not distinct from them), it follows that $[0]_{R}$ and $[1]_{R}$ are all distinct equivalence classes.

Remark.

• Recall that the sum of two integers is even if and only if they have the same parity. So, this relation relates every pair of integers that have the same parity. So, intuitively, the relation $R$ can partition the integers into two "pieces": set of all odd integers and set of all even integers.