Thread: 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

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).

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.

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?

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.

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.