Contraposition

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

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 . 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. 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. (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." (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. A \to B \, \leftrightarrow \, \neg A \lor B which can be made equivalent to its contrapositive, as follows: \begin{align} \neg A \lor B \,& \, \leftrightarrow B \lor \neg A \\ \, & \, \leftrightarrow \neg B \to \neg A \end{align} (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) 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 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. \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: q \to \neg\neg q       (instance of the (DN2)) (q \to \neg\neg q) \to ((p \to q) \to (p \to \neg\neg q))       (instance of the (HS1) (p \to q) \to (p \to \neg\neg q)       (from (1) and (2) by modus ponens) \neg\neg p \to p       (instance of the (DN1)) (\neg\neg p \to p) \to ((p \to \neg\neg q) \to (\neg\neg p \to \neg\neg q))       (instance of the (HS2)) (p \to \neg\neg q) \to (\neg\neg p \to \neg\neg q)       (from (4) and (5) by modus ponens) (p \to q) \to (\neg\neg p \to \neg\neg q)       (from (3) and (6) using the hypothetical syllogism metatheorem) (\neg\neg p \to \neg\neg q) \to (\neg q \to \neg p)       (instance of (A3)) (p \to q) \to (\neg q \to \neg p)       (from (7) and (8) using the hypothetical syllogism metatheorem) === 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 to requires that the other proposition, to be transposed or converted to 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: Premise (1): If P, then Q Premise (2): P 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: Premise (1): If P, then Q Premise (2): not Q 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". ==Distinguished from transposition== While most authors use the terms for the same thing, some authors distinguish transposition from contraposition. In traditional logic the reasoning process of transposition as a rule of inference is applied to categorical propositions through contraposition and obversion, a series of immediate inferences where the rule of obversion is first applied to the original categorical proposition "All S is P"; yielding the obverse "No S is non-P". In the obversion of the original proposition to a type "E" proposition, both terms become distributed. The obverse is then converted, resulting in "No non-P is S", maintaining distribution of both terms. The "No non-P is S" is again obverted, resulting in the [contrapositive] "All non-P is non-S". Since nothing is said in the definition of contraposition with regard to the predicate of the inferred proposition, it is permissible that it could be the original subject or its contradictory, and the predicate term of the resulting type "A" proposition is again undistributed. This results in two contrapositives, one where the predicate term is distributed, and another where the predicate term is undistributed. Contraposition is a type of immediate inference in which from a given categorical proposition another categorical proposition is inferred which has as its subject the contradictory of the original predicate. Since nothing is said in the definition of contraposition with regard to the predicate of the inferred proposition, it is permissible that it could be the original subject or its contradictory. This is in contradistinction to the form of the propositions of transposition, which may be material implication, or a hypothetical statement. The difference is that in its application to categorical propositions the result of contraposition is two contrapositives, each being the obvert of the other, i.e. "No non-P is S" and "All non-P is non-S". The distinction between the two contrapositives is absorbed and eliminated in the principle of transposition, which presupposes the "mediate inferences" of contraposition and is also referred to as the "law of contraposition". ==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 \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 \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 \sqrt{2} cannot be expressed as an irreducible fraction, then it must be the case that \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 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. 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 \lnot q → \lnot p share the same truth values in all scenarios: ===Example=== Let x be an integer. To prove: If x^2 is even, then 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 x is not even, then 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 x^2=x\cdot x is odd. Thus x^2 is not even. Having proved the contrapositive, we can then infer that the original statement is true. (\omega^{A}_{P\tilde \lnot Q}) = (\omega^{A}_{Q|P},\omega^{A}_{Q|\lnot P})\,\widetilde{\phi\,}\, a_{P}\,, where (\omega^{A}_{Q|P},\omega^{A}_{Q|\lnot P}) denotes a pair of binomial conditional opinions given by source A . The parameter a_{P} denotes the base rate (aka. the prior probability) of P . The pair of derivative inverted conditional opinions is denoted (\omega^{A}_{P\tilde \lnot Q}) . The conditional opinion \omega^{A}_{Q|P} 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^{A}_{Q\mid P} is an absolute TRUE opinion is equivalent to source A saying that P\to Q is TRUE, and the case where \omega^{A}_{Q\mid P} 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^{A}_{Q|P} is absolute TRUE the subjective Bayes' theorem operator \widetilde{\phi\,} of subjective logic produces an absolute FALSE derivative conditional opinion \omega^{A}_{P\widetilde \lnot Q} 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. \Pr(\lnot P\mid \lnot Q) = \frac{\Pr(\lnot Q \mid \lnot P)\,a(\lnot P)}{\Pr(\lnot Q\mid \lnot P)\,a(\lnot P)+\Pr(\lnot Q\mid P)\,a(P)}. In the equation above the 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 (aka. the prior probability) 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 represents a generalization of contraposition.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377903190 under CC BY-SA 4.0; modifications have been made.