Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Contradiction

  1. Jun 17, 2005 #1
    hello all

    well now i see that there are alot of ways of proving things, but there is one way in which I dont understand at first sight, and that is proof by contradiction, is there anyway general way of understanding it? I have worked on so many proofs but these are the only ones i most likely to have trouble with.
    I now normally assume that if i cant do the question then it must be a proof by contradiction, but see i dont understand how would such a proof be structured and how is it really proving something, the last proof i came across that i cant do is this one and I believe that it must be another proof by contradiction? so here we go

    let f:[a,b]->R be a continuous function. let M>0 and f(x)<M for all x an element of [a,b]. define g:[a,b]->R by
    then show that g is bounded
  2. jcsd
  3. Jun 17, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    I think the very first thing my mind does is try proof by contradiction.

    Anyways, suppose I tell you that each and ever time it rains, my feet hurt. Suppose I tell you today that my feet don't hurt. Then it couldn't possiby be raining, right, otherwise me feet would hurt. Let A be "it's raining" and B be "my feet hurt", then A implies B, i.e. A --> B. We also know that B is false, my feet don't hurt, so ~B. Then we validly infer that A is false, that is, ~A. So we have:

    A --> B

    This uses a rule called modus tollens. Anyways, the point if you want to prove some statement, you let A be it's negation. So you want to end up with ~A, which would be the negation of the negation of what you want to prove, which is just the affirmation of what you want to prove. What you want to do, then, is show that if you start with A, the negation of your desired conclusion, then that will lead you to some statement B which you know to be false, and can hence assert as your second premise, ~B.

    In this case, we want to prove that g is bounded, so let A stand for "g is unbounded." You want to choose B to be something that 1) you can prove to be false, and 2) you can prove to result from A. With these two facts, you get that a falsehood results from A, so A must itself be false, and thus the statement "g is unbounded" is false, meaning "g is bounded" is true, which is what you want. You could let B be "f is not continuous." You know that B is false, because it's given to you that f is in fact continuous. So how can you show that from A, B results? If g were unbounded, then we want to derive that f is discontinuous. Well if g were continuous, then by the extreme value theorem, g would have to have a min and max on [a,b], hence it would be bounded. So if we assume that g is unbounded, then (by a mini-proof-by-contradiction) we see that g would have to be discontinuous. We see that g is a strictly positive function, so if g is discontinuous, then 1/g would have to be discontinuous. If 1/g is discontinous, then the function defined by M - f(x) is discontinuous, which would lead to f being discontinuous, and this is the falsehood we wanted to derive.

    So we're exploiting the fact that a truth cannot lead to a falsehood, therefore if X leads to a falsehood, then X is itself false, and proving something to be true is the same as proving it's negation to be false, and that's what we're doing.
  4. Jun 17, 2005 #3
    thanxs AKG

    I now undertsand the structure of proving by contradiction but I dont undertsand what gives you the signal that you would need to use it? or when not to use it?

  5. Jun 18, 2005 #4
    i think it's usually used when nothing else will obviously work. like try proving that there are infinitely many primes directly (ie without contradiction). for contradiction it's kind of hard to say that it would be used for one type of theorem & not others. with mathematical induction it's usually pretty easy to see when it would be used, but not contradiction. i don't think so anyway.
  6. Jun 18, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    Like I said, for me, it's the first thing that pops into my head, even if it isn't the most efficient way to do the proof; it's not something I do consciously. For me, I try it first. I consider the negation of what I'm trying to prove, and see if something that's obviously false can easily be derived from it. If this doesn't work, then I try other approaches. For you, I suggest practice. Do a lot of problems and proofs until you get a better feel as to how to approach problems.
  7. Jun 18, 2005 #6


    User Avatar
    Science Advisor
    Homework Helper

    You can prove this directly. Let N be the maximum of f on [a,b], then M-N>0, since f attains it's maximum. So 0<g<=1/(M-N).

    Proof by contradiction should be in your standard toolkit of techniques. You'll get better at seeing where it's useful with practice. It can be helpful to try proving a statement in a few different ways to give insight not only on the problem, but to learn the strengths and weaknesses of the various techniques.

    This can also be done directly, e.g show the sequence of Fermat numbers [tex]2^{2^n}+1[/tex] are pairwise coprime or you could adapt Euclid's proof to generate an infinite sequence of primes.
  8. Jun 18, 2005 #7
    hello all

    well shmoe thats pretty nice, this is how i have structured it
    let N=sup{f(x):x is an element of [a,b]} and so f(x)<=N for x an element of [a,b]
    M-N>0 then g(x)>0 therefore
    0<g(x)=1/(M-f(x))<=1/(M-N) since this is finite then g(x) is bounded
    would this be correct?
    Now when we say a set, sequence or a function is bounded do we mean that it is bounded "above and below" or "above or below"?

    In terms of contradiction i have thought about it very carefully and concluded that if for example x<a, x=a, x>a, x has 3 options which could posibly be true or false, and so if there are more than 3 options its most likely cannot be done through proof by contradiction, and so a direct method would be your best approach would I be correct?
  9. Jun 18, 2005 #8


    User Avatar
    Science Advisor
    Homework Helper

    How are you concluding that M-N>0? You need to know there is a c on [a,b] where f(c)=N. A function does not in general have to attain it's sup on an interval. In this case it does since it's closed and bounded and f is continuous and the sup is just the max, but then you're already invoking the extreme value theorem so why bother mentioning sup at all?

    Bounded function usually means bounded above and below. The usual definition is |f|<B, for some finite B.

    Not necessarily. If something has multiple cases, some cases (or all) may require a proof by contradiction, others not.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook