# Conditional proof

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Conditional_proof
> Markdown URL: https://mediated.wiki/source/Conditional_proof.md
> Source: https://en.wikipedia.org/wiki/Conditional_proof
> Source revision: 1180327386
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Formal proof

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (July 2021) (Learn how and when to remove this message)

Transformation rules Propositional calculus Rules of inference (List) Implication introduction / elimination (modus ponens) Biconditional introduction / elimination Conjunction introduction / elimination Disjunction introduction / elimination Disjunctive / hypothetical syllogism Constructive / destructive dilemma Absorption / modus tollens / modus ponendo tollens Modus non excipiens Negation introduction Rules of replacement Associativity Commutativity Distributivity Double negation De Morgan's laws Transposition Material implication Exportation Tautology Predicate logic Rules of inference Universal generalization / instantiation Existential generalization / instantiation v t e

A **conditional proof** is a [proof](/source/Formal_proof) that takes the form of asserting a [conditional](/source/Material_conditional), and proving that the [antecedent](/source/Antecedent_(logic)) of the conditional necessarily leads to the [consequent](/source/Consequent).

## Overview

The assumed antecedent of a conditional proof is called the **conditional proof assumption** (**CPA**). Thus, the goal of a conditional proof is to demonstrate that if the CPA were true, then the desired conclusion [necessarily follows](/source/Logical_consequence). The validity of a conditional proof does not require that the CPA be true, only that *if it were true* it would lead to the consequent.

Conditional proofs are of great importance in [mathematics](/source/Mathematics). Conditional proofs exist linking several otherwise unproven [conjectures](/source/Conjecture), so that a proof of one conjecture may immediately imply the validity of several others. It can be much easier to show a proposition's truth to follow from another proposition than to prove it independently.

A famous network of conditional proofs is the [NP-complete](/source/NP-complete) class of complexity theory. There is a large number of interesting tasks (see *[List of NP-complete problems](/source/List_of_NP-complete_problems)*), and while it is not known if a polynomial-time solution exists for any of them, it is known that if such a solution exists for some of them, one exists for all of them. Similarly, the [Riemann hypothesis](/source/Riemann_hypothesis) has many consequences already proven.

## Symbolic logic

As an example of a conditional proof in [symbolic logic](/source/Mathematical_logic), suppose we want to prove A → C (if A, then C) from the first two premises below:

1. A → B ("If A, then B") 2. B → C ("If B, then C") 3. A (conditional proof assumption, "Suppose A is true") 4. B (follows from lines 1 and 3, modus ponens; "If A then B; A, therefore B") 5. C (follows from lines 2 and 4, modus ponens; "If B then C; B, therefore C") 6. A → C (follows from lines 3–5, conditional proof; "If A, then C")

## See also

- [Deduction theorem](/source/Deduction_theorem)

- [Logical consequence](/source/Logical_consequence)

- [Propositional calculus](/source/Propositional_calculus)

## References

- Robert L. Causey, *Logic, sets, and recursion*, Jones and Barlett, 2006.

- Dov M. Gabbay, Franz Guenthner (eds.), *Handbook of philosophical logic*, Volume 8, Springer, 2002.

---
Adapted from the Wikipedia article [Conditional proof](https://en.wikipedia.org/wiki/Conditional_proof) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Conditional_proof?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.