HOME

TheInfoList




In
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...

logic
and
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, contraposition refers to the
inference Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word ''wikt:infer, infer'' means to "carry forward". Inference is theoretically traditionally divided into deductive reasoning, deduction and i ...

inference
of going from a conditional statement into its
logically equivalent Logic (from Greek: grc, λογική, label=none, lit=possessed of reason Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=n ...
contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statement has its
antecedent An antecedent is a preceding event, condition, cause, phrase, or word. More specifically, it may refer to: * Antecedent (behavioral psychology), the stimulus that occurs before a trained behavior * Antecedent (genealogy), antonym of descendant, gen ...
and
consequent A consequent is the second half of a hypothetical proposition In logic and linguistics, a proposition is the meaning of a declarative sentence (linguistics), sentence. In philosophy, "Meaning (philosophy), meaning" is understood to be a non-li ...
inverted and flipped. Conditional statement P \rightarrow Q. In
formulas In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a chemical formula. The informal use of the term ''formula'' in science refers to the Commensurability (philosophy of science), general ...
: 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. The contrapositive ( \neg Q \rightarrow \neg P ) can be compared with three other statements: ;
Inversion Inversion or inversions may refer to: Arts * , a French gay magazine (1924/1925) * Inversion (artwork), ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas * Inversion (music), a term with various meanings in music theory and mus ...
(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 In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
is not at all dependent on whether or not the original proposition was true, as evidenced here. ;
Conversion Conversion or convert may refer to: Arts, entertainment, and media * Conversion (Doctor Who audio), "Conversion" (''Doctor Who'' audio), an episode of the audio drama ''Cyberman'' * Conversion (Stargate Atlantis), "Conversion" (''Stargate Atlantis ...
(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 In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, ...

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 In propositional calculus, propositional logic, ''modus tollens'' () (MT), also known as ''modus tollendo wiktionary:tollens, tollens'' (Latin language, Latin for "method of removing by taking away") and denying the consequent, is a Deductive r ...
''
rule of inference In the philosophy of logic Following the developments in formal logic with symbolic logic in the late nineteenth century and mathematical logic in the twentieth, topics traditionally treated by logic not being part of formal logic have tended to ...
.


Intuitive explanation

In the
Euler diagram An Euler diagram (, ) is a diagrammatic means of representing Set (mathematics), sets and their relationships. They are particularly useful for explaining complex hierarchies and overlapping definitions. They are similar to another set diagramm ...

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.


Formal definition

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 An antecedent is a preceding event, condition, cause, phrase, or word. More specifically, it may refer to: * Antecedent (behavioral psychology), the stimulus that occurs before a trained behavior * Antecedent (genealogy), antonym of descendant, gen ...
, and Q is the
consequent A consequent is the second half of a hypothetical proposition In logic and linguistics, a proposition is the meaning of a declarative sentence (linguistics), sentence. In philosophy, "Meaning (philosophy), meaning" is understood to be a non-li ...
. One statement is the contrapositive of the other only when its antecedent is the
negated In logic, negation, also called the logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted i ...

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 In logic and mathematics, statements p and q are said to be logically equivalent if they are provable from each other under a set of axioms, or have the same truth value in every model (logic), model. The logical equivalence of p and q is sometimes ...
, stating one effectively states the other; when one is
true True most commonly refers to truth, the state of being in congruence with fact or reality. True may also refer to: Places * True, West Virginia, an unincorporated community in the United States * True, Wisconsin, a town in the United States * Tr ...
, 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(P \to Q), or "All Ps are Qs," is contraposed to \forall(\neg Q \to \neg P), or "All non-Qs are non-Ps."


Simple proof by definition of a conditional

In
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal system A formal system is an used for inferring theorems from axioms according to a set of rules. These rul ...
, the conditional is defined as: :A \to B \, \leftrightarrow \, \neg A \lor B which can be made equivalent to its contrapositive, as follows: : \begin \neg A \lor B \,& \, \leftrightarrow B \lor \neg A \\ \, & \, \leftrightarrow \neg B \to \neg A \end


Simple proof by contradiction

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 In propositional logic Propositional calculus is a branch of logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from ...

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)


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 Logic (from Greek: grc, λογική, label=none, lit=possessed of reason Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=n ...
, 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 Conjunction may refer to: * Conjunction (astronomy), in which two astronomical bodies appear close together in the sky * Conjunction (astrology), astrological aspect in horoscopic astrology * Conjunction (grammar), a part of speech * Logical conjun ...
can be reversed with no effect (by
commutativity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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


Comparisons


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 In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, ...
. Similarly, take the statement "''All
quadrilaterals A quadrilateral is a polygon In geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, sh ...

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 In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
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 In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, ...
, 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 In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents stat ...
.


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
theorem In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s (especially if the truth of the contrapositive is easier to establish than the truth of the statement itself). A proof by contraposition (contrapositive) is a
direct proofIn mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually axioms, existing lemma (mathematics), lemmas and theorems, without making any furt ...
of the contrapositive of a statement. However, indirect methods such as
proof by contradiction In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents stateme ...
can also be used with contraposition, as, for example, in the proof of the irrationality of the
square root of 2 The square root of 2 (approximately 1.4142) is a positive real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they ...
. By the definition of a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
, the statement can be made that "''If \sqrt is rational, then it can be expressed as an
irreducible fraction An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction in which the numerator and denominator are integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquial ...
''". This statement is true because it is a restatement of a definition. The contrapositive of this statement is "''If \sqrt 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 cannot be expressed as an irreducible fraction, then it must be the case that \sqrt 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 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''2/''b''2 and noting that since ''N'' is a positive integer ''b''=1 so that ''N'' = ''a''2, a square number.


Correspondence to other mathematical frameworks


Intuitionistic logic

In
intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of ...
, the statement P \to Q cannot be proven to be equivalent to \lnot Q \to \lnot P. We can prove that P \to Q implies \lnot Q \to \lnot P, but the reverse implication, from \lnot Q \to \lnot P to P \to Q, requires the law of the excluded middle or an equivalent axiom.


Probability calculus

''Contraposition'' represents an instance of
Bayes' theorem In probability theory and statistics, Bayes' theorem (alternatively Bayes' law or Bayes' rule; recently Bayes–Price theorem), named after the Reverend Thomas Bayes, describes the probability of an event (probability theory), event, based on p ...
which in a specific form can be expressed as: \Pr(\lnot P\mid \lnot Q) = \frac. In the equation above the
conditional probability
conditional probability
\Pr(\lnot Q\mid P) generalizes the logical statement P \to \lnot Q, i.e. in addition to assigning TRUE or FALSE we can also assign any probability to the statement. The term a(P) denotes the
base rate In probability and statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, industrial, or social problem, it is convention ...
(aka. the
prior probability In Bayesian Thomas Bayes (/beɪz/; c. 1701 – 1761) was an English statistician, philosopher, and Presbyterian minister. Bayesian () refers to a range of concepts and approaches that are ultimately based on a degree-of-belief interpretation o ...
) of P. Assume that \Pr(\lnot Q \mid P) = 1 is equivalent to P\to \lnot Q being TRUE, and that \Pr(\lnot Q \mid P) = 0 is equivalent to P \to \lnot Q being FALSE. It is then easy to see that \Pr(\lnot P \mid \lnot Q) = 1 when \Pr(Q\mid P) = 1 i.e. when P \to Q is TRUE. This is because \Pr(\lnot Q\mid P) = 1 - \Pr(Q\mid P) = 0 so that the fraction on the right-hand side of the equation above is equal to 1, and hence \Pr(\lnot P\mid \lnot Q) = 1 which is equivalent to \lnot Q \to \lnot P being TRUE. Hence,
Bayes' theorem In probability theory and statistics, Bayes' theorem (alternatively Bayes' law or Bayes' rule; recently Bayes–Price theorem), named after the Reverend Thomas Bayes, describes the probability of an event (probability theory), event, based on p ...
represents a generalization of ''contraposition''.


Subjective logic

''Contraposition'' represents an instance of the subjective Bayes' theorem in
subjective logic Subjective logic is a type of probabilistic logicThe aim of a probabilistic logic (also probability logic and probabilistic reasoning) is to combine the capacity of probability theory to handle uncertainty with the capacity of deductive logic to ex ...
expressed as: (\omega^_,\omega^_) = (\omega^_,\omega^_)\,\widetilde\, a_\,, where (\omega^_,\omega^_) denotes a pair of binomial conditional opinions given by source A. The parameter a_ denotes the
base rate In probability and statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, industrial, or social problem, it is convention ...
(aka. the
prior probability In Bayesian Thomas Bayes (/beɪz/; c. 1701 – 1761) was an English statistician, philosopher, and Presbyterian minister. Bayesian () refers to a range of concepts and approaches that are ultimately based on a degree-of-belief interpretation o ...
) of P. The pair of inverted conditional opinions is denoted (\omega^_,\omega^_). The conditional opinion \omega^_ generalizes the logical statement P \to Q, i.e. in addition to assigning TRUE or FALSE the source A can assign any subjective opinion to the statement. The case where \omega^_ is an absolute TRUE opinion is equivalent to source A saying that P\to Q is TRUE, and the case where \omega^_ is an absolute FALSE opinion is equivalent to source A saying that P\to Q is FALSE. In the case when the conditional opinion \omega^_ is absolute TRUE the subjective Bayes' theorem operator \widetilde of
subjective logic Subjective logic is a type of probabilistic logicThe aim of a probabilistic logic (also probability logic and probabilistic reasoning) is to combine the capacity of probability theory to handle uncertainty with the capacity of deductive logic to ex ...
produces an absolute FALSE conditional opinion \omega^_ and thereby an absolute TRUE conditional opinion \omega^_ which is equivalent to \lnot Q \to \lnot P being TRUE. Hence, the subjective Bayes' theorem represents a generalization of both ''contraposition'' and
Bayes' theorem In probability theory and statistics, Bayes' theorem (alternatively Bayes' law or Bayes' rule; recently Bayes–Price theorem), named after the Reverend Thomas Bayes, describes the probability of an event (probability theory), event, based on p ...
.Audun Jøsang 2016:92


See also

* ''
Reductio ad absurdum In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents sta ...
''


References


Sources

* Audun Jøsang, 2016, ''Subjective Logic; A formalism for Reasoning Under Uncertainty'' Springer, Cham,


External links

*{{Commons category-inline Mathematical logic Theorems in propositional logic