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.

I need help in verifying the following please:

Let $f:X\to Y$ be a function, and let $A,B\subseteq X$, and let $C,D\subseteq Y$. Then

  • $f(A\cap B)\subseteq f(A)\cap f(B)$
  • $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$

I am not quite certain how to get started, and would appreciate any help. Thanks.


Edit:

Please excuse my ignorance, but I think that part of the trouble I am having is notational, since I only have this proposition from one book and the definitions of image and preimage from another. Here is what I have for the definitions:

Let $f: X \to Y$ be a function. Then the image of $A$ under $f$ is $$ f(A) := \{f(a) \in Y)(a \in A)\} $$ and the preimage of $C$ under $f$ is $$ f^{-1}(C) := \{(x \in X)(f(x) \in C)\}. $$

So are the above definitions `missing' something? Thanks again.

share|improve this question
2  
If $y\in f(A\cap B)$, what does that mean? What does it mean if $x\in f^{-1}(C\cap D)$? If $x\in f^{-1}(C)\cap f^{-1}(D)$? These should follow fairly smoothly just from definitions of image, preimage, and intersection. Start by writing those out, even if it seems obvious. –  Cameron Buie May 14 '12 at 6:11

2 Answers 2

You really have three things to prove:

  • $f(A\cap B)\subseteq f(A)\cap f(B)$;
  • $f^{-1}(C\cap D)\subseteq f^{-1}(C)\cap f^{-1}(D)$; and
  • $f^{-1}(C)\cap f^{-1}(D)\subseteq f^{-1}(C\cap D)$.

(The last two together of course give you $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$.) Each of these can be done by ‘element-chasing’. To get you started, I’ll illustrate with the first.

Suppose that $y\in f(A\cap B)$. By definition this means that there is some $x\in A\cap B)$ such that $y=f(x)$. By the definition of intersection, $x\in A$ and $x\in B$. Since $x\in A$, by definition $y=f(x)\in f(A)$. Similarly, $y\in f(B)$, and it follows from the definition of intersection that $y\in f(A)\cap f(B)$. Since $y$ was an arbitrary element of $f(A\cap B)$, this shows that every element of $f(A\cap B)$ belongs to $f(A)\cap f(B)$, i.e., that $f(A\cap B)\subseteq f(A)\cap f(B)$.

You can use the same kind of argument to prove each of the other two inclusions.

I’ve included more detail in the justifications than is perhaps strictly necessary, even at a beginning stage, but in general it’s best at first to include more explanation rather than less. There are two reasons for this. First, it forces you to think about the precise justifications for your statements; this helps to avoid one of the most common sources of careless error $-$ slipping in something that seems intuitively obvious without checking that it’s actually provable. Secondly, it makes it much easier for your instructor to tell whether you actually understand what you’re doing and to clear up any misconceptions that you may have.

Added: The definitions of image and preimage that you’re using are fine, though I don’t really like the notation that they use. I would write $$f[A]=\{f(a):a\in A\}$$ and $$f^{-1}[A]=\{x\in X:f(x)\in A\}\;,$$ but the substance of the definitions is the same. The image of a set $A\subseteq X$ under $f$ is the set of all ‘outputs’ of $f$ when the ‘inputs’ come only from $A$; the preimage of a set $A\subseteq Y$ under $f$ is the set of all points in $X$ that $f$ maps to points in $A$.

Since I dealt only with images in my original answer, perhaps I should say a little more about preimages. Suppose that $x\in f^{-1}(A)$ for some set $A\subseteq Y$. This means that $x$ is one of the points of $X$ taken by $f$ to some point of $A$. In other words, $f(x)$ must be in $A$. Conversely, if $f(x)\in A$, then by definition $x\in f^{-1}(A)$. Thus, $x\in f^{-1}(A)$ if and only if $f(x)\in A$. With that in hand, let’s look at the third of the three things that I listed above.

Suppose that $x\in f^{-1}(C)\cap f^{-1}(D)$; by definition of intersection this means that $x\in f^{-1}(C)$ and $x\in f^{-1}(D)$. We’ve just seen that $x\in f^{-1}(C)$ if and only if $f(x)\in C$. Similarly, $x\in f^{-1}(D)$ if and only if $f(x)\in D$. Thus, we now know that $f(x)\in C$ and $f(x)\in D$, i.e., that $f(x)\in C\cap D$. But this means that $x\in f^{-1}(C\cap D)$, and since $x$ was an arbitrary element of $f^{-1}(C)\cap f^{-1}(D)$, it follows that $f^{-1}(C)\cap f^{-1}(D)\subseteq f^{-1}(C\cap D)$.

share|improve this answer
    
The OP posted a follow-up question as an answer which I added to the question because it was too long for a comment. –  t.b. May 20 '12 at 17:14

What you are experiencing is the result of a common abuse of notation. Personally, I prefer to not engage in that abuse of notation when students are first exposed to these concepts, and only later allow the abuse.

Let $X$ and $Y$ be sets, and let $f\colon X\to Y$ be a function between $X$ and $Y$. As soon as you have such a function $f$, you can use $f$ to create two new, related, functions (we say that $f$ "induces" two function), called the direct image and the inverse image functions. I will use $\underline{f}$ for the direct image function, and $\overline{f}$ for the inverse image function.

The direct image function maps subsets of $X$ to subsets of $Y$; that is, it is a function $$\underline{f}\colon\mathcal{P}(X)\to\mathcal{P}(Y)$$ (where $\mathcal{P}(Z)$ is the "power set of $Z$", the set of all subsets of $A$), and is defined by: $$\underline{f}(A) = \{f(a)\mid a\in A\}\subseteq Y,\qquad\text{for a given }A\subseteq X.$$ Note how $f$ figures in the definition. The inverse image function maps subsets of $Y$ to subsets of $X$, $$\overline{f}\colon \mathcal{P}(Y)\to\mathcal{P}(X)$$ defined by $$\overline{f}(B) = \{x\in X \mid f(x)\in B\}\subseteq X,\qquad\text{for a given }B\subseteq Y.$$ Again, note how $f$ figures in the definition.

One way to think about this: an element $y\in Y$ is in the direct image of $A$, $\underline{f}(A)$, if and only if $y$ is the image of someone in $A$. An element $x\in X$ is in the inverse image of $C$, $x\in \overline{f}(C)$, if and only if the image of $x$ is in $C$.

For example: take $X=\{1,2,3\}$, $Y=\{a,b,c\}$, $f\colon X\to Y$ given by $f(1)=a$, $f(2)=b$, $f(3)=b$.

The power sets are: $$\begin{align*} \mathcal{P}(X) &= \Bigl\{ \varnothing,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\}\Bigr\}\\ \mathcal{P}(Y) &= \Bigl\{ \varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,b\},\ \{a,c\},\ \{b,c\},\ \{a,b,c\}\Bigr\} \end{align*}$$ What are $\underline{f}$ and $\overline{f}$? Since it's Sunday, I'll write them out in detail:

First, the direct image: $$\begin{align*} \underline{f}(\varnothing) &= \{f(x)\mid x\in\varnothing\} \\ &= \varnothing.\\ \underline{f}\Bigl( \{1\}\Bigr) &= \{f(1)\}\\ &= \{a\}.\\ \underline{f}\Bigl(\{2\}\Bigr) &= \{f(2)\}\\ &= \{b\}.\\ \underline{f}\Bigl(\{3\}\Bigr) &= \{f(3)\}\\ &= \{b\}.\\ \underline{f}\Bigl(\{1,2\}\Bigr) &= \{f(1),f(2)\}\\ &= \{a,b\}.\\ \underline{f}\Bigl(\{1,3\}\Bigr)&= \{f(1),f(3)\}\\ &= \{a,b\}.\\ \underline{f}\Bigl(\{2,3\}\Bigr) &= \{f(2),f(3)\} = \{b,b\}\\ &= \{b\}.\\ \underline{f}\Bigl(\{1,2,3\}\Bigr) &= \{f(1),f(2),f(3)\} = \{a,b,b\}\\ &= \{a,b\}. \end{align*}$$

If $A,B\subseteq X$, then $\underline{f}(A)$ and $\underline{f}(B)$ are subsets of $Y$, so it makes sense to take their intersection, which is a subset of $Y$; also, $A\cap B$ is a subset of $X$, so we can take its direct image. The first question is asking you to verify that the direct image of the intersection is contained in the intersection of the direct images. For example, with the function above, if $A=\{1,2\}$ and $B=\{2,3\}$, then $A\cap B=\{2\}$. Now note that $$\underline{f}(A\cap B) = \underline{f}(\{2\}) = \{b\}.$$ On the other hand, $$\underline{f}(A)\cap\underline{f}(B) = \{a,b\}\cap\{b\} = \{b\}.$$ So in this case, $f(A\cap B)= f(A)\cap f(B)$. We don't always get equality, though: if $A=\{1,2\}$ and $B=\{3\}$, then $$\underline{f}(A\cap B) = \underline{f}(\varnothing) = \varnothing \subsetneq \{2\} = \{1,2\}\cap\{2\} = \underline{f}(A)\cap\underline{f}(B).$$

The question is asking you to prove that the inclusion holds in every case. That is, you want to show that $f\colon X\to Y$ is a function between two sets, and $y\in \underline{f}(A\cap B)$, then $y\in \underline{f}(A)\cap \underline{f}(B)$.

On the other hand, the inverse image function is: $$\begin{align*} \overline{f}(\varnothing) &= \{x\in X\mid f(x)\in\varnothing\}\\ &=\varnothing.\\ \overline{f}\Bigl( \{a\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in \{a\}\Bigr\}\\ &= \{1\}.\\ \overline{f}\Bigl(\{b\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in\{b\}\Bigr\}\\ &= \{2,3\}.\\ \overline{f}\Bigl(\{c\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in\{c\}\Bigr\}\\ &= \varnothing.\\ \overline{f}\Bigl(\{a,b\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in\{a,b\}\Bigr\}\\ &= \{1,2,3\}.\\ \overline{f}\Bigl(\{a,c\}\Bigr)&= \Bigl\{x\in X\mid f(x)\in\{a,c\}\Bigr\}\\ &= \{1\}.\\ \overline{f}\Bigl(\{b,c\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in \{b,c\}\Bigr\}\\ &= \{2,3\}.\\ \overline{f}\Bigl(\{a,b,c\}\Bigr) &= \Bigl\{x\in X\mid f(x)\in \{a,b,c\}\Bigr\}\\ &= \{1,2,3\}. \end{align*}$$ Again, if $C$ and $D$ are subsets of $Y$, then so is $C\cap D$, and we can about the relationship between $\overline{f}(C\cap D)$ and $\overline{f}(C)\cap\overline{f}(D)$. The second problem is asking to verify you always have equality. That is, that $x\in \overline{f}(C\cap D)$ if and only if $x\in\overline{f}(C)\cap\overline{f}(D)$.


Once you get more familiar with the direct and inverse image functions, it is common to drop the underline and overline and simply denote all three functions (the original $f$, the direct image $\underline{f}$, and the inverse image $\overline{f}$) by $f$; this is done because there is usually no possible confusion between elements of $X$, subsets of $X$, and *subsets of $Y$, so from context one knows whether we are applying $f$, $\underline{f}$, or $\overline{f}$.

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.