# Proof by contradiction with implication

• Sep 29th 2012, 01:14 PM
narjsingh
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
• Sep 29th 2012, 02:27 PM
emakarov
Re: Proof by contradiction with implication
Quote:

Originally Posted by narjsingh
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).
• Sep 29th 2012, 05:11 PM
Prove It
Re: Proof by contradiction with implication
Quote:

Originally Posted by emakarov
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.
• Sep 30th 2012, 04:05 AM
narjsingh
Re: Proof by contradiction with implication
Quote:

Originally Posted by Prove It
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?
• Sep 30th 2012, 04:47 AM
emakarov
Re: Proof by contradiction with implication
Quote:

Originally Posted by Prove It
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
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.