What's the intuition behind using Law of Excluded Middle in Natural Deduction?

Question

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'?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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: