3
$\begingroup$

I am studying for my logic finals and I came across this question:

Prove $((E\implies F)\implies E)\implies E$

I don't understand how there is a classical contradiction in this proof.

Using natural deduction, could some one explain why there is a classical contradiction in this proof?

enter image description here

Thank you in advance!

  • 0
    Couldn't you just look at truth tables?2012-04-23
  • 0
    I have to format it using natural deduction.2012-04-23
  • 0
    Ah, I see. You had written that in your question as well...2012-04-23
  • 6
    You will need to explain which inference rules you have available. "Natural deduction" is not one thing but a family of related proof systems. They agree more or less on how the intuitionistic fragment works, but what you want to prove is [Peirce's law](http://en.wikipedia.org/wiki/Peirce%27s_law), which is not intuitionistically valid (but is itself one of several possible axioms that will extend intuitionistic logic to classical). So the proof you seek depends critically on which rule or axiom your variant of natural deduction uses to achieve classical logic.2012-04-23
  • 0
    @Henning Makholm This is an example i constructed, i managed it using a software, i just don't understand the rules. http://tinypic.com/view.php?pic=35kojt5&s=52012-04-23
  • 2
    @Fatz: Doesn't help. You have to _tell us what the rules are_.2012-04-23
  • 0
    The only way that E-->F is going to be false is if E is true and F is false. Now with that information, demonstrate using a truth table that for any values of E and F that the truth table is not unconditionally true. Once you find that, your contradiction are the values of E and F such that result in false.2012-04-23
  • 0
    @Neil so when the truth table us false then there is a classical contradiction?2012-04-23
  • 0
    Yes, without further insight, I would assume they're looking for an instance in which this can be false.2012-04-23
  • 2
    Isn't this Peirce's law...?2012-04-23
  • 0
    Wait, what is a classical contradiction?2012-04-23
  • 0
    @Neil thanks, i can see why it is false as all natural deductions must be a tautology, the classical contradiction or 'double negation' rule is not a tautology.2012-04-23
  • 0
    @Xabi It's not a tautology (since it's not a formula/wff), but it does always work out as valid as a rule of inference in classical logic.2012-04-28
  • 0
    @Neil, yeah i know this isn't a tautology, because its a classical contradiction, but in other games, natural deductions are tautologies. Thanks though.2012-04-28

3 Answers 3

2

In your proof, in steps 4, 6, and 10 you have a contradiction, because you have both E and $ \lnot $E in play. Since you have that contradiction, in the next step you infer the negation of the last assumption you made if you have a proposition which is not a negation, if you have a negation as the last assumption you made you infer the proposition that such a negation negates i. e. if you have p, and you get a contradiction, you may immediately infer $\lnot$p. If you have $\lnot$p, and you have a contradiction, you may immediately infer p.

The sort of contradiction that appears in such proofs isn't exactly the same as a formula which always comes out as false under all valuations (every row of its truth table comes out false), and maybe that has tripped you up here. However, since almost surely your system has a conjunction-introduction rule which says something like "from p and q, we may immediately infer (p$\land$q)", anytime you have a proposition "p" and its negation "$\lnot$p" you can infer a formula which always comes out as false under all valuations.

1

I can give it a try!

I'll assume you are using the natural deduction system that has the normal introduction and elimination rules for the logical symbols, the so-called "intuitionistic fragment" of propositional logic, together with double negation elimination "from $\lnot \lnot A$, conclude $A$'' (DNE). If you started out by adding the rule "if under assumption $\lnot p$ we have $\bot$, then $p$'', we can get (DNE) also.

Open the following assumptions in this order: 1) $(E \rightarrow F) \rightarrow E$, 2) $\lnot E$ and 3) $E \rightarrow F$. From 1) and 2), conclude $E$ contradicting 2), so that we can close assumption 3) and conclude $\lnot (E \rightarrow F)$ by the I-$\lnot$ rule. From this we get $\lnot \lnot E$ and then $E$. This contradicts 2) again, so we can close 2) and get $\lnot \lnot E$ by I-$\lnot$ rule again. By DNL, we have $E$. Hence we can close assumption 1) to get $((E\rightarrow F) \rightarrow E) \rightarrow E$ by I-$\rightarrow$ rule.

We used classical contradiction when we closed off 2) to conclude $E$ by showing that $\lnot E$ is absurd, and also to get from $\lnot \lnot E$ to $E$.

If the order of which assumptions to open seems ad-hoc, it's basically dictated by what you're trying to prove. Since Pierce's law has a $\rightarrow$ as an outer connective, it's prudent to try using the I-$\rightarrow$ first. Then we are left to show $E$ from assumption 1), which is handily proved by DNL.

Hope that helps!

  • 0
    We don't have either of De Morgan's laws at play here.2012-04-27
  • 1
    True, not in this proof. From $\lnot(E \rightarrow F)$ we conclude $\lnot \lnot E$ and then $E$ by (DNE), thanks. I'll make the edit above.2012-04-28