Abstract Nonsense

Munkres Chapter 1 Section 2

1.

Problem: Let $f:A\to B$. Let $A_0\subseteq A$ and $B_0\subseteq B$.

a) Show that $A_0\subseteq f^{-1}\left(f\left(A_0\right)\right)$ and that equality holds if $f$ is injective

b) Show that $f\left(f^{-1}\left(B_0\right)\right)\subseteq B_0$ and equality holds if and only if $f$ is surjective

Proof:

a) The first part is obvious enough. If $x\in A_0$ then $f(x)\in f\left(A_0\right)$ and so $x\in f^{-1}\left(f\left(A_0\right)\right)$ from where it follows that $A_0\subseteq f^{-1}\left(f\left(A_0\right)\right)$.

Now, suppose that $f$ is injective but $A_0\subsetneq f^{-1}\left(f\left(A_0\right)\right)$. Then, there is some $x\notin A_0$ such that $f(x)\in f\left(A_0\right)$. But, by definition since $f(x)\in f\left(A_0\right)$ there exists some $a\in A_0$ such that $f(x)=f(a)$ but since $a\in A_0$ and $x\notin A_0$ it follows that $x\ne a$ and this contradicts injectivity.

Conversely, suppose that $A_0=f^{-1}\left(f\left(A_0\right)\right)$. Then, if $x\ne y$ then $y\notin \{x\}$ and so $\{y\}\notin f^{-1}\left(f\left(\{x\}\right)\right)$ which means that $f(y)\ne f(x)$ as desired.

b) The first part is clear again. If $f(x)\in f\left(f^{-1}\left(B_0\right)\right)$ then $x\in f^{-1}\left(B_0\right)$ and so $f(x)\in B_0$ from where it follows that $f\left(f^{-1}\left(B_0\right)\right)\subseteq B_0$.

Now, suppose that $f$ is surjective. By the previous part it suffices to show the reverse inclusion. So, let $f(x)\in B_0$ (we know that any element of $B_0$ is of the form $f(x)$ by surjectivity), then $x\in f^{-1}\left(B_0\right)$ and so $f(x)\in f\left(f^{-1}\left(B_0\right)\right)$ and so $B_0\subseteq f\left(f^{-1}\left(B_0\right)\right)$ from where the conclusion follows.

Conversely, suppose that $B_0=f\left(f^{-1}\left(B_0\right)\right)$ and let $y_0\in B$. Then, $\{y\}=f\left(f^{-1}\left(\{y\}\right)\right)$ in particular $y\in f\left(A\right)$ from where it follows that $B\subseteq f(A)$ and so surjectivity is guaranteed.

2.

Problem: Let $f:A\to B$ and let $A_i\subseteq B$ and $B_i\subseteq B$ for $i=0,1$. Show that $f^{-1}$ preserves inclusions, unions, intersections, and differences of sets:

a) $B_0\subseteq B_1\implies f^{-1}\left(B_0\right)\subseteq f^{-1}\left(B_1\right)$

b) $f^{-1}\left(B_0\cup B_1\right)=f^{-1}\left(B_0\right)\cup f^{-1}\left(B_1\right)$

c) $f^{-1}\left(B_0\cap B_1\right)=f^{-1}\left(B_0\right)\cap f^{-1}\left(B_1\right)$

d) $f^{-1}\left(B_0-B_1\right)=f^{-1}\left(B_0\right)-f^{-1}\left(B_1\right)$

Show that $f$ preserves inclusions and unions only:

e) $A_0\subseteq A_1\implies f\left(A_0\right)\subseteq f\left(A_1\right)$

f) $f\left(A_0\cup A_1\right)=f\left(A_0\right)\cup f\left(A_1\right)$

g) $f\left(A_0\cap A_1\right)\subseteq f\left(A_0\right)\cap f\left(A_1\right)$ and show that equality holds precisely when $f$ is injective

h) $f\left(A_0-A_1\right)\supseteq f\left(A_0\right)-f\left(A_1\right)$ and show that equality holds precisely when $f$ is surjective.

Proof:

We assume in all cases that the sets are non-empty and in the case of intersections and set differences, intersecting. For, if not this is trivial.

a) Let $x\in f^{-1}\left(B_0\right)$ then $f(x)\in B_0$ and so $f(x)\in B_1$ and so $x\in f^{-1}\left(B_1\right)$, from where it follows that $f^{-1}\left(B_0\right)\subseteq f^{-1}\left(B_1\right)$

b) Let $x\in f^{-1}\left(B_0\cup B_1\right)$ then $f(x)\in B_0\cup B_1$ and so $f(x)\in B_0\text{ or }f(x)\in B_1$ and so $x\in f^{-1}\left(B_0\right)\text{ or }x\in f^{-1}\left(B_1\right)$ and so $x\in f^{-1}\left(B_0\right)\cup f^{-1}\left(B_1\right)$. Noting that all the “and so”s above were actually “if and only if”s shows the reverse inclusion.

c) We note that $x\in f^{-1}\left(B_0\cap B_1\right)$ if and only if $f(x)\in B_0\cap B_1$ which is true if and only if $f(x)\in B-0\text{ and }f(x)\in B_1$ which is true if and only if $x\in f^{-1}\left(B_0\right)\text{ and }x\in f^{-1}\left(B_1\right)$ which is true if and only if $x\in f^{-1}\left(B_0\right)\cap f^{-1}\left(B_1\right)$

d) We note that $x\in f^{-1}\left(B_0-B_1\right)$ if and only if $f(x)\in B_0-B_1$ which is true if and only if $f(x)\in B_0\text{ and }f(x)\notin B_1$. Now, clearly the first part is true if and only if $x\in f^{-1}\left(B_0\right)$ and (noticing that $x\in f^{-1}\left(B_1\right)\implies f(x)\in B_1$ )the second part is true if and only if $x\notin f^{-1}\left(B_1\right)$ and so putting these together we get the statement in the previous sentence is true if and only if $x\in f^{-1}\left(B_0\right)\text{ and }x\notin f^{-1}\left(B_1\right)$ which is true if and only if $x\in f^{-1}\left(B_0\right)-f^{-1}\left(B_1\right)$

e) Let $f(x)\in f\left(A_0\right)$ then $f(x)=f(a)$ for some $a\in A_0$. But, since $A_0\subseteq A_1$ it follows that $f(x)=f(a)$ for some $a\in A_1$ and so $f(x)\in f\left(A_1\right)$ from where it follows that $f\left(A_0\right)\subseteq f\left(A_1\right)$.

f) Let $f(x)\in f\left(A_0\cup A_1\right)$ then $f(x)=f(a)$ for some $a\in A_0\cup A_1$ and thus $f(x)=f(a)$ for some $a\in A_0\text{ or }a\in A_1$ and so either $f(x)=f(a)$ for some $a\in A_0$ or $f(x)=f(a)$ for some $a\in A_1$ and so $f(x)\in f\left(A_0\right)\text{ or }f(x)\in f\left(A_1\right)$ which is true if and only if $f(x)\in f\left(A_0\right)\cup f\left(A_1\right)$

g) Let $f(x)\in f\left(A_0\cap A_1\right)$ then $f(x)=f(a)$ for some $a\in A_0\cap A_1$ and so $f(x)=f(a)$ for some $a\in A_0$ and $f(x)=f(a)$ for some $a\in A_1$ and so $f(x)\in f\left(A_0\right)\text{ and }f(x)\in f\left(A_1\right)$ and so $f(x)\in f\left(A_0\right)\cap f\left(A_1\right)$ from where it follows that $f\left(A_0\cap A_1\right)$.

Now, suppose that $f$ is injective. By the last part to show equality it suffices to show the reverse inclusion. To do this we let $f(x)\in f\left(A_0\right)\cap f\left(A_1\right)$ then $f(x)\in f\left(A_0\right)\text{ and }f(x)\in f\left(A_1\right)$ and thus (by injectivity) $x\in A_0\text{ and }x\in A_1$ and so $x\in A_0\cap A_1$ and so $f(x)\in f\left(A_0\cap A_1\right)$. The conclusion follows by previous comment.

Conversely, suppose that $x\ne y$ then $\{x\}\cap\{y\}=\varnothing$ and so

$\varnothing=f\left(\varnothing\right)=f\left(\{x\}\cap\{y\}\right)=f\left(\{x\}\right)\cap f\left(\{y\}\right)=\{f(x)\}\cap\{f(y)\}$

