What's the difference between a contrapositive statement and a contradiction? [duplicate]

Solution 1:

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

Solution 2:

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.

Solution 3:

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.