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)?


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.

  • $\begingroup$ The statement as written is incorrect. I think one direction asks that it is true for all subsets of the domain (not sure though) $\endgroup$ – user370967 Nov 27 '17 at 14:25
  • $\begingroup$ 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. $\endgroup$ – SuperDeliciousCake Nov 27 '17 at 15:36
  • $\begingroup$ Always glad if I can help :) $\endgroup$ – user370967 Nov 28 '17 at 9:49

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)$.

  • 1
    $\begingroup$ 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! $\endgroup$ – SuperDeliciousCake Nov 27 '17 at 15:35
  • $\begingroup$ Sorted, thanks again. $\endgroup$ – SuperDeliciousCake Nov 27 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.