2
$\begingroup$

Using the Deduction Theorem and the principles of Ex Falso, Reductio ad Absurdum, and Indirect Proof, I am to show that:

(a) $$((A→B)→A)→A$$

and

(b) $$A,B ⊢ ¬(A→¬B)$$

I know how to forumlate the principles mentioned and I also intuitively see that (a) and (b) are valid. My problem, however, is that I actually can't figure out how to use the principle mention to show this ...

I would love it if someone could offers some assistance in showing how we apply the principle in order to show (a) and (b).

$\endgroup$

1 Answer 1

2
$\begingroup$

For (a) [Peirce's law] see this post : it is enough to omit steps 1) and 13).

For (b) :

$A,B \vdash ¬(A → ¬B)$

we have the following proof :

1) $A$ --- premise

2) $B$ --- premise

3) $A → ¬B$ --- assumed [a]

4) $¬B$ --- from 1) and 3) by $\to$-elimination (modus ponens)

5) $\bot$ --- from 2) and 4) by $\lnot$-elimination

6) $\lnot (A → ¬B)$ --- from 3) and 5) by $\lnot$-introduction, discharging [a].

Thus, steps 3) to 6) are nothing more than an Indirect Proof : assume the negation of the sought conclusion and derive a contradiction.

$\endgroup$
5
  • $\begingroup$ Thank you. So proving A ⊢ (B→A) would go like: 1) A (premise) 2) ¬(B→A) (ass. A) 3) ¬A (by 1 and 2) 4) ⊥ (by 1 and 4) 5) ¬¬(B→A)(RaA on 1 and 2, discharging [a]) 6) (B→A) (rule for double neg. on 5) Or would it? (Really just tried some things out). Thanks. $\endgroup$ Mar 11, 2015 at 14:16
  • $\begingroup$ @tomtronbone - not exactly ... from $A$ you can infer $(B \to A)$ directly; "intuitively", you need modus ponens with the premise $A$ and the tautology : $A \to (B \to A)$. $\endgroup$ Mar 11, 2015 at 14:37
  • $\begingroup$ You can see in the answer to this post the natural deduction proof of $A \vdash (B \to A)$. $\endgroup$ Mar 11, 2015 at 14:40
  • $\begingroup$ Thanks! But, you don't seem to be using any of the principles - or are you? $\endgroup$ Mar 11, 2015 at 14:58
  • $\begingroup$ @tomtronbone - in term of natural deduction rule, you can derive $B \to A$ from $A$ by $\to$-introduction alone, because you can discharge an assumption ($B$) also when it is not present. The idea is simply : $A \vdash A$ is valid and we can add "unnecessary" assunptions; thus : $A,B \vdash A$ is also valid (with $B$ whatever). Then apply $\to$-intro to get : $A \vdash (B \to A)$. $\endgroup$ Mar 11, 2015 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .