Prove that $\vdash p \lor \lnot p$ is true using natural deduction
I would like not to use de morgan law, as you would need to include that as a premise. I was thinking of this proof.
- $\lnot (p \lor \lnot p) \quad \quad \quad (H)$
- $p \quad \quad \quad \quad \quad (H)$
- $p \lor \lnot p \quad \quad \; \;(\lor \text{I} 2)$
- $ \bot \quad \quad \quad \quad \;\;(\lnot \text{E}1,3)$
- $\lnot p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \; (\lnot \text{I}2 - 4)$
- $p \lor \lnot p \;\;\;\;\;\;\;\;\; \;\;\;\;\;\,(\lor \text{I}5)$
- $\bot \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,(\lnot \text{E}1,6)$
- $p \lor \lnot p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\;\;\;(\bot \text{E}1-7)$
The "standard" Natural Deduction proof of it is :
1) $\lnot (p \lor \lnot p)$ --- assumed [a]
2) $p$ --- assumed [b]
3) $p \lor \lnot p$ --- 2) : $\lor$I
4) $\bot$ --- 1), 3) : $\rightarrow$E
5) $\lnot p$ --- 2), 4) : $\rightarrow$I, discharging [b]
6) $p \lor \lnot p$ --- 5) : $\lor$I
7) $\bot$ --- 1), 6) : $\rightarrow$E
8) $p \lor \lnot p$ --- 1), RAA, discharging [a]
As expected, we need the classical rule for indirect proof (RAA, which is equivalent to Double Negation) to prove it, because Excluded Middle : $p \lor \lnot p$ is not intuitionistically valid.