Smallest equivalence relation containing given pairs

Question

Let $X = (1,2,3,4,5,6,7)$. Find the smallest equivalence relation such that: $(1,2),(2, 3),(5,2), (4,6), (7,7)$ belongs to the relation.

Answer 1

Look at the relations given above.So far we are given: $1$ is related to $2$, $2$ is related to $3$, $2$ is related to $5$, $4$ is related to $6$, and $7$ is related to $7$. Let us call the smallest containing equivalence relation as $E$.

Now, there are three properties of an equivalence relation:

Reflexivity: According to reflexivity, for every element $a$, $(a,a)$ must be an element of the equivalence relation. Now, that means that $(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7) \in E$.

Symmetry: This says that whenever $(a,b) \in E$, then $(b,a) \in E$. Given $(1,2) \in E$, we get $(2,1) \in E$.Given $(2,3) \in E$, we get $(3,2) \in E$.Given $(5,2) \in E$, we get $(2,5) \in E$.Given $(4,6) \in E$, we get $(6,4) \in E$.

Transitivity : Whenever $(a,b) \in E$ and $(b,c) \in E$ then $(a,c) \in E$. Look at what we have, and I will individually note down all the possibilities:

i) Given $(1,2) \in E$ and $(2,3) \in E$, we get $(1,3) \in E$, and by symmetry, $(3,1)\in E$.

ii) Given $(5,2) \in E$ and $(2,3) \in E$, we get $(5,3) \in E$, and by symmetry, $(3,5)\in E$.

iii) Given $(1,2) \in E$ and $(2,5) \in E$, we get $(1,5) \in E$, and by symmetry, $(5,1)\in E$.

That completes the relation. We summarize by saying the following: There is a theorem that says that equivalence relations divide the set into equivalence classes, where two elements of a class are , in a pair, in $E$. Hence, when we write that $ a \sim b \sim c \sim d$, then it is implied that a pair of each of these elements is in $E$ (so for example, $(a,c) \in E$,$(d,b) \in E$, etc.) This is a convenient notation used to express equivalence relations.

So, you can check from the above analysis, that the following relations are true: $1 \sim 2 \sim 3 \sim 5$, $4 \sim 6$, $7 \sim 7$. So the respective smallest equivalence relation is given by this decomposition, where every pair of elements in each relation are in $E$.

To show that this is the smallest equivalence relation,I will leave as an exercise, but it should be obvious, because all the above elements must be contained in any equivalence relation containing the required elements.

Answer 2

An equivalence relation partitions the set into equivalence classes.   If $(a,b)$ is required to be in the relation, they must be in the same equivalence class.

If $\{a,b, ..., k\}$ is an equivalence class, then the following are in the relation: $$\begin{array}{c}(a, a),& (a,b),&\ldots,& (a,k),\\ (b,a),& (b,b),& \ldots,& (b,k), \\ \vdots & \vdots & \ddots & \vdots \\ (k, a),& (k, b),& \ldots,& (k, k)\end{array}$$

Thus the size of an equivalence relation equals the sum of squares of each partition.   So we want the most partitions that allow the relation to contain the required pairs.

• Because $x^2+y^2\leq (x+y)^2$ for all natural numbers (nonnegative integers).