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.

My question tries to address the intuition or situations when using the contrapositive to prove a mathematical statement is an adequate attempt.

Whenever we have a mathematical statement of the form $A \implies B$, we can always try to prove the contrapositive instead i.e. $\neg B \implies \neg A$. However, what I find interesting to think about is, when should this approach look promising? When is it a good idea when trying to prove something to use the contrapositive? What is the intuition that $A \implies B$ might be harder to do directly than if one tried to do the contrapositive?

I am looking more for a set of guidelines or intuitions or heuristics that might suggest that trying to use the contrapositive to prove the mathematical statement might be a good idea.

Some problems have structures that make it more "obvious" to try induction or contradiction. For example, in cases where a recursion is involved or something is iterating, sometimes induction is natural way of trying the problem. Or when some mathematical object has property X, then assuming it doesn't have property X can seem promising because assuming the opposite might lead to a contradiction. So I was wondering if there was something analogous to proving stuff using the contrapositive.

I was wondering if the community had a good set of heuristics for when they taught it could be a good idea to use the contrapositive in a proof.

Also, this question might benefit from some simple, but very insightful examples that show why the negation might be easier to prove. Also, I know that this intuition can be gained from experience, so providing good or solid examples could be a great way to contribute. Just don't forget to say what type of intuition you are trying to teach with your examples!

Note that I am probably not expecting an actual full proof super general magical algorithm because an algorithm like that could probably be used for automating prooving, which might imply something big like $P=NP$. (Obviously a proof of P vs NP is always interesting, but I think that asking the community to prove the P vs NP is not a realistic thing to ask...)

share|improve this question
1  
It's a good idea if it works :) No, seriously, I don't think there is some kind of general suggestion, but a nice question (+1). I would be interested in an answer as well. –  user127.0.0.1 Jan 15 at 0:21
2  
Prove is the verb, proof the is noun. –  Pedro Tamaroff Jan 15 at 0:25
    
Re the question, a bit of it is experience, and trial and error. Some proofs work out nicely by contradiction or contraposition (some people fail to distinguish those), some theorems yield nicely to direct proofs. –  Pedro Tamaroff Jan 15 at 0:26
    
Maybe a collection of the ideas/guidlines/examples learned by people that have the experience might be a great answer! :) –  Pinocchio Jan 15 at 0:30
2  
It also happens, one tries to argue by contradiction or contraposition when the negation is simpler than the assertion, for example, if an $\forall$ gets turned into a $\exists$, we can work with something less restrictive. For example, suppose I wanted to show that "If $X$ is a metric space $X$ with the Bolzano Weiertrass property (or that is sequentially compact) and $O$ is an open cover, then it has a Lebesgue number $\varepsilon_L$." This means that for every $x\in X$, $B(x,\varepsilon_L)$ is contained in some element of the cover. –  Pedro Tamaroff Jan 15 at 0:44
show 1 more comment

6 Answers 6

Contraposition is often helpful when an implication has multiple hypotheses, or when the hypothesis specifies multiple objects (perhaps infinitely many).

As a simple (and arguably artificial) example, compare, for $x$ a real number:

1(a). If $x^4 - x^3 + x^2 \neq 1$, then $x \neq 1$. (Not easy to see without implicit contraposition?)

1(b). If $x = 1$, then $x^4 - x^3 + x^2 = 1$. (Immediately obvious.)

Here's a classic from elementary real analysis, with $x$ again standing for a real number:

2(a). If $|x| \leq \frac{1}{n}$ for every positive integer $n$, then $x = 0$.

This is true, but awkward to prove directly because there are effectively infinitely many hypotheses (one for each positive $n$), yet no finite number of these hypotheses implies the conclusion.

2(b). If $x \neq 0$, there exists a positive integer $n$ such that $\frac{1}{n} < |x|$.

The contrapositive, which follows immediately from the Archimedean property, requires only a strategy for showing some hypothesis is violated if the conclusion is false.

3(a). If $f$ is a continuous, real-valued function on $[0, 1]$ and if $$ \int_0^1 f(x) g(x)\, dx = 0\quad\text{for every continuous $g$,} $$ then $f \equiv 0$.

3(b). If $f$ is a continuous, real-valued function on $[0, 1]$ that is not indentically zero, then $$ \int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some continuous $g$.} $$

Here contraposition is not especially helpful because the specific choice $f = g$ gives either direction. That is, 3(a) has infinitely many hypotheses, but one of them is sufficient to deduce the conclusion.

