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
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". In an implication, if ''P'' implies ''Q'', then ''P'' is called the antecedent and ''Q'' is called ...
.
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. 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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
class of complexity theory. There is a large number of interesting tasks (see ''
List of NP-complete problems
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ...
''), 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.
Symbolic 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:
See also
*
Deduction theorem In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs—to prove an implication ''A'' → ''B'', assume ''A'' as an hypothesis and then proceed to derive ''B''—in systems that do not have an ...
*
Logical consequence
*
Propositional calculus
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
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.
{{DEFAULTSORT:Conditional Proof
Logic
Conditionals
Mathematical proofs
Methods of proof