Results 1 to 7 of 7

Math Help - Contrapositive proof

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    3

    Contrapositive proof

    Hey New here on the forum. I have a small problem with some contrapositive proofs..

    I have to make a contrapositive proof that:
    ∀x, y ∈ R : x y < 1 ⇒ x < 1 ∨ y < 1

    I can logically see what I'm supposed to do.. and that the statement is correct.. but how do i prove it?? I know that the normal way is to prove that .. but I'm a little stuck from there.. anyone here who can help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    May 2009
    Posts
    471
    So you must prove that For all x,y\in\mathbb{R}, x\geq 1 and y\geq 1\Rightarrow x\cdot y\geq 1

    Idk how rigororous you need this proof to be...

    The general idea is Let x,b\in\mathbb{R} with x,y\geq 1

    So we can multiply both sides of x\geq 1 by y to get  xy\geq y

    But y\geq 1, so  xy\geq y\geq 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Kasperloeye View Post
    Hey New here on the forum. I have a small problem with some contrapositive proofs..
    I have to make a contrapositive proof that:
    ∀x, y ∈ R : x y < 1 ⇒ x < 1 ∨ y < 1
    \left( {x \geqslant 1 \wedge y \geqslant } \right)\; \Rightarrow \;\left( {x \cdot y \geqslant 1} \right)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2009
    Posts
    3

    Thanks ^^

    Quote Originally Posted by artvandalay11 View Post
    So you must prove that For all x,y\in\mathbb{R}, x\geq 1 and y\geq 1\Rightarrow x\cdot y\geq 1

    Idk how rigororous you need this proof to be...

    The general idea is Let x,b\in\mathbb{R} with x,y\geq 1

    So we can multiply both sides of x\geq 1 by y to get  xy\geq y

    But y\geq 1, so  xy\geq y\geq 1
    Thanks that really cleared things for me ^^ all hail the mighty proofmaster Hehe.. but then i have another question..

    Is it possible to make a contrapositive proof to prove that n <= n! ? and by that i mean for which nonnegative integers would the statement apply.
    Last edited by Kasperloeye; September 27th 2009 at 03:15 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    May 2009
    Posts
    471
    Quote Originally Posted by Kasperloeye View Post
    Thanks that really cleared things for me ^^ all hail the mighty proofmaster Hehe.. but then i have another question..

    Is it possible to make a contrapositive proof to prove that n <= n! ? and by that i mean for which nonnegative integers would the statement apply.
    Are you familiar with proof by induction?

    You wouldn't use a contrapositive proof, you would use proof by induction. You're base case would be n=4 since this fails for n=2 as n^2=2^2=4 and n!=2!=2, 3^2=9and  3!=3*2=6, 4^2=16 and 4!=4*3*2=24

    So above we showed n^2\leq n! for n=4

    Now we assume n^2\leq n! for some n and show it is true for (n+1)

    So consider (n+1)!-(n+1)^2=(n+1)n!-(n^2+2n+1) (we need to show this quantity is a natural number)

    =n\cdot n!+n!-n^2+2n+1

    By our assumption n^2\leq n! so n!-n^2\geq 0

    So n\cdot n!+n!-n^2+2n+1=n\cdot n! +k+2n+1 for some k\geq 0

    And now since n\in\mathbb{N}, n\cdot n!\in\mathbb{N} and 2n\in\mathbb{N} and 1\in\mathbb{N} so

    n\cdot n! +k+2n+1\in\mathbb{N} and so therefore (n+1)!-(n+1)^2 \in\mathbb{N} and so therefore (n+1)!\geq (n+1)^2

    so by induction we are done


    Now thats just an outline, you would need to "know/prove" that the sum of two natural numbers is a natural number and that the product of two natural numbers is a natural number, and something should be said like if k=0, nothing changes and if k>1 then k is a natural number

    You also need to be aware that m<n is by definition equivalent to (m-n)\in\mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2009
    Posts
    3
    So I'm not in a totally wrong direction when I did this:

    Quote Originally Posted by CompuChip View Post
    In your particular problem, you could consider a statement like "For all n >= 2, n2 <= (n!)".
    Hehe that's where it get's funny.. because n>= 2, n<=n! is like 2<=2! 4 <= 2 .. so it has to n /= 2


    So Basis should be n=4 since

    4<=4!
    16 <=24

    SO: For n=k, k<=k!

    but if we take it with n= k+1 it's (k+1) <=(k+1)!
    (k+1) <= (k+1)(k!)
    (k+1) <= k!
    but our hypothasis says k^2 <= k!, and because k+1 <= k^2 (for k>=4) then
    k+1 <= k^2 <= k!.

    right??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    May 2009
    Posts
    471
    yes that's also valid but for a rigorous proof you would need to state that k+1>0 and then need to prove that statement k+1<=k^2

    but yes your ideas and logic are sound
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with a proof - Contrapositive or Contradiction?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 24th 2010, 08:41 AM
  2. Proof by contrapositive
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2010, 03:45 PM
  3. contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 5th 2010, 01:07 PM
  4. Simple Contrapositive Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 19th 2009, 05:03 AM
  5. Proof by Contrapositive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2009, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum