Proof by contrapositive

In logic and mathematics, contraposition, or transposition, refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as § Proof by contrapositive. The contrapositive of a statement has its antecedent and consequent negated and swapped.

Conditional statement \(P \rightarrow Q\). In formulas: the contrapositive of \(P \rightarrow Q\) is \(\neg Q \rightarrow \neg P\).

If P, Then Q., If not Q, Then not P. "If it is raining, then I wear my coat.", "If I don't wear my coat, then it isn't raining."

The law of contraposition says that a conditional statement is true if, and only if, its contrapositive is true.

Contraposition (\(\neg Q \rightarrow \neg P\)) can be compared with three other operations:

Inversion (the inverse), \(\neg P \rightarrow \neg Q\)

"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), \(Q \rightarrow P\)

"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 (the logical complement), \(\neg (P \rightarrow Q)\)

"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 \(P \rightarrow Q\) is true and one is given that \(Q\) is false (i.e., \(\neg Q\)), then it can logically be concluded that \(P\) must be also false (i.e., \(\neg P\)). This is often called the law of contrapositive, or the modus tollens rule of inference.

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:

\(A \to B\)

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:

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

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

\((A \to B) \leftrightarrow (\neg B \to \neg A).\)

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 \(A \to B\) by checking that all girls in the United States do indeed have brown hair, or try to prove \(\neg B \to \neg A\) 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 \(\neg B \to \neg A\), and equivalently \(A \to B\).

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.

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

\((P \to Q)\)

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:

\((\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 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, \(\forall{x}(P{x} \to Q{x})\), or "All \(P\)s are \(Q\)s," is contraposed to \(\forall{x}(\neg Q{x} \to \neg P{x})\), or "All non-\(Q\)s are non-\(P\)s."

The transposition rule may be expressed as a sequent:

\((P \to Q) \vdash (\neg Q \to \neg P),\)

where \(\vdash\) is a metalogical symbol meaning that \((\neg Q \to \neg P)\) is a syntactic consequence of \((P \to Q)\) in some logical system; or as a rule of inference:

\(\frac{P \to Q}{\therefore \neg Q \to \neg P},\)

where the rule is that wherever an instance of "\(P \to Q\)" appears on a line of a proof, it can be replaced with "\(\neg Q \to \neg P\)"; or as the statement of a truth-functional tautology or theorem of propositional logic. The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as

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

where \(P\) and \(Q\) are propositions expressed in some formal system.

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

\(A \to B \, \leftrightarrow \, \neg A \lor B\)

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

\(\begin{aligned} \neg A \lor B \,& \, \leftrightarrow B \lor \neg A \\ \, & \, \leftrightarrow \neg B \to \neg A \end{aligned}\)

Let:

\((A \to B)\land \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 (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):

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

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

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

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:

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

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

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

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 \land \neg Q)\)

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

\(\neg(\neg Q \land 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 \land \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\)

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

\(\neg Q \to \neg P\)

In Hilbert-style deductive systems for propositional logic, only one side of the transposition is taken as an axiom, and the other is a theorem. We describe a proof of this theorem in the system of three axioms proposed by Jan Łukasiewicz:

A1. \(\phi \to \left( \psi \to \phi \right)\)

A2. \(\left( \phi \to \left( \psi \rightarrow \xi \right) \right) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)\)

A3. \(\left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right)\)

(A3) already gives one of the directions of the transposition. The other side, \(( \psi \to \phi ) \to ( \neg \phi \to \neg \psi)\), is proven below, using the following lemmas proven here:

(DN1) \(\neg \neg p \to p\) - Double negation (one direction)

(DN2) \(p \to \neg \neg p\) - Double negation (another direction)

(HS1) \((q \to r) \to ((p \to q) \to (p \to r))\) - one form of Hypothetical syllogism

(HS2) \((p \to q) \to ((q \to r) \to (p \to r))\) - another form of Hypothetical syllogism.

We also use the method of the hypothetical syllogism metatheorem as a shorthand for several proof steps.

The proof is as follows:

