Properties of injective functions

Printable View

Show 40 post(s) from this thread on one page

Jun 3rd 2010, 10:29 PM
Mollier

Properties of injective functions

Hi.

problem:
Show that if $f:A\rightarrow B$ is injective and $E\subseteq A$ , then $f^{-1}(f(E))=E$ .

I worked with this for a while but was unable to come up with a good answer.
After a bit of searching, I fould an article on planetmath which answers this question, but I do not understand it completely.
Here's what it says:

Theorem. Suppose $f:A\rightarrow B$ is an injection. Then, for all $C\subseteq A$ , it is the case that $f^{-1}(f(C))=C$ .
Proof. It follows from the definition of $f^{-1}$ that $C\subseteq f^{-1}(f(C))$ , whether or not $f$ happens to be injective.
Hence, all that need to be shown is that $f^{-1}(f(C))\subseteq C$ .
Assume the contrary. Then there would exist $x\in f^{-1}(f(C))$ such that $x\notin C$ .
By definition $x\in f^{-1}(f(C))$ means $f(x)\in f(C)$ , so there exists $y\in A$ such that $f(x)=f(y)$ .
Since $f$ is injective, one would have $x=y$ , which is impossible because $y$ is supposed to belong to $C$ but $x$ is not supposed to belong to $C$ .

I do not see why $y$ is supposed to belong to $C$ . What am I missing here?

Thanks!
Jun 3rd 2010, 10:56 PM
Drexel28

Quote:

Originally Posted by Mollier

Hi.

problem:
Show that if $f:A\rightarrow B$ is injective and $E\subseteq A$ , then $f^{-1}(f(E))=E$ .

I worked with this for a while but was unable to come up with a good answer.
After a bit of searching, I would an article on planetmath which answers this question, but I do not understand it completely.
Here's what it says:

Suppose Theorem. $f:A\rightarrow B$ is an injection. Then, for all $C\subseteq A$ , it is the case that $f^{-1}(f(C))=C$ .
Proof. It follows from the definition of $f^{-1}$ that $C\subseteq f^{-1}(f(C))$ , whether or not $f$ happens to be injective.
Hence, all that need to be shown is that $f^{-1}(f(C))\subseteq C$ .
Assume the contrary. Then there would exist $x\in f^{-1}(f(C))$ such that $x\notin C$ .
By definition $x\in f^{-1}(f(C))$ means $f(x)\in f(C)$ , so there exists $y\in A$ such that $f(x)=f(y)$ .
Since $f$ is injective, one would have $x=y$ , which is impossible because $y$ is supposed to belong to $C$ but $x$ is not supposed to belong to $C$ .

I do not see why $y$ is supposed to belong to $C$ . What am I missing here?

Thanks!

I don't like how that's said exactly, allow me to say it slightly different.

