3.4 Indirect Proof Methods: Conditional and Reductio ad Absurdum

Indirect proof methods are powerful tools in logic, allowing us to prove statements that might be challenging to demonstrate directly. These methods, including conditional proof and reductio ad absurdum, work by assuming the opposite or a related condition.

By exploring these techniques, we gain a deeper understanding of logical reasoning and expand our problem-solving toolkit. Indirect proofs complement direct methods, offering alternative approaches to tackle complex logical statements and arguments.

Indirect Proof Methods

Concepts of conditional proof and reductio

• Indirect proof methods prove a statement by considering its negation or a related conditional statement when a direct proof is difficult or not possible
• Conditional proof (CP) method proves a statement of the form $P \to Q$ by assuming $P$ is true and deriving $Q$ from this assumption, establishing the truth of $P \to Q$ if successful
• Reductio ad absurdum (RAA) method, also known as proof by contradiction, assumes the negation of the statement to be proved and derives a contradiction from this assumption, establishing the truth of the original statement if successful

Application of conditional proof method

To prove a statement of the form $P \to Q$ using CP:

1. Assume $P$ is true
2. Derive $Q$ using logical inferences and the assumption $P$
3. Conclude that $P \to Q$ is true if successful

Example: Prove $(A \land B) \to (A \lor C)$

1. Assume $A \land B$ is true
2. Infer $A$ from $A \land B$ (simplification)
3. Infer $A \lor C$ from $A$ (addition)
4. Conclude $(A \land B) \to (A \lor C)$ is true

Reductio ad absurdum for contradiction proofs

To prove a statement $P$ using RAA:

1. Assume $\lnot P$ (the negation of $P$)
2. Derive a contradiction (e.g., $Q \land \lnot Q$) using logical inferences and the assumption $\lnot P$
3. Conclude that $P$ must be true if successful

Example: Prove $A \to (B \to A)$

1. Assume $\lnot (A \to (B \to A))$
2. Infer $A \land \lnot (B \to A)$ (negation of implication)
3. Infer $A$ (simplification)
4. Infer $B \land \lnot A$ from $\lnot (B \to A)$ (negation of implication)
5. Infer $\lnot A$ (simplification)
6. Contradiction: both $A$ and $\lnot A$ are true
7. Conclude $A \to (B \to A)$ is true

Direct vs indirect proof methods

• Direct proof method proves a statement by deriving it directly from known premises and inference rules, starting with the premises and reaching the conclusion through a sequence of logical steps
• Indirect proof methods (CP and RAA) prove a statement by considering its negation or a related conditional statement
  • CP assumes the antecedent of a conditional statement and derives the consequent
  • RAA assumes the negation of the statement to be proved and derives a contradiction
• Indirect proofs are useful when a direct proof is difficult or not possible
• Both direct and indirect proofs rely on logical inferences and the rules of propositional logic

Selection of appropriate proof methods

• Direct proof is suitable when the statement can be easily derived from known premises and inference rules and is not a conditional or a negation
• Conditional proof is suitable when the statement to be proved is a conditional ($P \to Q$) and it is easier to assume the antecedent ($P$) and derive the consequent ($Q$)
• Reductio ad absurdum is suitable when the statement to be proved is a negation or a statement that leads to a contradiction and it is easier to assume the negation of the statement and derive a contradiction
• Multiple proof methods may be applicable in some cases, and the choice depends on the structure of the statement and the ease of deriving the conclusion (e.g., proving $A \lor \lnot A$ using direct proof or RAA)