Abstract Nonsense

Crushing one theorem at a time

Munkres Chapter one Section two: Functions


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 iff f

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

Proof:

a) Let x\in A_0, then$ latex f(x)\in f\left(A_0\right)$ and so x\in f^{-1}\left(f\left(A_0\right)\right). Now, suppose that f is injective and let x\in f^{-1}\left(f\left(A_0\right)\right) clearly then f(x)\in f\left(A_0\right). It follows by injectivity that x\in A_0 (if this isn’t apparent, note that by definition f(x)\in f\left(A_0\right) means that f(x)=f(y) for some y\in A_0. Now, by injectivity we see that x=y and so the result becomes clear). Conversely, suppose that A_0=f^{-1}\left(f\left(A_0\right)\right) for every A_0\subseteq A. Then, in particular we see that \{x\}=f^{-1}\left(f(\{x\})\right) and so

x\ne y\implies y\notin \{x\}=f^{-1}\left(f(\{x\})\right)\implies f(y)\ne f(x)

from where injectivity follows.

b) Let f(x)\in f\left(f^{-1}\left(B_0\right)\right), then f(x)=f(y) for some y\in f^{-1}\left(B_0\right). It follows then that f(y)=f(x)\in B_0.

Now, suppose that f is surjective and let f(x)\in B_0. Then, x\in f^{-1}\left(B_0\right) and so f(x)\in f\left(f^{-1}\left(B_0\right)\right). Conversely, suppose that f\left(f^{-1}\left(B_0\right)\right)=B_0 for every B_0\subseteq B. Then, in particular we see that f\left(A\right)=f\left(f^{-1}\left(B\right)\right)=B and surjectivity follows.

2.

Problem: Let f:A\to B and let A_i\subseteq A 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); show that equality holds iff f is injective

h) f\left(A_0-A_1\right)\supseteq f\left(A_0\right)-f\left(A_1\right); show that equality holds iff f is injective

Proof:

a) Let x\in f^{-1}\left(B_0\right), then f(x)\in B_0 and so f(x)\in B_1 and thus x\in f^{-1}\left(B_1\right)

b) See number three

c) See number three

d) Let x\in f^{-1}\left(B_0-B_1\right) then f(x)\in B_0-B_1, or f(x)\in B-0\text{ and }f(x)\notin B_1 it follows that x\in f^{-1}\left(B_0\right) and x\notin f^{-1}\left(B_1\right) (otherwise f(x)\in f\left(f^{-1}\left(B_1\right)\right)\subseteq B_1). This is equivalent to saying that x\in f^{-1}\left(B_0\right)-f^{-1}\left(B_1\right). Conversely, let x\in f^{-1}\left(B_0\right)-f^{-1}\left(B_1\right), then x\in f^{-1}\left(B_0\right) and x\notin f^{-1}\left(B_1\right). Thus, f(x)\in f\left(f^{-1}\left(B_0\right)\right)\subseteq B_0 and f(x)\notin B_1. It follows that f(x)\in B_0-B_1 or x\in f^{-1}\left(B_0-B_1\right)

e) Let f(x)\in f\left(A_0\right) then f(x)=f(y) for some y\in A_0 and thus (since y\in A_1) we see that f(x)=f(y) for some y\in A_1 which is equivalent to saying that f(x)\in f\left(A_1\right).

f) See number three

g) See number three for the first part. Clearly, it suffices to prove the second part for two sets. So, suppose that f is injective and let f(x)\in\left(A_0\cap A_1\right) then x\in A_0\cap A_1 and so x\in A_0 and x\in A_1 and so f(x)\in f\left(A_0\right) and f(x)\in f\left(A_1\right), or f(x)\in f\left(A_0\right)\cap f\left(A_1\right). The proposed equality follows.

Conversely, suppose that f\left(A_0\cap A_1\right)=f\left(A_0\right)\cap f\left(A_1\right) for every A_0,A_1\subseteq A. We see then in particular the following line of reasoning

x\ne y\implies \{x\}\cap\{y\}=\varnothing

and thus

\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)\}

and clearly singletons are disjoint iff they’re single elements are not equal. Thus, condensing

x\ne y\implies f(x)\ne f(y)

