Equivalence relation

An equiv­alence re­la­tion is a bi­nary re­la­tion $$\sim$$ on a set $$S$$ that can be used to say whether el­e­ments of $$S$$ are equiv­a­lent.

An equiv­alence re­la­tion satis­fies the fol­low­ing prop­er­ties:

1. For any $$x \in S$$, $$x \sim x$$ (the re­flex­ive prop­erty).

2. For any $$x,y \in S$$, if $$x \sim y$$ then $$y \sim x$$ (the sym­met­ric prop­erty).

3. For any $$x,y,z \in S$$, if $$x \sim y$$ and $$y \sim z$$ then $$x \sim z$$ (the tran­si­tive prop­erty).

In­tu­itively, any el­e­ment is equiv­a­lent to it­self, equiv­alence isn’t di­rec­tional, and if two el­e­ments are equiv­a­lent to the same third el­e­ment then they’re equiv­a­lent.

Equiv­alence classes

When­ever we have a set $$S$$ with an equiv­alence re­la­tion $$\sim$$, we can di­vide $$S$$ into equiv­alence classes, i.e. sets of mu­tu­ally equiv­a­lent el­e­ments. The equiv­alence class of some $$x \in S$$ is the set of el­e­ments of $$S$$ equiv­a­lent to $$x$$, writ­ten $$[x]=\{y \in S \mid x \sim y\}$$, and we say that $$x$$ is a “rep­re­sen­ta­tive” of $$[x]$$. We call the set of equiv­alence classes $$S/\sim = \{[x] \mid x \in S\}$$.

From the defi­ni­tion of an equiv­alence re­la­tion, 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 par­ti­tioned into sub­sets ($$S$$ is the dis­joint union of the el­e­ments of a col­lec­tion $$A$$), you can go the other way and define a re­la­tion with two el­e­ments re­lated when­ever they’re in the same sub­set ($$x \sim y$$ when there is some $$U \in A$$ with $$x,y \in U$$). Then this is an equiv­alence re­la­tion, and the par­ti­tion of the set is the set of equiv­alence classes un­der this re­la­tion (that is, $$[x] \in A$$ and $$A=S/\sim$$).

Defin­ing func­tions on equiv­alence classes

Sup­pose you have a func­tion $$f: S \to U$$ and want to define a cor­re­spond­ing func­tion $$f^*: S/\sim \to U$$, where $$U$$ can be any set. You define $$f^*([x])$$ to be $$f(x)$$. This could be a prob­lem; what if $$x \sim y$$ but $$f(x) \neq f(y)$$? Then $$f^*([x])=f^*([y])$$ wouldn’t be well-defined. When­ever you define a func­tion on equiv­alence classes in terms of rep­re­sen­ta­tives, you have to make sure the defi­ni­tion doesn’t de­pend on which rep­re­sen­ta­tive you hap­pen to pick. In fact, one way you might ar­rive at an equiv­alence re­la­tion is to say that $$x \sim y$$ when­ever $$f(x)=f(y)$$.

If you have a func­tion $$f: S \to S$$ and want to define $$f^*: S/\sim \to S/\sim$$ by $$f^*([x])=[f(x)]$$, you have to ver­ify that when­ever $$x \sim y$$, $$[f(x)]=[f(y)]$$, equiv­a­lently $$f(x) \sim f(y)$$.

Examples

Con­sider the in­te­gers with the re­la­tion $$x \sim y$$ if $$n|x-y$$, for some $$n \in \mathbb N$$. This is the in­te­gers mod $$n$$. The ad­di­tion and mul­ti­pli­ca­tion op­er­a­tions can be in­her­ited from the in­te­gers, so it makes sense to talk about ad­di­tion and mul­ti­pli­ca­tion mod $$n$$.

The real num­bers can be defined as equiv­alence classes of Cauchy se­quences.

Iso­mor­phism is an equiv­alence re­la­tion (un­less the ob­jects form a proper class).

Parents: