# What is wrong with my proof (set theory)

$f:A\to B$ is given, $C_1$ and $C_2$ are subsets of $A$. Is it true that $f(C_1 \cap C_2) = f(C_1) \cap f(C_2)$?

I can give an example to prove it wrong: if we take $C_1=[-1,0]\,,\, C_2=[0,1]$ , and if $f(x)=x^2$ , then, I know that $[0,1]≠\{0\}$ therefore the statement is wrong. However, I tried to prove it and:

From left to right:

$$x\in f(C_1 \cap C_2) \Rightarrow f^{-1}(x) \in C_1 \cap C_2 \Rightarrow f^{-1}(x) \in C_1\;\; \text{and}\;\; f^{-1}(x) \in C_2 \Rightarrow$$

$$x\in f(C_1) \;\;\text{and}\;\; x\in f(C_2) \Rightarrow x\in f(C_1)\cap f(C_2)$$

Therefore it is true. Let's check from right to left:

$$x∈f(C_1)\cap f(C_2) \Rightarrow x∈f(C1)\;\;\text{ and}\;\; x∈f(C_2) \Rightarrow f^{-1}(x)∈C_1\;\; \text{and}\;\; f^{-1}(x)∈C_2$$

$$\Rightarrow f^{-1}(x)∈C_1\cap C_2 \Rightarrow x∈f(C_1\cap C_2)$$

This seems true also. However it should not be. What is wrong can you see?

-

Both halves of your argument suffer from the same problem: your calculations work only if $f$ is one-to-one. Take the second half: you start with an arbitrary $x\in f[C_1]\cap f[C_2]$ and infer that $x\in f[C_1]$ and $x\in f[C_2]$, which is fine. But then you talk about $f^{-1}(x)$ as if this were a single object, and there’s no reason to think that this is the case. You know that there is some $y_1\in C_1$ such that $x=f(y_1)$ and some $y_2\in C_2$ such that $x=f(y_2)$; you don’t know, however, that $y_1=y_2$, and indeed, as your example shows, this may not be the case. Thus, you cannot conclude that there is some $y\in C_1\cap C_2$ such that $x=f(y)$.

You made the same mistake in the first half of your argument, though in that case the inclusion that you were trying to prove actually is true. Remember, if $f$ isn’t known to be one-to-one, there may be a large set of things mapped to $x$ by $f$. You really should talk about $$f^{-1}[\{x\}]=\{y:f(h)\in\{x\}\}=\{y:f(y)=x\}\;,$$ just as you might talk about $f^{-1}[C_1]=\{y:f(y)\in C_1\}$: in both cases you’re looking at a set of elements in the domain, not at a single element.

-

First of all, you don't prove a counterexample. You use it to show that the premise holds but the conclusion does not.

You did that, just before attempting to prove.

Now the mistake you had was in the "from right to left" part. The fact that $x\in f(C_1)\cap f(C_2)$ does not mean that $f^{-1}(x)\in C_1\cap C_2$. It is possible that $x=f(y_1)=f(y_2)$ where $y_i\in C_i$.

For example, $1\in f([0,1])\cap f([-1,0])$ but $1=1^2=(-1)^2$.

-

The problem is that there is no such thing as $f^{-1}$. You have $$x\in f(C_1)\Rightarrow \exists a\in C_1\colon f(a)=x$$ and similarly $$x\in f(C_2)\Rightarrow \exists b\in C_2\colon f(b)=x.$$ But the values guaranteed to exis can be different.

-
$\,f^{-1}\,$ is a well-known and widely accepted symbol for "inverse image", though it is also used for "the inverse function of". – DonAntonio Oct 15 '12 at 21:51

The problem in your proof is the assumption that a function $f^{-1}$ with the property $f^{-1}(x) \in C \Leftrightarrow x \in f(C)$ exists. Such a function only exists if $f$ is bijective, and in fact, for injective $f$ (and hence, for injective $f$), the claim $f(C_1 \cap C_2) = f(C_1) \cap f(C_2)$ holds.

-
It isn't necessary the function is bijective. The symbol $\,f^{-1}\,$ seems to be used here in the widely accepted meaning of "inverse image", not inverse function. – DonAntonio Oct 15 '12 at 21:52
True, but the notation is confusing in that case: If he were talking about the inverse image, $f^{-1}(c)$ should be a subset of <whatever>, not an element. – Johannes Kloos Oct 16 '12 at 8:48
Well, that precisely is part of his mistake(s) – DonAntonio Oct 16 '12 at 13:20