Sets and functions proofs

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

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 ${S_{α}}$ be a partition of $S$ . Then the relation defined by $s \sim 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. (ab) If $[s] \cap [t] \neq \emptyset$ then $[s] = [t]$ . (aa) Let $s \in S$ . Since $s \sim s$ , $s \in [s]$ . (ab) Assume $[s] \cap [t] \neq \emptyset$ . To show: $[s] = [t]$ . Since $[s] \cap [t] \neq \emptyset$ , there is an $r \in [s] \cap [t]$ . So $s \sim r$ and $r \sim t$ . By transitivity, $s \sim t$ . To show: (aba) $[s] \subseteq [t]$ . (abb) $[t] \subseteq [s]$ . (aba) Suppose $u \in [s]$ . Then $u \sim s$ . We know $s \sim t$ . So, by transitivity, $u \sim t$ . Therefore $u \in [t]$ . So $[s] \subseteq [t]$ . (abb) Suppose $v \in [t]$ . Then $v \sim t$ . We know $t \sim s$ . So, by transitivity, $v \sim s$ . Therefore $v \in [s]$ . So $[t] \subseteq [s]$ . So $[s] = [t]$ . 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. To show: (ba) If $s \in S$ then $s \sim s$ . (bb) If $s \sim t$ then $t \sim s$ . (bc) If $s \sim t$ and $t \sim u$ then $s \sim u$ . (ba) Since $s$ and $s$ are in the same $S_{α}$ , $s \sim s$ . (bb) Assume $s \sim t$ . Then $s$ and $t$ are in the same $S_{α}$ . So $t \sim s$ . (bc) Assume $s \sim t$ and $t \sim u$ . Then $s$ and $t$ are in the same $S_{α}$ and $t$ and $u$ are in the same $S_{α}$ . So $s \sim u$ . So $\sim$ is an equivalence relation. $□$

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

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

References

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

page history