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