Results 1 to 5 of 5

Math Help - Proof by contradiction with implication

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    manchester
    Posts
    10

    Proof by contradiction with implication

    basically the question is

    Prove by contradiction that for any integer n,


    n^2 is not divisible by 7 => n is not divisible by 7
    the first part is p and the second q

    I've got a mind block i keep going at he question from each angle and its exhausted me. I know there must be an assumption. The assumption I used was that n^2 is divisible by 7.
    Then i thought i would make n^2=7k where k is an integer

    => n= (7k)^1/2 (square root of 7k)

    => n is not divisible by seven

    => P is true but Q is false therefore statement is false

    i think this 100% wrong please can some one help also im a bsc economics student
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof by contradiction with implication

    Quote Originally Posted by narjsingh View Post
    I know there must be an assumption. The assumption I used was that n^2 is divisible by 7.
    Why do you think that the assumption is that n^2 is divisible by 7? And this is the assumption of what exactly?

    Suppose you need to prove that for all n, P(n) implies Q(n). Here is a direct proof: fix an arbitrary n, assume P(n), use it to conclude Q(n). Here is a proof by contradiction: fix an arbitrary n, assume ~Q(n) (i.e., the negation of Q(n)), use it to conclude ~P(n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,969
    Thanks
    1011

    Re: Proof by contradiction with implication

    Quote Originally Posted by emakarov View Post
    Why do you think that the assumption is that n^2 is divisible by 7? And this is the assumption of what exactly?

    Suppose you need to prove that for all n, P(n) implies Q(n). Here is a direct proof: fix an arbitrary n, assume P(n), use it to conclude Q(n). Here is a proof by contradiction: fix an arbitrary n, assume ~Q(n) (i.e., the negation of Q(n)), use it to conclude ~P(n).
    No, that's not a proof by contradiction. That's a contrapositive proof.

    A proof by contradiction (reducio ad absurdium) is where you make a statement and show that it is false, thereby showing at the same time that the opposite of your original statement must be true.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2012
    From
    manchester
    Posts
    10

    Re: Proof by contradiction with implication

    Quote Originally Posted by Prove It View Post
    No, that's not a proof by contradiction. That's a contrapositive proof.

    A proof by contradiction (reducio ad absurdium) is where you make a statement and show that it is false, thereby showing at the same time that the opposite of your original statement must be true.
    any chance of showing me how that is done please?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof by contradiction with implication

    Quote Originally Posted by Prove It View Post
    A proof by contradiction (reducio ad absurdium) is where you make a statement and show that it is false, thereby showing at the same time that the opposite of your original statement must be true.
    You are right. Proofs by contradiction and contrapositive are often combined in a proof of an implication A -> B. First, as usual, we assume A. Second, towards contradiction, we assume ~B, i.e., that B is false. Then we prove that this assumption ~B leads to ~A, i.e., we prove the contrapositive ~B -> ~A of A -> B. This conclusion ~A together with the assumption A constitutes a contradiction, so, finishing the proof by contradiction, we conclude B. Altogether, we assumed A and concluded B, i.e., we proved A -> B.

    To repeat briefly: Assume A, assume ~B towards contradiction, use it to prove ~A, which makes a contradiction with A; therefore, B. In my experience, this is often called a proof by contradiction when applied to an implication.

    Quote Originally Posted by narjsingh View Post
    any chance of showing me how that is done please?
    Make sure you understand intuitively why the outline above is indeed a proof of A -> B. Identify what A and B are in your concrete problem, write the brief outline above replacing A and B with the concrete statements they stand for. Read the resulting proof outline and again make sure that you understand intuitively why it would work if you fill in the missing sub-proofs. Fill the missing steps. Explain in detail any problems that you may have.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 8th 2010, 06:45 AM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  3. Proof - Implication signs
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 12th 2009, 10:51 AM
  4. meaning of double implication in a proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 4th 2008, 10:48 AM
  5. Replies: 5
    Last Post: August 19th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum