2

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.

Shaun
  • 44,997
  • 2
    Yeah, classical logic's $A\to B$ is not a very intuitive model of implication. So the answer to “what is the intuition” may be “there isn't any”. You might find the implication of constructive logic to be a more intuitive model. In constructive logic the interpretation of $(A\to B)\lor (B\to C)$ is “I either have a method for turning a proof of $A$ into a proof of $B$, or I have a method for turning a proof of $B$ into a proof of $C$”. Put this way, there's no reason to expect it to necessarily be true, and indeed it's not constructively valid. – MJD Oct 06 '23 at 19:01
  • 3
    I've resolved a lot of my problems with the counterintuitive behaviour of $\to$ by realising the classical definition of "$A \to B$" is often different to what I mean when I say "$A$ implies $B$" in the setting of "normal" maths. Usually when I say "$A$ implies $B$", there's a free variable which I am implicitly universally quantifying over. EG "if $4 \mid n$, then $2 \mid n$" is really $\forall n \in \Bbb N, 4 \mid n \to 2 \mid n$". I almost never reason about a single instance of an implication. Accordingly, these weird facts about implication usually don't hold for quantified implications.. – Izaak van Dongen Oct 06 '23 at 23:04
  • 3
    In some sense the validity of $(A \to B) \lor (B \to C)$ says "if $X$, $Y$, and $Z$ are subsets of ${1}$, then $X \subseteq Y$ or $Y \subseteq Z$". This is not so weird to me - and when I think about it, the reason I accept that is because of an excluded middle argument (if $X \nsubseteq Y$, then $Y$ must be empty). Some part of me automatically tries to read it as "if $X$, $Y$, and $Z$ are subsets of some big old set $U$, then $X \subseteq Y$ or $Y \subseteq Z$". This would be weird, and it's of course not true. I hope that this perspective is somewhat helpful! – Izaak van Dongen Oct 06 '23 at 23:11
  • 1
    @IzaakvanDongen I don't remember having seen this explanation, but really like it. Thanks! – MJD Jan 30 '24 at 21:03

2 Answers2

6

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.

Kovomaka
  • 713
  • 1
    That's a great way of looking at it. Thank you! – Shaun Oct 06 '23 at 17:56
  • 1
    It also helps to understand why the formula is not valid in intuitionnistic logic : we used $B \vee \neg B$ here (but of course, it does not show that we absolutely had to use it) – Kovomaka Oct 06 '23 at 17:57
  • 1
    @MJD $(A \to B) \lor (B \to C)$ follows from $B \lor \neg B$ by constructive dilemma. – PW_246 Oct 06 '23 at 19:07
0

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

ryang
  • 38,879
  • 14
  • 81
  • 179