Contraposition

  (Redirected from Contrapositive)

In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition.[1] The contrapositive of a statement has its antecedent and consequent inverted and flipped. For instance, the contrapositive of the conditional statement "If it is raining, then I wear my coat" is the statement "If I don't wear my coat, then it isn't raining." In formulas: the contrapositive of is .[2] The law of contraposition says that a conditional statement is true if, and only if, its contrapositive is true.[3]

The contrapositive can be compared with three other conditional statements related to :

Inversion (the inverse),
"If it is not raining, then I don't wear my coat." Unlike the contrapositive, the inverse's truth value is not at all dependent on whether or not the original proposition was true, as evidenced here.
Conversion (the converse),
"If I wear my coat, then it is raining." The converse is actually the contrapositive of the inverse, and so always has the same truth value as the inverse (which as stated earlier does not always share the same truth value as that of the original proposition).
Negation,
"It is not the case that if it is raining then I wear my coat.", or equivalently, "Sometimes, when it is raining, I don't wear my coat. " If the negation is true, then the original proposition (and by extension the contrapositive) is false.

Note that if is true and one is given that is false (i.e., ), then it can logically be concluded that must be also false (i.e., ). This is often called the law of contrapositive, or the modus tollens rule of inference.[4]

Intuitive explanationEdit

In the Euler diagram shown, if something is in A, it must be in B as well. So we can interpret "all of A is in B" as:

 

It is also clear that anything that is not within B (the blue region) cannot be within A, either. This statement, which can be expressed as:

 

is the contrapositive of the above statement. Therefore, one can say that

 .

In practice, this equivalence can be used to make proving a statement easier. For example, if one wishes to prove that every girl in the United States (A) has brown hair (B), one can either try to directly prove   by checking that all girls in the United States do indeed have brown hair, or try to prove   by checking that all girls without brown hair are indeed all outside the US. In particular, if one were to find at least one girl without brown hair within the US, then one would have disproved  , and equivalently  .

In general, for any statement where A implies B, not B always implies not A. As a result, proving or disproving either one of these statements automatically proves or disproves the other, as they are logically equivalent to each other.

Formal definitionEdit

A proposition Q is implicated by a proposition P when the following relationship holds:

 

This states that, "if P, then Q", or, "if Socrates is a man, then Socrates is human." In a conditional such as this, P is the antecedent, and Q is the consequent. One statement is the contrapositive of the other only when its antecedent is the negated consequent of the other, and vice versa. Thus a contrapositive generally takes the form of:

 .

That is, "If not-Q, then not-P", or, more clearly, "If Q is not the case, then P is not the case." Using our example, this is rendered as "If Socrates is not human, then Socrates is not a man." This statement is said to be contraposed to the original and is logically equivalent to it. Due to their logical equivalence, stating one effectively states the other; when one is true, the other is also true, and when one is false, the other is also false.

Strictly speaking, a contraposition can only exist in two simple conditionals. However, a contraposition may also exist in two complex, universal conditionals, if they are similar. Thus,  , or "All Ps are Qs," is contraposed to  , or "All non-Qs are non-Ps."[5]

Simple proof by definition of a conditionalEdit

In first-order logic, the conditional is defined as:

 

which can be made equivalent to its contrapositive, as follows:

 

Simple proof by contradictionEdit

Let:

 

It is given that, if A is true, then B is true, and it is also given that B is not true. We can then show that A must not be true by contradiction. For if A were true, then B would have to also be true (by Modus Ponens). However, it is given that B is not true, so we have a contradiction. Therefore, A is not true (assuming that we are dealing with bivalent statements that are either true or false):

 

We can apply the same process the other way round, starting with the assumptions that:

 

Here, we also know that B is either true or not true. If B is not true, then A is also not true. However, it is given that A is true, so the assumption that B is not true leads to a contradiction, which means that it is not the case that B is not true. Therefore, B must be true:

 

Combining the two proved statements together, we obtain the sought-after logical equivalence between a conditional and its contrapositive:

 

More rigorous proof of the equivalence of contrapositivesEdit

Logical equivalence between two propositions means that they are true together or false together. To prove that contrapositives are logically equivalent, we need to understand when material implication is true or false.

 

This is only false when P is true and Q is false. Therefore, we can reduce this proposition to the statement "False when P and not-Q" (i.e. "True when it is not the case that P and not-Q"):

 

The elements of a conjunction can be reversed with no effect (by commutativity):

 

We define   as equal to " ", and   as equal to   (from this,   is equal to  , which is equal to just  ):

 

This reads "It is not the case that (R is true and S is false)", which is the definition of a material conditional. We can then make this substitution:

 

By reverting R and S back into P and Q, we then obtain the desired contrapositive:

 

ComparisonsEdit

name form description
implication if P then Q first statement implies truth of second
inverse if not P then not Q negation of both statements
converse if Q then P reversal of both statements
contrapositive if not Q then not P reversal and negation of both statements
negation P and not Q contradicts the implication

ExamplesEdit

Take the statement "All red objects have color." This can be equivalently expressed as "If an object is red, then it has color."

  • The contrapositive is "If an object does not have color, then it is not red." This follows logically from our initial statement and, like it, it is evidently true.
  • The inverse is "If an object is not red, then it does not have color." An object which is blue is not red, and still has color. Therefore, in this case the inverse is false.
  • The converse is "If an object has color, then it is red." Objects can have other colors, so the converse of our statement is false.
  • The negation is "There exists a red object that does not have color." This statement is false because the initial statement which it negates is true.

In other words, the contrapositive is logically equivalent to a given conditional statement, though not sufficient for a biconditional.

