Proving $(H \implies H) \implies G \quad \therefore \quad G$ using natural deduction

Question

I'm stuck on this extra credit logic problem for my course...

Prove

$$(H \implies H) \implies G \quad \therefore \quad G$$

using methods of natural deduction.

Any help would be highly appreciated. Thanks.

Answer 1

Use the meaning $\lnot a \vee b$ where ever an $a\implies b$ appears: $$ (H\implies H) \implies G \\ (\lnot H\vee H) \implies G \\ \lnot((\lnot H\vee H)) \vee G \\ (H \wedge \lnot H)) \vee G \\ \mbox{false } \vee G \\ G $$

Answer 2

Not exactly sure what you mean by natural deduction, I'm gonna assume you want a proof witouth using formalities at all:

$H$ has only two possible states, $T$ or $F$. Therefore $H \implies H$ can only be $(T \implies T) \equiv T$, or $(F \implies F) \equiv T$. So now we have $T \implies G$. Since this statement is a premise, we are to take it as True, meaning we assume $(T \implies G) \equiv T$. This will only if and only if $G \equiv T.$

Answer 3

Hint:

What is the antecedent of the assumption? Can you prove that antecedent?

Answer 4

Natural Deduction refers to several deductive systems in first-order logic, and so without additional information it isn't clear which specific system is intended.

Written in tree form, and not writing out sequents, one possible derivation would look something like this (the MathJax formatting is not ideal, but it conveys the idea): $$ \begin{array}{cc} \begin{array}{ll} \begin{array}{cl} \\ \\ \\ \hline [H \Rightarrow H] \Rightarrow G{} & u \end{array} & \begin{array}{cc} \hline H & v \\ \hline H \land H & \land I \\ \hline H & \land E \\ \hline H \Rightarrow H & \Rightarrow I^{v} \end{array} \end{array} \\ \hline G & \Rightarrow E\\ \hline ([H \Rightarrow H] \Rightarrow G) \Rightarrow G & \Rightarrow I^u \end{array} $$

The proposition in question, $([H \Rightarrow H] \Rightarrow G)\Rightarrow G$, is intuitionistically valid, so the proof should not require rewriting the implications in terms of disjunction and negation, and it should not require reasoning by cases based on the truth values of $H$ and $G$.