3
$\begingroup$

I've recently started learning First-Order Logic and I have been doing some Natural Deduction exercises. I understand the principles behind most of the Inference Rules but when it comes to applying Classical Rules such as the law of excluded middle, I struggle to reason why it has been used.

For example:

In the proof for:

(φ → ∃x. ψ) ⊢ ∃x. (φ → ψ)

  1. φ → ∃xψ (hypothesis)
  2. φ ∨ ¬φ (law of excluded middle)

    ...

    ∃x. (φ → ψ)

The solution proceeds by using law of excluded middle for φ so that you can use the ∃ elimination rule to reach the conclusion. I understand the solution but I cannot understand why someone has thought to use law of excluded middle to proceed. Is there any intuition behind this, or is it just a 'trick'?

$\endgroup$
2
$\begingroup$

As per @Sudix's answer above, the intuition behind the use of the Law of Excluded Middle in the proof of :

$(φ → ∃x ψ) ⊢ ∃x (φ → ψ)$

is to apply a "case analysis".

(i) Assume that $φ$ does not hold, i.e. assume $¬φ$.

This means (by the truth-table for the conditional) that $φ → ψ$ is TRUE, and thus also $∃x (φ → ψ)$ is TRUE.

(ii) Now assume that $φ$ holds, i.e. assume $φ$.

We know that the premise $(φ → ∃x ψ)$ holds, and this means (again by the truth-table for the conditional) that also $∃x ψ$ is TRUE, i.e. that $ψ$ is TRUE for some $x$.

Thus, $φ → ψ$ is TRUE for some $x$, i.e. $∃x (φ → ψ)$ is TRUE.

$\endgroup$
  • $\begingroup$ Thanks for the response, it's a helpful insight to the meaning of Law of Excluded Middle. As a further question, are there any obvious signs that indicate that a particular deduction will need the Law of Excluded middle in order to solve it? I understand that it allows you to carry out a case analysis which in turn simplifies the problem by allowing you to reason the above conditionals being true. But what is it about the form of (φ→∃xψ) ⊢ ∃x(φ→ψ) that indicates you should use LEM, if anything? $\endgroup$ – AC19 May 23 '18 at 21:08
  • 1
    $\begingroup$ @AC19 One rule of thumb is this. Any disjunction should make you think of proof by cases. Implication is really a kind of disjunction, since $a\implies b$ is equivalent to $\neg a\vee b$. In particular, if "$a\implies b$" is involved, it's reasonable to suspect that at some point our proof will break into an $a$-case and a $\neg a$-case, which hinges on the excluded middle. $\endgroup$ – Noah Schweber May 23 '18 at 21:40
3
$\begingroup$

The law of excluded middle is kinda similar to a case analysis (e.g. for an alternating series the cases even, odd). In this case, the intuition behind the law of excluded middle is that one of the cases is trivial: ¬φ ⊢ ∃x. (φ → ψ)

As is usual, each of the cases is simpler than the original question. This is especially true here: As above case is trivial, only the other case remains to show, so all in all you get a hypothesis (i.e. φ) for free that you can use in your deduction.

$\endgroup$
1
$\begingroup$

I wouldn't call it a 'trick' as much as I would call it a good 'strategy', and over time, as you do more and more of these proofs, you'll start to recognize the times when using the Law of Excluded Middle would be good to use ... and on what statement to use it.

I also would like to point out that just because some proof works out by using the Law of Excluded Middle does not mean that you need the Law of Excluded Middle. In other words, you shouldn't feel like you wouldn't be able to complete the proof if you didn't think to use Excluded Middle.

Indeed, in this case, you can also do a proof by Contradiction:

enter image description here

$\endgroup$
  • $\begingroup$ Also, If you have proof by contradiction, nothing actually requires LEM since you can prove LEM by contradiction. (Also, probably beyond the scope of this question, but when I hear “requires LEM” I think “is not intuitionistically valid”, and this theorem requires it in that sense.) $\endgroup$ – spaceisdarkgreen May 24 '18 at 19:43
0
$\begingroup$

For an intuition one might think of an example or model of the law of excluded middle, e.g. the set of all subsets $P(X)$ of a set $X$ when regarding for a $\phi$ the set $P_\phi:=\{x\in X | \phi(x) \}$ of all elements $x$ in $X$ for which $\phi(x)$ is true and interpreting $\neg \phi$ as the complement $(P_\phi)^c:=\{x\in X|x\not\in P_\phi\}$, moreover $\land$ is interpreted as $\cap$ and $\lor$ as $\cup$ (this is also the standard example of a Boolean algebra).

This structure obeys the law of excluded middle, because in this structure for any $A\in P(X)$ it holds that $X=A\cup A^c$, i.e. any element $x\in X$ is either in $A$ or it is in the complement $A^c$.

B.t.w. not every structure is obeying the law of excluded middle, e.g. a Heyting algebra is in general not a model of the law of excluded middle. A standard example of a Heyting algebra is e.g. the set of open subsets of a topological space (with $\neg$ interpreted as inner part of the complement).

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