Properties of injective functions

Hi.

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

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

Thanks!

Quote:

---

Originally Posted by Mollier

Hi.

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

I do not see why $\displaystyle y$ is supposed to belong to $\displaystyle 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 $\displaystyle x\in f^{-1}(f(C))$ but $\displaystyle x\notin C$. Then clearly I have that $\displaystyle f(x)\in f(C)$, right? But $\displaystyle f(C)=\left\{f(x):x\in C\right\}$ and so $\displaystyle f(x)=f(y)$ for some $\displaystyle y\in C$ (since that's what everything in $\displaystyle f(C)$ "looks" like!). But, since $\displaystyle y\in C$ and $\displaystyle x\notin C$ we clearly must have that $\displaystyle x\ne y$ but since $\displaystyle f(x)=f(y)$ this contradicts injectivity.

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

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

(II) Let $\displaystyle x\in E$. Then $\displaystyle f(x)\in f(E)$. Hence, $\displaystyle x\in f^{-1}(f(E))$ and so $\displaystyle 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: $\displaystyle y$ is in $\displaystyle C$ because $\displaystyle f(C)=\{ f(y):y\in C \}$. (I think there's a typo in planetmath;the $\displaystyle A$ should be a $\displaystyle C$.)

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

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?

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.

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.

Quote:

---

Originally Posted by Drexel28

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

---

Actually that is not completely clear to me. $\displaystyle x\notin C$ means to me that $\displaystyle x\in A$. $\displaystyle f(x)$ is then somewhere in $\displaystyle B$.
I don't see why it has to be in $\displaystyle f(C)$. Care to explain a bit more? Thanks.
Ojones: Again, I do not see how $\displaystyle x\in f^{-1}(f(E))$ implies that $\displaystyle f(x)\in f(E)$. Why can't $\displaystyle f(x)$ go somewhere else in $\displaystyle 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!

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

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

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.

Quote:

---

Originally Posted by ojones

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

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

---

Aha, now I get it :)
Thanks!

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

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.

" A quotation doesn't establish anything." --Joe the plumber circa 1922

Quote:

---

Originally Posted by bobak

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

---

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

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

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

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

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

Thanks.