1. if $f$ and $g$ are injective then $g\circ f$ is injective,
2. if $f$ and $g$ are surjective then $g\circ f$ is surjective, and
3. if $f$ and $g$ are bijective then $g\circ f$ is bijective.

Let $f:S\to T$ be a function and let $U\subseteq S$. The image of $U$ under $f$ is the subset of $T$ given by $$f\left(U\right)=\left\{f\left(u\right)|u\in U\right\}\text{.}$$

Let $f:S\to T$ be a function. The image of $U$ under $f$ is the subset of $T$ given by $$\mathrm{im}U=\left\{f\left(s\right)|s\in S\right\}\text{.}$$ Note that $\mathrm{im}f=f\left(S\right)$.

Let $f:S\to T$ be a function and let $V\subseteq T$. The inverse image of $V$ under $f$ is the subset of $S$ given by $$f^{-1}\left(V\right)=\left\{s\in S|f\left(s\right)\in V\right\}\text{.}$$

Let $f:S\to T$ be a function and let $t\in T$. The fiber of $f$ over $t$ is the subset of $S$ given by $$f^{-1}\left(t\right)=\left\{s\in S|f\left(s\right)=t\right\}\text{.}$$

Let $f:S\to T$ be a function. Show that the set $F=\left\{f^{-1}\left(t\right)|t\in T\right\}$ of fibers of the map $f$ is a partition of $S$.

1. Let $f:S\to T$ be a function. Define $$\begin{array}{rcl}f\prime :S& ⟶& imf\\ s& ⟼& f\left(s\right)\text{.}\end{array}$$ Show that the map $f\prime$ is well defined and surjective.
2. Let $f:S\to T$ be a function and let $F=\left\{f^{-1}\left(t\right)|t\in \mathrm{im}f\right\}=\left\{f^{-1}\left(t\right)|t\in T\right\}\backslash \varnothing$ be the set of nonempty fibers of the map $f$. Define $$\begin{array}{rrcl}\hat{f}:& F& ⟶& T\\ & f^{-1}\left(t\right)& ⟼& t\end{array}\text{.}$$ Show that the map $\hat{f}$ is well defined and injective.
3. Let $f:S\to T$ be a function and let $F=\left\{f^{-1}\left(t\right)|t\in \mathrm{im}f\right\}=\left\{f^{-1}\left(t\right)|t\in T\right\}\backslash \varnothing$ be the set of nonempty fibers of the map $f$. Define $$\begin{array}{rrcl}\hat{f}\prime :& F& ⟶& \mathrm{im}T\\ & f^{-1}\left(t\right)& ⟼& t\end{array}\text{.}$$ Show that the map $\hat{f}\prime$ is well defined and bijective.

Let $S$ be a set. The power set of $S$, $2^S$, is the set of all subsets of $S$.