Contrast with the superficially similar-looking:

4(a). If $f$ is a continuous, real-valued function on $[0, 1]$ and if $$ \int_0^1 f(x) g(x)\, dx = 0\quad\text{for every non-negative step function $g$,} $$ then $f \equiv 0$.

4(b). If $f$ is a continuous, real-valued function on $[0, 1]$ that is not indentically zero, then $$ \int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some non-negative step function $g$.} $$

(Sketch of 4(b): If $f$ is not identically $0$, there is an $x_0$ in $(0, 1)$ such that $f(x_0) \neq 0$. By continuity, there exists a $\delta > 0$ such that $[x_0 - \delta, x_0 + \delta] \subset (0, 1)$ and $|f(x)| > |f(x_0)|/2$ for all $x$ with $|x - x_0| < \delta$. Let $g$ be the characteristic function of $[x_0 - \delta, x_0 + \delta]$.)

As in 2(a), the hypothesis of 4(a) comprises infinitely many conditions, and no finite number suffice. Here, the contrapositive 4(b) arises naturally, because in trying to establish 4(a) directly one is all but forced to ask how the conclusion could fail.

share|improve this answer
    
Fantastic answer –  Spencer Jan 25 at 4:31
    
I have been a little busy lately and havn't had time to read your answer, but I feel if so many people liked your response, you'll get the bounty. However, I will read it later and probably write comments/questions, just to make sure if people in the future come and read it, they can take advantage of our comments. Btw, thanks! :) –  Pinocchio Feb 1 at 15:48
add comment

Here are some examples, hope they help. First an easy one.

Theorem. Let $n$ be an integer. If $n$ is even then $n^2$ is even.

Proof (outline). Let $n$ be even. Then $n=2k$ for some integer $k$, so $n^2=4k^2=2(2k^2)$, which is even.

Now try the converse by the same method.

Theorem. Let $n$ be an integer. If $n^2$ is even then $n$ is even.

Proof (attempted). Suppose that $n^2$ is even, say $n^2=2k$. Then $n=\sqrt{2k}$ and so...???? This seems hopeless, $\sqrt{2k}$ does not look like an integer at all, never mind proving that it's even!

Now try proving the converse by using its contrapositive.

Theorem. Let $n$ be an integer. If $n^2$ is even then $n$ is even.

Proof. We have to prove that if $n$ is odd, then $n^2$ is odd. So, let $n=2k+1$; then $n^2=4k^2+4k+1=2(2k^2+2k)+1$ which is odd. Done!

I think the point here is that for the attempt at a direct proof we start with $n^2=2k$. This implicitly gives us some information about $n$, but it's rather indirect and hard to get hold of. Using the contrapositive begins with $n=2k+1$, which gives us very clear and usable information about $n$.

Perhaps you could put a heuristic in the following form: "try both ways, just for a couple of steps, and see if either looks notably easier than the other".

share|improve this answer
2  
Well, you can use that $2$ is prime. Since $2\mid n^2,2\mid n$, so $n=2k$. =) –  Pedro Tamaroff Jan 15 at 1:19
3  
@Pedro, bad idea in my view because you are using a sophisticated result to prove something very simple. In any case the question was about techniques of proof, not about how to prove my particular example. –  David Jan 15 at 1:24
1  
I am just saying you're forcing an impossibility that is not there. –  Pedro Tamaroff Jan 15 at 1:27
    
In a way, "try both ways" is essentially using proof by contradiction. In fact, I often find myself using proof by contradiction (or at least, proving from both directions at once) when constructing a solution, and I only simplify my solution to direct or contrapositive later. That's because proof by contradiction, or "try both ways", essentially lets you use two hypotheses rather than just one, and in that sense it is superior. –  Goos Jan 27 at 20:25
add comment

Look at another example:

In the language of sets, it takes the form $$A\subset B\Longleftrightarrow B^c\subset A^c,$$ where $A^c$ is the complement of $A$.

share|improve this answer
    
Not exactly what I was looking for, but quite a interesting and cure example. Maybe if you add an intuition explanation, it would be more clear what you were trying to communicate. Regardless, I thought it was a cute example. :) –  Pinocchio Jan 24 at 22:04
    
When you are confronted to prove $A=B$ via $A\subset B$ and $A\supset B$, one or the two of these may need to be transformed by this technique. –  janmarqz Jan 24 at 22:44
add comment

