Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Conditional proof

Formal proof

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated October 15, 2023

A conditional proof is a proof that takes the form of asserting a conditional, and proving that the antecedent of the conditional necessarily leads to the consequent.

01Overview

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. 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. Conditional proofs exist linking several otherwise unproven conjectures, 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 class of complexity theory. There is a large number of interesting tasks (see 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 has many consequences already proven.

02Symbolic logic

As an example of a conditional proof in symbolic 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")
Watch videos about Conditional proofExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Conditional proof”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Deduction theorem

In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs from a hypothesis in systems that do not explicitly axiomatize that hypothesis, i.e. to prove an implication A → B {\displaystyle A\to B} , it is sufficient to assume A {\displaystyle A} as a hypothesis and then proceed to derive B {\displaystyle B} .

Logical consequence

Logical consequence is a fundamental concept in logic which describes the relationship between statements that hold true when one statement logically follows from one or more statements. A valid logical argument is one in which the conclusion is entailed by the premises, because the conclusion is the consequence of the premises.

Propositional logic

Propositional logic is a branch of classical logic. It is also called statement logic, sentential calculus, propositional calculus, sentential logic, or sometimes zeroth-order logic.