5
$\begingroup$

Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking:

"lets start with some form of the law of the excluded middle (LEM) and take it from there."

But recently I more and more realise that most proofs can be done simpler and shorter in other ways, even if you may add forms of LEM as one line theorems into a proof. (like in some Fitch setups)

With LEM you standard get into an $ \lor$ elimination proof, (giving two subproofs) while without LEM, you can do the same with a single $\lnot$ introduction subproof.

This made me wonder are there proofs where introducing some form of LEM does shorten the proof?

(off course this is except proofs of the law of excluded middle itself or a closely related theorems like $\forall x (F(x) \lor \lnot F(x)) $)

My question is about "normal" natural deductions containing just the standard introduction and elimination rules for connectives:

  • $ \land $ introduction and elimination
  • $ \lor $ introduction and elimination
  • $ \to $ introduction and elimination
  • $ \equiv $ introduction and elimination
  • $ \bot $ introduction and elimination
  • $ \lnot$ introduction and
  • $ \lnot \lnot $ elimination

So without recourse to de DeMorgan laws and other derrived rules.

$\endgroup$
  • $\begingroup$ How many steps does it take you to produce a proof of the law of Clavius CCNppp without the use of the law of the excluded middle? $\endgroup$ – Doug Spoonwood May 13 '14 at 18:43
  • 1
    $\begingroup$ Two notes on your question, hope you'll find them helpful: how long or short a proof is would require some work to make it precise, and be specific to the proof system. You hint at this issue yourself when you mention subproofs. And asking about length of proofs is very different from asking whether LEM is needed. I think you have answers to both questions. $\endgroup$ – MikeC May 14 '14 at 18:24
  • $\begingroup$ Here's a fun fact. From a classical point of view, $A$ is indistinguishable from $¬ (¬ A)$, and if $A$ is provable classically, $¬ (¬ A)$ is provable intuitionistically (1). $\endgroup$ – Rui Baptista May 15 '14 at 0:58
2
$\begingroup$

Sure. There exist natural deduction proofs which have all sorts of irrelevant hypotheses and blow up to thousands, or hundreds of lines long. But, there exist proofs which use the law of the excluded middle which are shorter.

Perhaps better let's consider this formula CCpqCCrqCAprq which can replace the A-elimination rule. We can "commute the antecedents" a few times and obtain CApqCCprCCqrr. Consequently, CCpqCCNpqq is a theorem. Using the law of the excluded middle we can write a proof like this:

hypothesis   1 | Cpq
hypothesis   2 || CNpq
LEM          3 || ApNp
Ao {3, 2, 1} 4 || q
Ci 2-4       5 |  CCNpqq
Ci 1-5       6   CCpqCCNpqq.

But does there exist any natural deduction proof which after introduction the hypophthesis "Cpq" and "CNpq" allows use to deduce "q" in just two more steps? I don't see how such a proof could exist. A proof of CCNpqCCpqq will also take 6 steps here, but without the law of the excluded middle, I don't see how you could find a shorter proof. So, it almost surely holds that the law of the excluded middle can sometimes lead to the shortest proof of a theorem.

$\endgroup$
  • $\begingroup$ you are right, thanks $\endgroup$ – Willemien May 19 '14 at 21:21
3
$\begingroup$

First, there are theorems provable in a classical setting that cannot be proved without LEM just because they are not true (in full generality) in certain intuitionistic settings, such as the Extreme Value Theorem; see this recent text. Other than that, relying on LEM often shortens the proof but of course gives a weaker result. For instance, showing that $\sqrt{2}$ is irrational is certainly shorter if one is allowed to use LEM, but a proof without an estimate leaves one with a sawdust taste in one's mouth, according to Bishop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.