1. \(q \to \neg\neg q\)       (instance of the (DN2))
2. \((q \to \neg\neg q) \to ((p \to q) \to (p \to \neg\neg q))\)       (instance of the (HS1)
3. \((p \to q) \to (p \to \neg\neg q)\)       (from (1) and (2) by modus ponens)
4. \(\neg\neg p \to p\)       (instance of the (DN1))
5. \((\neg\neg p \to p) \to ((p \to \neg\neg q) \to (\neg\neg p \to \neg\neg q))\)       (instance of the (HS2))
6. \((p \to \neg\neg q) \to (\neg\neg p \to \neg\neg q)\)       (from (4) and (5) by modus ponens)
7. \((p \to q) \to (\neg\neg p \to \neg\neg q)\)       (from (3) and (6) using the hypothetical syllogism metatheorem)
8. \((\neg\neg p \to \neg\neg q) \to (\neg q \to \neg p)\)       (instance of (A3))
9. \((p \to q) \to (\neg q \to \neg p)\)       (from (7) and (8) using the hypothetical syllogism metatheorem)

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.

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

In traditional logic, contraposition is a form of immediate inference in which a proposition is inferred from another and where the former has for its subject the contradictory of the original logical proposition's predicate. In some cases, contraposition involves a change of the former's quality (i.e. affirmation or negation). For its symbolic expression in modern logic, see the rule of transposition. Contraposition also has philosophical application distinct from the other traditional inference processes of conversion and obversion where equivocation varies with different proposition types.

In traditional logic, the process of contraposition is a schema composed of several steps of inference involving categorical propositions and classes. A categorical proposition contains a subject and predicate where the existential impact of the copula implies the proposition as referring to a class with at least one member, in contrast to the conditional form of hypothetical or materially implicative propositions, which are compounds of other propositions, e.g. "If P, then Q" (P and Q are both propositions), and their existential impact is dependent upon further propositions where quantification existence is instantiated (existential instantiation), not on the hypothetical or materially implicative propositions themselves.

Full contraposition is the simultaneous interchange and negation of the subject and predicate, and is valid only for the type "A" and type "O" propositions of Aristotelian logic, while it is conditionally valid for "E" type propositions if a change in quantity from universal to particular is made (partial contraposition). Since the valid obverse is obtained for all the four types (A, E, I, and O types) of traditional propositions, yielding propositions with the contradictory of the original predicate, (full) contraposition is obtained by converting the obvert of the original proposition. For "E" statements, partial contraposition can be obtained by additionally making a change in quantity. Because nothing is said in the definition of contraposition with regard to the predicate of the inferred proposition, it can be either the original subject, or its contradictory, resulting in two contrapositives which are the obverts of one another in the "A", "O", and "E" type propositions.

By example: from an original, 'A' type categorical proposition,

All residents are voters,

which presupposes that all classes have members and the existential import presumed in the form of categorical propositions, one can derive first by obversion the 'E' type proposition,

No residents are non-voters.

The contrapositive of the original proposition is then derived by conversion to another 'E' type proposition,

No non-voters are residents.

The process is completed by further obversion resulting in the 'A' type proposition that is the obverted contrapositive of the original proposition,

All non-voters are non-residents.

Condensed: the full section is in Wikipedia.

In the inferred proposition, the consequent is the contradictory of the antecedent in the original proposition, and the antecedent of the inferred proposition is the contradictory of the consequent of the original proposition. The symbol for material implication signifies the proposition as a hypothetical, or the "if, then" form, e.g. "if P, then Q".

The biconditional statement of the rule of transposition (↔) refers to the relation between hypothetical (→) propositions, with each proposition including an antecedent and consequential term. As a matter of logical inference, to transpose or convert the terms of one proposition requires the conversion of the terms of the propositions on both sides of the biconditional relationship, meaning that transposing or converting (P → Q) to (Q → P) requires that the other proposition, (¬Q → ¬P), to be transposed or converted to (¬P → ¬Q). Otherwise, converting the terms of one proposition and not the other renders the rule invalid, violating the sufficient condition and necessary condition of the terms of the propositions, where the violation is that the changed proposition commits the fallacy of denying the antecedent or affirming the consequent by means of illicit conversion.

The truth of the rule of transposition is dependent upon the relations of sufficient condition and necessary condition in logic.

In the proposition "If P, then Q", the occurrence of P is sufficient reason for the occurrence of Q. P, as an individual or a class, materially implicates Q, but the relation of Q to P is such that the converse proposition "If Q, then P" does not necessarily have sufficient condition. The rule of inference for sufficient condition is modus ponens, which is an argument for conditional implication:

1. Premise (1): If P, then Q
2. Premise (2): P
3. Conclusion: Therefore, Q

Since the converse of premise (1) is not valid, all that can be stated of the relationship of P and Q is that in the absence of Q, P does not occur, meaning that Q is the necessary condition for P. The rule of inference for necessary condition is modus tollens:

1. Premise (1): If P, then Q
2. Premise (2): not Q
3. Conclusion: Therefore, not P