Set Theory

Set Theory Logo

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

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:

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

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.

Page 1 Page 2