Conditional proof

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 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 NPcomplete class of complexity theory. There are a large number of interesting tasks, and while it is not known if a polynomialtime 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.
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:
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
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.
Categories: Logic
 Conditionals
 Proofs
Wikimedia Foundation. 2010.
Look at other dictionaries:
conditional proof — conditional proof, rule of … Philosophy dictionary
conditional proof, rule of — The rule in a deductive system that if A1…An⊦ B then A1…An–⊦ An→ B … Philosophy dictionary
Conditional — may refer to: Causal conditional, if X then Y, where X is a cause of Y Conditional mood (or conditional tense), a verb form in many languages Conditional probability, the probability of an event A given that another event B has occurred… … Wikipedia
Conditional immortality — Conditional immortality, or conditionalism, is the Christian doctrine that the human soul is naturally mortal, and that immortality is granted by God as a gift. Immortality, therefore, is conditional; this viewpoint stands in contrast to the more … Wikipedia
Prooftheoretic semantics — is an approach to the semantics of logic that attempts to locate the meaning of propositions and logical connectives not in terms of interpretations, as in Tarskian approaches to semantics, but in the role that the proposition or logical… … Wikipedia
Conditional independence — These are two examples illustrating conditional independence. Each cell represents a possible outcome. The events R, B and Y are represented by the areas shaded red, blue and yellow respectively. And the probabilities of these events are shaded… … Wikipedia
Conditional preservation of the saints — The Five Articles of Remonstrance Conditional election Unlimited atonement Total depravity … Wikipedia
Material conditional — The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q (typically read if p then q or p implies q ) is logically equivalent to the negative compound: not (p and not q). A… … Wikipedia
Method of conditional probabilities — In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic they work by showing that a random object, chosen from some… … Wikipedia
Direct proof — In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions. In order … Wikipedia