Let $S$ be a set and let ${\left\{0,1\right\}}^S$ be the set of all functions $f:S\to \left\{0,1\right\}$. Given a subset $T\subseteq S$ define a function $f_T:S\to \left\{0,1\right\}$ by $$f_T\left(s\right)=\left\{\begin{array}{ll}0\text{,}& \text{if }s\notin T\text{,}\\ 1\text{,}& \text{if }s\in T\text{.}\end{array}\right.$$

Show that the map $$\begin{array}{rcll}\psi :& 2^S& ⟶& {\left\{0,1\right\}}^S\\ & T& ⟼& f_T\end{array}$$ is a bijection.

Let $\circ :S\times S\to S$ be an associative operation on a set $S$. An identity for $\circ$ is an element $e\in S$ such that $e\circ s=s\circ e=s$ for all $s\in S$.

Let $e$ be an identity for an associative operation $\circ$ on a set $S$. Let $s\in S$. A left inverse for $s$ is an element $t\in S$ such that $t\circ s=e$. A right inverse for $s$ is an element $t\prime \in S$ such that $s\circ t\prime =e$. An inverse for $s$ is an element $s^{-1}\in S$ such that $s^{-1}\circ s=s\circ s^{-1}=e$.

1. Let $\circ$ be an operation on a set $S$. Show that if $S$ contains an identity for $\circ$ then it is unique.
2. Let $e$ be an identity for an associative operation $\circ$ on a set $S$. Let $s\in S$. Show that if $s$ has an inverse then it is then it is unique.

1. Let $S$ and $T$ be sets and let ${\iota }_S$ and ${\iota }_T$ be the identity maps on $S$ and $T$ respectively. Show that for any function $f:S\to T$, $$\begin{array}{c}{\iota }_T\circ f=f\text{,}\text{and}\\ f\circ {\iota }_S=f\text{.}\end{array}$$
2. Let $f:S\to T$ be a function. Show that if an inverse function to $f$ exists then it is unique. (Hint: The proof is very similar to the proof in Ex. 5b above.)

1. Assume $f$ and $g$ are injective.
2. To show: If $s_1,s_2\in S$ and $\left(g\circ f\right)\left(s_1\right)=\left(g\circ f\right)\left(s_2\right)$ then $s_1=s_2$.
   1. Assume $s_1,s_2\in S$ and $\left(g\circ f\right)\left(s_1\right)=\left(g\circ f\right)\left(s_2\right)$.
   2. Then $g\left(f\left(s_1\right)\right)=g\left(f\left(s_2\right)\right)$.
   3. Thus, since $g$ is injective, $f\left(s_1\right)=f\left(s_2\right)$
   4. Thus, since $f$ is injective, $s_1=s_2$.
3. So $g\circ f$ is injective.
4. $\square$
2. Assume $f$ and $g$ are surjective.
3. To show: If $u\in U$ then there exists $s\in S$ such that $\left(g\circ f\right)\left(s\right)=u$.
   1. Assume $u\in U$.
   2. Since $g$ is surjective there exists $t\in T$ such that $g\left(t\right)=u$.
   3. Since $f$ is surjective there exists $s\in S$ such that $f\left(s\right)=t$.
   4. So $$\begin{array}{rcl}\left(g\circ f\right)\left(s\right)& =& g\left(f\left(s\right)\right)\\ & =& g\left(t\right)\\ & =& u\text{.}\end{array}$$
   5. So there exists $s\in S$ such that $\left(g\circ f\right)\left(s\right)=u$.
4. So $g\circ f$ is surjective.
5. $\square$
3. Assume that $f$ and $g$ are bijective.
4. To Show:
   79. $g\circ f$ is injective.
   80. $g\circ f$ is surjective.
5. Proof:
   79. Since $f$ and $g$ are bijective, $f$ and $g$ are injective.
   80. Thus, by (a), $g\circ f$ is injective.
   79. Since $f$ and $g$ are bijective, $f$ and $g$ are surjective.
   80. Thus, by (b), $g\circ f$ is surjective.
6. So $g\circ f$ is bijective.
7. $\square$

1. If $s\prime \in S$ then $s\prime \in f^{-1}\left(t\right)$ for some $t\in T$.
2. If $f^{-1}\left(t_1\right)\cap f^{-1}\left(t_2\right)\ne \varnothing$ then $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.

1. Assume $s\prime \in S$.
2. Then $f^{-1}\left(f\left(s\prime \right)\right)=\left\{s\in S|f\left(s\right)=f\left(s\prime \right)\right\}$.
3. Since $f\left(s\prime \right)=f\left(s\prime \right)$, $s\prime \in f^{-1}\left(f\left(s\prime \right)\right)$.
2. Assume $f^{-1}\left(t_1\right)\cap f^{-1}\left(t_2\right)\ne \varnothing$.
3. Let $s\in f^{-1}\left(t_1\right)\cap f^{-1}\left(t_2\right)$.
4. So $f\left(s\right)=t_1$ and $f\left(s\right)=t_2$
5. To show: $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
   1. To show:
      53. $f^{-1}\left(t_1\right)\subseteq f^{-1}\left(t_2\right)$.
      54. $f^{-1}\left(t_2\right)\subseteq f^{-1}\left(t_1\right)$.
   2. Proof:
      53. Let $k\in f^{-1}\left(t_1\right)$.
      54. Then $f\left(k\right)=t_1=f\left(s\right)=t_2$.
      55. So $k\in f^{-1}\left(t_2\right)$.
      56. So $f^{-1}\left(t_1\right)\subseteq f^{-1}\left(t_2\right)$.
      54. Let $h\in f^{-1}\left(t_2\right)$.
      55. Then $f\left(h\right)=t_2=f\left(s\right)=t_1$.
      56. So $h\in f^{-1}\left(t_1\right)$.
      57. So $f^{-1}\left(t_2\right)\subseteq f^{-1}\left(t_1\right)$.
6. So $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.

1. To show:
   27. $f\prime$ is well defined.
   28. $f\prime$ is surjective.
2. Proof:
   27. To Show:
       703. If $s\in S$ then $f\prime \left(s\right)\in \mathrm{im}f$.
       704. If $s_1=s_2$ then $f\prime \left(s_1\right)=f\prime \left(s_2\right)$.
   28. Proof:
       703. Assume $s\in S$.
       704. Then $f\prime \left(s\right)=f\left(s\right)\in \mathrm{im}f$ by definition of $f\prime$ and $\mathrm{im}f$.
       704. Assume $s_1=s_2$.
       705. Then, by definition of $f\prime$, $$f\prime \left(s_1\right)=f\left(s_1\right)=f\left(s_2\right)=f\prime \left(s_2\right)\text{.}$$
   29. So $f\prime$ is well defined.
   28. To show: If $t\in \mathrm{im}f$ then there exists $s\in S$ such that $f\prime \left(s\right)=t$.
   29. 1. Assume $t\in \mathrm{im}f$.
       2. Then $f\left(s\right)=t$ for some $s\in S$.
       3. So $f\prime \left(s\right)=f\left(s\right)=t$.
   30. So $f\prime$ is surjective.
3. $\square$
2. To show:
   53. $\hat{f}$ is well defined.
   54. $\hat{f}$ is injective.
3. Proof:
   53. To show:
       1379. If $f^{-1}\left(t\right)\in F$ then $\hat{f}\left(f^{-1}\left(t\right)\right)\in T$.
       1380. If $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$ then $\hat{f}\left(f^{-1}\left(t_1\right)\right)=\hat{f}\left(f^{-1}\left(t_2\right)\right)$.
   54. Proof:
       1379. Assume $f^{-1}\left(t\right)\in F$.
       1380. Then $\hat{f}\left(f^{-1}\left(t\right)\right)=t\in T$, by definition.
       1380. Assume $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
       1381. Let $s\in f^{-1}\left(t_1\right)$.
       1382. Then $s\in f^{-1}\left(t_2\right)$ also.
       1383. So $t_1=s=t_2$.
       1384. Then $$\hat{f}\left(f^{-1}\left(t_1\right)\right)=t_1=t_2=\hat{f}\left(f^{-1}\left(t_2\right)\right)\text{.}$$
   55. So $\hat{f}$ is well defined.
   54. To Show: If $\hat{f}\left(f^{-1}\left(t_1\right)\right)=\hat{f}\left(f^{-1}\left(t_2\right)\right)$ then $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
       1. Assume $\hat{f}\left(f^{-1}\left(t_1\right)\right)=\hat{f}\left(f^{-1}\left(t_2\right)\right)$.
       2. Then $t_1=t_2$.
       3. To show: $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
          1. This is clearly true since $t_1=t_2$.
   55. So $\hat{f}$ is injective.
4. $\square$
3. By part (b) above, the function $$\begin{array}{rcl}\hat{f}:F& ⟶& T\\ f^{-1}\left(t\right)& ⟼& t\end{array}$$ is well defined and surjective.
4. By part (a) above, the function $$\begin{array}{rcl}\hat{f}\prime :F& ⟶& \mathrm{im}\hat{f}\\ f^{-1}\left(t\right)& ⟼& t\end{array}$$ is well defined and surjective.
5. To show:
   79. $\mathrm{im}\hat{f}=\mathrm{im}f$.
   80. $\hat{f}\prime$ is injective.
6. Proof:
   79. To Show:
       2055. $\mathrm{im}\hat{f}\subseteq \mathrm{im}f$.
       2056. $\mathrm{im}f\subseteq \mathrm{im}\hat{f}$.
   80. Proof:
       2055. Assume $t\in \mathrm{im}\hat{f}$.
       2056. Then $f^{-1}\left(t\right)$ is nonempty.
       2057. So there exists $s\in S$ such that $f\left(s\right)=t$.
       2058. So $t\in \mathrm{im}f$.
       2059. So $\mathrm{im}\hat{f}\subseteq \mathrm{im}f$.
       2056. Assume $t\in \mathrm{im}f$.
       2057. Then there exists $s\in S$ such that $f\left(s\right)=t$.
       2058. So $f^{-1}\left(t\right)\ne \varnothing$.
       2059. So $t\in \mathrm{im}\hat{f}$.
       2060. So $\mathrm{im}f\subseteq \mathrm{im}\hat{f}$.
   81. So $\mathrm{im}\hat{f}=\mathrm{im}f$.
   80. To show: If $\hat{f}\prime \left(f^{-1}\left(t_1\right)\right)=\hat{f}\prime \left(f^{-1}\left(t_2\right)\right)$ then $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
       1. Assume $\hat{f}\prime \left(f^{-1}\left(t_1\right)\right)=\hat{f}\prime \left(f^{-1}\left(t_2\right)\right)$.
       2. So $t_1=t_2$.
       3. So $f^{-1}\left(t_1\right)=f^{-1}\left(t_2\right)$.
   81. So $\hat{f}\prime$ is injective.
7. So $\hat{f}\prime$ is well defined and bijective.
8. $\square$

1. $\psi$ is well defined.
2. $\psi$ is bijective.

1. To show:
   27. If $T\in 2^S$ then $\psi \left(T\right)=f_T\in {\left\{0,1\right\}}^S$.
   28. If $T_1$ and $T_2$ are subsets of $S$ and $T_1=T_2$ then $\psi \left(T_1\right)=\psi \left(T_2\right)$.
2. Proof:
3. 27. It is clear from the definition of $f_T$ that $\psi \left(T\right)=f_T$ is a function from $S$ to $\left\{0,1\right\}$.
   28. Assume $T_1$ and $T_2$ are subsets of $S$ and that $T_1=T_2$.
   29. To show: $\psi \left(T_1\right)=\psi \left(T_2\right)$.
       1. To show: $f_{T_1}=f_{T_2}$.
          1. To show: If $s\in S$ then $f_{T_1}\left(s\right)=f_{T_2}\left(s\right)$.
             1. Assume $s\in S$.
             2. Case 1:
                1. If $s\in T_1$ then, since $T_1=T_2$, $s\in T_2$.
                2. So $f_{T_1}\left(s\right)=1=f_{T_2}\left(s\right)$.
             3. Case 2:
                1. If $s\notin T_1$ then, since $T_1=T_2$, $s\notin T_2$.
                2. So $f_{T_1}\left(s\right)=0=f_{T_2}\left(s\right)$.
          2. So $f_{T_1}\left(s\right)=f_{T_2}\left(s\right)$ for all $s\in S$.
       2. So $f_{T_1}=f_{T_2}$.
   30. So $\psi \left(T_1\right)=f_{T_1}=f_{T_2}=\psi \left(T_2\right)$.
4. So $\psi$ is well defined.
2. By virtue of Proposition 2.2.3 [??? - CORRECT?] we would like to show:
3. $\psi :2^S\to {\left\{0,1\right\}}^S$ has an inverse function.
4. Given a function $f:s\to \left\{0,1\right\}$ define $$T_f=\left\{s\in S|f\left(s\right)=1\right\}\text{.}$$
5. Define a function $\varphi :{\left\{0,1\right\}}^S\to 2^S$ by $$\begin{array}{rcl}\varphi :{\left\{0,1\right\}}^S& ⟶& 2^S\\ f& ⟼& T_f\text{.}\end{array}$$
6. To Show:
   53. $\varphi$ is well defined.
   54. $\varphi$ is an inverse function to $\psi$.
7. Proof:
   53. To show:
       1379. If $f\in {\left\{0,1\right\}}^S$ then $\varphi \left(f\right)=T_f\in 2^S$.
       1380. If $f_1,f_2\in {\left\{0,1\right\}}^S$ and $f_1=f_2$ then $\varphi \left(f_1\right)=\varphi \left(f_2\right)$.
   54. Proof:
       1379. By definition $T_f=\left\{s\in s|f\left(s\right)=1\right\}$ is a subset of $S$.
       1380. Assume $f_1,f_2\in {\left\{1,2\right\}}^S$ and $f_1=f_2$.
       1381. To show: $\varphi \left(f_1\right)=\varphi \left(f_2\right)$.
             1. To show: $T_{f_1}=T_{f_2}$.
             2. 1. To Show:
                   35881. $T_{f_1}\subseteq T_{f_2}$.
                   35882. $T_{f_1}\subseteq T_{f_2}$.
             3. 1. Proof:
                   35881. Assume $s\in T_{f_1}$.
                   35882. Then $f_1\left(s\right)=1$.
                   35883. Since $f_2\left(s\right)=f_1\left(s\right)$, $f_2\left(s\right)=1$.
                   35884. Thus $s\in T_{f_2}$.
                   35885. So, $T_{f_1}\subseteq T_{f_2}$
                   35882. Assume $s\in T_{f_2}$.
                   35883. Then $f_2\left(s\right)=1$.
                   35884. Since $f_1\left(s\right)=f_2\left(s\right)$, $f_1\left(s\right)=1$.
                   35885. Thus $s\in T_{f_1}$.
                   35886. So, $T_{f_2}\subseteq T_{f_1}$
             4. So $T_{f_1}=T_{f_2}$.
       1382. So $\varphi \left(f_1\right)=\varphi \left(f_2\right)$.
   55. So $\varphi$ is well defined.
   54. To Show:
       1405. If $T\in 2^S$ then $\varphi \left(\psi \left(T\right)\right)=T$.
       1406. If $f\in {\left\{0,1\right\}}^S$ then $\psi \left(\varphi \left(f\right)\right)=f$.
   55. Proof:
       1405. Assume $T\subseteq S$.
       1406. To show: $\varphi \left(\psi \left(T\right)\right)=T$
             1. To show: $T_{f_T}=T$.
             2. To Show:
                36531. $T_{f_T}\subseteq T$.
                36532. $T\subseteq T_{f_T}$.
             3. Proof:
                36531. Assume $t\in T_{f_T}$.
                36532. Then $f_T\left(t\right)=1$.
                36533. So $t\in T$.
                36534. So $T_{f_T}\subseteq T$.
                36532. Assume $t\in T$.
                36533. Then $f_T\left(t\right)=1$.
                36534. So $t\in T_{f_T}$.
                36535. So $T\subseteq T_{f_T}$.
             4. So $T_{f_T}=T$.
       1407. So $\varphi \left(\psi \left(T\right)\right)=T$
       1406. Assume $f\in {\left\{0,1\right\}}^S$.
       1407. To show: $\varphi \left(\psi \left(f\right)\right)=f$.
             1. By definition, $\psi \left(\varphi \left(f\right)\right)=f_{T_f}$.
             2. To show: If $s\in S$ then $f_{T_f}\left(s\right)=f\left(s\right)$.
                1. Assume $s\in S$.
                2. Case 1: $f\left(s\right)=1$.
                   1. Then $s\in T_f$.
                   2. So $f_{T_f}=1$.
                   3. So $f_{T_f}=f\left(s\right)$.
                3. Case 2: $f\left(s\right)=0$.
                   1. Then $s\notin T_f$.
                   2. So $f_{T_f}=0$.
                   3. So $f_{T_f}=f\left(s\right)$.
             3. So $f_{T_f}\left(s\right)=f\left(s\right)$.
       1408. So $\psi \left(\varphi \left(f\right)\right)=f$.
   56. So $\varphi$ is an inverse function to $\psi$.
8. So $\psi$ is bijective.
9. $\square$

1. Let $e,e\prime \in S$ be identities for $\circ$.
2. Then $e\circ e\prime =e$, since $e\prime$ is an identity, and $e\circ e\prime =e\prime$, since $e$ is an identity.
3. So, $e=e\prime$.
2. Let $t,u\in S$ be inverses for $s$.
3. By associativity of $\circ$, $u=\left(t\circ s\right)\circ u=t\circ \left(s\circ u\right)=t$.
4. $\square$

1. Assume $f:S\to T$ is a function.
2. To show:
   27. ${\iota }_T\circ f=f$.
   28. $f\circ {\iota }_T=f$.
3. Proof:
   27. If $s\in S$ then ${\iota }_T\left(f\left(s\right)\right)=f\left(s\right)$.
   28. If $s\in S$ then $f\left({\iota }_S\left(s\right)\right)=f\left(s\right)$.
4. (aa) and (ab) follow immediately from the definitions of ${\iota }_T$ and ${\iota }_S$.
2. Assume $\varphi$ and $\psi$ are both inverse functions to $f$.
3. To show: $\varphi =\psi$.
4. By the definitions of identity and inverse functions $$\varphi =\varphi \circ \left(f\circ \psi \right)=\left(\varphi \circ f\right)\circ \psi =\psi \text{.}$$
5. So, if an inverse functions exists, then it is unique.
6. $\square$