# Does the Intersection of Images imply an Injective Function?

I've read that 'f(A n B) = f(A) n f(B) is true iff f is an injective function' (and thus the statement is biconditional), and I've been trying to understand why this is true, but struggling.

I understand from the proofs the implication that if f is Injective $\implies$ f(A n B) = f(A) n f(B). But it's the reverse implication I'm struggling with, as I seem to be finding counter examples; where am I going wrong?

Let f be a function s.t. f(A n B) = f(A) n f(B). Clearly, if x $\in$ (A n B) $\implies$ f(x) $\in$ ( f(A) n f(B) ).

But for some functions, couldn't there also be a set C $\neq$ (A u B) such that f(C) = f(A) n f(B)? And hence, f would be a many-one function, despite f(A n B) = f(A) n f(B)?

Example:

Consider the domain D = {1, 2, 3, 4, 5, 6, 7} and the codomain E = {a, b} and a function f that maps D to E s.t. odd numbers in D map to a and even numbers map to b.

Now, let the sets A, B, C $\subset$ D equal {1, 2} and {1, 2, 3} and {5, 6} respectively. Then, (A n B) = {1, 2} and f(A) n f(B) = {a, b} = f(A n B).

But clearly now, f(C) = {a, b} = f(A) n f(B) - the equality holds, but f is many-one, not injective.

I must be wrong in my logic somewhere/not understood some basic facts about sets and their equality, but can't see what? Any thoughts?

Thanks very much, indeed.

• The statement as written is incorrect. I think one direction asks that it is true for all subsets of the domain (not sure though) – user370967 Nov 27 '17 at 14:25
• Thanks @Math_QED, I see now how I misunderstood the original statement I read. The equality must be true for every pair of subsets of the domain, not just two in particular (which is what I was thinking without realising), in order for the function to be injective (and thus for the statement to be biconditional). Thanks again. – SuperDeliciousCake Nov 27 '17 at 15:36
• Always glad if I can help :) – user370967 Nov 28 '17 at 9:49

## 1 Answer

Suppose that for each subsets $A$ and $B$ of the domain of $f$, it is true that $f(A\cap B)=f(A)\cap f(B)$. You want to deduce from this that $f$ is injective. Let $x$ and $y$ be distinct elements of the domain of $f$; you want to prove that $f(x)\neq f(y)$. Since $x\neq y$, $\{x\}\cap\{y\}=\emptyset$, and therefore$$f(\{x\})\cap f(\{y\})=f(\{x\}\cap\{y\})=\emptyset.$$But$$f(\{x\})\cap f(\{y\})=\bigl\{f(x)\bigr\}\cap\bigl\{f(y)\bigr\}$$and saying that this set is empty means precisely that $f(x)\neq f(y)$.

• I think your use of the word 'each' at the start of your answer alone sparked in my mind where I went wrong. Many thanks! Basically, I misunderstood the original statement. In the counterexample I gave, the equality was true for 2 /particular/ subsets of D, and yet (as demonstrated by C) f was a many-one function. But I understand now that the equality in the original biconditional statement is strictly true for /every/ pair of subsets of D. And thus my example wasn't a relevant counterexample, hence why I was tripping over it. Your full explanation of course proves the implication. Thanks! – SuperDeliciousCake Nov 27 '17 at 15:35
• Sorted, thanks again. – SuperDeliciousCake Nov 27 '17 at 15:39