Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

I keep mixing them up, because they are very similar.

Some contrapositives resemble some contradictions.

share|improve this question
    
I would suggest looking into truth tables to show $p \implies q \iff \n q implies \n p$. Then practice writing negations of logical statements. –  CodeKingPlusPlus Nov 2 '12 at 6:54
    
$p \implies q \iff \neg q \implies \neg p$ –  CodeKingPlusPlus Nov 2 '12 at 7:29
    
Dear Gladstone, I hope the answers below have helped to clarify the differences between a contrapositive statement and a contradiction. –  amWhy Nov 2 '12 at 18:32
add comment

marked as duplicate by azimut, mrf, Lord_Farin, Davide Giraudo, TZakrevskiy Sep 25 '13 at 20:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

up vote 3 down vote accepted

A contrapositive has truth value equivalent to the original statement:

$$\text{It is raining}\implies\text{I have an umbrella}$$ has a contrapositive (and is equivalent to) $$\text{I do not have an umbrella}\implies\text{it is not raining}$$

Proving the contrapositive is equivalent to proving the original statement, and can sometimes be cleaner. Note that we're dealing with (hopefully) true statements this way. We're trying to prove truth, not falsity.

A proof by contradiction proves a statement true that can be proven false (typically is already known to be false) by other means, meaning that the logic being used is inconsistent. Rather than working with a statement directly, it assumes its negation and derives an absurdity. The goal here is to reach a falsehood, not truth. While this works, and can sometimes be nice, working in an inconsistent theory means that intermediate results proven or needed along the way are useless. If a proof by contradiction suggests (or can be easily turned into) a more direct proof of similar difficulty, the direct proof is typically preferred.

share|improve this answer
    
proving by contrapositive is by making the statement a negative statement? –  Gladstone Asder Nov 1 '12 at 22:13
    
the only reason between a negation and a contrapositive statement is that a contrapositive changes the order of the terms, right? –  Gladstone Asder Nov 1 '12 at 22:14
2  
The contrapositive is not the negative. If the original statement is true, the contrapositive is true while the negative is false. The negative of $p\implies q$ is $p\land\lnot q$, while the contrapositive is $\lnot q\implies \lnot p$ –  Robert Mastragostino Nov 1 '12 at 22:30
add comment

When one speaks of a contrapositive or proving a contrapositive, one is speaking about the contrapositive of an implication (an "if...then" statement), and as pointed out in the earlier answers, if one wants to prove that $$P \implies Q\tag{1}$$ one can choose, instead, to prove $$\lnot Q \implies \lnot P,\tag{2}$$ because both statements are equivalent (i.e., if one is true, so is the other...and if one is false, so is the other). Don't confuse the appearance of the $\lnot$ symbol on each side of (2) as being either a negation of (1) nor contradiction. To see what I mean, one can correctly state that (1) (which does not contain the "$\lnot$" symbol) is the contrapostive of (2) because (2) is equivalent to $$\lnot(\lnot P) \implies \lnot(\lnot Q) \equiv P \implies Q.\tag{3}$$

In contrast, a contradiction is obtained when one derives or asserts that both a statement $P$ and its negation $\lnot P\;$ hold, i.e., when one asserts or derives: $$P \land \lnot P\tag{4}$$ (E.g., $x \in A \land x \notin A$ is a contradiction, and as such, is false regardless of whether or not $x \in A$).

Another way of putting it is that a contradiction is any statement which is always false (i.e., a statement which is "inherently" false), and a contradiction can be thought of as the "opposite" of a tautology which is always true: e.g. $P \lor \lnot P$ is a tautology, and as such is true without knowing whether $P$ is true or false).

share|improve this answer
add comment

The contrapositive says that to argue $P\implies Q$, you instead argue $\sim Q\implies \sim P$.

Argument by contradiction is done by assuming $P$ and showing $P \implies \rm{False}$.

Proving there is an infinity of primes is done by contradiction. You assume that there are finitely many. You take their product and add 1; you are forced to conclude this new object is relatively prime to every prime, which is impossible. The initial premise implies false, so it must be false.

Here is the contrapositive. Suppose that $ab$ odd. Then $a$ and $b$ is odd. let us argue by the contrapositive. Suppose $a$ or $b$ is even. Wlog, assume $a$ is even; write $a = 2n$ for an integer $n$. Then $ab = 2n = 2nb$; Since $2|ab$, $ab$ is even.

share|improve this answer
    
Did you mean to write "by assuming $P \land \lnot Q$" on line 2? –  Matt N. Dec 20 '12 at 19:09
    
Make a truth table: $(P\implies Q)\iff(\sim Q \implies \sim P).$ –  ncmathsadist Dec 21 '12 at 0:36
    
No, the second line, not the first line. If you assume $P$ and derive not $P$ then false. But what does that say about $Q$? –  Matt N. Dec 21 '12 at 7:31
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.