Proof by Contradiction

In summary, the conversation discusses the use of proof by contradiction in mathematical proofs. It is a technique where one starts by assuming the negation of the statement they want to prove and then deriving a contradiction. This signals that the original statement must be true. It is often used as a last resort when other methods do not work. The conversation also mentions the importance of practice in developing a better understanding of when and how to use proof by contradiction. The example of proving that there are infinitely many primes is given, with the suggestion that it can also be proven directly without using proof by contradiction.
  • #1
steven187
176
0
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
[tex]g(x)=\frac{1}{M-f(x)}[/tex]
then show that g is bounded
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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
 
  • #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.
 
  • #5
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.
 
  • #6
steven187 said:
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
[tex]g(x)=\frac{1}{M-f(x)}[/tex]
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.

fourier jr said:
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 [tex]2^{2^n}+1[/tex] are pairwise coprime or you could adapt Euclid's proof to generate an infinite sequence of primes.
 
  • #7
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?
 
  • #8
steven187 said:
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?

steven187 said:
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.

steven187 said:
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.
 

What is "Proof by Contradiction"?

"Proof by Contradiction" is a method of mathematical or logical proof that involves assuming the opposite of what is being proven in order to reach a contradiction, which then proves the original statement to be true.

How does "Proof by Contradiction" work?

In "Proof by Contradiction", you start by assuming the opposite of what you are trying to prove. Then, using logical reasoning and previously established truths, you arrive at a contradiction. This contradiction proves that the original statement must be true, as the opposite cannot be true at the same time.

What is the difference between "Proof by Contradiction" and other proof methods?

"Proof by Contradiction" differs from other proof methods in that it relies on showing that the opposite of the statement being proven leads to a contradiction, rather than directly proving the statement to be true. It is often used when direct proof methods are difficult or impossible to apply.

When should you use "Proof by Contradiction"?

"Proof by Contradiction" is most commonly used when trying to prove a statement that is difficult to prove directly. It can also be used to prove statements that involve negations or to show that something does not exist.

What are the limitations of "Proof by Contradiction"?

One limitation of "Proof by Contradiction" is that it may not always be applicable or useful. It also requires careful logical reasoning and may be difficult for some people to understand. Additionally, some philosophers argue that it is not a valid form of proof, as it relies on the assumption that a contradiction is impossible.

Similar threads

Replies
3
Views
1K
Replies
5
Views
269
  • Calculus
Replies
2
Views
1K
Replies
5
Views
1K
Replies
1
Views
1K
Replies
2
Views
167
  • Calculus
Replies
5
Views
2K
  • Calculus
Replies
6
Views
1K
Back
Top