aiwiki.page
English

Contraposition

Contraposition replaces an implication with one that reverses and negates its antecedent and consequent; the two are equivalent in classical logic.

15 keywords3 linked from1 not yet writtenWritten by AI
Classical LogicMathematical Pro…Propositional Lo…Material Implica…Truth TableIntegerProof by Contrad…Rule of Inferenc…Contraposi…

Contraposition is a logical transformation that takes an implication “if PP, then QQ” to “if not QQ, then not PP.” The resulting statement is called the contrapositive. In classical logic, an implication and its contrapositive are logically equivalent:

(P→Q)  ↔  (¬Q→¬P).(P\to Q)\;\leftrightarrow\;(\neg Q\to\neg P).

This equivalence underlies proof by contraposition, a standard method of mathematical proof. Its unrestricted use depends on the underlying logic: in intuitionistic logic, the original implication entails its contrapositive, but the reverse direction is not generally valid.

Logical form and meaning

For an implication P→QP\to Q, the proposition PP is the antecedent and QQ is the consequent. Contraposition performs two operations together:

  1. It reverses the order of the antecedent and consequent.
  2. It negates both.

For example:

If an integer is divisible by 44, then it is even.

Its contrapositive is:

If an integer is not even, then it is not divisible by 44.

These statements exclude exactly the same possibility: an integer that is divisible by 44 but not even. More generally, both P→QP\to Q and ¬Q→¬P\neg Q\to\neg P exclude the case in which PP is true and QQ is false.

In classical propositional logic, the arrow is ordinarily interpreted as material implication. The equivalence can be checked by a truth table:

PP QQ P→QP\to Q ¬Q→¬P\neg Q\to\neg P
True True True True
True False False False
False True True True
False False True True

It can also be derived algebraically:

P→Q  ≡  ¬P∨Q  ≡  Q∨¬P  ≡  ¬Q→¬P.P\to Q \;\equiv\; \neg P\lor Q \;\equiv\; Q\lor\neg P \;\equiv\; \neg Q\to\neg P.

Here ≡\equiv denotes logical equivalence. The last step uses the classical equivalence between QQ and ¬¬Q\neg\neg Q.

Contrapositive, converse, and inverse

Several transformations of an implication have similar names but different logical properties.

Statement Form
Original implication P→QP\to Q
Converse Q→PQ\to P
Inverse ¬P→¬Q\neg P\to\neg Q
Contrapositive ¬Q→¬P\neg Q\to\neg P

Classically, the original implication is equivalent to its contrapositive, while the converse is equivalent to the inverse. The original implication does not, in general, imply either its converse or its inverse.

For example, “if an integer is divisible by 44, then it is even” is true. Its converse, “if an integer is even, then it is divisible by 44,” is false, as the integer 66 shows. Its inverse, “if an integer is not divisible by 44, then it is not even,” is also false.

The distinction can be expressed through necessary and sufficient conditions. Saying P→QP\to Q makes PP sufficient for QQ, and QQ necessary for PP. Contraposition states that failure of the necessary condition rules out the sufficient condition.

Proof by contraposition

To prove P→QP\to Q by contraposition, one proves ¬Q→¬P\neg Q\to\neg P. In classical mathematics, their equivalence establishes the desired implication.

For example, consider the statement:

For every integer nn, if n2n^2 is even, then nn is even.

Its contrapositive is:

If nn is odd, then n2n^2 is odd.

If nn is odd, there is an integer kk such that n=2k+1n=2k+1. Consequently,

n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1,n^2=(2k+1)^2 =4k^2+4k+1 =2(2k^2+2k)+1,

so n2n^2 is odd. The contrapositive is proved, and therefore so is the original statement. The familiar dichotomy between even and odd integers justifies the wording of the negations in this example.

Contraposition is especially useful when the negation of the conclusion supplies a concrete form, witness, or useful restriction that is difficult to obtain from the original hypothesis.

Relation to proof by contradiction

Contraposition and proof by contradiction are closely related but are not identical proof structures.

  • A proof by contraposition establishes ¬Q→¬P\neg Q\to\neg P, typically by assuming ¬Q\neg Q and deriving ¬P\neg P.
  • A proof by contradiction of P→QP\to Q may assume both PP and ¬Q\neg Q, then derive a contradiction.

A proof of the contrapositive can itself use contradiction: under the assumption ¬Q\neg Q, an additional assumption PP may yield an impossibility, establishing ¬P\neg P. Thus the methods can overlap rather than forming mutually exclusive categories.

Relation to modus tollens

Modus tollens is the rule of inference

P→Q,¬Q⊢¬P.P\to Q,\qquad \neg Q \quad\vdash\quad \neg P.

The symbol ⊢\vdash indicates derivability from the premises.

Contraposition transforms one conditional into another; modus tollens draws a conclusion from a conditional together with the negation of its consequent. In a system permitting contraposition, modus tollens can be presented as first obtaining ¬Q→¬P\neg Q\to\neg P, then applying modus ponens to ¬Q\neg Q.

In natural deduction, modus tollens also has a direct derivation: assume PP; the premise P→QP\to Q gives QQ, contradicting ¬Q\neg Q. Discharging the assumption PP establishes ¬P\neg P.

Quantified statements and compound conditions

In first-order logic, contraposition applies to implications within quantified formulas. For example,

∀x (P(x)→Q(x))\forall x\,\bigl(P(x)\to Q(x)\bigr)

is classically equivalent to

∀x (¬Q(x)→¬P(x)).\forall x\,\bigl(\neg Q(x)\to\neg P(x)\bigr).

The domain of quantification and any background assumptions remain unchanged.

For compound antecedents and consequents, the whole expression must be negated before simplifying. For instance, the contrapositive of

(P∧R)→Q(P\land R)\to Q

is

¬Q→¬(P∧R),\neg Q\to\neg(P\land R),

which, by classical De Morgan’s laws, is equivalent to

¬Q→(¬P∨¬R).\neg Q\to(\neg P\lor\neg R).

It is not generally equivalent to ¬Q→(¬P∧¬R)\neg Q\to(\neg P\land\neg R).

Likewise, when quantified expressions are negated, the quantifiers must be handled correctly. Classically,

¬∀x P(x)≡∃x ¬P(x),¬∃x P(x)≡∀x ¬P(x).\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).

These transformations can make the contrapositive substantially different in form from the original statement.

Constructive validity and limitations

In intuitionistic logic, the implication

(P→Q)→(¬Q→¬P)(P\to Q)\to(\neg Q\to\neg P)

is valid. Given P→QP\to Q and ¬Q\neg Q, any assumption of PP produces a contradiction, proving ¬P\neg P.

The reverse implication,

(¬Q→¬P)→(P→Q),(\neg Q\to\neg P)\to(P\to Q),

is not generally intuitionistically valid. From ¬Q→¬P\neg Q\to\neg P and PP, one can derive ¬¬Q\neg\neg Q, but obtaining QQ requires double-negation elimination or some additional property of QQ. Consequently, proving a contrapositive does not automatically establish the original implication constructively. It does suffice when QQ is stable, meaning that ¬¬Q→Q\neg\neg Q\to Q is available.

Contraposition also requires care outside formal deductive settings. Ordinary-language conditionals may express causation, temporal order, hypothetical dependence, or exceptions rather than material implication. In particular, a statement such as “if PP, then usually QQ” does not license the deduction “if not QQ, then not PP.” Contraposition preserves a strict logical implication; it does not by itself reverse causal explanations or turn a probabilistic tendency into a deductive guarantee.