imported>Skyerise at 23:12, 15 October 2023

2023-10-15T23:12:00Z

New page

{{Short description|Formal proof}}
{{no footnotes|date=July 2021}}
{{Transformation rules}}
A '''conditional proof''' is a [[formal proof|proof]] that takes the form of asserting a [[Material conditional|conditional]], and proving that the [[antecedent (logic)|antecedent]] of the conditional necessarily leads to the [[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 [[Logical consequence|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 [[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 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.

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

{|
|-
|align=right| 1. || A → B    || ("If A, then B")
|-
|align=right| 2. || B → C || ("If B, then C")
|-
|colspan=3| <hr>
|-
|align=right| 3. || A ||(conditional proof assumption, "Suppose A is true")
|-
|align=right| 4. || B || (follows from lines 1 and 3, [[modus ponens]]; "If A then B; A, therefore B")
|-
|align=right| 5. || C || (follows from lines 2 and 4, [[modus ponens]]; "If B then C; B, therefore C")
|-
|align=right| 6. || A → C || (follows from lines 3–5, conditional proof; "If A, then C")
|}

==See also==
* [[Deduction theorem]]
* [[Logical consequence]]
* [[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.

{{DEFAULTSORT:Conditional Proof}}
[[Category:Logic]]
[[Category:Conditionals]]
[[Category:Mathematical proofs]]
[[Category:Methods of proof]]

Conditional proof - Revision history

imported>Skyerise at 23:12, 15 October 2023