from where it follows that $f(x)\ne f(y)$

Remark: I technically took $A_0$ to be any subset of $A$

h) Let $f(x)\in f\left(A_0\right)-f\left(A_1\right)$ then $f(x)\in f\left(A_0\right)$ and $f(x)\notin f\left(A_1\right)$ and so $f(x)=f(a)$ for some $a\in A_0$ but this $a\notin A_1$ and so $f(x)=f(a)$ for some $a\in A_0-A_1$ and so $f(x)\in f\left(A_0-A_1\right)$

Now, suppose that $f$ is injective. From the last part to prove equality it suffices to show the reverse inclusion. So, let $f(x)\in f\left(A_0-A_1\right)$ then $x\in A_0-A_1$ (by injectivity) and so $x\in A_0\text{ and }x\notin A_1$ and so $f(x)\in f\left(A_0\right)\text{ and }f(x)\notin f\left(A_1\right)$ (second part by injectivity) and thus $f(x)\in f\left(A_0\right)-f\left(A_1\right)$

Conversely, if $f(x)=f(y)$ then

$\varnothing=\{f(x)\}-\{f(y)\}=f\left(\{x\}\right)-f\left(\{y\}\right)=f\left(\{x\}-\{y\}\right)$

from where it follows that

$\{x\}-\{y\}=\varnothing\implies \{x\}\subseteq\{y\}\implies x\in\{y\}\implies x=y$

Injectivity follows.

Remark: The same remark applies.

3.

Problem: Show that b), c), f) and g) of the last exercise hold for arbitrary unions and intersections.

Proof:

We once again assume that all the following are non-empty since the proof otherwise is trivial.

b) Let $\displaystyle x \in f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$ then $\displaystyle f(x)\in\bigcup_{\alpha\in\mathcal{A}}U_\alpha$ and so in particular $f(x)\in U_{\alpha_0}$ for some $\alpha_0\in\mathcal{A}$. Thus, $x\in f^{-1}\left(U_{\alpha_0}\right)$ and so $\displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$. It follows that

$\displaystyle f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)\subseteq\bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$

Conversely, let $\displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$ then $x\in f^{-1}\left(U_{\alpha_0}\right)$ for some $\alpha_0\in\mathcal{A}$. Thus, $f(x)\in U_{\alpha_0}$ and so $\displaystyle f(x)\bigcup_{\alpha\in\mathcal{A}}U_\alpha$ so that $\displaystyle x\in f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$. It follows that

$\displaystyle \bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)\subseteq f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$

The problem follows.

c) Let $\displaystyle x\in f^{-1}\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$ then $\displaystyle f(x)\in\bigcap_{\alpha\in\mathcal{A}}U_\alpha$ and so $f(x)\in U_\alpha$ for every $\alpha\in\mathcal{A}$. Thus, $x\in f^{-1}\left(U_\alpha\right)$ for every $\alpha\in\mathcal{A}$ and thus $\displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$

$\displaystyle f^{-1}\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)\subseteq \bigcap_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$

Conversely, if $\displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)$ we have that $x\in f^{-1}\left(U_\alpha\right)$ for every $\alpha\in\mathcal{A}$ and so $f(x)\in U_\alpha$ for every $\alpha\in\mathcal{A}$. Thus, $\displaystyle f(x)\in\bigcap_{\alpha\in\mathcal{A}}U_\alpha$ and so $\displaystyle x\in f^{-1}\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$. It follows that

$\displaystyle \bigcap_{\alpha\in\mathcal{A}}f^{-1}\left(U_\alpha\right)\subseteq f^{-1}\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$

from where the problem follows.

f) Let $\displaystyle f(x)\in f\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$ then $f(x)=f(a)$ where $\displaystyle a\in\bigcup_{\alpha\in\mathcal{A}}U_\alpha$. So, $f(x)=f(a)$ where $a\in U_{\alpha_0}$ for some $\alpha_0\in\mathcal{A}$. It follows that $f(x)\in f\left(U_{\alpha_0}\right)$ and thus $\displaystyle f(x)\in\bigcup_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$ from where it follows that

$\displaystyle f\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)\subseteq\bigcup_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$

Conversely, let $\displaystyle f(x)\in\bigcup_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$ then $f(x)\in f\left(U_{\alpha_0}\right)$ for some $\alpha_0\in\mathcal{A}$. Thus, $f(x)=f(a)$ for some $a\in U_{\alpha_0}$ thus $f(x)=f(a)$ for some $\displaystyle a\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}$ and so $\displaystyle f(x)\in f\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$ from where it follows that

$\displaystyle \bigcup_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)\subseteq f\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)$

and so the problem follows.

g) Let $\displaystyle f(x)\in f\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$, then $f(x)=f(a)$ for some $\displaystyle a\in\bigcap_{\alpha\in\mathcal{A}}U_\alpha$. It follows that $f(x)=f(a)$ for some $U_\alpha$ for every $\alpha\in\mathcal{A}$. Thus, $\displaystyle f(x)\in\bigcap_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$ from where it follows that

$\displaystyle f\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)\subseteq \bigcap_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$

Now, assume that $f$ is injective and let $\displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)$. Then, $f(x)\in f\left(U_\alpha\right)$ for every $\alpha\in\mathcal{A}$. Thus, by injectivity we have that $x\in U_\alpha$ for every $\alpha\in\mathcal{A}$ and so $\displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}U_\alpha$. Thus, $\displaystyle f(x)\in f\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$ and thus

$\bigcap_{\alpha\in\mathcal{A}}f\left(U_\alpha\right)\subseteq f\left(\bigcap_{\alpha\in\mathcal{A}}U_\alpha\right)$

from where the problem follows.

4.

Problem: Let $f:A\to B$ and $g:B\to C$.

a) If $C_0\subseteq C$ show that $\left(g\circ f\right)^{-1}\left(C_0\right)=f^{-1}\left(g^{-1}\left(C_0\right)\right)$

b) If $f$ and $g$ are injective show that $g\circ f$ is injective.

c) If $g\circ f$ is injective what can you say about the injectivity $g$ or $f$?

d) If $f$ and $g$ are surjective prove that $g\circ f$ is surjective.

e) If $g\circ f$ is surjective what can you say about $g$ and $f$‘s surjectivity?

f) Summarize your answers to b-e in the form of a theorem.

Proof:

a) Let $x\in \left(g\circ f\right)^{-1}\left(C_0\right)$, then $(g\circ f)(x)\in C_0$ and so $g(f(x))\in C_0$. So, $f(x)\in g^{-1}\left(C_0\right)$ and so finally $x\in f^{-1}\left(g^{-1}\left(C_0\right)\right)$.

Conversely, if $x\in f^{-1}\left(g^{-1}\left(C_0\right)\right)$ then $f(x)\in g^{-1}\left(C_0\right)$ and so $g(f(x))=(g\circ f)(x)\in C_0$ so that $x\in \left(g\circ f\right)^{-1}\left(C_0\right)$.

The conclusion follows.

b) If $x\ne y\in A$ then $f(x)\ne f(y)\in B$ (by $f$‘s injectivity) and so $g(f(x))\ne g(f(y))\in C$ (by $g$‘s injectivity). The conclusion follows.

c) We claim that $g\circ f$ is injective implies that $f$ is injective. To do this we prove the contrapositive. Suppose that $f$ was not injective, then there is $x\ne y\in A$ such that $f(x)=f(y)$ and so clearly then $g(f(x))=g(f(y))$ and so $g\circ f$ is not injective. The conclusion follows.

d) This follows since $g\left(f\left(A\right)\right)=g\left(B\right)=C$ as desired.

e) We claim that $g\circ f$ is surjective implies that $g$ is surjective. One again, we do this by proving the contrapositive. We note that $g\left(f\left(A\right)\right)\subseteq g\left(B\right)\subsetneq C$ from where the conclusion follows.

f) I’m not sure what’s desired but I guess it would be that b) and d) imply that if $f,g$ are bijections then $g\circ f$ is a bijection. Also, c) and e) prove that if $g\circ f$ is a bijection then $f$ is injective and $g$ surjective.

5.

Problem: In genereal, let us denote the identity function for a set $C$ by $\text{id}_C$. That is define $\text{id}_C:C\to C:x\mapsto x$.

Given $f:A\to B$ we say the function $g:B\to A$ is a left inverse for $f$ if $g\circ f=\text{id}_A$. Also, we say $h:B\to A$ is a right inverse if $f\circ h=\text{id}_B$.

