How to prove that $\vdash \neg \neg (p \vee \neg p)$? (Natural Deduction)

Question

I do know that double negation and LEM are equivalent, but can we prove $$\vdash \neg \neg (p \vee \neg p)$$ without using either of them, in a Fitch-style proof?

Answer 1

Yes, we can.

Hint: assume $\lnot (p \lor \lnot p)$ and derive a contradiction.

The conclusion follows by $(\lnot \text I)$, which is intuitionistically valid.

Answer 2

What you may use is the fact that in intuitionistic logic one can derive from $\lnot(p\lor q)$ that $\lnot p\land\lnot q$ (and vice versa: the two ways to interpret $p$ NOR $q$ are equivalent)*. And substituting $q:=\lnot p$ into those expressions, the second form easily leads to a contradiction. With this, you should be able to prove what you want to without much difficulty.

*The same is not true for NAND: while from $\lnot p\lor\lnot q$ one easily deduces $\lnot(p\land q)$, the opposite deduction is not possible in intuitionistic logic.