In classical logic, $\vdash (A\to B)\lor(B\to C)$. What is going on here?

194 Views Asked by At

Note: this is a and question. It need not, therefore, have a precise answer.

Motivation:

Consider the formula

$$(A\to B)\lor (B\to C).\tag{1}$$

Suppose it is not true. Then $\lnot(A\to B)$ and $\lnot (B\to C)$. From the former, we have, in particular, $\lnot B$, but from the latter, we have $B$, a contradiction.

So $(1)$ is true!


It is shown here that $(1)$ requires the Law of Excluded Middle; that is, $(1)$ is not intuitionistic.


This question inspired this very question, since $(1)$ is more general than

$$(A\to B)\lor (B\to A).\tag{2}$$

The Question:

What exactly is going on here? To clarify, what is the intuition behind $(1)$?

Thoughts:

This answer goes some way towards clarifying things, but focuses on $(2)$.

"What is the issue? The proof given is fine!"

Well, my problem is with disjunctive syllogism and $(1)$. We could conclude $B\to C$ from $\lnot(A\to B)$. This seems absurd. The only way around it I see is to keep I mind that the truth table is

$$\begin{array}{c|c|c} P & Q & P\to Q\\ \hline T & T & T\\ T & F & F\\ F & T & T\\ F & F & T \end{array}.$$

I don't think I can articulate it much better than that. I suppose if I could, I wouldn't need to ask this question.

2

There are 2 best solutions below

3
On BEST ANSWER

You can think about this in terms of whether or not $B$ holds.

If $B$ holds, then $A \to B$ has to hold, since the conclusion is true.

Otherwise, $B$ is false. And then $B \to C$ holds, since a false premise implies everything. This is where the intuition seems to fail ; and why some fragments of logic don't allow $\bot$ to imply everything.

0
On

$\vdash (A\to B)\lor(B\to C)$

Logically, the above two disjuncts cannot both be false: if the first is false then the second must be vacuously true, while if the second is false the first must have a true consequence and thus automatically be true.