Peirce's Law Equivalent to Law of Excluded Middle

Theorem

Peirce's Law:

$\left({p \implies q}\right) \implies p \vdash p$

is logically equivalent to the Law of the Excluded Middle:

$\vdash p \lor \neg p$

That is, Peirce's Law holds if and only if the Law of the Excluded Middle holds.

Proof

Let $PL$ stand for the proposition Peirce's Law holds.

Let $LEM$ stand for the proposition The Law of the Excluded Middle holds.

Sufficient Condition

First we show that $LEM \implies PL$.

Let us assume that $LEM$ is true.

Then:

	\(\displaystyle \vdash\)	\(\displaystyle p\)	\(\lor\)	\(\displaystyle \neg p\)	\(\displaystyle \)
	\(\displaystyle \vdash\)	\(\displaystyle q\)	\(\lor\)	\(\displaystyle \neg q\)	\(\displaystyle \)

Suppose $\neg PL$:

$\left({p \implies q}\right) \implies p \not \vdash p$

Then there exists a model $\mathcal M: \left\{{p, q}\right\} \to \left\{{T, F}\right\}$ such that:

	\(\displaystyle \)	\(\displaystyle \mathcal M \left({p}\right)\)	\(=\)	\(\displaystyle F\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \mathcal M \left({\left({p \implies q}\right) \implies p}\right)\)	\(=\)	\(\displaystyle T\)	\(\displaystyle \)

But then:

$\left({F \implies q}\right) \implies F$

That is:

$F \implies q \vdash F$

From Implication Properties:

$F \implies q \vdash T$

From this contradiction we see that it can not be the case that $\left({p \implies q}\right) \implies p \not \vdash p$ must be false.

Therefore $PL$ is true:

$\left({p \implies q}\right) \implies p \vdash p$

that is, Peirce's Law holds.

So $LEM \implies PL$.

$\Box$

A simpler proof in intuitionistic logic: we can prove that $(p \vee \neg p)\implies (((p\implies q)\implies p)\implies p)$ is a tautology of intuitionistic logic.

We need to prove $p$ using premises $p \vee \neg p$ and $(p\implies q)\implies p$.

There are to cases: $p$ or $\neg p$. In the first, $p$ is already proved. In the latter, $p\implies q$ follows from $\neg p$, so we get $p$ from the second premise.

$\Box$

Necessary Condition

Now assume that Peirce's Law holds.

Suppose that $p$ is not false.

If we can show that $p$ therefore has to be true, we have proved that $LEM$ is true.

If $p \implies q$ is true, it must be that $p$ is true.

But when $q$ is false, $p \implies q$ does not hold when $p$ is true.

Therefore $\left({p \implies q}\right) \implies p$ is true.

But if $PL$ is true, that means $p$ is true.

Thus we see that $PL \implies LEM$.

$\blacksquare$

Maybe simpler proof in intuitionistic logic: $\neg(p \vee \neg p) \implies \neg p$ is a tautology, since it's equivalent to $(\neg(p \vee \neg p) \wedge p) \implies \perp$, which is obvious from $p\implies(p\vee\neg p)$.

Furthermore, this implies that $\neg(p \vee \neg p) \implies (p\vee\neg p)$ is also a tautology. Here we use the Peirce's Law:

$(((p \vee \neg p)\implies \perp) \implies (p \vee \neg p)) \implies (p \vee \neg p)$

So we get that $(p \vee \neg p)$ is also a tautology.

$\blacksquare$