5
$\begingroup$

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!

$\endgroup$
1
  • 4
    $\begingroup$ If $A$ and $C$ are both true, and $B$ is false, then $(B\to C)\to(A\to C)$ is true (since $A\to C$ is true), but $A\to B$ is false. $\endgroup$ Dec 8, 2020 at 18:39

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ You can force a new line by using \`, instead of jumping in and out of math display mode. I used align*` to align them, but you don't have to. $\endgroup$ Dec 8, 2020 at 22:48
  • $\begingroup$ @ArturoMagidin Thanks, I will keep that in mind. It looks better. $\endgroup$ Dec 8, 2020 at 22:51
  • $\begingroup$ There's a way in LaTeX to put comments between aligned formulas so the alignment keeps but I'm not sure how (or if it is possible) to do it in MathJax. $\endgroup$ Dec 8, 2020 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .