Contraposition


Contraposition
For contraposition in the field of traditional logic, see Contraposition (traditional logic).
For contraposition in the field of symbolic logic, see Transposition (logic).

Contraposition is a logical relationship between two propositions, or statements. For example, take the following (true) proposition: "All bats are mammals." We can restate that as "If something is a bat, then it is a mammal." The contrapositive is, "If something is not a mammal, then it is not a bat." In mathematics and in logic, the contrapositive is always guaranteed to be true, as long as the original proposition is true. If the original proposition is false, the contrapositive will always be false.

Compare that to the other common relationships between propositions:

  • Inversion (the inverse): "If something is not a bat, then it is not a mammal." 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. The inverse here is clearly not true.
  • Conversion (the converse): "If something is a mammal, then it is a bat." The converse is actually the contrapositive of the inverse and so always has the same truth value as the inverse, which is not necessarily the same as that of the original proposition.
  • Contradiction: "There exists a bat that is not a mammal. " If the contradiction is true, the original proposition (and by extension the contrapositive) is untrue. Here, of course, the contradiction is untrue.

Contents

Simple proof using Venn diagrams

Venn A subset B.svg

It appears clear that if something is in A, it must be in B, as well. We can rephrase all A is (in) B as

(A \to B)

It is also clear that anything that is not within B cannot be within A, either. This statement,

(\neg B \to \neg A)

is the contrapositive. Therefore we can say that

(A \to B)(\neg B \to \neg A)

Practically speaking, this makes life much easier when trying to prove something. For example, if we want to prove that every girl in the United States (A) is blonde (B), we can either try to prove (A \to B) by checking all girls in the United States to see if they are all blonde, or we can simply disprove the contrapositive by finding one nonblonde girl in the United States. Upon finding one, we have disproven (\neg B \to \neg A) and, by extension, (A \to B).

To conclude, for any statement where A implies B, then not B always implies not A. Proving or disproving either one of these statements automatically proves or disproves the other. They are fully equivalent.

Formal definition

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

(P \to Q)

In vernacular terms, 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. The contrapositive of the example is

(\neg Q \to \neg P).

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 "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. Likewise with falsity.

Strictly speaking, a contraposition can only exist in two simple conditionals. However, a contraposition may also exist in two complex conditionals, if they are similar. Thus, \forall{x}(P{x} \to Q{x}), or "All Ps are Qs," is contraposed to \forall{x}(\neg Q{x} \to \neg P{x}), or "All non-Qs are non-Ps."

Simple proof by contradiction

Suppose that it is given that

(A \to B)\and \neg B

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 (given). 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 concrete statements that are either true or not true):

(A \to B) \to (\neg B \to \neg A)


We can apply the same process the other way round:

(\neg B \to \neg A)\and A

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 contradiction and must be false. Therefore, B must be true:

(\neg B \to \neg A) \to (A \to B)


Combining the two proved statements makes them logically equivalent:

(A \to B) \iff (\neg B \to \neg A)

More rigorous proof of the equivalence of contrapositives

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.

(P \to Q)

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"):

\neg(P \and \neg Q)

The elements of a conjunction can be reversed with no effect:

\neg(\neg Q \and P)

We define R as equal to "\neg Q", and S as equal to \neg P (from this, \neg S is equal to \neg\neg P, which is equal to just P):

\neg(R \and \neg S)

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:

(R \to S)

When we swap our definitions of R and S, we arrive at the following:

(\neg Q \to \neg P)

Comparisons

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
contradiction P and not Q negation of second statement

Examples

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." Again, 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, of course, so, the converse of our statement is false.
  • The contradiction is "There exists a red object that does not have the properties of color". If the contradiction were true, then both the converse and the inverse would be correct in exactly that case where the shade of red is not a color. However, in our world this statement is entirely untrue (and therefore false).

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 shape is a quadrilateral, then it has four sides."

  • The contrapositive is "If a shape 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 shape is not a quadrilateral, then it does not have four sides." In this case, unlike the last example, the inverse of the argument is true.
  • The converse is "If a shape has four sides, then it is a quadrilateral." Again, in this case, unlike the last example, the converse of the argument is true.
  • The contradiction 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 shape is a quadrilateral if, and only if, it has four sides." (The phrase if and only if is sometimes abbreviated iff.) That is, having four sides is both necessary to be a quadrilateral, and alone sufficient to deem it a quadrilateral.

Truth

  • 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 contradiction 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, it is known as a logical biconditional.

Application

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 via proof by contradiction, as 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 \sqrt{2} is rational, then it can be expressed as an irreducible fraction". This statement is true because it is a restatement of a true definition. The contrapositive of this statement is "If \sqrt{2} 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 \sqrt{2} cannot be expressed as an irreducible fraction, then it must be the case that \sqrt{2} is not a rational number.

A similar, but not identical tool for proving mathematical theorems is the proof by contraposition.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • contraposition — ● contraposition nom féminin Loi logique selon laquelle il est équivalent de dire que A implique B et que non B implique non A. contraposition [kɔ̃tʀapozisjɔ̃] n. f. ÉTYM. 1900, Larousse; de contra , et position. ❖ ♦ Didact. (log.). Déd …   Encyclopédie Universelle

  • Contraposition — Con tra*po*si tion, n. [Pref. contra + position: cf. f. conterposition.] 1. A placing over against; opposite position. [Obs.] F. Potter. [1913 Webster] 2. (Logic) A so called immediate inference which consists in denying the original subject of… …   The Collaborative International Dictionary of English

  • Contraposition — (v. lat.), 1) Gegenstellung; 2) (Log.), wenn man aus einem Urtheile, ohne demselben eine andere Materie zu geben, ein neues bildet u. die Begriffe dabei so versetzt, daß die sogenannte Qualität verändert wird, also daß aus einem verneinenden… …   Pierer's Universal-Lexikon

  • contraposition — I noun antagonism, antithesis, confrontation, confrontment, contradiction, contradistinction, contrariety, contrast, converse, counterpart, disagreement, disparity, dissimilarity, incompatibility, obverse, odds, opposite, opposite side,… …   Law dictionary

  • contraposition — 1550s, from L.L. contrapositionem (nom. contrapositio), noun of action from contraposit , pp. stem of contraponere, from contra against (see CONTRA (Cf. contra)) + ponere to put, place (see POSITION (Cf. position)) …   Etymology dictionary

  • contraposition — [kän΄trə pə zish′ən] n. a placing opposite or over against; antithesis; contrast …   English World dictionary

  • Contraposition — Proposition contraposée La contraposition (ou modus tollens) est un type de raisonnement logique consistant à affirmer une implication (« si A alors B ») et à poser ensuite la négation du conséquent (« or, non B ») pour en… …   Wikipédia en Français

  • Contraposition — (Roget s Thesaurus) < N PARAG:Contraposition >N GRP: N 1 Sgm: N 1 contraposition contraposition opposition Sgm: N 1 polarity polarity Sgm: N 1 inversion inversion &c. 218 Sgm: N 1 opposite side opposite side Sgm: N 1 reverse …   English dictionary for students

  • contraposition — noun Etymology: Late Latin contraposition , contrapositio, from Latin contraponere to place opposite, from contra + ponere to place more at position Date: 1551 the relationship between two propositions when the subject and predicate of one are… …   New Collegiate Dictionary

  • contraposition — /kon treuh peuh zish euhn/, n. 1. placement opposite or against. 2. opposition, contrast, or antithesis. 3. Logic. the inference drawn from a proposition by negating its terms and changing their order, as by inferring Not B implies not A from A… …   Universalium