Equivalence Relation

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.)

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