How do I solve prove this natural deduction problem?

Question

Premises: $\neg(A \to B)\ ,\ \neg B \to C$ .

Conclusion: $C$

My intuition is that I should do a sub-derivation where I prove $\neg C$ is an absurdity. However, I soon run into issues. If I could prove that $B$ is an absurdity, that would work also, but I'm not sure how to do so using the first premise.

Answer 1

Write the first premise as $\neg\neg(A \land \neg B) \equiv A \land \neg B $ , so $\neg B$ is true. Therefore, from the second premise it follows $C$.

Answer 2

Start by assuming that B is true.

You can prove a contradiction from that, to establish $\lnot B$.

Within the assumption you can prove $A \to B$

Answer 3

There is no need to assume $¬C$, here is an intuitionistic derivation:

$1). ¬(A → B) - premise$

$2). (¬B → C) - premise$

$3). B - assumption$

$4). A - assumption$

$5). A → B - I→ in 3,4 $

$6). ⊥ in 1,5$

$7). B - EFSQ (close-assumption- 5)$

$8). A → B - I→ in 4,7$

$9). ⊥ in 1,8 (close-assumption-4)$

$10). ¬B - I¬ in 3$

$11). C - E→ in 2,10$

Answer 4

$A \Rightarrow B$ is logically equivalent to $(\neg A) \vee B$.

Start of Edit Insert
See lemontree's comments/reactions to my answer which seem to indicate that the above statement can not be assumed, but rather must be proven. Based on this indication, I agree with lemontree that this answer is both unintended and inferior to other answers presented.
End of Edit Insert

Consequently, its negation is $A \wedge (\neg B).$

So you are given that

$A \wedge (\neg B)$

and

$(\neg B) \Rightarrow C.$

Answer 5

My intuition is that I should do a sub-derivation where I prove $\neg C$ is an absurdity. However, I soon run into issues. If I could prove that $B$ is an absurdity, that would work also, but I'm not sure how to do so using the first premise.

The contradiction of the first premise requires but a conditional proof: derive $B$ under the assumption of $A$.

Since your instinct was to derive that contradiction under the assumption of $B$, go with that.

• $\neg(A\to B)$ by premise
• $\neg B\to C$ by premise
  • $\neg C$ by supposition
    • $B$ by supposition
      • $A$ by supposition
      • $B$ by reiteration
    • $A\to B$ by deduction (conditional introduction)
    • Contradiction!
  • $\neg B$ by denial (negation introduction)
  • $C$ by affirmation (modus ponens, or conditional elimination)
  • Contradiction!
• $\neg\neg C$ by denial
• $C$ by double negation elimination.

Which is a valid proof, but a little inspection reveals some redundancy which we may prune away.

• $\neg(A\to B)$ by premise
• $\neg B\to C$ by premise
  • $B$ by supposition
    • $A$ by supposition
    • $B$ by reiteration
  • $A\to B$ by deduction (conditional introduction)
  • Contradiction!
• $\neg B$ by denial (negation introduction)
• $C$ by affirmation (modus ponens, or conditional elimination)