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.

Here is what I've done for the proof, I just need a little bit of guidance in finishing it up.

Proof:

Suppose $A \subseteq X \text{ and } B \subseteq Y$, Let $z \in f(A \cap f^{-1}(B))$ be arb.

First I unpacked the goal statement:

$ \Rightarrow z \in f(A) \cap B $

$ \Rightarrow z \in f(A) \land z \in B $

$ \Rightarrow \exists x \in A \text{ s.t } z = f(x) \land z \in B $

Next I unpacked the assumptions:

$ \Rightarrow \exists x \in A \cap f^{-1}(B) \text{ s.t } z = f(x) $

$ \Rightarrow \exists x \in A \land x \in f^{-1}(B) \text{ s.t } z = f(x) $

$ \Rightarrow \exists (x \in A \text{ s.t } z = f(x)) \land (x \in Y \land x \in B \text{ s.t } z = f(x)) $

So I've proven that $ \exists x \in A \text{ s.t } z = f(x) $, but how do I go about proving that $x \subseteq Y$ and $z \in B$?

share|improve this question
    
Are we to assume $f: X \to Y$? –  amWhy Nov 12 '12 at 23:35
    
Yes, I apologize, I forgot to type that. –  mh234 Nov 12 '12 at 23:41
    
No worries; we appreciate your efforts, and the fact that you typeset your question. –  amWhy Nov 12 '12 at 23:46
    
Just some advice on style: the way you use the symbol "$\wedge$" in the title is slightly strange. I can't help reading the construction "$A \subseteq X \wedge B \subseteq Y$" as a single proposition. You might use it in a statement like: "If $A \subseteq X \wedge B \subseteq Y$, then $A \cup B \subseteq X \cup Y$". The way you've used in the title is different, and peculiar in a way I'm having difficulty articulating. –  Mike F Jul 2 '13 at 5:06

3 Answers 3

up vote 3 down vote accepted

You could profitably go one step further in unpacking the target: you want to show that there is an $x\in A$ such that $z=f(x)\in B$. Now take the first step in your unpacking of the hypothesis (but with the typo corrected): there is an $x\in A\cap f^{-1}[B]$ such that $z=f(x)$. That’s exactly what you want: since $x\in f^{-1}[B]$, it’s immediate that $f(x)\in B$.

And now that the exploration’s done, and the two ends have met in the middle, you can write it up properly:

Let $z\in f\big[A\cap f^{-1}[B]\big]$ be arbitrary; then $z=f(x)$ for some $x\in A\cap f^{-1}[B]$. Then $z=f(x)\in f[A]$ and $z=f(x)\in f\big[f^{-1}[B]\big]\subseteq B$, so $z\in f[A]\cap B$, and hence $f\big[A\cap f^{-1}[B]\big]\subseteq f[A]\cap B$.

share|improve this answer

So you have $x\in A$, so $z = f(x) \in f(A)$.

And $x\in f^{-1}(B)$ so $z = f(x) \in f(f^{-1}(B))\subseteq B$.

In all $z\in f(A)$ and $z\in B$, so $z\in f(A)\cap B$.

share|improve this answer

Let me add a calculational answer to this old question. Throughout I will implicitly assume that $x \in X$, $y \in Y$, $A, A_1, A_2 \subseteq X$ and $B \subseteq Y$. And I'm assuming that apart from set theory and logic, we're only allowed to use the following basic properties, which hold for any $A$, $B$, $x$, and $y$: \begin{array}\\ (0) & y \in f[A] & \equiv & \langle \exists x : x \in A : f(x) = y \rangle \\ (1) & x \in f^{-1}[B] & \equiv & f(x) \in B \\ \end{array} Using only these properties will make the proof a little longer, but as you will see it is mostly quite mechanical: expand the above two 'definitions' and do what comes naturally.


Looking at the shape of $$(2)\;\;\;f[A\cap f^{-1}[B]] \;\subseteq\; f[A] \cap B$$ the first thing that warrants investigation is the left hand side. Can we simplify it? Let's be bold, and look at the more general $f[A_1 \cap A_2]$: for any $y$, $A_1$ and $A_2$ \begin{align} & y \in f[A_1 \cap A_2] \\ \equiv & \;\;\;\;\;\text{"basic property $(0)$"} \\ & \langle \exists x : x \in A_1 \cap A_2 : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"set theory: definition of $\cap$"} \\ & \langle \exists x : x \in A_1 \land x \in A_2 : f(x) = y \rangle \\ \Rightarrow & \;\;\;\;\;\text{"logic: weaken by splitting range of $\exists$"} \\ & \langle \exists x : x \in A_1 : f(x) = y \rangle \;\land\; \langle \exists x : x \in A_2 : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"basic property $(0)$, twice"} \\ & y \in f[A_1] \;\land\; y \in f[A_2] \\ \equiv & \;\;\;\;\;\text{"set theory: definition of $\cap$"} \\ & y \in f[A_1] \cap f[A_2] \\ \end{align} So by the definition of $\;\subseteq\;$ we've proven that $$(3)\;\;f[A_1 \cap A_2] \;\subseteq\; f[A_1] \cap f[A_2]$$ for any $A_1$ and $A_2$. Using this, our first main step is, for any $A$ and $B$ \begin{align} & f[A \cap f^{-1}[B]] \\ (*)\;\;\subseteq & \;\;\;\;\;\text{"by $(3)$"} \\ & f[A] \cap f[f^{-1}[B]] \\ \end{align} That directly leads us into the next investigation: what can we say about $f[f^{-1}[B]]$? Well, for any $y$ and $B$ \begin{align} & y \in f[f^{-1}[B]] \\ \equiv & \;\;\;\;\;\text{"basic property $(0)$"} \\ & \langle \exists x : x \in f^{-1}[B] : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"basic property $(1)$"} \\ & \langle \exists x : f(x) \in B : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"logic: use right hand part in left"} \\ & \langle \exists x : y \in B : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify: extract $y \in B$, which does not use $x$, out of $\exists$"} \\ & y \in B \;\land\; \langle \exists x : : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"make implicit assumption explicit -- to allow us to use $(0)$"} \\ & y \in B \;\land\; \langle \exists x : x \in X : f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"basic property $(0)$; definition of $\cap$"} \\ & y \in B \cap f[X] \\ \end{align} By set extensionality, we've now shown that $$(4)\;\;f[f^{-1}[B]] \;=\; B \cap f[X]$$ for any $B$. Therefore we continue our main calculation, for any $A$ and $B$: \begin{align} & f[A] \cap f[f^{-1}[B]] \\ = & \;\;\;\;\;\text{"simplify $f[f^{-1}[\cdot]]$ using $(4)$"} \\ & f[A] \cap B \cap f[X] \\ (**)\;\;\subseteq & \;\;\;\;\;\text{"set theory -- working toward the right hand side of (2)"} \\ & f[A] \cap B \\ \end{align} This completes the proof.


Note how the calculational approach helped us to discover two nice facts in this domain. Finally, here is a third. Looking at both places where this proof has an inequality, i.e., the steps marked $(*)$ and $(**)$, when will we have an equality, i.e., when will the more general $$f[A\cap f^{-1}[B]] \;=\; f[A] \cap B$$ hold? Clearly $(**)$ holds when $f[X] = Y$, i.e., when $f$ is surjective. And (as shown in, e.g., Please critique these proofs on function theorems) $(*)$ holds when $f$ is injective. Therefore we will have equality when $f$ is both, i.e., $f$ is a bijection.

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.