I'm looking for a way to prove : $$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$$

From the axioms :

A1) $(A) \rightarrow ( B \rightarrow A )$

A2) $(A \rightarrow ( B \rightarrow C )) \rightarrow((A\rightarrow B)\rightarrow(A\rightarrow C ))$

A3) $A \rightarrow (B \rightarrow (A \wedge B ))$

A4) $(A \wedge B )\rightarrow A$

A5) $(A \wedge B )\rightarrow B$

A6) $(A \rightarrow B )\rightarrow ((C \rightarrow B )\rightarrow ((A\vee C)\rightarrow B))$

A7) $A \rightarrow (A \vee B)$

A8) $A \rightarrow (B \vee A)$

A9) $ \neg \neg A \rightarrow A $

and MP

I'm studying in computer science and I don't know any think about logic course. Sorry for easy question and bad english.

  • $\begingroup$ It is not easy to help you without almost giving you the solution. Let call $C$ the proposition $A \rightarrow B$. Can you see the connexion between $C$ and $\neg B \rightarrow \neg A$? As a starter, in natural language? If you can prove that this is $\neg\neg C$, you’re done with A9. $\endgroup$ – Elvis Dec 22 '11 at 10:49
  • 1
    $\begingroup$ Technically all axioms need fully parenthesized. Usually, this isn't a problem, since you only need to insert outer parentheses... e. g. (a^b)->b means ((a^b)->b). I wouldn't have mentioned this here, except that A→B→(¬B→¬A) is ambiguous as it stands. Both (A->(B->(¬B→¬A))) and ((A->B)->(¬B→¬A)) qualify as theorems, but they say something different. Which one do you want proved? Or both of them? $\endgroup$ – Doug Spoonwood Dec 22 '11 at 13:27
  • 1
    $\begingroup$ @Elvis: The law of excluded middle is not the problem: A9 is equivalent, in the presence of a sufficient fragment of intuitionistic logic. The trouble, I think, is that the axiom $\bot \to A$ is missing. $\endgroup$ – Zhen Lin Dec 23 '11 at 1:09
  • 1
    $\begingroup$ @ZhenLin: What do you take the "law of excluded middle" to be? For me it's $A\lor\neg A$, and that's not a consequence of the axioms here, because it's not valid in Joriki's model. (Also, $\bot$ appears not to be in the language at all, so it cannot exactly be $\bot\to A$ that is missing). $\endgroup$ – Henning Makholm Dec 23 '11 at 1:28
  • 1
    $\begingroup$ a) This is not an answer; it should be part of the question instead. b) You might want to explain a bit about what you're trying to do here. c) As my answer shows that there is no proof, it's an inefficient use of your time to continue searching for one. d) The noun is "proof", the verb is "prove". $\endgroup$ – joriki Dec 23 '11 at 10:39

You can't prove this because there's a model for this theory in which it's not true. Let $\to$,$\lor$ and $\land$ have their usual meanings, and let $\neg$ be the identity operation. Then all the axioms hold, but the theorem you want to prove doesn't.

  • $\begingroup$ i don`t know . my teacher write this question in my mid term exam in logic course and i can't write the answer :( . $\endgroup$ – mobin S.S.Bidgoli Dec 23 '11 at 10:11
  • 2
    $\begingroup$ @mobinS.S.Bidgoli: Now you do know: There is no proof for what you seek. This may be because the exam is in error or because you have misread or misquoted it here. $\endgroup$ – Henning Makholm Dec 23 '11 at 10:30
  • $\begingroup$ in my class we prove like this : A1) $ A \rightarrow (B\rightarrow C) $ A2) $ ( A \rightarrow (B\rightarrow C))\rightarrow ((A\rightarrow B)\rightarrow (A \rightarrow C ) ) $ A3) $ ( (\neg A) \rightarrow(\neg B )\rightarrow (((\neg A)\rightarrow B)\rightarrow C) $ then prove $ (A \rightarrow A ) $ $\endgroup$ – mobin S.S.Bidgoli Dec 23 '11 at 16:21
  • $\begingroup$ @mobin: As far as "A1)" is meant to indicate that what follows is an instance of the axiom scheme A1 in the question: It isn't, since different variables $A$ and $C$ appear where the axiom scheme has the same variable $A$. The part after "A3)" seems to have little to do with the axiom scheme listed as A3 in the question; I don't understand what you're trying to do. If you insist on trying to prove the unprovable, please add some explanations to your formulas that make them intelligible to other mortals. Again, I believe your time would be better invested in trying to understand my answer. $\endgroup$ – joriki Dec 24 '11 at 0:56

You mention two different axiom systems.

The one is your last comment [(A1), (A2) and (A3) : correcting a typo in (A3); it must be : $(((¬A)→(¬B))→(((¬A)→B)→A))$] is the one used in the "classic" Elliott Mendelson, Introduction to Mathematical Logic (4th ed - 1997): see page 35.

It is sound and complete respect to tautologies; thus, $(A→B)→(¬B→¬A)$ is provable [see Lemma 1.11.e, page 38].

The axiom system in your original question is derived from the 10-axiom system $\mathsf L_4$ of Mendelson [see Example page 42], that is from the axiom system of S.C.Kleene, Introduction to Metamathematics (1952).

But it is lacking of axiom (9) :

$(A→B)→((A→\lnot B)→\lnot A)$.

Thus, the axiom system is incomplete and you cannot prove $(A→B)→(¬B→¬A)$, as stated by Joriki.



$A1: A\rightarrow B$ Hipothesis

$A2: x\rightarrow ( x'')$

$A3: B\rightarrow B''$ Substitute x with B in A2

$A4: A \rightarrow B'' $ S-Rule(A1,A3)

$A5: A' \lor B'' $ Abbreviation $A\rightarrow B''$

$A6: B'' \lor A' $ Deduction rule on A5: $A\lor B \vdash B\lor A $

$A7: B' \rightarrow A' $ Abbreviation A6


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.