Solutions to Sets and Functions Problems

## Solutions to Sets and Functions Problems

 Let $S$, $T$ and $U$ be sets and let $f:S\to T$ and $g:T\to U$ be functions. Show that if $f$ and $g$ are injective then $g\circ f$ is injective, if $f$ and $g$ are surjective then $g\circ f$ is surjective, and 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 U = f u | u ∈ U .$ Let $f:S\to T$ be a function. The image of $U$ under $f$ is the subset of $T$ given by $im U = f s | s ∈ S .$ 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 V = s ∈ S | f s ∈ V .$ 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 t = s ∈ S | f s = t .$ 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$. Let $f:S\to T$ be a function. Define $f ′ : S ⟶ im f s ⟼ f s .$ Show that the map $f\prime$ is well defined and surjective. 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\}\\varnothing$ be the set of nonempty fibers of the map $f$. Define $f ^ : F ⟶ T f -1 t ⟼ t .$ Show that the map $\stackrel{^}{f}$ is well defined and injective. 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\}\\varnothing$ be the set of nonempty fibers of the map $f$. Define $f ^ ′ : F ⟶ im T f -1 t ⟼ t .$ Show that the map $\stackrel{^}{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 Show that the map $ψ : 2 S ⟶ 0 1 S T ⟼ f T$ is a bijection. Let $\circ :S×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$. Let $\circ$ be an operation on a set $S$. Show that if $S$ contains an identity for $\circ$ then it is unique. 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. 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$, $ι T ∘ f = f , and f ∘ ι S = f .$ 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.)
 Assume $f$ and $g$ are injective. 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}$. 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)$. Then $g\left(f\left({s}_{1}\right)\right)=g\left(f\left({s}_{2}\right)\right)$. Thus, since $g$ is injective, $f\left({s}_{1}\right)=f\left({s}_{2}\right)$ Thus, since $f$ is injective, ${s}_{1}={s}_{2}$. So $g\circ f$ is injective. $\square$ Assume $f$ and $g$ are surjective. To show: If $u\in U$ then there exists $s\in S$ such that $\left(g\circ f\right)\left(s\right)=u$. Assume $u\in U$. Since $g$ is surjective there exists $t\in T$ such that $g\left(t\right)=u$. Since $f$ is surjective there exists $s\in S$ such that $f\left(s\right)=t$. So $g ∘ f s = g f s = g t = u .$ So there exists $s\in S$ such that $\left(g\circ f\right)\left(s\right)=u$. So $g\circ f$ is surjective. $\square$ Assume that $f$ and $g$ are bijective. To Show: $g\circ f$ is injective. $g\circ f$ is surjective. Proof: Since $f$ and $g$ are bijective, $f$ and $g$ are injective. Thus, by (a), $g\circ f$ is injective. Since $f$ and $g$ are bijective, $f$ and $g$ are surjective. Thus, by (b), $g\circ f$ is surjective. So $g\circ f$ is bijective. $\square$ To show: If $s\prime \in S$ then $s\prime \in {f}^{-1}\left(t\right)$ for some $t\in T$. 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)$. Proof: Assume $s\prime \in S$. Then ${f}^{-1}\left(f\left(s\prime \right)\right)=\left\{s\in S\phantom{\rule{.5em}{0ex}}|\phantom{\rule{.5em}{0ex}}f\left(s\right)=f\left(s\prime \right)\right\}$. Since $f\left(s\prime \right)=f\left(s\prime \right)$, $s\prime \in {f}^{-1}\left(f\left(s\prime \right)\right)$. Assume ${f}^{-1}\left({t}_{1}\right)\cap {f}^{-1}\left({t}_{2}\right)\ne \varnothing$. Let $s\in {f}^{-1}\left({t}_{1}\right)\cap {f}^{-1}\left({t}_{2}\right)$. So $f\left(s\right)={t}_{1}$ and $f\left(s\right)={t}_{2}$ To show: ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. To show: ${f}^{-1}\left({t}_{1}\right)\subseteq {f}^{-1}\left({t}_{2}\right)$. ${f}^{-1}\left({t}_{2}\right)\subseteq {f}^{-1}\left({t}_{1}\right)$. Proof: Let $k\in {f}^{-1}\left({t}_{1}\right)$. Then $f\left(k\right)={t}_{1}=f\left(s\right)={t}_{2}$. So $k\in {f}^{-1}\left({t}_{2}\right)$. So ${f}^{-1}\left({t}_{1}\right)\subseteq {f}^{-1}\left({t}_{2}\right)$. Let $h\in {f}^{-1}\left({t}_{2}\right)$. Then $f\left(h\right)={t}_{2}=f\left(s\right)={t}_{1}$. So $h\in {f}^{-1}\left({t}_{1}\right)$. So ${f}^{-1}\left({t}_{2}\right)\subseteq {f}^{-1}\left({t}_{1}\right)$. So ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. So the set $F=\left\{{f}^{-1}\left(t\right)\phantom{\rule{.5em}{0ex}}|\phantom{\rule{.5em}{0ex}}t\in T\right\}$ of fibres of the map $f$ is a partition of $S$. $\square$ To show: $f\prime$ is well defined. $f\prime$ is surjective. Proof: To Show: If $s\in S$ then $f\prime \left(s\right)\in \mathrm{im}f$. If ${s}_{1}={s}_{2}$ then $f\prime \left({s}_{1}\right)=f\prime \left({s}_{2}\right)$. Proof: Assume $s\in S$. Then $f\prime \left(s\right)=f\left(s\right)\in \mathrm{im}f$ by definition of $f\prime$ and $\mathrm{im}f$. Assume ${s}_{1}={s}_{2}$. Then, by definition of $f\prime$, $f ′ s 1 = f s 1 = f s 2 = f ′ s 2 .$ So $f\prime$ is well defined. To show: If $t\in \mathrm{im}f$ then there exists $s\in S$ such that $f\prime \left(s\right)=t$. Assume $t\in \mathrm{im}f$. Then $f\left(s\right)=t$ for some $s\in S$. So $f\prime \left(s\right)=f\left(s\right)=t$. So $f\prime$ is surjective. $\square$ To show: $\stackrel{^}{f}$ is well defined. $\stackrel{^}{f}$ is injective. Proof: To show: If ${f}^{-1}\left(t\right)\in F$ then $\stackrel{^}{f}\left({f}^{-1}\left(t\right)\right)\in T$. If ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$ then $\stackrel{^}{f}\left({f}^{-1}\left({t}_{1}\right)\right)=\stackrel{^}{f}\left({f}^{-1}\left({t}_{2}\right)\right)$. Proof: Assume ${f}^{-1}\left(t\right)\in F$. Then $\stackrel{^}{f}\left({f}^{-1}\left(t\right)\right)=t\in T$, by definition. Assume ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. Let $s\in {f}^{-1}\left({t}_{1}\right)$. Then $s\in {f}^{-1}\left({t}_{2}\right)$ also. So ${t}_{1}=s={t}_{2}$. Then $f ^ f -1 t 1 = t 1 = t 2 = f ^ f -1 t 2 .$ So $\stackrel{^}{f}$ is well defined. To Show: If $\stackrel{^}{f}\left({f}^{-1}\left({t}_{1}\right)\right)=\stackrel{^}{f}\left({f}^{-1}\left({t}_{2}\right)\right)$ then ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. Assume $\stackrel{^}{f}\left({f}^{-1}\left({t}_{1}\right)\right)=\stackrel{^}{f}\left({f}^{-1}\left({t}_{2}\right)\right)$. Then ${t}_{1}={t}_{2}$. To show: ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. This is clearly true since ${t}_{1}={t}_{2}$. So $\stackrel{^}{f}$ is injective. $\square$ By part (b) above, the function $f ^ : F ⟶ T f -1 t ⟼ t$ is well defined and surjective. By part (a) above, the function $f ^ ′ : F ⟶ im f ^ f -1 t ⟼ t$ is well defined and surjective. To show: $\mathrm{im}\stackrel{^}{f}=\mathrm{im}f$. $\stackrel{^}{f}\prime$ is injective. Proof: To Show: $\mathrm{im}\stackrel{^}{f}\subseteq \mathrm{im}f$. $\mathrm{im}f\subseteq \mathrm{im}\stackrel{^}{f}$. Proof: Assume $t\in \mathrm{im}\stackrel{^}{f}$. Then ${f}^{-1}\left(t\right)$ is nonempty. So there exists $s\in S$ such that $f\left(s\right)=t$. So $t\in \mathrm{im}f$. So $\mathrm{im}\stackrel{^}{f}\subseteq \mathrm{im}f$. Assume $t\in \mathrm{im}f$. Then there exists $s\in S$ such that $f\left(s\right)=t$. So ${f}^{-1}\left(t\right)\ne \varnothing$. So $t\in \mathrm{im}\stackrel{^}{f}$. So $\mathrm{im}f\subseteq \mathrm{im}\stackrel{^}{f}$. So $\mathrm{im}\stackrel{^}{f}=\mathrm{im}f$. To show: If $\stackrel{^}{f}\prime \left({f}^{-1}\left({t}_{1}\right)\right)=\stackrel{^}{f}\prime \left({f}^{-1}\left({t}_{2}\right)\right)$ then ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. Assume $\stackrel{^}{f}\prime \left({f}^{-1}\left({t}_{1}\right)\right)=\stackrel{^}{f}\prime \left({f}^{-1}\left({t}_{2}\right)\right)$. So ${t}_{1}={t}_{2}$. So ${f}^{-1}\left({t}_{1}\right)={f}^{-1}\left({t}_{2}\right)$. So $\stackrel{^}{f}\prime$ is injective. So $\stackrel{^}{f}\prime$ is well defined and bijective. $\square$ To show: $\psi$ is well defined. $\psi$ is bijective. Proof: To show: If $T\in {2}^{S}$ then $\psi \left(T\right)={f}_{T}\in {\left\{0,1\right\}}^{S}$. 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)$. Proof: 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\}$. Assume ${T}_{1}$ and ${T}_{2}$ are subsets of $S$ and that ${T}_{1}={T}_{2}$. To show: $\psi \left({T}_{1}\right)=\psi \left({T}_{2}\right)$. To show: ${f}_{{T}_{1}}={f}_{{T}_{2}}$. To show: If $s\in S$ then ${f}_{{T}_{1}}\left(s\right)={f}_{{T}_{2}}\left(s\right)$. Assume $s\in S$. Case 1: If $s\in {T}_{1}$ then, since ${T}_{1}={T}_{2}$, $s\in {T}_{2}$. So ${f}_{{T}_{1}}\left(s\right)=1={f}_{{T}_{2}}\left(s\right)$. Case 2: If $s\notin {T}_{1}$ then, since ${T}_{1}={T}_{2}$, $s\notin {T}_{2}$. So ${f}_{{T}_{1}}\left(s\right)=0={f}_{{T}_{2}}\left(s\right)$. So ${f}_{{T}_{1}}\left(s\right)={f}_{{T}_{2}}\left(s\right)$ for all $s\in S$. So ${f}_{{T}_{1}}={f}_{{T}_{2}}$. So $\psi \left({T}_{1}\right)={f}_{{T}_{1}}={f}_{{T}_{2}}=\psi \left({T}_{2}\right)$. So $\psi$ is well defined. By virtue of Proposition 2.2.3 [??? - CORRECT?] we would like to show: $\psi :{2}^{S}\to {\left\{0,1\right\}}^{S}$ has an inverse function. Given a function $f:s\to \left\{0,1\right\}$ define $T f = s ∈ S | f s = 1 .$ Define a function $\varphi :{\left\{0,1\right\}}^{S}\to {2}^{S}$ by $ϕ : 0 1 S ⟶ 2 S f ⟼ T f .$ To Show: $\varphi$ is well defined. $\varphi$ is an inverse function to $\psi$. Proof: To show: If $f\in {\left\{0,1\right\}}^{S}$ then $\varphi \left(f\right)={T}_{f}\in {2}^{S}$. 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)$. Proof: By definition ${T}_{f}=\left\{s\in s\phantom{\rule{.5em}{0ex}}|\phantom{\rule{.5em}{0ex}}f\left(s\right)=1\right\}$ is a subset of $S$. Assume ${f}_{1},{f}_{2}\in {\left\{1,2\right\}}^{S}$ and ${f}_{1}={f}_{2}$. To show: $\varphi \left({f}_{1}\right)=\varphi \left({f}_{2}\right)$. To show: ${T}_{{f}_{1}}={T}_{{f}_{2}}$. To Show: ${T}_{{f}_{1}}\subseteq {T}_{{f}_{2}}$. ${T}_{{f}_{1}}\subseteq {T}_{{f}_{2}}$. Proof: Assume $s\in {T}_{{f}_{1}}$. Then ${f}_{1}\left(s\right)=1$. Since ${f}_{2}\left(s\right)={f}_{1}\left(s\right)$, ${f}_{2}\left(s\right)=1$. Thus $s\in {T}_{{f}_{2}}$. So, ${T}_{{f}_{1}}\subseteq {T}_{{f}_{2}}$ Assume $s\in {T}_{{f}_{2}}$. Then ${f}_{2}\left(s\right)=1$. Since ${f}_{1}\left(s\right)={f}_{2}\left(s\right)$, ${f}_{1}\left(s\right)=1$. Thus $s\in {T}_{{f}_{1}}$. So, ${T}_{{f}_{2}}\subseteq {T}_{{f}_{1}}$ So ${T}_{{f}_{1}}={T}_{{f}_{2}}$. So $\varphi \left({f}_{1}\right)=\varphi \left({f}_{2}\right)$. So $\varphi$ is well defined. To Show: If $T\in {2}^{S}$ then $\varphi \left(\psi \left(T\right)\right)=T$. If $f\in {\left\{0,1\right\}}^{S}$ then $\psi \left(\varphi \left(f\right)\right)=f$. Proof: Assume $T\subseteq S$. To show: $\varphi \left(\psi \left(T\right)\right)=T$ To show: ${T}_{{f}_{T}}=T$. To Show: ${T}_{{f}_{T}}\subseteq T$. $T\subseteq {T}_{{f}_{T}}$. Proof: Assume $t\in {T}_{{f}_{T}}$. Then ${f}_{T}\left(t\right)=1$. So $t\in T$. So ${T}_{{f}_{T}}\subseteq T$. Assume $t\in T$. Then ${f}_{T}\left(t\right)=1$. So $t\in {T}_{{f}_{T}}$. So $T\subseteq {T}_{{f}_{T}}$. So ${T}_{{f}_{T}}=T$. So $\varphi \left(\psi \left(T\right)\right)=T$ Assume $f\in {\left\{0,1\right\}}^{S}$. To show: $\varphi \left(\psi \left(f\right)\right)=f$. By definition, $\psi \left(\varphi \left(f\right)\right)={f}_{{T}_{f}}$. To show: If $s\in S$ then ${f}_{{T}_{f}}\left(s\right)=f\left(s\right)$. Assume $s\in S$. Case 1: $f\left(s\right)=1$. Then $s\in {T}_{f}$. So ${f}_{{T}_{f}}=1$. So ${f}_{{T}_{f}}=f\left(s\right)$. Case 2: $f\left(s\right)=0$. Then $s\notin {T}_{f}$. So ${f}_{{T}_{f}}=0$. So ${f}_{{T}_{f}}=f\left(s\right)$. So ${f}_{{T}_{f}}\left(s\right)=f\left(s\right)$. So $\psi \left(\varphi \left(f\right)\right)=f$. So $\varphi$ is an inverse function to $\psi$. So $\psi$ is bijective. $\square$ Let $e,e\prime \in S$ be identities for $\circ$. Then $e\circ e\prime =e$, since $e\prime$ is an identity, and $e\circ e\prime =e\prime$, since $e$ is an identity. So, $e=e\prime$. Let $t,u\in S$ be inverses for $s$. By associativity of $\circ$, $u=\left(t\circ s\right)\circ u=t\circ \left(s\circ u\right)=t$. $\square$ Assume $f:S\to T$ is a function. To show: ${\iota }_{T}\circ f=f$. $f\circ {\iota }_{T}=f$. Proof: If $s\in S$ then ${\iota }_{T}\left(f\left(s\right)\right)=f\left(s\right)$. If $s\in S$ then $f\left({\iota }_{S}\left(s\right)\right)=f\left(s\right)$. (aa) and (ab) follow immediately from the definitions of ${\iota }_{T}$ and ${\iota }_{S}$. Assume $\varphi$ and $\psi$ are both inverse functions to $f$. To show: $\varphi =\psi$. By the definitions of identity and inverse functions $ϕ = ϕ ∘ f ∘ ψ = ϕ ∘ f ∘ ψ = ψ .$ So, if an inverse functions exists, then it is unique. $\square$