Prove that this is a valid formula using axioms of propositional logic

Question

The question is how to prove using basic axioms this expression:

$$(A \to B) \to ((\lnot C \to A) \to (\lnot C \to B))$$

I have the list of axioms, one of them looks like this: $A \to (B \to A)...$ But I don't understand how to apply this to my expression...

Answer 1

OK, first prove Hypothetical Syllogism ($\{A \rightarrow B, B \rightarrow C \} \vDash A \rightarrow C$ as a Lemma:

1. $A \rightarrow B$ Premise

2. $B \rightarrow C$ Premise

3. $(B \rightarrow C) \rightarrow (A \rightarrow (B \rightarrow C))$ Axiom 1

4. $A \rightarrow (B \rightarrow C)$ MP 2,3

5. $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ Axiom 2

6. $(A \rightarrow B) \rightarrow (A \rightarrow C)$ MP 4,5

7. $A \rightarrow C$ MP 1,6

Of course, $A$, $B$, and $C$ can be any statement here, so this means that you can infer any statement of the form $\varphi \rightarrow \gamma$ from two statements $\varphi \rightarrow \psi$ and $\psi \rightarrow \gamma$. Let's call this Lemma HS, and use it to get your desired result:

1. $(A \rightarrow B) \rightarrow (\neg C \rightarrow (A \rightarrow B))$ Axiom 1

2. $(\neg C \rightarrow (A \rightarrow B)) \rightarrow ((\neg C \rightarrow A) \rightarrow (\neg C \rightarrow B))$ Axiom 2

3. $(A \rightarrow B) \rightarrow ((\neg C \rightarrow A) \rightarrow (\neg C \rightarrow B))$ HS 1,2

Note you are only using Axioms 1 and 2 since this is all about conditionals.

Answer 2

Start with a premised proof:

$$\begin{array} {rl} \text{Premise} :& A \Rightarrow B \\ \text{Premise} :& \lnot C \Rightarrow A \\ \text{Premise} :& \lnot C \\ \text{MP} :& A \\ \text{MP} :& B \end{array}$$

Then apply deduction theorem:

$$\begin{array} {rl} \text{Ax 1} :& (A \Rightarrow B) \Rightarrow \lnot C \Rightarrow A \Rightarrow B \\ \text{Ax 2} :& (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{Premise} :& A \Rightarrow B \\ \text{Premise} :& \lnot C \Rightarrow A \\ \text{MP} :& \lnot C \Rightarrow A \Rightarrow B \\ \text{MP} :& (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{MP} :& \lnot C \Rightarrow B \end{array}$$

Then apply deduction theorem again:

$$\begin{array} {rl} \text{Ax 1} :& (A \Rightarrow B) \Rightarrow \lnot C \Rightarrow A \Rightarrow B \\ \text{Ax 2} :& (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{Premise} :& A \Rightarrow B \\ \text{MP} :& \lnot C \Rightarrow A \Rightarrow B \\ \text{MP} :& (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \end{array}$$

Then apply deduction theorem again:

$$\begin{array} {rl} \\ \text{Ax 2} :& (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow \\ & (\lnot C \Rightarrow A) \Rightarrow \\ & \lnot C \Rightarrow B \\ \text{Ax 1} :& ((\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B) \Rightarrow \\ & (A \Rightarrow B) \Rightarrow \\ & (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{MP} :& (A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{Ax 2} :& ((A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B) \Rightarrow \\ & ((A \Rightarrow B) \Rightarrow \lnot C \Rightarrow A \Rightarrow B) \Rightarrow \\ & (A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{MP} :& ((A \Rightarrow B) \Rightarrow \lnot C \Rightarrow A \Rightarrow B) \Rightarrow (A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \\ \text{Ax 1} :& (A \Rightarrow B) \Rightarrow \lnot C \Rightarrow A \Rightarrow B \\ \text{MP} :& (A \Rightarrow B) \Rightarrow (\lnot C \Rightarrow A) \Rightarrow \lnot C \Rightarrow B \end{array}$$