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: