information:extraction, linguistic:translation, information:filtering
Proof by contrapositive

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). A proof by contrapositive is a direct proof of the contrapositive of a statement. 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 2 {\displaystyle {\sqrt {2}}} 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 2 {\displaystyle {\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 2 {\displaystyle {\sqrt {2}}} cannot be expressed as an irreducible fraction, then it must be the case that 2 {\displaystyle {\sqrt {2}}} 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 = a / b and noting that since N is a positive integer b =1 so that N = a, a square number.

In mathematics, proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive. In other words, the conclusion "if A, then B " is inferred by constructing a proof of the claim "if not B, then not A " instead. More often than not, this approach is preferred if the contrapositive is easier to prove than the original conditional statement itself.

Logically, the validity of proof by contrapositive can be demonstrated by the use of the following truth table, where it is shown that p → q and ¬ {\displaystyle \lnot } q → ¬ {\displaystyle \lnot } p share the same truth values in all scenarios: