Abstract Nonsense

Crushing one theorem at a time

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.

Advertisements

June 15, 2010 - Posted by | Fun Problems, Munkres, Topology | , , , , ,

2 Comments »

  1. In problem 1 why do you feel a need to show that surjectivity and injectivity is guaranteed ?

    Is not just showing “a subset of b” and “b subset of a” enough to prove
    set a = set b

    Comment by mehdi | May 11, 2012 | Reply

  2. ok I got it you said iff but the book only says if. THANKS FOR ANSWERS

    Comment by mehdi | May 11, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: