Sequent notation

The transposition rule may be expressed as a sequent:

${\displaystyle (P\to Q)\vdash (\neg Q\to \neg P),}$

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

${\displaystyle {\frac {P\to Q}{\therefore \neg Q\to \neg P}},}$

where the rule is that wherever an instance of "${\displaystyle P\to Q}$" appears on a line of a proof, it can be replaced with "${\displaystyle \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

${\displaystyle (P\to Q)\to (\neg Q\to \neg P),}$

where ${\displaystyle P}$ and ${\displaystyle Q}$ are propositions expressed in some formal system.

Simple proof by definition of a conditional

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

${\displaystyle A\to B\,\leftrightarrow \,\neg A\lor B}$

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

${\displaystyle {\begin{aligned}\neg A\lor B\,&\,\leftrightarrow B\lor \neg A\\\,&\,\leftrightarrow \neg B\to \neg A\end{aligned}}}$

Simple proof by contradiction

Let:

${\displaystyle (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):

${\displaystyle (A\to B)\to (\neg B\to \neg A)}$

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

${\displaystyle (\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:

${\displaystyle (\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:

${\displaystyle (A\to B)\equiv (\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.

${\displaystyle P\to Q}$

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

${\displaystyle \neg (P\land \neg Q)}$

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

${\displaystyle \neg (\neg Q\land P)}$

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

${\displaystyle \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:

${\displaystyle R\to S}$

By reverting R and S back into ${\displaystyle P}$ and ${\displaystyle Q}$, we then obtain the desired contrapositive:

${\displaystyle \neg Q\to \neg P}$

In classical propositional calculus system

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. ${\displaystyle \phi \to \left(\psi \to \phi \right)}$

A2. ${\displaystyle \left(\phi \to \left(\psi \rightarrow \xi \right)\right)\to \left(\left(\phi \to \psi \right)\to \left(\phi \to \xi \right)\right)}$

A3. ${\displaystyle \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, ${\displaystyle (\psi \to \phi )\to (\neg \phi \to \neg \psi )}$, is proven below, using the following lemmas proven here:

(DN1) ${\displaystyle \neg \neg p\to p}$ - Double negation (one direction)

(DN2) ${\displaystyle p\to \neg \neg p}$ - Double negation (another direction)

(HS1) ${\displaystyle (q\to r)\to ((p\to q)\to (p\to r))}$ - one form of Hypothetical syllogism

(HS2) ${\displaystyle (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. ${\displaystyle q\to \neg \neg q}$       (instance of the (DN2))
2. ${\displaystyle (q\to \neg \neg q)\to ((p\to q)\to (p\to \neg \neg q))}$       (instance of the (HS1)
3. ${\displaystyle (p\to q)\to (p\to \neg \neg q)}$       (from (1) and (2) by modus ponens)
4. ${\displaystyle \neg \neg p\to p}$       (instance of the (DN1))
5. ${\displaystyle (\neg \neg p\to p)\to ((p\to \neg \neg q)\to (\neg \neg p\to \neg \neg q))}$       (instance of the (HS2))
6. ${\displaystyle (p\to \neg \neg q)\to (\neg \neg p\to \neg \neg q)}$       (from (4) and (5) by modus ponens)
7. ${\displaystyle (p\to q)\to (\neg \neg p\to \neg \neg q)}$       (from (3) and (6) using the hypothetical syllogism metatheorem)
8. ${\displaystyle (\neg \neg p\to \neg \neg q)\to (\neg q\to \neg p)}$       (instance of (A3))
9. ${\displaystyle (p\to q)\to (\neg q\to \neg p)}$       (from (7) and (8) using the hypothetical syllogism metatheorem)

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

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

Form of transposition

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.

Sufficient condition

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

Necessary condition

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

Necessity and sufficiency example

An example traditionally used by logicians contrasting sufficient and necessary conditions is the statement "If there is fire, then oxygen is present". An oxygenated environment is necessary for fire or combustion, but simply because there is an oxygenated environment does not necessarily mean that fire or combustion is occurring. While one can infer that fire stipulates the presence of oxygen, from the presence of oxygen the converse "If there is oxygen present, then fire is present" cannot be inferred. All that can be inferred from the original proposition is that "If oxygen is not present, then there cannot be fire".

Relationship of propositions

The symbol for the biconditional ("↔") signifies the relationship between the propositions is both necessary and sufficient, and is verbalized as "if and only if", or, according to the example "If P, then Q 'if and only if' if not Q, then not P".

Necessary and sufficient conditions can be explained by analogy in terms of the concepts and the rules of immediate inference of traditional logic. In the categorical proposition "All S is P", the subject term S is said to be distributed, that is, all members of its class are exhausted in its expression. Conversely, the predicate term P cannot be said to be distributed, or exhausted in its expression because it is indeterminate whether every instance of a member of P as a class is also a member of S as a class. All that can be validly inferred is that "Some P are S". Thus, the type "A" proposition "All P is S" cannot be inferred by conversion from the original type "A" proposition "All S is P". All that can be inferred is the type "A" proposition "All non-P is non-S" (note that (P → Q) and (¬Q → ¬P) are both type "A" propositions). Grammatically, one cannot infer "all mortals are men" from "All men are mortal". An type "A" proposition can only be immediately inferred by conversion when both the subject and predicate are distributed, as in the inference "All bachelors are unmarried men" from "All unmarried men are bachelors".

Difference with proof by contradiction

Proof by contradiction: Assume (for contradiction) that ${\displaystyle \neg A}$ is true. Use this assumption to prove a contradiction. It follows that ${\displaystyle \neg A}$ is false, so ${\displaystyle A}$ is true.

Proof by contrapositive: To prove ${\displaystyle A\to B}$, prove its contrapositive statement, which is ${\displaystyle \neg B\to \neg A}$.

Example

Let ${\displaystyle x}$ be an integer.

To prove: If ${\displaystyle x^{2}}$ is even, then ${\displaystyle x}$ is even.

Although a direct proof can be given, we choose to prove this statement by contraposition. The contrapositive of the above statement is:

If ${\displaystyle x}$ is not even, then ${\displaystyle x^{2}}$ is not even.

This latter statement can be proven as follows: suppose that x is not even, then x is odd. The product of two odd numbers is odd, hence ${\displaystyle x^{2}=x\cdot x}$ is odd. Thus ${\displaystyle x^{2}}$ is not even.

Having proved the contrapositive, we can then infer that the original statement is true.^[16]

Intuitionistic logic

In intuitionistic logic, the statement ${\displaystyle P\to Q}$ cannot be proven to be equivalent to ${\displaystyle \lnot Q\to \lnot P}$. We can prove that ${\displaystyle P\to Q}$ implies ${\displaystyle \lnot Q\to \lnot P}$ (see below), but the reverse implication, from ${\displaystyle \lnot Q\to \lnot P}$ to ${\displaystyle P\to Q}$, requires the law of the excluded middle or an equivalent axiom.

Assume ${\displaystyle P\to Q}$ (initial assumption)

Assume ${\displaystyle Q\to \bot }$

From ${\displaystyle P\to Q}$ and ${\displaystyle Q\to \bot }$, conclude ${\displaystyle P\to \bot }$

Discharge assumption; conclude ${\displaystyle (Q\to \bot )\to (P\to \bot )}$

Turning ${\displaystyle (A\to \bot )}$ into ${\displaystyle \lnot A}$, conclude ${\displaystyle \lnot Q\to \lnot P}$

Discharge assumption; conclude ${\displaystyle (P\to Q)\to (\lnot Q\to \lnot P)}$.

Subjective logic

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

${\displaystyle (\omega _{P{\tilde {|}}Q}^{A},\omega _{P{\tilde {|}}\lnot Q}^{A})=(\omega _{Q|P}^{A},\omega _{Q|\lnot P}^{A})\,{\widetilde {\phi \,}}\,a_{P}\,,}$

where ${\displaystyle (\omega _{Q|P}^{A},\omega _{Q|\lnot P}^{A})}$ denotes a pair of binomial conditional opinions given by source ${\displaystyle A}$. The parameter ${\displaystyle a_{P}}$ denotes the base rate (aka. the prior probability) of ${\displaystyle P}$. The pair of derivative inverted conditional opinions is denoted ${\displaystyle (\omega _{P{\tilde {|}}Q}^{A},\omega _{P{\tilde {|}}\lnot Q}^{A})}$. The conditional opinion ${\displaystyle \omega _{Q|P}^{A}}$ generalizes the logical statement ${\displaystyle P\to Q}$, i.e. in addition to assigning TRUE or FALSE the source ${\displaystyle A}$ can assign any subjective opinion to the statement. The case where ${\displaystyle \omega _{Q\mid P}^{A}}$ is an absolute TRUE opinion is equivalent to source ${\displaystyle A}$ saying that ${\displaystyle P\to Q}$ is TRUE, and the case where ${\displaystyle \omega _{Q\mid P}^{A}}$ is an absolute FALSE opinion is equivalent to source ${\displaystyle A}$ saying that ${\displaystyle P\to Q}$ is FALSE. In the case when the conditional opinion ${\displaystyle \omega _{Q|P}^{A}}$ is absolute TRUE the subjective Bayes' theorem operator ${\displaystyle {\widetilde {\phi \,}}}$ of subjective logic produces an absolute FALSE derivative conditional opinion ${\displaystyle \omega _{P{\widetilde {|}}\lnot Q}^{A}}$ and thereby an absolute TRUE derivative conditional opinion ${\displaystyle \omega _{\lnot P{\widetilde {|}}\lnot Q}^{A}}$ which is equivalent to ${\displaystyle \lnot Q\to \lnot P}$ being TRUE. Hence, the subjective Bayes' theorem represents a generalization of both contraposition and Bayes' theorem.^[17]