Conditional proof
Encyclopedia
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
.
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. Note that the validity of a conditional proof does not require that the CPA is actually true, only that if it is true it leads to the consequent.
Conditional proofs are of great importance in mathematics
. Conditional proofs exist linking several otherwise unproven conjecture
s, 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 are a large number of interesting tasks, 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 any of them, one exists for all of them.
Likewise, the Riemann hypothesis
has a large number of consequences already proven.
, suppose we want to prove A → C (if A, then C) from the first two premises below:
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
that takes the form of asserting a conditional
Material conditional
The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...
, and proving that the antecedent
Antecedent (logic)
An antecedent is the first half of a hypothetical proposition.Examples:* If P, then Q.This is a nonlogical formulation of a hypothetical proposition...
of the conditional necessarily leads to the consequent
Consequent
A consequent is the second half of a hypothetical proposition. In the standard form of such a proposition, it is the part that follows "then".Examples:* If P, then Q.Q is the consequent of this hypothetical proposition....
.
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. Note that the validity of a conditional proof does not require that the CPA is actually true, only that if it is true it leads to the consequent.
Conditional proofs are of great importance in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
. Conditional proofs exist linking several otherwise unproven conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
s, 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
class of complexity theory. There are a large number of interesting tasks, 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 any of them, one exists for all of them.
Likewise, the Riemann hypothesis
Riemann hypothesis
In mathematics, the Riemann hypothesis, proposed by , is a conjecture about the location of the zeros of the Riemann zeta function which states that all non-trivial zeros have real part 1/2...
has a large number of consequences already proven.
Symbolic logic
As an example of a conditional proof in symbolic logicMathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, 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 Modus ponens In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments... ; "If A then B; A, therefore B") |
| 5. | C | (follows from lines 2 and 4, modus ponens Modus ponens In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments... ; "If B then C; B, therefore C") |
| 6. | A → C | (follows from lines 3–5, conditional proof; "If A, then C") |