Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$f(S\cap T) \neq f(S) \cap f(T)$

but

$f^{-1}(Q \cap R)=f^{-1}(Q) \cap f^{-1}(R)$

Can you explain it in simple terms, so I understand why and develop the intuition to see if a statement is true or false just by looking at it?

share|improve this question
5  
Please don’t get the idea that anybody can tell whether a formula or a statement is true or false just by looking at it. If you’ve proved it, then you may well see afterwards that the proof was easy; if, as in the case that $f(S\cap T)\ne f(S)\cap f(T)$, you’ve found an easy counterexample, then all will be clear after the fact. But never before the fact. –  Lubin Dec 8 '12 at 2:01
    
Formal proof for the second one is given here. Some counterexamples to the first one are given here. –  Martin Sleziak Oct 1 '13 at 12:18

4 Answers 4

Suppose $x\in f^{-1}(Q\cap R)$. Then $f(x)\in Q\cap R$, and in particular, $f(x)\in Q$ and $f(x)\in R$. Thus $x\in f^{-1}(Q)$ and $x\in f^{-1}(R)$, and we have $x\in f^{-1}(Q)\cap f^{-1}(R)$. This gives us that $f^{-1}(Q\cap R)\subset f^{-1}(Q)\cap f^{-1}(R)$.

On the other hand, suppose $x\in f^{-1}(Q)\cap f^{-1}(R)$. Then $x\in f^{-1}(Q)$ and $x\in f^{-1}(R)$, so $f(x)\in Q$ and $f(x)\in R$, hence $f(x)\in Q\cap R$. This tells us $x\in f^{-1}(Q\cap R)$, therefore $f^{-1}(Q)\cap f^{-1}(R)\subset f^{-1}(Q\cap R)$.

With these two arguments, we have $f^{-1}(Q)\cap f^{-1}(R)= f^{-1}(Q\cap R)$.

share|improve this answer

The main difference between the two statements is the following:

Given some $x$ in the $f^{-1}$(something) there exists only ONE $y$ so that $f(x)=y$. This is used in the proof of the other inclusion for the equality....

BUT, given some $y$ in $f($something), there could exists different $x$ such that $f(x)=y$. It is actually easy to see that for a fixed $f$, one can find $S,T$ so that $F(S \cap T) \neq f(S) \cap f(T)$ if and only if this happens (i.e. if $f$ is not one-to-one).

share|improve this answer

Here is another way of looking at it, based ultimately on ideas from category theory (adjunctions).

Suppose we have a function $f: X \to Y$. The basic connection between direct image $f(-): P(X) \to P(Y)$ between power sets and inverse image $f^{-1}(-): P(Y) \to P(X)$ is that for $A \in P(X)$, $B \in P(Y)$, we have

$$f(A) \subseteq B\;\;\; \text{iff}\;\;\; A \subseteq f^{-1}(B).$$

If $\{B_i\}_{i \in I}$ is a family of subsets of $Y$, we have

$$A \subseteq f^{-1}(\bigcap_{i \in I} B_i) \;\; \text{iff} \;\; f(A) \subseteq \bigcap_{i \in I} B_i \;\; \text{iff}\;\; \forall_{i \in I} f(A) \subseteq B_i \;\; \text{iff} \;\; \forall_{i \in I} A \subseteq f^{-1}(B_i) \;\; \text{iff}\;\; A \subseteq \bigcap_{i \in I} f^{-1}(B_i).$$

Putting $A = f^{-1}(\bigcap_{i \in I} B_i)$ and reasoning forward, we get $f^{-1}(\bigcap_{i \in I} B_i) \subseteq \bigcap_{i \in I} f^{-1}(B_i)$. Putting $A = \bigcap_{i \in I} f^{-1}(B_i)$ and reasoning backward, we get $\bigcap_{i \in I} f^{-1}(B_i) \subseteq f^{-1}(\bigcap_{i \in I} B_i)$. From both containments, we get equality.

The nice thing about this style of proof is its portability and generality: it extends far beyond the specific set-theoretic context considered here.

share|improve this answer

Visualization is by far the most powerful technique for honing mathematical understanding. Lets take advantage of this.

Start by getting out some paper, and a pen. Put 12 points on the left and 5 on the right, representing two sets $X$ and $Y$.

Now draw an arbitrary function. Okay, not quite arbitrary. Make sure that no lines are crossing - this will make it easier to visualize. Also make sure that every point on the right corresponds to at least one point on the left. Again, easier to visualize.

Now stare at your piece of paper a little bit. Observe that

  1. Every $f^{-1}(y)$ is non-empty.
  2. If $y$ and $y'$ are distinct, we have that $f^{-1}(y)$ and $f^{-1}(y)$ are disjoint.

So the preimages of the elements of $Y$ partition $X$. And each block $B \subseteq X$ on the left has a very sensible "name" or label, namely the unique $y$ on the right such that $f^{-1}(y) = B$. So in some sense, the blocks on the left and the elements on the right are "the same." They're in bijective correspondence.

Now whip out a pencil. Draw two subcircles $P$ and $Q$ on the right, compute their intersection. That's three sets of interest, namely $P,Q$ and $P \cap Q$. Now compute the preimage of $f^{-1}(P).$ Notice in particular that $f^{-1}(P)$ is the disjoint union of all the $f^{-1}(p)$ such that $p \in P.$ Its a disjoint union of blocks, just like $P$ is a disjoint union of singletons $\{p\}$ with $p \in P$.

Compute also $f^{-1}(Q)$ and $f^{-1}(P \cap Q)$. Does the intersection of $f^{-1}(P)$ and $f^{-1}(Q)$ precisely equal $f^{-1}(P \cap Q)?$ It sure does. Why are they equal? Because the elements of $Y$ behave just like the blocks of $X$.

Okay, now whip out an eraser, get rid of the pencil subsets, and draw some new ones. Wash, rinse and repeat. Pretty quickly, its going to be making a lot of sense.

Now get your pen back out, and add some redundant points on the right such that $f^{-1}(y)$ is empty. Then do another computation (in pencil!) to convince yourself that essentially nothing has changed.

The next step is, practice visualizing it in your mind. The trick is, don't get bogged down in the details. Does some particular $f^{-1}(y)$ have three elements, or five elements? WHO CARES! The important thing to be able to see in your mind that the points on the right in the range (image) of the function correspond in a bijective fashion to the blocks on the left. Once again, let me reiterate that its okay to imagine the function as consisting of non-overlapping line segments. Essentially no generality is lost.

Pretty soon (it may take anywhere between 10 minutes of intense thought and 5 weeks of ongoing practice), its all going to seem pretty obvious. Once it seems obvious, try to prove the statement yourself, based on introspection. Keep asking youself: "Why is it so obvious to me that it must be true?" and this will guide you to writing a proof that is maximally insightful for you.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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