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. 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.
Symbolic logicedit
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")
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.
April 11, 2024
conditional, proof, this, article, includes, list, references, related, reading, external, links, sources, remain, unclear, because, lacks, inline, citations, please, help, improve, this, article, introducing, more, precise, citations, july, 2021, learn, when,. 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 template message 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 Contents 1 Overview 2 Symbolic logic 3 See also 4 ReferencesOverview editThe 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 Symbolic logic editAs 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 See also editDeduction theorem Logical consequence Propositional calculusReferences editRobert L Causey Logic sets and recursion Jones and Barlett 2006 Dov M Gabbay Franz Guenthner eds Handbook of philosophical logic Volume 8 Springer 2002 Retrieved from https en wikipedia org w index php title Conditional proof amp oldid 1180327386, wikipedia, wiki, book, books, library,