Similarly, take the statement "All quadrilaterals have four sides," or equivalently expressed "If a polygon is a quadrilateral, then it has four sides."

  • The contrapositive is "If a polygon does not have four sides, then it is not a quadrilateral." This follows logically, and as a rule, contrapositives share the truth value of their conditional.
  • The inverse is "If a polygon is not a quadrilateral, then it does not have four sides." In this case, unlike the last example, the inverse of the statement is true.
  • The converse is "If a polygon has four sides, then it is a quadrilateral." Again, in this case, unlike the last example, the converse of the statement is true.
  • The negation is "There is at least one quadrilateral that does not have four sides." This statement is clearly false.

Since the statement and the converse are both true, it is called a biconditional, and can be expressed as "A polygon is a quadrilateral if, and only if, it has four sides." (the phrase if and only if is sometimes abbreviated as iff.) That is, having four sides is both necessary to be a quadrilateral, and alone sufficient to deem it a quadrilateral.

TruthEdit

  • If a statement is true, then its contrapositive is true (and vice versa).
  • If a statement is false, then its contrapositive is false (and vice versa).
  • If a statement's inverse is true, then its converse is true (and vice versa).
  • If a statement's inverse is false, then its converse is false (and vice versa).
  • If a statement's negation is false, then the statement is true (and vice versa).
  • If a statement (or its contrapositive) and the inverse (or the converse) are both true or both false, then it is known as a logical biconditional.

ApplicationEdit

Because the contrapositive of a statement always has the same truth value (truth or falsity) as the statement itself, it can be a powerful tool for proving mathematical theorems (especially if the truth of the contrapositive is easier to establish than the truth of the statement itself).[1] A proof by contraposition (contrapositive) is a direct proof of the contrapositive of a statement.[6] However, indirect methods such as proof by contradiction can also be used with contraposition, as, for example, in the proof of the irrationality of the square root of 2. By the definition of a rational number, the statement can be made that "If   is rational, then it can be expressed as an irreducible fraction". This statement is true because it is a restatement of a definition. The contrapositive of this statement is "If   cannot be expressed as an irreducible fraction, then it is not rational". This contrapositive, like the original statement, is also true. Therefore, if it can be proven that   cannot be expressed as an irreducible fraction, then it must be the case that   is not a rational number. The latter can be proved by contradiction.

The previous example employed the contrapositive of a definition to prove a theorem. One can also prove a theorem by proving the contrapositive of the theorem's statement. To prove that if a positive integer N is a non-square number, its square root is irrational, we can equivalently prove its contrapositive, that if a positive integer N has a square root that is rational, then N is a square number. This can be shown by setting N equal to the rational expression a/b with a and b being positive integers with no common prime factor, and squaring to obtain N = a2/b2 and noting that since N is a positive integer b=1 so that N = a2, a square number.

Correspondence to other mathematical frameworksEdit

Probability calculusEdit

Contraposition represents an instance of Bayes' theorem which in a specific form can be expressed as:

 .

In the equation above the conditional probability   generalizes the logical statement  , i.e. in addition to assigning TRUE or FALSE we can also assign any probability to the statement. The term   denotes the base rate (aka. the prior probability) of  . Assume that   is equivalent to   being TRUE, and that   is equivalent to   being FALSE. It is then easy to see that   when   i.e. when   is TRUE. This is because   so that the fraction on the right-hand side of the equation above is equal to 1, and hence   which is equivalent to   being TRUE. Hence, Bayes' theorem represents a generalization of contraposition.[7]

Subjective logicEdit

Contraposition represents an instance of the subjective Bayes' theorem in subjective logic expressed as:

 ,

where   denotes a pair of binomial conditional opinions given by source  . The parameter   denotes the base rate (aka. the prior probability) of  . The pair of inverted conditional opinions is denoted  . The conditional opinion   generalizes the logical statement  , i.e. in addition to assigning TRUE or FALSE the source   can assign any subjective opinion to the statement. The case where   is an absolute TRUE opinion is equivalent to source   saying that   is TRUE, and the case where   is an absolute FALSE opinion is equivalent to source   saying that   is FALSE. In the case when the conditional opinion   is absolute TRUE the subjective Bayes' theorem operator   of subjective logic produces an absolute FALSE conditional opinion   and thereby an absolute TRUE conditional opinion   which is equivalent to   being TRUE. Hence, the subjective Bayes' theorem represents a generalization of both contraposition and Bayes' theorem.[8]

See alsoEdit

ReferencesEdit

  1. ^ a b "The Definitive Glossary of Higher Mathematical Jargon — Contrapositive". Math Vault. 2019-08-01. Retrieved 2019-11-26.
  2. ^ "Definition of CONTRAPOSITIVE". www.merriam-webster.com. Retrieved 2019-11-26.
  3. ^ "The Law of Contraposition". beisecker.faculty.unlv.edu. Retrieved 2019-11-26.
  4. ^ "Modus ponens and modus tollens | logic". Encyclopedia Britannica. Retrieved 2019-11-26.
  5. ^ "Predicates and Quantified Statements II". www.csm.ornl.gov. Retrieved 2019-11-26.
  6. ^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2001), A Transition to Advanced Mathematics (5th ed.), Brooks/Cole, p. 37, ISBN 0-534-38214-2
  7. ^ Audun Jøsang 2016:2
  8. ^ Audun Jøsang 2016:92

SourcesEdit

  • Audun Jøsang, 2016, Subjective Logic; A formalism for Reasoning Under Uncertainty Springer, Cham, ISBN 978-3-319-42337-1

External linksEdit