and injectivity follows.

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). This, in particular says that f(x)=f(y) for some y\in A_0 and y\notin A_1 (otherwise f(y)=f(x)\in f\left(A_1\right). Thus, f(x)=f(y) for some y\in A_0-A_1, or f(x)\in f\left(A_0-A_1\right).

Now, suppose that f is injective and let f(x)\in f\left(A_0-A_1\right), then by injectivity x\in A_0-A_1 and so x\in A_0 and x\notin A_1. Thus, f(x)\in f\left(A_0\right) and f(x)\notin f\left(A_1\right). So, f(x)\in f\left(A_1\right)-f\left(A_0\right). Conversely, if f\left(A_0-A_1\right)=f\left(A_0\right)-f\left(A_1\right) then we see that

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

but f(A)=\varnothing iff A=\varnothing. It follows that \{x\}-\{y\}=\varnothing and so x=y.

3.

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

Proof:

a) 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. Thus, there exists some \alpha_0\in\mathcal{A} such that f(x)\in U_{\alpha_0} and so x\in f^{-1}\left(U_{\alpha_0}\right). Therefore, \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(U_{\alpha}\right).

Conversely, if let 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}. Therefore, f(x)\in U_{\alpha_0} so that \displaystyle f(x)\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}. So finally, we may conclude that \displaystyle x\in f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}U_\alpha\right)

c) We merely need note that

\displaystyle A-f^{-1}\left(\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}\right)=f^{-1}\left(B-\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}\right)=f^{-1}\left(\bigcup_{\alpha\in\mathcal{A}}\left(B-U_{\alpha}\right)\right)

(where the first equality is gotten noticing that A=f^{-1}\left(B\right) and using property d) from the previous problem). Then, recalling the last problem we can see that this is equal to

\displaystyle \bigcup_{\alpha\in\mathcal{A}}f^{-1}\left(B-U_{\alpha}\right)=\bigcup_{\alpha\in\mathcal{A}}\left(f^{-1}\left(B\right)-f^{-1}\left(U_{\alpha}\right)\right)=A-\bigcap_{\alpha\in\mathcal{A}}f^{-1}\left(U_{\alpha}\right)

and so comparing the LHS of the first equality with the RHS of the last leads to the desired result.

f) Let \displaystyle f(x)\in f\left(\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}\right). Then, f(x)=f(y) for some  \displaystyle y\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}. Thus, f(x)=f(y) for some y\in U_{\alpha_0} for some \alpha_0\in \mathcal{A}. Thus, f(x)\in f\left(U_{\alpha_0}\right) and so \displaystyle f(x)\in\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}. It follows that f(x)=f(y) for some y\in U_{\alpha_0} and so f(x)=f(y) for some \displaystyle y\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}. Therefore, \displaystyle f(x)\in f\left(\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}\right)

g) Let \displaystyle f(x)\in f\left(\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}\right). Then, f(x)=f(y) for some \displaystyle y\in\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}. It follows that f(x)=f(y) for some y\in U_{\alpha} for every \alpha\in\mathcal{A}. Thus, f(x)\in f\left(U_{\alpha}\right) for every \alpha\in\mathcal{A} and so \displaystyle f(x)\in\bigcap_{\alpha\in\mathcal{A}}f\left(U_{\alpha}\right)

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 of f and g?

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 the surjectivity of f and g?

Proof:

a) Let x\in \left(g\circ f\right)^{-1}\left(C_0\right), then \left(g\circ f \right)(x)=g(f(x))\in C_0 but this clearly implies that 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) we see that f(x)\in g^{-1}\left(C_0\right) and so g(f(x))=(g\circ f)(x)\in C_0. Therefore, x\in \left(g\circ f\right)^{-1}\left(C_0\right)

b) If x\ne y then by the injectivity of f we see that f(x)\ne f(y) and so by the injectivity of g it follows that g(f(x))\ne g(f(y)).

c) If g\circ f is injective then f is injective. To see this, suppose not; then there exists x,y\in A such that x\ne y but f(x)=f(y)\implies g(f(x))=g(f(y)) which contradicts g\circ f‘s injectivity.

d) We note that g\left(f\left(A\right)\right)=g\left(B\right)=C from where the conclusion follows.

e) It must be true that g is surjective. To see this suppose not. Then,

g\left(f\left(A\right)\right)\subseteq g\left(B\right)\subsetneq C

which contradicts the surjectivity of g\circ f

5.

Problem: In general, let us denote the identity function on 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 that a function  g:B\to A is a left inverse for f if g\circ f=\text{id}_A; and we see that h:B\to A is a right inverse for f if f\circ h=\text{id}_B.

a) Show 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 that has a left inverse but no right inverse

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

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

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

Proof:

a) If f(x)=f(y) we see that x=g(f(x))=g(f(y))=y and so f is injective. Conversely, let y\in B be arbitrary, we know that f(h(y))=y and so h(y)\in A is the required element which maps to y under f

b) The inclusion map \iota:\mathbb{N}\hookrightarrow\mathbb{Z}:x\mapsto x. Clearly it has no right inverse or it’d be surjective. But, the mapping

