## Sets and functions proofs

Last update: 15 May 2012

## Sets and functions

(a)   Let $S$ be a set and let $\sim$ be an equivalence relation on $S$. Then the set of equivalence classes of the relation $\sim$ is a partition of $S$.
(b)   Let $S$ be a set and let $\left\{{S}_{\alpha }\right\}$ be a partition of $S$. Then the relation defined by $s∼t if s and t are in the same Sα$ is an equivalence relation on $S$.

 Proof. (a) To show: (aa) If $s\in S$ then $s$ is in some equivalence class. $\phantom{\text{(a)}}$ $\phantom{\text{To show:}}$ (ab) If $\left[s\right]\cap \left[t\right]\ne \varnothing$ then $\left[s\right]=\left[t\right]$. $\phantom{\text{(a)}}$ (aa) Let $s\in S$. $\phantom{\text{(a)}}$ $\phantom{\text{(aa)}}$ Since $s\sim s$, $s\in \left[s\right]$. $\phantom{\text{(a)}}$ (ab) Assume $\left[s\right]\cap \left[t\right]\ne \varnothing$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ To show: $\left[s\right]=\left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Since $\left[s\right]\cap \left[t\right]\ne \varnothing$, there is an $r\in \left[s\right]\cap \left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ So $s\sim r$ and $r\sim t$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ By transitivity, $s\sim t$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ To show: (aba) $\left[s\right]\subseteq \left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{To show:}}$ (abb) $\left[t\right]\subseteq \left[s\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ (aba) Suppose $u\in \left[s\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(aba)}}$ Then $u\sim s$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(aba)}}$ We know $s\sim t$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(aba)}}$ So, by transitivity, $u\sim t$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(aba)}}$ Therefore $u\in \left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ So $\left[s\right]\subseteq \left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ (abb) Suppose $v\in \left[t\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(abb)}}$ Then $v\sim t$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(abb)}}$ We know $t\sim s$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(abb)}}$ So, by transitivity, $v\sim s$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ $\phantom{\text{(abb)}}$ Therefore $v\in \left[s\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ So $\left[t\right]\subseteq \left[s\right]$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ So $\left[s\right]=\left[t\right]$. So the equivalence classes partition $S$. (b) We must show that $\sim$ is an equivalence relation, i.e. that $\sim$ is reflexive, symmetric, and transitive. $\phantom{\text{(b)}}$ To show: (ba) If $s\in S$ then $s\sim s$. $\phantom{\text{(b)}}$ $\phantom{\text{To show:}}$ (bb) If $s\sim t$ then $t\sim s$. $\phantom{\text{(b)}}$ $\phantom{\text{To show:}}$ (bc) If $s\sim t$ and $t\sim u$ then $s\sim u$. $\phantom{\text{(b)}}$ (ba) Since $s$ and $s$ are in the same ${S}_{\alpha }$, $s\sim s$. $\phantom{\text{(b)}}$ (bb) Assume $s\sim t$. $\phantom{\text{(b)}}$ $\phantom{\text{(bb)}}$ Then $s$ and $t$ are in the same ${S}_{\alpha }$. $\phantom{\text{(b)}}$ So $t\sim s$. $\phantom{\text{(b)}}$ (bc) Assume $s\sim t$ and $t\sim u$. $\phantom{\text{(b)}}$ $\phantom{\text{(bc)}}$ Then $s$ and $t$ are in the same ${S}_{\alpha }$ and $t$ and $u$ are in the same ${S}_{\alpha }$. $\phantom{\text{(b)}}$ So $s\sim u$. So $\sim$ is an equivalence relation. $\square$

Let $f:S\to T$ be a function. An inverse function to $f$ exists if and only if $f$ is bijective.

 Proof. $⇒$ Assume $f:S\to T$ has an inverse function ${f}^{-1}:T\to S$. $\phantom{⇒}$ To show: (a) $f$ is injective. $\phantom{⇒}$ $\phantom{\text{To show:}}$ (b) $f$ is surjective. $\phantom{⇒}$ (a) Assume $f\left({s}_{1}\right)=f\left({s}_{2}\right)$. $\phantom{⇒}$ $\phantom{\text{(a)}}$ To show: ${s}_{1}={s}_{2}$. $s1 = f-1 (f(s1)) = f-1 (f(s2)) = s2.$ $\phantom{⇒}$ So $f$ is injective. $\phantom{⇒}$ (b) Let $t\in T$. $\phantom{⇒}$ $\phantom{\text{(b)}}$ To show: There exists $s\in S$ such that $f\left(s\right)=t$. $\phantom{⇒}$ $\phantom{\text{(b)}}$ Let $s={f}^{-1}\left(t\right)$. $\phantom{⇒}$ $\phantom{\text{(b)}}$ Then $f(s) =f(f-1(t) )=t.$ $\phantom{⇒}$ So $f$ is surjective. So $f$ is bijective. $⇐$ Assume $f:S\to T$ is bijective. $\phantom{⇐}$ To show: $f$ has an inverse function. $\phantom{⇐}$ We need to define a function $\phi :T\to S$. $\phantom{⇐}$ Let $t\in T$. $\phantom{⇒}$ Since $f$ is surjective there exists $s\in S$ such that $f\left(s\right)=t$. $\phantom{⇐}$ Define $\phi \left(t\right)=s$. $\phantom{⇐}$ To show: (a) $\phi$ is well defined. $\phantom{⇐}$ $\phantom{\text{To show:}}$ (b) $\phi$ is an inverse function to $f$. $\phantom{⇐}$ (a) To show: (aa) If $t\in T$ then $\phi \left(t\right)\in S$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ $\phantom{\text{To show:}}$ (ab) If ${t}_{1},{t}_{2}\in T$ and ${t}_{1}={t}_{2}$ then $\phi \left({t}_{1}\right)=\phi \left({t}_{2}\right)$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ (aa) This follows from the definition of $\phi$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ (ab) Assume ${t}_{1},{t}_{2}\in T$ and ${t}_{1}={t}_{2}$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Let ${s}_{1},{s}_{2}\in S$ such that $f\left({s}_{1}\right)={t}_{1}$ and $f\left({s}_{2}\right)={t}_{2}$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Since ${t}_{1}={t}_{2}$, $f\left({s}_{1}\right)=f\left({s}_{2}\right)$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Since $f$ is injective this implies that ${s}_{1}={s}_{2}$. $\phantom{⇐}$ $\phantom{\text{(a)}}$ So $\phi \left({t}_{1}\right)={s}_{1}={s}_{2}=\phi \left({t}_{2}\right)$. $\phantom{⇐}$ So $\phi$ is well defined. $\phantom{⇐}$ (b) To show: (ba) If $s\in S$ then $\phi \left(f\left(s\right)\right)=s$. $\phantom{⇐}$ $\phantom{\text{(b)}}$ $\phantom{\text{To show:}}$ (bb) If $t\in T$ then $f\left(\phi \left(t\right)\right)=t$. $\phantom{⇐}$ $\phantom{\text{(b)}}$ (ba) This follows from the definition of $\phi$. $\phantom{⇐}$ $\phantom{\text{(b)}}$ (bb) Assume $t\in T$. $\phantom{⇐}$ $\phantom{\text{(b)}}$ $\phantom{\text{(bb)}}$ Let $s\in S$ be such that $f\left(s\right)=t$. $\phantom{⇐}$ $\phantom{\text{(b)}}$ $\phantom{\text{(bb)}}$ Then $f(φ(t)) =f(s)=t.$ $\phantom{⇐}$ $\phantom{\text{(b)}}$ So $\phi \circ f$ and $f\circ \phi$ are the identity functions on $S$ and $T$, respectively. So $\phi$ is an inverse function to $f$. $\square$

## References

[Ra] A. Ram, Lecture notes in abstract algebra, University of Wisconsin, 1994 MR?????