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 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.

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.

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

  • Proof-theoretic 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”