One reason why doing a proof of $A\Rightarrow B$ by contradiction might be easier is the following. For a direct proof you can only use $A$ being true as your working ground, while a proof by contradiction gives you both $A$ and $\neg B$ to get started, so you can draw more conclusions.

In this case, we aren't even proving $\neg B \Rightarrow \neg A$ but $$A \wedge \neg B \Rightarrow \text{false}.$$

In the end, all of these are equivalent of course.

share|improve this answer
    
So contradiction is the same as contrapositive basically? Or what do you mean? –  Pinocchio Jan 25 at 4:13
    
Well logically all these implications are equivalent. But if you just prove the contraposition, you assume $\neg B$ and try to infer $\neg A$, while a proof by contradiction gives you $A\wedge\neg B$ as the assumption and you try to reach a contradiction from that. –  Christoph Jan 25 at 11:51
    
I think that is better to distinguish between, contraposition, based on the tautological schema : $\vdash (P \supset Q) \supset (\lnot Q \supset \lnot P)$ from the ex falso quodlibet, based on : $\vdash (\lnot P \supset (P \supset Q))$. –  Mauro ALLEGRANZA Jan 26 at 10:31
    
A proof by contradiction is based on the tautological schema : $\vdash (P \supset Q) \supset ( (P \supset \lnot Q) \supset \lnot P )$. –  Mauro ALLEGRANZA Jan 27 at 15:45
add comment

On what basis we think that, in general, a contrapositive argument is "more easy" to find that a direct one ?

In user86418's very useful list of examples, we have that :

(1) has "logical form" : $\forall x ( \lnot \phi(x) \rightarrow \lnot \psi(x) )$

So, when we contrapose it, we reduce it to : $\psi(x) \rightarrow \phi(x)$ that is the direct one.

(2) has the form : $\forall x (\forall n \phi (x,n) \rightarrow x = 0 )$; the contraposition give us : $ x \neq 0 \rightarrow \exists n \lnot \phi (x,n) $

(3) and (4) both are like : $\forall f ( \forall g \int_0^1 f(x) g(x)\, dx = 0 \rightarrow f \equiv 0 )$.

The contrapositive is "if $f$ is not indentically zero" $\rightarrow \exists g \int_0^1 f(x) g(x)\, dx \neq 0$.

My suggestion is that, the last three cases support the idea that is not, in general, more easy to prove $(\lnot Q \rightarrow \lnot P)$ instead of the direct $(P \rightarrow Q)$, but is more easy to prove :

$(\lnot \psi \rightarrow \exists \lnot \phi)$

instead of :

$(\forall \phi \rightarrow \psi)$.

My suggestion (to be verified) is that the interplay between conditional and quantifiers is the relevant issue here.

share|improve this answer
add comment

PS this Answer is just a rough draft, maybe I will add more later

In general there are 6 ways to proof conditional theorems.

I think that if you want to prove $ P \to Q $ you have the following 6 options (they are more details later)

  1. Direct conditional proof
  2. Direct contrapositive proof
  3. Conditional indirect proof
  4. Contrapositive indirect proof
  5. Indirect proof
  6. Indirect Contrapositive proof

Which way is easiest in your case depends on what the theorem you want to proof is, I think in general:

  • start with what the easiest statements are.
  • try to start with positive statements (negation just add an extra level of complexity)
  • if only one of the formulas "$ P \lor \lnot P $ " $ ( \forall x P(x) \lor \forall x \lnot P(x) ) $ or "$ Q \lor \lnot Q $" $ ( \forall x Q(x) \lor \forall x \lnot Q (x) )$ is provable, prefer the negation of that variable above the negation of the other variable.

  • Direct conditional proof is best (it is constructive)

  • Then then the methods 2, 3 and 4.

  • Only use one of the Indirect proofs if everything else fails (because they do add an extra layer of negation), if you act this way possibly you will never have to use the indirect method again, although many will argue that the methods 3 and 4 are just indirect proof methods in disguise.

PS 1 the names of the methods 2, 3, 4 and 6 are my own, there is no official terminology. (I just made them up while thinking about the question)

PS 2 off course there are many combinations possible of the 6 methods I mentioned, and it is even true that an "Conditional indirect proof" is a combination of an "Indirect proof" inside a "Direct proof" , but I organised them a bit so that all major methods (my opinion) are mentioned.

PS 3 all proofs methods that contain a "double negation elimination" (~~Elimination) are not constructive (you proof that $ P \to Q $ is a theorem, but have not found a method to transform a P into a Q), but in fact all except the direct proof method contain ~~Eliminations.

