Converse of $(A\rightarrow B)\rightarrow((B\rightarrow C)\rightarrow(A\rightarrow C))$

Question

I have a basic question about the following proposition.

$(A\rightarrow B)\rightarrow((B\rightarrow C)\rightarrow(A\rightarrow C))$

I can prove it in intuitionistic logic. But I wonder if we have the converse in intuitionistic logic? Or in classical logic?

$((B\rightarrow C)\rightarrow(A\rightarrow C))\rightarrow(A\rightarrow B)$

Thanks!

Answer 1

To see how I found the assignment that falsifies the converse, $$\Bigl((B\to C)\to (A\to C)\Bigr)\to (A\to B),$$ recall that an implication $P\to Q$ is false when $P$ is true and $Q$ is false. So to (try to) falsify this implication, we want $A\to B$ to be false, which means that we must have $A$ true and $B$ false.

Once you have $A$ true and $B$ false, the implication $(B\to C)$ will be true regardless of the truth value of $C$, so to make the antecedent true we just need $A\to C$ to be true as well, which we can achieve by letting $C$ be true. Thus, $A$ and $C$ true and $B$ false will make this proposition formula false: the consequent $A\to B$ is false; the antecedent is true because its consequent $A\to C$ is true (because its consequent $C$ is true).

Answer 2

You can show that the formula evaluates to False under some assignments by picking a falsifying assignment and then check if it indeed falsifies the formual. This can be done easily, you only have $2^3 = 8$ assignments so it won't take you long to go over all assignments and look for a falsifying one (note that when you have $n$ variables, you have an exponential number of assignments so this is not always a good approach). So if you meet more complicated formulas, it can be helpful to first simplify the formula using distribution and de Morgan rules as follows. In propositional logic, every formula of the form $\varphi_1 \to \varphi_2$ is equivalent to the formula $\neg \varphi_1 \lor \varphi_2$. Therefore, $$\begin{align*} ((B\to C) \to (A\to C)) \to (A\to B)&\equiv ((\neg B \lor C) \to (\neg A \lor C)) \to (\neg A \lor B) \\ &\equiv ((\neg(\neg B \lor C)) \lor (\neg A \lor C)) \to (\neg A \lor B)\end{align*}$$ Using de Morgan laws, the above formula is equivalent to $$\begin{align*} &\equiv ((\neg\neg B \wedge \neg C) \lor (\neg A \lor C)) \to (\neg A \lor B)\\ &\equiv (( B \wedge \neg C) \lor (\neg A \lor C)) \to (\neg A \lor B)\\ &\equiv \neg(( B \wedge \neg C) \lor (\neg A \lor C)) \lor (\neg A \lor B)\end{align*}$$ Again, by de Morgan $$\begin{align*} &\equiv (\neg( B \wedge \neg C) \wedge \neg(\neg A \lor C)) \lor (\neg A \lor B)\\ &\equiv (( \neg B \lor \neg \neg C) \wedge (\neg \neg A \wedge \neg C)) \lor (\neg A \lor B)\\ &\equiv (( \neg B \lor C) \wedge ( A \wedge \neg C)) \lor (\neg A \lor B)\end{align*}$$ By the distribution rule $$ \equiv ( (\neg B \lor C) \lor (\neg A \lor B) ) \wedge ( (A \wedge \neg C) \lor (\neg A \lor B))$$

Since $B\lor \neg B \equiv \text{True}$, the above formula is equivalent to $$\begin{align*} &\equiv ( \text{True} \lor C \lor \neg A ) \wedge ( (A \wedge \neg C) \lor (\neg A \lor B))\\ &\equiv \text{True} \wedge ( (A \wedge \neg C) \lor (\neg A \lor B))\\ &\equiv (A \wedge \neg C) \lor (\neg A \lor B) \end{align*}$$ This formula is a bit easier than the original one. When $A$ is True, the above formula is equivalent to $\neg C \lor B$ which is obviously not equivalent to True. Indeed, if you follow the assignment in the comment section and assign $A = \text{True}$, $C = \text{True}$, $B = \text{False}$, you get that the formula evaluates to $\neg \text{True} \lor \text{False} = \text{False}$.