Equivalence Relations

Definition 39   An equivalence relation on A is a symmetric, reflexive, transitive relation.

Proposition 4.17   For any relation R there is a smallest equivalence relation containing R

Definition 40   A partition of a set A is a set of subsets of A, $P=\{A_\lambda\vert\lambda\in \Lambda\}$, such that

1.

No $A_\lambda$ is empty

2.

$${\bigcup_{\lambda\in \Lambda}A_\lambda=A}$$

3.

If $\lambda \neq \kappa$ then $A_\lambda \cap A_\kappa =\emptyset$.

Proposition 4.18   Any partition P determines an equivalence relation $\equiv_P$ with $a\equiv_P b$ if and only if a and b are in the same element of P.

Proposition 4.19   Any equivalence relation R on a set A determines a partition A/R consisting of sets of the form $[x]=\{a\vert aRx\}$.

Proposition 4.20   If P is a partition then $A/{\equiv_P}=P$.

Proposition 4.21   If R is an equivalence relation then $\equiv_{A/R}=R$.

Proposition 4.22   If $f:A\to B$ is a function then there is an equivalence relation given by $a \equiv_f a'$ if and only if f(a)=f(a').

Proposition 4.23   If R is an equivalence relation on A then the function $[]:A\to A/R$ with [](a)=[a] is onto. Furthermore, all onto functions can be thought of as arising in this way.

Proposition 4.24   If $f:A\to B$ then the relation $\equiv_f$ on A given by $\{(a,a')\vert f(a)=f(a')\}$ is an equivalence relation. Furthermore, we can define a function $m:A/\equiv_f\to B$ by m([a])=f(a) and mwill be monic.

Corollary 4.25   Every function $f:A\to B$ can be written as $f=m\circ e$where e is epimorphic and m is monomorphic.