# Thread: Is this an equivalent definition for injection?

1. ## Is this an equivalent definition for injection?

I recently had problem set which asked to prove that if for any $\displaystyle A, B \subset X$, we have
$\displaystyle f(A \cap B) = f(A) \cap f(B)$ then $\displaystyle f$ is an injection. (EDITED**)

My proof started with the intention to show that if (pointwise) $\displaystyle f(A) = f(B), then A = B$. And I did that, but when I got it returned, apparently I didn't use the definition of an injection since injectivity implies that for all $\displaystyle x1, x2 \in X, f(x1) = f(x2)$ implies $\displaystyle x1 = x2$.

However, I feel that my proof was valid since A and B can have very well been singleton sets with x1 and x2, respectively. Is my approach incorrect?

2. ## Re: Is this an equivalent definition for injection?

Originally Posted by elemental
I recently had problem set which asked to prove that if for any $\displaystyle A, B \subset X$, then we have
$\displaystyle f(A \cap B) = f(A) \cap f(B)$.
This is not a grammatically correct sentence. What is it that you were asked to prove?

3. ## Re: Is this an equivalent definition for injection?

I had to prove the following statement:

Let $\displaystyle f : X -> Y$ be a function with domain $\displaystyle X$ and codomain $\displaystyle Y$
Prove that if for any $\displaystyle A, B \subset X$ we have $\displaystyle f(A \cap B) = f(A) \cap f(B)$ then $\displaystyle f$ is an injection.

Sorry, I did not clarify the injection clause before.

4. ## Re: Is this an equivalent definition for injection?

Originally Posted by elemental
I recently had problem set which asked to prove that if for any $\displaystyle A, B \subset X$, then we have
$\displaystyle f(A \cap B) = f(A) \cap f(B)$.
You cannot prove that.
You can prove that $\displaystyle f(A \cap B) \subseteq f(A) \cap f(B)$
If $\displaystyle t\in f(A\cap B)$ then $\displaystyle \exists k\in A\cap B~\&~f(k)=t$.
That means $\displaystyle [k\in A~\&~f(k)=t]~\&~[k\in B~\&~f(k)=t]$
So $\displaystyle t\in f(A)\cap f(B).$

5. ## Re: Is this an equivalent definition for injection?

Thanks Plato, but I had incorrectly typed the question before. If you'd like to, please check my correction in my last post!

6. ## Re: Is this an equivalent definition for injection?

Originally Posted by elemental
Thanks Plato, but I had incorrectly typed the question before. If you'd like to, please check my correction in my last post!
Now if $\displaystyle s\in f(A)\cap f(b)$ then $\displaystyle s\in f(A)~\&~s\in f(B).$
Take then one at a time:
$\displaystyle (\exists j\in A)[f(j)=s]~\&~(\exists h\in B)[f(j)=s]$.
but $\displaystyle f\text{ is injective so }f(j)=f(h) \Rightarrow h=j$

Thus $\displaystyle s\in f(A\cap B)$

7. ## Re: Is this an equivalent definition for injection?

Originally Posted by Plato
Now if $\displaystyle s\in f(A)\cap f(b)$ then $\displaystyle s\in f(A)~\&~s\in f(B).$
Take then one at a time:
$\displaystyle (\exists j\in A)[f(j)=s]~\&~(\exists h\in B)[f(j)=s]$.
but $\displaystyle f\text{ is injective so }f(j)=f(h) \Rightarrow h=j$

Thus $\displaystyle s\in f(A\cap B)$
The OP has to prove the converse statement: if $\displaystyle f(A \cap B) \supseteq f(A) \cap f(B)$ for all A and B, then f is injective.

8. ## Re: Is this an equivalent definition for injection?

Originally Posted by emakarov
The OP has to prove the converse statement: if $\displaystyle f(A \cap B) \supseteq f(A) \cap f(B)$ for all A and B, then f is injective.
In that case suppose $\displaystyle x\ne y~\&~f(x)=f(y)$ then let $\displaystyle A=\{x\}~\&~B=\{y\}$ what happens?

9. ## Re: Is this an equivalent definition for injection?

Originally Posted by elemental
I recently had problem set which asked to prove that if for any $\displaystyle A, B \subset X$, we have
$\displaystyle f(A \cap B) = f(A) \cap f(B)$ then $\displaystyle f$ is an injection. (EDITED**)

My proof started with the intention to show that if (pointwise) $\displaystyle f(A) = f(B), then A = B$. And I did that, but when I got it returned, apparently I didn't use the definition of an injection since injectivity implies that for all $\displaystyle x1, x2 \in X, f(x1) = f(x2)$ implies $\displaystyle x1 = x2$.

However, I feel that my proof was valid since A and B can have very well been singleton sets with x1 and x2, respectively. Is my approach incorrect?
I agree that if

f(A) = f(B) implies A = B for all A, B (*),

then

f(x1) = f(x2) implies x1 = x2 for all x1, x2 (**).

As you said, (*) implies (**) by taking A = {x1} and B = {x2}. Therefore, if you proved (*), you basically solved the problem. However, while the step from (*) to (**) can be considered negligible and omitted when talking about some complicated theorem whose proof takes many pages, it is not negligible in the problem designed to test your understanding of injective functions. Since the problem is relatively simple, the proof also has to be spelled out in great detail. So I can understand the issue your instructor had with your proof, which does not even use the definition of injection.

As Plato says, it is easier to prove (**) by considering singleton A and B from the start.

10. ## Re: Is this an equivalent definition for injection?

Ah, I see what you mean and will keep it in mind for the future. Thanks a lot!