# Valid example of proof by contradiction?

• May 9th 2011, 11:30 PM
Ontolog
Valid example of proof by contradiction?
I'm studying "How To Prove It" (Velleman) and I'm on exercise 3.7. The solution I gave is a "proof by contradiction" and I would like to verify that the method of proof and result are valid.

$\displaystyle \\\mbox{Suppose that }a\mbox{ is a real number. Prove that if }a^3 > a\mbox{ then }a^5 > a\mbox{.}\\\\\mbox{Suppose }a^5 \leq a\mbox{. Then }a^5 - a \leq 0\mbox{ and }a^5 - a = (a^3 - a)(a^2 + 1) \leq 0\mbox{.}\\\mbox{However, we know that }a^3 > a\mbox{ so the first factor }a^3 - a > 0\mbox{.}\\\mbox{The second factor is also positive since }x \ne 0 \rightarrow x^2 > 0\mbox{ for all }x \in \mathbb{R}\mbox{,}\\\mbox{which implies that }a^2 + 1 > 0\mbox{ as well. }\\\mbox{This leads to a contradiction however, therefore }a^3 > a \rightarrow a^5 > a\mbox{.}$

Is this a well formed proof? How explicit do I have to be? For example, is it OK for me to leave out the fact that for a, b in R, a > 0 and b > 0 implies that ab > 0? If so, then what else could I have left out?

Maybe these things will be more clear once working on more complicated proofs?
• May 9th 2011, 11:58 PM
FernandoRevilla
Quote:

Originally Posted by Ontolog
Is this a well formed proof?

Yes, it is.

Quote:

How explicit do I have to be? For example, is it OK for me to leave out the fact that for a, b in R, a > 0 and b > 0 implies that ab > 0? If so, then what else could I have left out?

Depends on the context. For example I suppose you are allowed to use all the properties appearing in your proof.
• May 10th 2011, 01:01 AM
Ontolog
Quote:

Originally Posted by FernandoRevilla
Depends on the context. For example I suppose you are allowed to use all the properties appearing in your proof.

Thanks for the feedback! Could you give me an example of a situation where you can't use certain properties (besides the obvious ones of, you are proving that particular property or using a property that is an extension of the one you are proving)?
• May 10th 2011, 01:10 AM
emakarov
I agree that your proof is fine. To be extremely picky, I would only make some stylistic changes.

Quote:

Suppose that a is a real number. Prove that if a^3 > a then a^5 > a.

Suppose that a^3 > a, but a^5 <= a. Then a^5 - a <= 0 and a^5 - a = (a^3 - a)(a^2 + 1) <= 0. However, we know that a^3 > a, so the first factor a^3 - a > 0. The second factor is also positive since x^2 >= 0 for all x in R, which implies that a^2 + 1 > 0 as well. This leads to a contradiction with the fact that (a^3 - a)(a^2 + 1) <= 0, however; therefore, a^3 > a -> a^5 > a.
In particular, one feature of a good proof is uniform complexity, when the amount of reasoning required to go from one statement to the next is about the same throughout the proof. I hate it when one particular step in some textbook proofs is much more complicated than others; it has to be broken into several steps.

Here the "proof speed" is supposed to be pretty low, i.e., even rather simple steps need to be explained. I found the following sentence:
Quote:

The second factor is also positive since x != 0 -> x^2 > 0 for all x in R,which implies that a^2 + 1 > 0 as well.
to be more complicated than others. First, it was not stated that a != 0 (though it is obvious from the fact that a^3 - a > 0) and, second, a^2 + 1 > 0 even when a = 0.
• May 10th 2011, 01:24 AM
Ontolog
Thanks for the excellent feedback! It gives me a much better idea of what's involved in a proof. My original conception was that a proof must follow some very specific steps, otherwise it isn't a valid proof (maybe this idea comes from my background in programming). However, it seems that as long as there are no errors in logic, simply transforming the premise into the conclusion with a well-worded explanation is fine.
• May 10th 2011, 01:54 AM
Deveno
an alternate, and much (in my opinion) more direct contradiction would be:

....then (a^3 - a)(a^2 + 1) ≤ 0.

since a^2 + 1 > 0 for all a, we have that a^3 - a ≤ 0, that is, a^3 ≤ a, contradicting that a^3 > a.

(assuming, of course, that one has proved already that a^2 ≥ 0, so that a^2 + 1 > a^2 ≥ 0).
• May 10th 2011, 02:26 AM
emakarov
Quote:

My original conception was that a proof must follow some very specific steps, otherwise it isn't a valid proof (maybe this idea comes from my background in programming).
Ultimately, this is correct. In fact, you'll be happy to know that proofs are programs. However, when proofs are intended to be read by people, some steps are omitted and proofs are presented as you say.