LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
equivalence_relation [2007/03/30 20:36]
vkuncak
equivalence_relation [2007/03/30 20:45]
vkuncak
Line 1: Line 1:
 ====== Equivalence relation ====== ====== Equivalence relation ======
  
-An equivalence relation $\sim$ is a binary relation on set $A$ (that is, a subset of $A^2$) that is reflexive, ​symmatric, and transitive, that is, the following three properties hold:+An equivalence relation $\sim$ is a binary relation on set $A$ (that is, a subset of $A^2$) that is reflexive, ​symmetric, and transitive, that is, the following three properties hold:
  
   * $x \sim x$   * $x \sim x$
Line 8: Line 8:
  
   * $x \sim y\ \land\ y \sim z\ \rightarrow\ x \sim z$   * $x \sim y\ \land\ y \sim z\ \rightarrow\ x \sim z$
 +
 +Given an equivalence relation $\sim$, we define the set of equivalence classes $A_{/\sim}$ by
 +\begin{equation*}
 +  A_{/\sim} = \{ \{y \mid x \sim y\} \mid x \in A \}
 +\end{equation*}
 +
 +The equivalence classes of a non-empty set form a [[partition]] of $A$.  ​
 +
 +Conversely, given a [[partition]] $P \subseteq 2^A$ of set $A$, the relation defined by 
 +\begin{equation*}
 +  x \sim y\ \iff\ \exists S \in P. \{x,y\} \subseteq S
 +\end{equation*}
 +is an equivalence relation such that $A_{/\sim} = P$.