Let $f:X \rightarrow Y$ be a function and $B_1, B_2 \in \mathcal{P}(Y)$. Prove that $B_1 \subseteq B_2 \Rightarrow \overleftarrow{f}(B_1) \subseteq\overleftarrow{f}(B_2)$.

My attempt:

$\begin{align} B_1 \subseteq B_2 & \Rightarrow & 'f(x)\in B_1 \Rightarrow f(x) \in B_2' \\ & \Rightarrow & 'x \in \overleftarrow{f}(B_1) \Rightarrow x \in \overleftarrow{f}(B_2)'\\ & \Rightarrow & '\overleftarrow{f}(B_1) \subseteq \overleftarrow{f}(B_2)', \text{ as required} \end{align}$

Then, the question asks to prove that the converse is not universally true.

Looking at my proof, I really think that each implication is reversible, so I am tempted to replace the '$\Rightarrow$' with $\iff$. So, either my proof is wrong or I am misreading some of the implication(s). Please advise.

This exercise also made me want to ask the following question: If the '$\iff$' version of a given statement is known to be false and the '$\Rightarrow$' is known to be true, does it always mean that the proof of the '$\Rightarrow$' will contain some implications that are not reversible?

Furthermore, if we are also told that $f$ is surjective, would the converse be true? If yes, then how will the proof look like i.e. how does it differ from the version where we assumed that $f$ is not surjective?


This is not reversible without the assumption that $f$ is surjective. Note that for a function $f: X \to Y$ the statement $f(x) \in B_1 \Rightarrow f(x) \in B_2$ needint imply $B_1 \subset B_2$, as

$$B_1 \subset B_2 \Leftrightarrow (y \in B_1 \Rightarrow y \in B_2)$$

But the latter statement is only equivalent to the $f(x)$ statement if we can guarantee every $y \in B_1$ can be written as some $f(x)$, i.e. $B_1 \subset f(X)$. And if we want this to hold for arbitrary $B_1$ we better have surjectivity.

Said another way, we run into the problem that $f(f^{-1}(B_1)) = B_1 \cap f(X)$. If $f$ is surjective, then this is simply $B_1 \cap f(X) = B_1 \cap Y = B_1$. If we assume surjectivity, or less restrictively simply $B_1 \subset f(X)$ then we simply use the easy fact that the map $f: P(X) \to P(Y)$ taking a subswet to it's image preserves inclusion to see that if $f^{-1}(B_1) \subset f^{-1}(B_2)$ then

$$ B_1 = f(X) \cap B_1 = f(f^{-1}(B_1)) \subset f(f^{-1}(B_2)) = B_2 \cap f(X) \subset B_2$$

For an explicit example, let $X = Y = \mathbb{R}$ and $f:x \mapsto x^2$. Let $B_1 = [-1,1]$ and $B_2 = [0,4]$. Then $$f^{-1}(B_1) = [-1,1] \subset [-2,2] = f^{-1}(B_2)$$

But $B_1 \not\subset B_2$.

So in conclusion, yes certainly if you have a string of logical implications $$ P = P_1 \Rightarrow P_2 \Rightarrow ... \Rightarrow P_n = Q$$ proving an implication $P \Rightarrow Q$ where the converse fails then at least one of the implications $P_{i+1} \Rightarrow P_i$ is false (otherwise we simply use transitivity of logical implication). In fact its also true that if the converse $Q \Rightarrow P$ holds then all intermediary steps are equivalent to each other.

  • 1
    $\begingroup$ A little more detail as to why would be useful here. $\endgroup$ – rogerl Jul 17 '14 at 1:12
  • $\begingroup$ a little more detail added. $\endgroup$ – JHance Jul 17 '14 at 1:34
  • $\begingroup$ @JHance I need some clarification on the notation you used...does $f^{-1}(B_1)$ mean the same thing as $\overleftarrow{f}(B_1)?$ $\endgroup$ – mauna Jul 17 '14 at 14:48
  • 1
    $\begingroup$ @mauna $f(f^{-1}(B_1)) \neq B_1$ in general, as my example showed. So if all we know is that $f^{-1}(B_1) = [-1,1]$ then all we know (in this case) is that $B_1 \cap [0, \infty) = [0,1]$. Since $B_1$ is allowed to be any subset of $Y = \mathbb{R}$, we cannot dismiss the possibility that it contains elements from $(-\infty, 0 ) = Y\backslash f(X)$. $\endgroup$ – JHance Jul 17 '14 at 17:06
  • 1
    $\begingroup$ More generally, your question asks if it is true for every $B_1, B_2 \subset Y$. We thus have to be able to say it for any specified $B_1$. $\endgroup$ – JHance Jul 17 '14 at 17:38

If all the implications of a proof are reversible, you can "run the proof backwards" to prove the converse of the statement. So, if you know the converse of a true statement is false, you necessarily have to have a "non-reversible step" in a proof of the type you give above (I say of the type that you give, meaning a direct proof where each statement is implied by the previous one. If you were proving an implication by contradiction, for instance, things wouldn't be so clear-cut.)

For your question about "$\iff$" proofs, note that if $P\iff Q$ is false but $P \implies Q$ is true, than $Q \implies P$ must be false since $P \iff Q$ is equivalent to $(P \implies Q)\&(Q\implies P)$. If you give a direct proof of $P \implies Q$, by the above discussion you must have a one-way step somewhere along the way.

For $f$ surjective, $f^{-1}(B_1) \subset f^{-1}(B_2) \implies B_1 \subset B_2$ is true. You could prove this by replacing all implications with equivalences in your proof, justifying this as needed. The only step that really requires it is the first one: to replace $B_1 \subset B_2 \implies (f(x) \in B_1 \implies f(x) \in B_2)$ with $B_1 \subset B_2 \iff (f(x) \in B_1 \implies f(x) \in B_2)$, you need to note that every element of $Y$ can be written in the form of $f(x)$ for some $x$.


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.