Equivalence relation


by Dylan Hendrickson Jul 5 2016 updated Jul 7 2016

A relation that allows you to partition a set into equivalence classes.

[summary: An equivalence relation is a binary Relation that is reflexive, [symmetric_relation symmetric], and transitive. You can think of it as a way to say when two elements of a Set are "the same" or "equivalent," despite not being literally the same element. It can be used to [set_partition partition] a set into equivalence classes.]

An equivalence relation is a binary Relation $~$\sim$~$ on a Set $~$S$~$ that can be used to say whether [element_of_a_set elements] of $~$S$~$ are equivalent.

An equivalence relation satisfies the following properties:

  1. For any $~$x \in S$~$, $~$x \sim x$~$ (the reflexive property).
  2. For any $~$x,y \in S$~$, if $~$x \sim y$~$ then $~$y \sim x$~$ (the [symmetric_relation symmetric] property).
  3. For any $~$x,y,z \in S$~$, if $~$x \sim y$~$ and $~$y \sim z$~$ then $~$x \sim z$~$ (the transitive property).

Intuitively, any element is equivalent to itself, equivalence isn't directional, and if two elements are equivalent to the same third element then they're equivalent.

Equivalence classes

Whenever we have a set $~$S$~$ with an equivalence relation $~$\sim$~$, we can divide $~$S$~$ into equivalence classes, i.e. sets of mutually equivalent elements. The equivalence class of some $~$x \in S$~$ is the set of elements of $~$S$~$ equivalent to $~$x$~$, written $~$[x]=\{y \in S \mid x \sim y\}$~$, and we say that $~$x$~$ is a "representative" of $~$[x]$~$. We call the set of equivalence classes $~$S/\sim = \{[x] \mid x \in S\}$~$.

From the definition of an equivalence relation, it's easy to show that $~$x \in [x]$~$ and $~$[x]=[y]$~$ if and only if $~$x \sim y$~$.

If you have a set already [set_partition partitioned] into subsets ($~$S$~$ is the [-disjoint_union] of the elements of a collection $~$A$~$), you can go the other way and define a relation with two elements related whenever they're in the same subset ($~$x \sim y$~$ when there is some $~$U \in A$~$ with $~$x,y \in U$~$). Then this is an equivalence relation, and the partition of the set is the set of equivalence classes under this relation (that is, $~$[x] \in A$~$ and $~$A=S/\sim$~$).

Defining functions on equivalence classes

Suppose you have a Function $~$f: S \to U$~$ and want to define a corresponding function $~$f^*: S/\sim \to U$~$, where $~$U$~$ can be any set. You define $~$f^*([x])$~$ to be $~$f(x)$~$. This could be a problem; what if $~$x \sim y$~$ but $~$f(x) \neq f(y)$~$? Then $~$f^*([x])=f^*([y])$~$ wouldn't be well-defined. Whenever you define a function on equivalence classes in terms of representatives, you have to make sure the definition doesn't depend on which representative you happen to pick. In fact, one way you might arrive at an equivalence relation is to say that $~$x \sim y$~$ whenever $~$f(x)=f(y)$~$.

If you have a function $~$f: S \to S$~$ and want to define $~$f^*: S/\sim \to S/\sim$~$ by $~$f^*([x])=[f(x)]$~$, you have to verify that whenever $~$x \sim y$~$, $~$[f(x)]=[f(y)]$~$, equivalently $~$f(x) \sim f(y)$~$.


Consider the integers with the relation $~$x \sim y$~$ if $~$n|x-y$~$, for some $~$n \in \mathbb N$~$. This is the integers mod $~$n$~$. The [-addition] and [-multiplication] operations can be inherited from the integers, so it makes sense to talk about addition and multiplication mod $~$n$~$.

The real numbers can be defined as equivalence classes of Cauchy sequences.

Isomorphism is an equivalence relation (unless the objects form a [-proper_class]).