# Properties of injective functions

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• June 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!
• June 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.
• June 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$.)
• June 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
• June 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?
• June 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.
• June 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.
• June 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!
• June 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.
• June 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.
• June 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!
• June 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
• June 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.
• June 6th 2010, 06:35 PM
Chris11
" A quotation doesn't establish anything." --Joe the plumber circa 1922
• June 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
Page 1 of 2 12 Last