Equivalence Relations

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

Proposition 67   For any relation $R$ there is a smallest equivalence relation containing $R$

(3 Points )

Definition 47   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 68   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$.

(3 Points )

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

(3 Points )

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

(2 Points )

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

(2 Points )

Proposition 72   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')$.

(3 Points )

Proposition 73   If $R$ is an equivalence relation on $A$ then the function

$$[ ]:A\to A/R\mbox{ with }[ ](a)=[a]$$

is onto. Furthermore, all onto functions can be thought of as arising in this way.

(4 Points )

Proposition 74   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 $m$ will be monic.

(4 Points )

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

(2 Points )

Total for section: 58.