What is the Concept of Proof by Contradiction in Mathematics?

[steven187]

hello all

well now i see that there are a lot of ways of proving things, but there is one way in which I don't 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 can't do the question then it must be a proof by contradiction, but see i don't understand how would such a proof be structured and how is it really proving something, the last proof i came across that i can't 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
$$g(x)=\frac{1}{M-f(x)}$$
then show that g is bounded

 

[AKG]

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
~B
-------
~A

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.

 

[steven187]

thanxs AKG

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

steven

 

[fourier jr]

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.

 

[AKG]

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.

 

[shmoe]

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
$$g(x)=\frac{1}{M-f(x)}$$
then show that g is bounded

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.

like try proving that there are infinitely many primes directly (ie without contradiction).

This can also be done directly, e.g show the sequence of Fermat numbers $$2^{2^n}+1$$ are pairwise coprime or you could adapt Euclid's proof to generate an infinite sequence of primes.

 

[steven187]

hello all

well shmoe that's 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?

 

[shmoe]

well shmoe that's 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?

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?

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"?

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

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?

Not necessarily. If something has multiple cases, some cases (or all) may require a proof by contradiction, others not.