a) Prove that if $f$ has a left inverse, $f$ is injective, and if $f$ has a right inverse, $f$ is surjective.

b) Give an example of a function has a left inverse but no right inverse

c) Give an example of a function that has a right inverse but no left inverse.

d) Can a function have more than left inverse? More than one right inverse?

e) Show that if $f$ has  both a left $g$ and a right inverse $h$ then $f$ is bijective and $g=h=f^{-1}$

Proof:

a) Suppose that $f$ has a left inverse $g$ and let $\ne y\in A$. We know then that $x=g(f(x))\ne g(f(y))=y$ which would be impossible (since $g$ is a function$if $f(x)=f(y)$. Conversely, let $f$ have right inverse $h$ and let $y\in B$ be arbitrary. We know then that $f(h(y))=y$ and since $h(y)\in A$ it is the desired value whose image is $y$. b) Consider the function $f:[0,1]\to\mathbb{R}:x\mapsto x$. Clearly this has a left inverse but no right inverse. c) How about $f:\mathbb{R}\to\{1\}:x\mapsto 1$? d) A left inverse need not be unique by this definition. For example, consider the mapping $f:[0,1]\to\mathbb{R}:x\mapsto x$. Then, we can define $g:\mathbb{R}\to[0,1]$ by $\displaystyle g(x)=\begin{cases}x\quad\text{if}\quad x\in[0,1] \\ c\quad\text{if}\quad x\notin[0,1]\end{cases}$ Clearly then $g(f(x))=x$ for every $x\in[0,1]$. But, we may take $c$ to be anything so that $g$ is not unique. Right inverses are not unique either. For example, consider $\displaystyle f:\{1,2,3,4\}\to\{1,2\}:x\mapsto\begin{cases}1\quad\text{if}\quad x=1,2\\2\quad\text{if}\quad x=3,4\end{cases}$ We then consider two function $h_1:\{1,2\}\to\{1,2,3,4\}:x\mapsto\begin{cases}1\quad\text{if}\quad x=1\\3\quad\text{if}\quad x=2\end{cases}$ We then note that $f\left(h(1)\right)=f(1)=1$ and $f\left(h(2)\right)=f(3)=2$ So that $f\circ h_1=\text{id}_{\{1,2\}}$ But, a similar analysis shows that if $h_2$ is defined by $h_2:\{1,2\}\to\{1,2,3,4\}:x\mapsto\begin{cases} 2\quad\text{if}\quad x=1\\ 4\quad\text{if}\quad x=2\end{cases}$ also has the property that $f\circ h_2=\text{id}_{\{1,2\}}$ And since $h_1\ne h_2$ it follows that right inverses need not be unique. e) Clearly by our previous problems we have that $f$ having a left and right inverse respectively implies that$laetx f\$ is injective and surjective respectively and thus bijective. Now, Let $y\in B$ be arbitrary and suppose that

$h(y)\ne f^{-1}(y)$

then we see by $f$‘s injectivity that

$y=f(h(y))\ne f(f^{-1}(y))=y$

which is clearly absurd. Also, let $y\in B$ be arbitrary, then by surjectivity we have that $y=f(x)$ for some $x\in A$. Then, if $g(y)\ne f^{-1}(y)$ this implies that

$x=g(f(x))=g(y)\ne f^{-1}(y)=f^{-1}(f(x))=x$

which is also a contradiction. It follows that $g=f^{-1}$ and $h=f^{-1}$ and thus $g=h=f^{-1}$ as desired.

6.

Problem: Let $f:\mathbb{R}\to\mathbb{R}:x\mapsto x^3-x$. By restricting the domain and range of $f$ appropriately obtain from $f$ a bijective function $g$.

Proof: We note that $f'(x)=3x^2-1$ and so $f$ is increasing on $[1,2]$. Thus,

$f\left([1,2]\right)\subseteq \left[f(1),f(2)\right]=\left[2,11\right]$

but since $f$ is continuous it follows from the intermediate value theorem that $f\left([1,2]\right)=[2,11]$ and thus noting that $f$ is injective on $[1,2]$ (since it’s continuous and monotone) we may conclude that $f\mid_{[1,2]}:[1,2]\to[2,11]$ is bijective.

June 15, 2010 -