Equivalence Relation

Return to Glossary.

Formal Definition


An equivalence relation $\mathcal{R}$ on a set $S$ is a relation that satisfies the following properties:

1. Reflexive: x$\mathcal{R}$x for all x$\in$$S$
2. Symmetric: If x$\mathcal{R}$y, then y$\mathcal{R}$x.
3. Transitive: If x$\mathcal{R}$y and y$\mathcal{R}$z then x$\mathcal{R}$z.

Informal Definition


The relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of the set is a member of one and only one cell of the partition.

Example(s)


Let the set {a, b, c} have the equivalence relation
{(a,a), (b,b), (c,c) (b,c), (c,b)}.

The following sets are equivalence classes of this relation:
[a] = {a}, [b] = [c] = {b,c}.

The set of all equivalence classes for this relation is
{ {a}, {b,c} }.

Non-example(s)


  • The relation $\geq$ between real numbers is reflexive and transitive, but not symmetric. For example, 7$\geq$5 does not imply that 5$\geq$7.
  • The empty relation $\mathcal{R}$ on a non-empty set $X$ is symmetric but not reflexive. (If $X$ is also empty then $\mathcal{R}$ is reflexive.)

Additional Comments


The following are considered equivalence relations:

  • "is equal to" on the set of real numbers
  • "has the same birthday as" on the set of all people
  • "is congruent to, modulo n" on the integers
  • "has the same image under a function" on the elements of the domain of the function
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License