It has been suggested that Proof by contrapositive be merged into this article. (Discuss) Proposed since April 2024. |
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statement has its antecedent and consequent inverted and flipped.
Conditional statement . In formulas: the contrapositive of is . [1]
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. [2]
The contrapositive () can be compared with three other statements:
Note that if is true and one is given that is false (i.e., ), then it can logically be concluded that must be also false (i.e., ). This is often called the law of contrapositive, or the modus tollens rule of inference. [3]
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:
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:
is the contrapositive of the above statement. Therefore, one can say that
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 by checking that all girls in the United States do indeed have brown hair, or try to prove 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 , and equivalently .
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:
This states that, "if , then ", or, "if Socrates is a man, then Socrates is human." In a conditional such as this, is the antecedent, and 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:
That is, "If not-, then not-", or, more clearly, "If 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, , or "All s are s," is contraposed to , or "All non-s are non-s." [4]
In first-order logic, the conditional is defined as:
which can be made equivalent to its contrapositive, as follows:
Let:
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):
We can apply the same process the other way round, starting with the assumptions that:
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:
Combining the two proved statements together, we obtain the sought-after logical equivalence between a conditional and its contrapositive:
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.
This is only false when is true and is false. Therefore, we can reduce this proposition to the statement "False when and not-" (i.e. "True when it is not the case that and not-"):
The elements of a conjunction can be reversed with no effect (by commutativity):
We define as equal to "", and as equal to (from this, is equal to , which is equal to just ):
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:
By reverting R and S back into and , we then obtain the desired contrapositive:
name | form | description |
---|---|---|
implication | if P then Q | first statement implies truth of second |
inverse | if not P then not Q | negation of both statements |
converse | if Q then P | reversal of both statements |
contrapositive | if not Q then not P | reversal and negation of both statements |
negation | P and not Q | contradicts the implication |
Take the statement "All red objects have color." This can be equivalently expressed as "If an object is red, then it has color."
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."
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.
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 contraposition (contrapositive) is a direct proof of the contrapositive of a statement. [5] 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 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 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 cannot be expressed as an irreducible fraction, then it must be the case that 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 = a2/b2 and noting that since N is a positive integer b=1 so that N = a2, a square number.
In intuitionistic logic, the statement cannot be proven to be equivalent to . We can prove that implies , but the reverse implication, from to , requires the law of the excluded middle or an equivalent axiom.
Contraposition represents an instance of Bayes' theorem which in a specific form can be expressed as:
In the equation above the conditional probability generalizes the logical statement , i.e. in addition to assigning TRUE or FALSE we can also assign any probability to the statement. The term denotes the base rate (aka. the prior probability) of . Assume that is equivalent to being TRUE, and that is equivalent to being FALSE. It is then easy to see that when i.e. when is TRUE. This is because so that the fraction on the right-hand side of the equation above is equal to 1, and hence which is equivalent to being TRUE. Hence, Bayes' theorem represents a generalization of contraposition. [6]
Contraposition represents an instance of the subjective Bayes' theorem in subjective logic expressed as:
where denotes a pair of binomial conditional opinions given by source . The parameter denotes the base rate (aka. the prior probability) of . The pair of derivative inverted conditional opinions is denoted . The conditional opinion generalizes the logical statement , i.e. in addition to assigning TRUE or FALSE the source can assign any subjective opinion to the statement. The case where is an absolute TRUE opinion is equivalent to source saying that is TRUE, and the case where is an absolute FALSE opinion is equivalent to source saying that is FALSE. In the case when the conditional opinion is absolute TRUE the subjective Bayes' theorem operator of subjective logic produces an absolute FALSE derivative conditional opinion and thereby an absolute TRUE derivative conditional opinion which is equivalent to being TRUE. Hence, the subjective Bayes' theorem represents a generalization of both contraposition and Bayes' theorem. [7]
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.
In logic, a logical connective is a logical constant. Connectives can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives representing the truth functions of conjunction, disjunction, implication, equivalence, and negation. Some sources include other connectives, as in the table below.
In propositional logic, modus ponens, also known as modus ponendo ponens, implication elimination, or affirming the antecedent, is a deductive argument form and rule of inference. It can be summarized as "P implies Q.P is true. Therefore, Q must also be true."
In propositional logic, modus tollens (MT), also known as modus tollendo tollens and denying the consequent, is a deductive argument form and a rule of inference. Modus tollens is a mixed hypothetical syllogism that takes the form of "If P, then Q. Not Q. Therefore, not P." It is an application of the general truth that if a statement is true, then so is its contrapositive. The form shows that inference from P implies Q to the negation of Q implies the negation of P is a valid argument.
In probability theory and statistics, Bayes' theorem, named after Thomas Bayes, describes the probability of an event, based on prior knowledge of conditions that might be related to the event. For example, if the risk of developing health problems is known to increase with age, Bayes' theorem allows the risk to an individual of a known age to be assessed more accurately by conditioning it relative to their age, rather than assuming that the individual is typical of the population as a whole.
In logic and mathematics, the converse of a categorical or implicational statement is the result of reversing its two constituent statements. For the implication P → Q, the converse is Q → P. For the categorical proposition All S are P, the converse is All P are S. Either way, the truth of the converse is generally independent from that of the original statement.
In logic, an inverse is a type of conditional sentence which is an immediate inference made from another conditional sentence. More specifically, given a conditional sentence of the form , the inverse refers to the sentence . Since an inverse is the contrapositive of the converse, inverse and converse are logically equivalent to each other.
In logic, negation, also called the logical not or logical complement, is an operation that takes a proposition to another proposition "not ", standing for " is not true", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .
In logic and mathematics, the logical biconditional, also known as material biconditional or equivalence or biimplication or bientailment, is the logical connective used to conjoin two statements and to form the statement " if and only if ", where is known as the antecedent, and the consequent.
In propositional logic, material implication is a valid rule of replacement that allows for a conditional statement to be replaced by a disjunction in which the antecedent is negated. The rule states that P implies Q is logically equivalent to not- or and that either form can replace the other in logical proofs. In other words, if is true, then must also be true, while if is not true, then cannot be true either; additionally, when is not true, may be either true or false.
In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition A is logically equivalent to not (not-A), or by the formula A ≡ ~(~A) where the sign ≡ expresses logical equivalence and the sign ~ expresses negation.
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional.
The material conditional is an operation commonly used in logic. When the conditional symbol is interpreted as material implication, a formula is true unless is true and is false. Material implication can also be characterized inferentially by modus ponens, modus tollens, conditional proof, and classical reductio ad absurdum.
In logic, the contrapositive of a conditional statement is formed by negating both terms and reversing the direction of inference. More specifically, the contrapositive of the statement "if A, then B" is "if not B, then not A." A statement and its contrapositive are logically equivalent, in the sense that if the statement is true, then its contrapositive is true and vice versa.
In propositional logic, transposition is a valid rule of replacement that permits one to switch the antecedent with the consequent of a conditional statement in a logical proof if they are also both negated. It is the inference from the truth of "A implies B" to the truth of "Not-B implies not-A", and conversely. It is very closely related to the rule of inference modus tollens. It is the rule that
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation-complete theorem-proving technique for sentences in propositional logic and first-order logic. For propositional logic, systematically applying the resolution rule acts as a decision procedure for formula unsatisfiability, solving the Boolean satisfiability problem. For first-order logic, resolution can be used as the basis for a semi-algorithm for the unsatisfiability problem of first-order logic, providing a more practical method than one following from Gödel's completeness theorem.
Markov's principle, named after Andrey Markov Jr, is a conditional existence statement for which there are many equivalent formulations, as discussed below.