PS 4 Proof to get $ P \to Q $ from $ \lnot Q \to \lnot P $ :

This proof in itself contains a double negation elimination, so all proofs leading to $ \lnot Q \to \lnot P $ are not constructive.

1 | . . . ~Q -> ~P       proved before
2 | |____ P              Assumption
3 | | |__ ~Q             Assumption
4 | | | . ~P             1,3 -> Eliminations
5 | | | . contradiction  2,3 contradiction Introduction
. | | <----------------------- end subproof
6 | | . . ~~Q            3-5 ~ Introduction
7 | | . . Q              6   ~~Elimination
. | <------------------------- end subproof
8 | . . . P -> Q         2-7 ->Introduction

The different methods:

1) Direct Conditional proof

  • Assume P
  • some how get to Q
  • implication introduction

Formal proof

1 | |____ P          Assumption
: | | : : ?????????     some aplications of inference rules
: | | : : ?????????     some aplications of inference rules
k | | . . Q             inference rule
. | <-------------------- end subproof
m | . . . P -> Q     1-k -> Introduction

2) Direct Contrapositive proof

  • Assume ~Q
  • some how get to ~P
  • implication introduction

Formal proof

1 | |____ ~Q          Assumption
: | | : : ?????????      some aplications of inference rules
: | | : : ?????????      some aplications of inference rules
k | | . . ~P             inference rule
. | <--------------------- end subproof
m | . . . ~Q -> ~P    1-k ->  Introduction

3) Conditional Indirect proof

  • Assume P
  • Assume ~Q
  • some contradiction
  • Reductio ad absurdum
  • implication introduction

Formal proof

1 | |____ P              Assumption
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
a | | |__ ~Q             Second Assumption
: | | | : ?????????         some aplications of inference rules
: | | | : ?????????         some aplications of inference rules
i | | | . contradiction     contradiction Introduction
. | | <---------------------- end subproof
j | | . . ~~Q            a-i ~ Introduction
k | | . . Q              j   ~~Elimination
. | <------------------------ end subproof 
m | . . . P -> Q         1-k ->  Introduction

The results between line 1 and a maybe interesting of their own accoord, that is why this method is better than 5) Indirect proof

4) Contrapositive Indirect proof

This is a variation of conditional indirect proof method (no 3) the assumptions are reshuffeled. choose this method if from assuming ~Q more usefull things are provable than from assuming P.

  • Assume ~Q
  • Assume P
  • some contradiction
  • Reductio ad absurdum
  • implication introduction

Formal proof

1 | |____ ~Q            Assumption
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
a | | |__ P             Second Assumption
: | | | : ?????????        some aplications of inference rules
: | | | : ?????????        some aplications of inference rules
i | | | . contradiction    contradiction Introduction 
. | | <---------------------- end subproof
k | | . . ~P            a-i ~ Introduction
. | <------------------------ end subproof
m | . . . ~Q -> P       1-k ->  Introduction

The results between line 1 and a maybe interesting off their own accoord, that is why this method is better than 6) Indirect contrapositive proof

5) Indirect proof

  • Assume ~(P -> Q)
  • some contradiction
  • Reductio ad absurdum

Formal proof

1 | |____ ~(P -> Q)     Assumption
2 | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
j | | : : ?????????         some aplications of inference rules
k | | . . Contradiction     contradiction Introduction
. | <------------------------ end subproof
m | . . . ~~(P -> Q)    1-k ~ Introduction
n | . . . P -> Q        m   ~~Elimination

Often (allways?) this proof can be replaced by a Conditional Indirect Proof (3), it is advisable to use that method.

6) Indirect Contrapositive proof

  • Assume ~(~Q -> ~P)
  • some contradiction
  • Reductio ad absurdum

Formal proof

1 | |____ ~(~Q -> ~P)    Assumption
2 | | : : ?????????          some aplications of inference rules
: | | : : ?????????          some aplications of inference rules
: | | : : ?????????          some aplications of inference rules
j | | : : ?????????          some aplications of inference rules
k | | . . Contradiction      contradiction Introduction
. | <------------------------ end subproof 
m | . . . ~~(~Q -> ~P)   1-k ~ Introduction
n | . . . ~Q -> ~P       m   ~~Elimination

Often (allways?) this proof can be replaced by an Contrapositive Indirect proof (4), it is advisable to use that method.

PS this Answer is (still) just a rough draft, maybe I will add more later

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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