Suppose that $x\in f^{-1}(f(C))$ but $x\notin C$ . Then clearly I have that $f(x)\in f(C)$ , right? But $f(C)=\left\{f(x):x\in C\right\}$ and so $f(x)=f(y)$ for some $y\in C$ (since that's what everything in $f(C)$ "looks" like!). But, since $y\in C$ and $x\notin C$ we clearly must have that $x\ne y$ but since $f(x)=f(y)$ this contradicts injectivity.
Jun 3rd 2010, 11:12 PM
ojones

I've found that places like PlanetMath and Wikipedia usually don't give the clearest explanations. Here's my approach: the statement $f^{-1}(f(E))=E$ is equivalent to $f^{-1}(f(E))\subseteq E$ and $E\subseteq f^{-1}(f(E))$ which we prove separaretly as follows.

(I) $x\in f^{-1}(f(E)) \Rightarrow f(x)\in f(E)$ . Hence, $f(x)=f(e)$ for some $e\in E$ . But $f$ is injective and so $x=e$ . That is, $x\in E$ and so $f^{-1}(f(E))\subseteq E$ .

(II) Let $x\in E$ . Then $f(x)\in f(E)$ . Hence, $x\in f^{-1}(f(E))$ and so $E\subseteq f^{-1}(f(E))$ . (This part doesn't require injectivity.)

The proof by contradiction given in planetmath is completely unnecessary. There's an unwritten rule in mathematics that direct proofs are to be preferred over indirect ones. In other words, don't prove something by contradiction if you have a direct proof available.

Finally, in answer to your question: $y$ is in $C$ because $f(C)=\{ f(y):y\in C \}$ . (I think there's a typo in planetmath;the $A$ should be a $C$ .)
Jun 3rd 2010, 11:18 PM
Drexel28

Quote:

Originally Posted by ojones

There's an unwritten rule in mathematics that direct proofs are to be preferred over indirect ones..

Oh, yeah. Why haven't I ever seen this law? :P
Jun 3rd 2010, 11:21 PM
ojones

Drexel28: You will not "see" this law, you will hear it if you mix in the right circles. Do you have a doctorate in mathematics?
Jun 4th 2010, 12:08 AM
Drexel28

Quote:

Originally Posted by ojones

Do you have a doctorate in mathematics?

Haha, either that is a huge compliment or your being condescending, but no.
Jun 4th 2010, 03:43 PM
ojones

Drexel28: I didn't mean to sound condescending. What I mean is that grad school is where you start to learn the differences between good and bad proofs. At the undergraduate level, instructors are just happy to see a proof!

One reason why direct proofs are preferred over indirect ones is because they often give more information. For example, proving the existece of something with a direct proof requires producing the object or providing an algorithm to find it. A proof by contradiction tells you only that the object exists and nothing more.
Jun 5th 2010, 12:22 AM
Mollier

Quote:

Originally Posted by Drexel28

Suppose that $x\in f^{-1}(f(C))$ but $x\notin C$ . Then clearly I have that $f(x)\in f(C)$ , right?

Actually that is not completely clear to me. $x\notin C$ means to me that $x\in A$ . $f(x)$ is then somewhere in $B$ .
I don't see why it has to be in $f(C)$ . Care to explain a bit more? Thanks.
Ojones: Again, I do not see how $x\in f^{-1}(f(E))$ implies that $f(x)\in f(E)$ . Why can't $f(x)$ go somewhere else in $B$ ?
I feel stupid for asking this as I'm sure it should be obvious, but I still don't have a good grasp of the obvious :)
Thanks!
Jun 5th 2010, 03:21 PM
ojones

This is just the definition of the preimage of a set: if $B^\prime \subseteq B$ then $f^{-1}(B^\prime )=\{ a\in A : f(a)\in B^\prime \}$ .

Hence, $f^{-1}(f(C))=\{ a\in A : f(a)\in f(C)\}$ . Hence $x\in f^{-1}(f(C)) \Rightarrow f(x)\in f(C)$ . Drexel28 is using the same fact.
Jun 5th 2010, 04:59 PM
Plato

Quote:

Originally Posted by ojones

One reason why direct proofs are preferred over indirect ones is because they often give more information. For example, proving the existece of something with a direct proof requires producing the object or providing an algorithm to find it. A proof by contradiction tells you only that the object exists and nothing more.

That is total nonsense.
To quote R L Moore “a proof is a proof”
All other considerations are simply matters of style.
The answer.
Jun 6th 2010, 12:43 AM
Mollier

Quote:

Originally Posted by ojones

This is just the definition of the preimage of a set: if $B^\prime \subseteq B$ then $f^{-1}(B^\prime )=\{ a\in A : f(a)\in B^\prime \}$ .

Hence, $f^{-1}(f(C))=\{ a\in A : f(a)\in f(C)\}$ . Hence $x\in f^{-1}(f(C)) \Rightarrow f(x)\in f(C)$ . Drexel28 is using the same fact.

Aha, now I get it :)
Thanks!
Jun 6th 2010, 12:51 AM
bobak

I think you should now answer the natural following questions.

Quote:

Prove that a function is surjective if and only if it has a right inverse. and hence deduce that bijective functions are invertible.

Bobak
Jun 6th 2010, 06:25 PM
ojones

Plato:

"Proofs by contradiction should not be used if a direct proof is available" - Paul Halmos on mathematical writing.

"All students are enjoined in the strongest possible terms to eschew proofs by contradiction!" - Halsey Royden in Real Analysis.
Jun 6th 2010, 06:35 PM
Chris11

" A quotation doesn't establish anything." --Joe the plumber circa 1922
Jun 6th 2010, 09:08 PM
Mollier

Quote:

Originally Posted by bobak

I think you should now answer the natural following questions.
Bobak

My book states the following:
If $f:A\Rightarrow B$ (surjective) and $H\subseteq B$ , then $f(f^{-1}(H))=H$ .

I try to prove this in a way similiar to the proof ojones gave.

1.
Let $f(x)\in f(f^{-1}(H))$ . Then $f(x)=f(a)$ for some $a\in A$ and $f(a)\in H$ . Hence $f(x)\in H$ and so $f(f^{-1}(H))\subseteq H$ .

2.
Let $f(x)\in H$ . There exist some $x\in A$ such that $x\in f^{-1}(H)$ . Hence, $f(x)\in f(f^{-1}(H))$ and so $H\subseteq f(f^{-1}(H))$ .

Doesn't look as convincing as I would like, but it's the best I can do.

Thanks.

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 06:04 PM.

Copyright © 2005-2016 Math Help Forum. All rights reserved.