Equivalence Relations

Three Conditions Working Together

In “Relations,” a relation on a set \(A\) was defined as a subset of \(A\times A\). That tutorial introduced reflexivity, symmetry, and transitivity as separate properties a relation may or may not have. An equivalence relation is precisely a relation on one set that has all three properties at once. The combination captures a useful idea: objects can be treated as equivalent even when they are not literally equal.

For example, two integers can be considered equivalent when they have the same remainder upon division by \(4\). The integers \(2\) and \(14\) are different, but they have the same remainder, so they are equivalent in this sense. The chosen relation determines what “equivalent” means; it does not change ordinary equality.

Definition (Equivalence Relation). Let \(A\) be a set, and let \(R\) be a relation on \(A\), so \(R\subseteq A\times A\). The relation \(R\) is an equivalence relation on \(A\) if it is reflexive, symmetric, and transitive: $$ \begin{aligned} &\text{Reflexive:} && (x,x)\in R &&\text{for every }x\in A,\\ &\text{Symmetric:} && (x,y)\in R\Longrightarrow(y,x)\in R &&\text{for all }x,y\in A,\\ &\text{Transitive:} && (x,y)\in R\text{ and }(y,z)\in R\Longrightarrow(x,z)\in R &&\text{for all }x,y,z\in A. \end{aligned} $$ When the relation is named \(\sim\), membership \((x,y)\in R\) is commonly written \(x\sim y\).

Each condition has a distinct role. Reflexivity requires every element to be related to itself. Symmetry says that the order of the two objects does not matter. Transitivity says that if one object is related to a second, and the second to a third, then the first must be related to the third. These are the definitions of the three relation properties from the previous tutorial; the new requirement is that all three hold simultaneously.

Equality as a Basic Example

Ordinary equality provides the model for the three conditions. Every object equals itself; if \(x=y\), then \(y=x\); and if \(x=y\) and \(y=z\), then \(x=z\). The next theorem records this familiar relation in set language.

Theorem (Equality Relation). For any set \(A\), the relation $$ \Delta_A=\{(x,x):x\in A\} $$ is an equivalence relation on \(A\).

Proof. We check the three required properties. Let \(x\in A\). By the definition of \(\Delta_A\), the pair \((x,x)\) belongs to \(\Delta_A\), so \(\Delta_A\) is reflexive. Next, suppose \(x,y\in A\) and \((x,y)\in\Delta_A\). Membership in \(\Delta_A\) means that the two coordinates are equal, so \(x=y\). Therefore \(y=x\), and hence \((y,x)\in\Delta_A\). Thus \(\Delta_A\) is symmetric. Finally, suppose \(x,y,z\in A\), with \((x,y)\in\Delta_A\) and \((y,z)\in\Delta_A\). The first membership gives \(x=y\), and the second gives \(y=z\). By transitivity of equality, \(x=z\), so \((x,z)\in\Delta_A\). Therefore \(\Delta_A\) is transitive, and all three properties hold. \(\square\)

A Reliable Verification Strategy

To prove that a relation is an equivalence relation, handle the three conditions separately. In particular, a symmetry proof begins with an arbitrary pair assumed to be in the relation and establishes that its reversal is in the relation. A transitivity proof begins with two related pairs that share the middle coordinate and derives the required pair joining the endpoints. Using arbitrary elements is what establishes the universal statements, rather than checking just a few selected pairs.

Congruence Modulo an Integer

A central example uses divisibility. For an integer \(m\geq 2\), two integers are congruent modulo \(m\) when their difference is divisible by \(m\). Here divisibility by \(m\) means that the difference equals \(mk\) for some integer \(k\). We use the notation \(x\equiv y\pmod m\). The domain matters: this relation is on \(\mathbb Z\), the set of integers.

Theorem (Congruence Modulo \(m\) Is an Equivalence Relation). Let \(m\geq2\) be an integer. On \(\mathbb Z\), define $$ x\equiv y\pmod m \quad\Longleftrightarrow\quad x-y=mk\text{ for some }k\in\mathbb Z. $$ This relation is an equivalence relation.

Proof. We verify each property. For any \(x\in\mathbb Z\), \(x-x=0=m\cdot0\), with \(0\in\mathbb Z\). Therefore \(x\equiv x\pmod m\), proving reflexivity. Suppose \(x\equiv y\pmod m\). Then \(x-y=mk\) for some \(k\in\mathbb Z\). It follows that $$ y-x=-(x-y)=-mk=m(-k). $$ Since \(-k\in\mathbb Z\), this proves \(y\equiv x\pmod m\), so the relation is symmetric. Now suppose \(x\equiv y\pmod m\) and \(y\equiv z\pmod m\). There are integers \(k,\ell\) such that \(x-y=mk\) and \(y-z=m\ell\). Adding these equations gives $$ x-z=(x-y)+(y-z)=mk+m\ell=m(k+\ell). $$ Because \(k+\ell\in\mathbb Z\), we have \(x\equiv z\pmod m\). The relation is transitive, and therefore it is an equivalence relation. \(\square\)

It is useful to separate a general proof from examples of individual membership. Showing that several pairs satisfy the congruence definition does not prove the relation is an equivalence relation. The theorem succeeds because it starts with arbitrary integers and verifies each required property for all of them.

Functions Give Equivalence Relations

A relation can identify inputs by comparing their outputs under a rule. Let \(A\) and \(B\) be sets, and let \(f\) be a rule that assigns to each \(x\in A\) a value \(f(x)\in B\) (functions are studied formally in a later tutorial). Define a relation on \(A\) by declaring \(x\sim_f y\) exactly when \(f(x)=f(y)\). This relation may relate distinct inputs, but it always has the three properties of an equivalence relation.

Theorem (Equal Function Values Define an Equivalence Relation). Let \(f:A\to B\) be a function, and define $$ x\sim_f y\quad\Longleftrightarrow\quad f(x)=f(y) $$ for \(x,y\in A\). Then \(\sim_f\) is an equivalence relation on \(A\).

Proof. Let \(x\in A\). Since \(f(x)=f(x)\), the definition gives \(x\sim_f x\). Thus the relation is reflexive. Suppose \(x,y\in A\) and \(x\sim_f y\). Then \(f(x)=f(y)\). By symmetry of equality, \(f(y)=f(x)\), so \(y\sim_f x\). Thus the relation is symmetric. Finally, suppose \(x,y,z\in A\), \(x\sim_f y\), and \(y\sim_f z\). These assumptions mean \(f(x)=f(y)\) and \(f(y)=f(z)\). By transitivity of equality, \(f(x)=f(z)\), so \(x\sim_f z\). The relation is transitive as well. Hence it is an equivalence relation on \(A\). \(\square\)

Failures and Common Misreadings

The three conditions are independent tests. A relation can satisfy some of them and fail another. For instance, the strict order relation \(x<y\) on \(\mathbb R\) is not reflexive: no real \(x\) satisfies \(x<x\). It is also not symmetric, since \(1<4\) but \(4<1\) is false. Either failure alone is enough to show that this relation is not an equivalence relation.

The relation \(x\leq y\) on \(\mathbb R\) is reflexive and transitive, but it is not symmetric. Indeed, \(1\leq2\), while \(2\leq1\) is false. This illustrates why checking only two of the three properties is insufficient. Similarly, a relation can be symmetric and reflexive but fail transitivity; every property must be checked on its own terms.

The domain is part of the claim. A relation might be considered on one set and not another, because reflexivity requires a diagonal pair for every element of that particular set. When a problem states that \(R\) is a relation on \(A\), all variables in the three tests range over \(A\). Do not silently replace \(A\) with a larger set, or test only the elements that happen to appear in a short list of pairs.

One useful consequence of symmetry can be stated using the inverse relation introduced in “Relations.” If \(R\) is an equivalence relation on \(A\), symmetry says every pair in \(R\) has its reversal in \(R\). Consequently, taking the inverse does not change the relation.

Proposition. If \(R\) is an equivalence relation on \(A\), then $$ R^{-1}=R. $$ Proof. Suppose \(R\) is an equivalence relation on \(A\). We prove the two inclusions. If \((x,y)\in R\), symmetry gives \((y,x)\in R\). By the definition of inverse, this means \((x,y)\in R^{-1}\). Therefore \(R\subseteq R^{-1}\). Conversely, suppose \((x,y)\in R^{-1}\). By the definition of inverse, \((y,x)\in R\). Symmetry then gives \((x,y)\in R\), so \(R^{-1}\subseteq R\). By equality by double inclusion, \(R^{-1}=R\). \(\square\)

This proposition uses symmetry; reflexivity and transitivity are not needed for this particular conclusion. Keeping track of which hypothesis justifies each step makes the proof both shorter and more precise.