Differences
This shows you the differences between two versions of the page.
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$. | ||