j:\mathbb{Z}\to\mathbb{N}:x\mapsto\begin{cases}x & \mbox{if}\quad x\in\mathbb{N}\\ 0 & \mbox{if}\quad x\notin\mathbb{N}\end{cases}

surely satisfies the left inverse requirement since

j(\iota(x))=j(x)=x,\text{ }\forall x\in\mathbb{N}.

c) Consider the function f:\mathbb{R}\to\{1\}:x\mapsto 1. Clearly this possesses no left inverse, otherwise it’d be injective. But, j:\{1\}\to\mathbb{R}:1\mapsto1 has the quality that f(j(1))=f(j(1))=f(1)=1 and so j is a suitable right inverse

d) Yes, in the first example we could have taken j(x)=-1,\text{ }x\notin\mathbb{N} and the second example we could have had j(1)=0, yet both are left and right inverses respectively.

e) Clearly by a) and b) we see that f is bijective. Furthermore, let f(x)\in B be arbitrary (we can say f(x) since it’s surjective), then

f^{-1}(f(x))=g(f(x))\implies f^{-1}=g

and

f(f^{-1}(x))=x=f(h(x))\implies f(f^{-1}(x))=f(h(x))\overset{*}{\implies}f^{-1}(x)=h(x)

where * is furnished by f‘s injectivity. Thus, putting the two together gives g=f^{-1}=h.

6.

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

Proof: Merely take \text{Dom }g=\{1\} and \text{Ran }g=\{0\} and so then the function g:\{1\}\to\{0\}:x\mapsto x^3-x is bijective and a restriction of f (in fact, you could take the vaccuous function f:\varnothing\to\varnothing)

Advertisements

September 25, 2010 - Posted by | Fun Problems, Munkres, Topology | , , , , ,

7 Comments »

  1. Wow! That looks impressive. What prerequisites should one meet to understand this stuff (how much of set theory etc)?

    Comment by Student | September 25, 2010 | Reply

    • I can’t tell if you’re a real person or a bot haha. Though, your e-mail is hoffmankunze which are the authors of a good lin. alg. book. To answer your question: this stuff really isn’t that hard and the only prerequisites are the stuff in the prior post (Munkres section one). This is that set theory.

      Comment by drexel28 | September 25, 2010 | Reply

      • Definitely not a bot. As you have deducted, it would have been a miracle if a bot could appreciate the good book so as to turn the authors into its namesake. 😀

        That’s a relief for me then. Someone told me that it’s futile to even try learning topology if one hasn’t got a complete mastery of set theory, so I was too afraid to even look at a topology book. All the set theory I know was learnt from the preliminary section of Herstein’s Topics In Algebra, so it isn’t strong. (I need to learn some set theory, anyway, since it seems to be everywhere; so let me know if you know any good books, please). Thanks.

        Comment by Student | September 26, 2010

  2. I’m sorry friend! It’s true that topology is probably one of the most heavily set theoretic subjects commonly encountered…besides set theory itself. If you’ve done Herstein (or algebra in general, though Herstein is a very good book) you should be well acquainted with the function aspect of set theory. If you want to learn topology you can pick up Munkres and just start. It’s fairly well self-contained and teaches you all the set theory you need to know (in fact, it will teach you as much or more set theory than most undergraduates/graduates know). If you’re looking for something more comprehensive I LOVED the book Set Theory and Logic by Stoll. If found it to be a comprehensive (and abstract 🙂 ), but readable, exposition on all the set theory a non-set theorist (or set-theoretic topologist) could want to know. In fact, he even goes into some serious logic including the infamous Goedel’s theorem.

    If you have any questions whatsoever, feel free to contact me on here or at afy25@drexel.edu

    Comment by drexel28 | September 26, 2010 | Reply

    • Thanks. I will get both books. The latter merely because I want this burden of set theory that seems to be everywhere not to bother me ever again. But I’m glad that Munkres contains all the set theory that one would need to go through the book and more. That really makes it a brilliant book. Yes, I’ve done Herstein but not yet any other book on Algebra (counting Linear Algebra out – I’ve done Hoffman and Kunze, as you have gathered). I will contact you to let you know how it goes. You are very kind. Thank you.

      Comment by Student | September 27, 2010 | Reply

  3. No problem friend, anything for a fellow math enthusiast!

    Comment by drexel28 | September 27, 2010 | Reply

  4. I am Industrial engineer and I am studying the munkres book by my own. I think this have wonderful applications in my field but at the beginning they are difficult to see. If you know about that kind of stuff I would be happy to talk about.

    Thanks a lot for sharing your work

    Comment by Luis Felipe Cardona | July 18, 2011 | 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: