Equivalence Relations

Definition of an Equivalence Relation

A binary relation on a non-empty set A is said to be an equivalence relation if and only if the relation is

reflexive
symmetric, and
transitive.

Two elements a and b related by an equivalent relation are called equivalent elements and generally denoted as a ∼ b or a ≡ b. For an equivalence relation R, you can also see the following notations: a ∼_R b, a ≡_R b.

The equivalence relation is a key mathematical concept that generalizes the notion of equality. It provides a formal way for specifying whether or not two quantities are the same with respect to a given setting or an attribute.

Examples of Equivalence Relations

Equality Relation

The equality relation between real numbers or sets, denoted by \(=,\) is the canonical example of an equivalence relation.

The equality relation \(R\) on the set of real numbers is defined by

\[R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{R}, b \in \mathbb{R}, a = b} \,\right\}.\]

\(R\) is reflexive since every real number equals itself: \(a = a.\)

\(R\) is symmetric: if \(a = b\) then \(b = a.\)

The relation \(R\) is transitive: if \(a = b\) and \(b = c,\) then we get

\[\left\{ \begin{array}{l} a = b\\ b = c \end{array} \right.,\;\; \Rightarrow a = b = c,\;\; \Rightarrow a = c.\]

Parity Relation

Two numbers are said to have the same parity if they are both even or both odd. Consider the set of integers and define a relation \(R:\)

\[R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{Z}, b \in \mathbb{Z}, a \text{ and } b \text{ have the same parity}} \right\}.\]

The parity relation \(R\) is an equivalence relation.

\(R\) is reflexive as, for any \(a \in \mathbb{Z},\) the number \(a\) has the same parity as itself: \(\left( {a,a} \right) \in R.\)

\(R\) is symmetric. If \(\left( {a,b} \right) \in R,\) and therefore both \(a\) and \(b\) have the same parity, then we can write \(\left( {b,a} \right) \in R.\)

The relation \(R\) is transitive. If \(\left( {a,b} \right) \in R\) and \(\left( {b,c} \right) \in R,\) then all three numbers \(a, b,\) and \(c\) have the same parity, so \(\left( {a,c} \right) \in R.\)

Congruence Modulo \(n\)

Let \(n\) be a non-zero integer. The numbers \(a,b \in \mathbb{Z}\) are said to be congruent modulo \(n\) if \(n \mid \left( {a - b} \right),\) that is \(n\) divides \(\left( {a - b} \right).\) This is written as

\[a \equiv b \;\left( {\bmod n} \right).\]

For example,

\[7 \equiv 12 \;\left( {\bmod 5} \right).\]

Congruence modulo \(n\) is an equivalence relation. Let

\[R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{Z}, b \in \mathbb{Z}, a \equiv b\;\left({\bmod n} \right)} \right\}.\]

\(R\) is reflexive since \(a - a = 0\) is a multiple of any \(n.\)

\(R\) is symmetric. If \(a \equiv b\;\left( {\bmod n}\right),\) then \(a - b = n\cdot k,\) where \(k\) is an integer. Hence, \(b - a = n\cdot \left({-k}\right),\) where \(-k\) is also an integer. So we have \(b \equiv a\;\left( {\bmod n}\right).\)

The relation \(R\) is transitive. Suppose that \(a \equiv b\;\left( \kern-2pt{\bmod n}\right)\) and \(b \equiv c\;\left( \kern-2pt{\bmod n}\right).\) We can write these equations as

\[a - b = n \cdot k \;\text{ and }\;b - c = n \cdot \ell,\]

where \(k, \ell\) are some integers.

By adding these together, we have

\[\left( {a - c} \right) = \left( {a - b} \right) + \left( {b - c} \right) = n \cdot k + n \cdot l = n\left( {k + l} \right).\]

Since \(k\) and \(\ell\) are integers, then their sum \(k + \ell\) is also an integer. It follows from here that \(a \equiv c\;\left({\bmod n}\right).\) This proves the transitivity of \(R.\)

Note that congruence modulo \(n\) for \(n = 2\) is also called the parity relation considered above.

Some Other Examples

The following relations are equivalence relations:

"\(a\) and \(b\) live in the same city" on the set of all people;
"\(a\) and \(b\) are the same age" on the set of all people;
"\(a\) and \(b\) were born in the same month" on the set of all people;
"\(a\) and \(b\) have the same remainder when divided by \(3\)" on the set of integers;
"\(a\) and \(b\) have the same last digit" on the set of integers;
Any relation that can be defined using expressions like “have the same” or “are the same” is an equivalence relation.

Any relation that can be defined using expressions like “have the same” or “are the same” is an equivalence relation.

"\(a\) and \(b\) are parallel lines" on the set of all straight lines of a plane;
"\(a\) and \(b\) are similar triangles" on the set of all triangles;
Two functions \(f\left( x \right)\) and \(g\left( x \right),\) where \(x \in \mathbb{R},\) are said to be equivalent as \(x \to {x_0},\) if
\[\lim\limits_{x \to {x_0}} \frac{{f\left( x \right)}}{{g\left( x \right)}} = 1,\]
provided \({g\left( x \right)} \ne 0\) at \(x = {x_0}.\) For example, \(\sin x \sim x\) as \(x \to 0.\)

Equivalence Relation Closure

Let \(R\) be an arbitrary binary relation on a non-empty set \(A.\) To turn \(R\) into an equivalence relation, we can take the reflexive, symmetric, and transitive closures of \(R.\) This triple operation is denoted by \(tsr\left(R\right).\)

\(tsr\left(R\right)\) is the the smallest equivalence relation that contains \(R.\) The order of taking symmetric and transitive closures is essential. One can show, for example, that \(str\left(R\right)\) need not be an equivalence relation.

The equivalence relation \(tsr\left(R\right)\) can be calculated by the formula

\[tsr\left( R \right) = t\left( {s\left( {r\left( R \right)} \right)} \right) = {\left( {R \cup I \cup {R^{ - 1}}} \right)^*},\]

where the asterisk symbol denotes the connectivity relation.

See solved problems on Page 2.

Calculus

Set Theory