weird natural deduction question

64 Views Asked by At

There are these two questions that my professor posted, and they absolutely stumped me:

$ \vdash (\exists x. \bot) \implies P $ and $(\exists x. \top) \vdash (\forall x. \bot ) \implies P$.

What do I even do with the $(\exists x. \bot)$ part? It got me stuck for quite some time. Any help will be appreciated.

2

There are 2 best solutions below

3
On BEST ANSWER

In a syntax that allows vacuous quantification (bad and un-Fregean, but now sadly usually permitted), $\exists x\,\phi$ is equivalent to plain $\phi$, where $\phi$ is closed, without free variables, and so $\exists x\,\bot$ is equivalent to plain $\bot$. And you know, presumably, about the ex falso principle $\vdash \bot \to P$. Put those two together to get the first result.

Can you now see why the second result similarly holds?

0
On

Here are some proofs in the Fitch system:

$\def\fitch#1#2{\begin{array}{|l}#1 \\ \hline #2\end{array}}$

$\fitch{ 1. }{ \fitch{ 2.\exists x. \bot}{ \fitch{ 3.\bot }{ 4.P \quad \bot \text{ Elim } 3} \\ 5.P \quad \exists \text{ Elim } 2, 3-4} \\ 6. \exists x. \bot \rightarrow P \quad \rightarrow \text{ Intro } 2-5}$

$\fitch{ 1. \exists x. \top }{ \fitch{ 2.\forall x. \bot}{ 3.\bot \quad \forall \text{ Elim } 2\\ 4.P \quad \bot \text{ Elim } 3} \\ 5. \forall x. \bot \rightarrow P \quad \rightarrow \text{ Intro } 2-4}$

Note that for the second proof you never use the $\exists x. \top$. Indeed, $\forall x. \bot \rightarrow P$ is valid all by itself.