# If a converse of an implication is false, does this mean that the proof of that implication will always have an implication that is not reversible?

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.

• A little more detail as to why would be useful here. – rogerl Jul 17 '14 at 1:12
• a little more detail added. – JHance Jul 17 '14 at 1:34
• @JHance I need some clarification on the notation you used...does $f^{-1}(B_1)$ mean the same thing as $\overleftarrow{f}(B_1)?$ – mauna Jul 17 '14 at 14:48
• @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)$. – JHance Jul 17 '14 at 17:06
• 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$. – 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$.