Results 1 to 7 of 7

Math Help - Valid example of proof by contradiction?

  1. #1
    Newbie
    Joined
    May 2011
    From
    Los Angeles
    Posts
    23

    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.

    \\\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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Quote Originally Posted by Ontolog View Post
    Is this a well formed proof?

    Yes, it is.


    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    From
    Los Angeles
    Posts
    23
    Quote Originally Posted by FernandoRevilla View Post
    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)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I agree that your proof is fine. To be extremely picky, I would only make some stylistic changes.

    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:
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    From
    Los Angeles
    Posts
    23
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. IS this proof valid or invalid?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: August 9th 2011, 02:48 PM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  3. Is this a Valid proof? [Vectors]
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: November 8th 2009, 12:14 PM
  4. Inductive Proof, is this way valid?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 9th 2009, 05:46 PM
  5. Is proof valid?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 9th 2006, 05:26 AM

/mathhelpforum @mathhelpforum