2
$\begingroup$

I having heavy difficulties with this exercise beacuse it doesn't have any premise. I can't get the result I want (which is posted on the title of the question) straight to the top level

1.              p Assumption
2.                  (p => q) => p Assumption
3.                  p Reiteration: 1
4.              ((p => q) => p) => p Implication Introduction: 2, 3
5.          p => ((p => q) => p) => p Implication Introduction: 1, 4

ps: I don't want the entire proof of the expression. I would appreciate hints. If it is really complicated, then I accept the entire proof so I can study further.

ps: I know you all want to help, but I have only these operations available: -assumption -reiteration -delete -negation introduction -negation elimination -and introduction -and elimination -or introduction -or elimination -implication introduction -implication elimination -biconditional introduction -biconditional elimination It was cool to know Peirce's law, however I didn't find a way to implement it through the resources above.

$\endgroup$
  • 1
    $\begingroup$ See Peirce's Law. $\endgroup$ – Mauro ALLEGRANZA Mar 18 '17 at 14:21
  • $\begingroup$ Mauro, could you please post your answer so I can mark it as the solution? $\endgroup$ – Carlos Oliveira Mar 19 '17 at 14:42
1
$\begingroup$

For a proof of Peirce's law with Natural Deduction's based Fitch system, you can see the answer to the post: using the Fitch system how do I prove $((p \implies q) \implies p) \implies p$ ?

If you are not falimiar with the rules using $\bot$ (the falsum) you can rewrite it as follows:

1) assume $(P \to Q) \to P$

2) assume [a]: $P$ and [b]: $¬P$ and derive by $¬$E: $Q$

3) derive $P \to Q$ by $→$I, discharging [a]

4) use it with 1) to derive $P$ by $→$E.

Now we have again a contradiction with the [b] assumption: $¬P$.

The next step needs $¬$I, to derive from the said contradicition: $¬¬P$, discharging [b].

Up to now, having discharged the "temporary" assumptions [a] and [b], we have:

$(P \to Q) \to P \vdash ¬¬P$.

The following step needs $¬¬$I (Double Negation elimination) to derive $P$ from $¬¬P$ and conclude with: $(P \to Q) \to P \vdash P$.

The final step needs $\to$I to conclude with:

$\vdash ((P \to Q) \to P) \to P$.

$\endgroup$
2
$\begingroup$

HINT

whenever you want to prove something of the form $\phi \rightarrow \psi$, do a conditional proof where you assume $\phi$ and try to get to $\psi$.

So in your case, assume $(p \rightarrow q) \rightarrow p$, and try to get to $p$

You did do a conditional proof, but notice that the conditional you obtained was not the one you want.

HINT 2

To get to $p$ inside the conditional proof ... Do a proof by contradiction

HINT 3

If you are still stuck ... See the 9th post under 'Related' on the right.

$\endgroup$
  • $\begingroup$ Thanks for the hints. I have tried do it that way, but i can't get "p" by a contradiction. I have seen this symbol ⊥, which I don't have on hands for use and my course didn't explain yet what it means. $\endgroup$ – Carlos Oliveira Mar 18 '17 at 15:19
  • $\begingroup$ @CarlosOliveira If you don't have $\bot$, then you probably need to get to $p$ as well as $\neg p$. That is: if you assume $\neg p$, and can get to $p$ as well as $\neg p$ (That last one is trivial by reiteration), then you can infer $\neg neg p$, or maybe even directly $p$. $\endgroup$ – Bram28 Mar 18 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.