Give a natural deduction proof of $\varphi\vdash\top$, where $\varphi$ is any formula

Question

As in the title, the question is

Give a natural deduction proof of $\varphi\vdash\top$, where $\varphi$ is any formula.

Could I do this proof by deriving $\varphi \rightarrow \top$ with $ \rightarrow$-introduction rule which says that if you can derive a formula $\psi$ from a formula $\varphi$, then $\varphi \rightarrow \psi$ is true. So, with this derivation I will use $\varphi$ as an assumption and derive from $\varphi$, or am I thinking wrong? I prefer hints before solution!

Answer 1

HINT

I'll give you an answer in Hilbert-style, and I suggest you to try to convert it into Natural Deduction.

A quite "ubiquitous" axiom in Hilbert-style propositional logic is :

$\vdash \psi \rightarrow (\varphi \rightarrow \psi)$.

Thus, if we can prove $\vdash \psi$, we can use modus ponens (i.e. $\rightarrow$-elimination) to conclude with :

$\vdash \varphi \rightarrow \psi$.

The lesson is :

if we have proved a formula $\psi$, we can always add a "premise" $\varphi$ whatever to assert $\vdash \varphi \rightarrow \psi$.

Thus, the question suggests the following strategy : we have to prove : $\vdash \top$ and then use it as $\psi$ above.

---

Proof

i) $\varphi$ --- assumed

ii) $\bot$ --- assumed

iii) $\bot \vdash \bot$ --- from ii)

iv) $\vdash \bot \rightarrow \bot$ --- from iii) by $\rightarrow$-intro

v) $\vdash \lnot \bot$ --- by def of $\lnot$

vi) $\vdash \top$ --- abbreviation.

Thus, from i) and vi) :

$\varphi \vdash \top$.