Proof by contradiction query

[apple2357]

I am trying to do a proof by contradiction question and i am stuck at stage 1:



How do i contradict this? It strikes me there are two options:

1. Suppose 4^n -1 is NOT prime when n is odd
2. Suppose 4^n-1 is prime when n is NOT odd ( i.e. even)

How do i know which contradiction to start with in this particular case? Or can this be proved by contradiction in two different ways and it doesn't matter?

With the two classic proofs by contradiction ( root 2 is irrational, infinite number of primes) it feels clear to me what the contradiction statement is, but with the one above it doesn't?

I don't want anyone to do the proof for me just to offer advice about how to contradict the statement. Thanks

 

[yoscar04]

Assume n is even and try to rewrite the expression 4ⁿ-1. This assumption should get you to a contradiction that 4ⁿ-1 is prime.

 

[Deleted member 4993]

I am trying to do a proof by contradiction question and i am stuck at stage 1:

View attachment 20576

How do i contradict this? It strikes me there are two options:

1. Suppose 4^n -1 is NOT prime when n is odd
2. Suppose 4^n-1 is prime when n is NOT odd ( i.e. even)

How do i know which contradiction to start with in this particular case? Or can this be proved by contradiction in two different ways and it doesn't matter?

With the two classic proofs by contradiction ( root 2 is irrational, infinite number of primes) it feels clear to me what the contradiction statement is, but with the one above it doesn't?

I don't want anyone to do the proof for me just to offer advice about how to contradict the statement. Thanks

In my opinion - #2 is correct contradiction.

As I see these

IF (input) \(\displaystyle \ \to \ \ \)THEN(output) statements

The contradiction would be:

IF (input) \(\displaystyle \ \to \ \ \)THEN (NOT output) statements

In this case,

INPUT is (4ⁿ -1) is prime and

OUTPUT is (n is ODD)

In contradiction the INPUT remains the same but the OUTPUT is NOT. So in this case CONTRADICTION would be:

INPUT is (4ⁿ -1) is prime and

OUTPUT is (n is NOT ODD)

 

[apple2357]

Ok, thanks. The input and output is a good way to think about it. Thats helpful.

 

[HallsofIvy]

I am trying to do a proof by contradiction question and i am stuck at stage 1:

View attachment 20576

How do i contradict this? It strikes me there are two options:

1. Suppose 4^n -1 is NOT prime when n is odd

This is certainly NOT the correct "contradiction" and that is something you need to be very clear about!

The basic proposition is "if A then B". What you give above is "if not A then not B" which is not a all the same! Suppose I am in the practice of having a sandwich for lunch every day. Then the statement "If today is Tuesday then I will have a sandwich for lunch" is true. But the statement "If today is NOT Tuesday I will NOT have a sandwich for lunch" is false!

 

[apple2357]

This is certainly NOT the correct "contradiction" and that is something you need to be very clear about!

The basic proposition is "if A then B". What you give above is "if not A then not B" which is not a all the same! Suppose I am in the practice of having a sandwich for lunch every day. Then the statement "If today is Tuesday then I will have a sandwich for lunch" is true. But the statement "If today is NOT Tuesday I will NOT have a sandwich for lunch" is false!

I think my first contradiction above is ' if not A then B' ? my second one is ' if A then not B'.
Though i like the way you are thinking about it

 

[Dr.Peterson]

I think my first contradiction above is ' if not A then B' ? my second one is ' if A then not B'.
Though i like the way you are thinking about it

Do you see that "if not A, then B" does not contradict "if A, then B"? The latter has nothing at all to say about the case where A is not true, so it can easily be true when the former is true.

Proof by contradiction of "if A then B" means that we suppose that A is true but B is not, and show that is impossible.

 

[apple2357]

Do you see that "if not A, then B" does not contradict "if A, then B"? The latter has nothing at all to say about the case where A is not true, so it can easily be true when the former is true.

Proof by contradiction of "if A then B" means that we suppose that A is true but B is not, and show that is impossible.

Yes, thanks. I do see it. Was just struggling to explain it or was getting myself in a muddle over it!

 

[pka]

The fact that \((p\to q) \equiv \neg p \vee q\) means that the negation is:
\(p\wedge \neg q\) in this case, \( 4^n-1\) is prime and \(n\) is even(not odd).

 

[apple2357]

The fact that \((p\to q) \equiv \neg p \vee q\) means that the negation is:
\(p\wedge \neg q\) in this case, \( 4^n-1\) is prime and \(n\) is even(not odd).

Just trying to interpret the notation here..

So the first line means p implies q is equivalent to either not P or q is true ?
So the contradiction is p and not q are both true?

 

[pka]

Just trying to interpret the notation here..

Lets start over. If \(\bf 4^n-1\) is prime then \(\bf n\) is odd.
That is to be proved. Is that correct?
Since notation is a difficulty, we will use English words.
If P implies Q then the contrapositive is if not Q then not P. The two are equivalent.
This is equivalent: If n is even then \(4^n-1\) is not prime.
If \(n\) is even then \(n=2j\) thus \(4^n=4^{2j}=16^j\). We note that for any positive integer \(k,~16^k\) ends in the digit \(6\).
So\(16^j-1\) ends in the digit \(5\) that means the number cannot be prime. WHY?
So the crontrapositive, If \(4^n-1\) is prime then \(n\) odd, is true.

 

[yoscar04]

Lets start over. If \(\bf 4^n-1\) is prime then \(\bf n\) is odd.
That is to be proved. Is that correct?
Since notation is a difficulty, we will use English words.
If P implies Q then the contrapositive is if not Q then not P. The two are equivalent.
This is equivalent: If n is even then \(4^n-1\) is not prime.
If \(n\) is even then \(n=2j\) thus \(4^n=4^{2j}=16^j\). We note that for any positive integer \(k,~16^k\) ends in the digit \(6\).
So\(16^j-1\) ends in the digit \(5\) that means the number cannot be prime. WHY?
So the crontrapositive, If \(4^n-1\) is prime then \(n\) odd, is true.

Or it can be factorized as 4ⁿ-1=2²ⁿ-1=(2ⁿ+1)(2ⁿ-1) which clearly is not prime.

 

[Deleted member 4993]

Or it can be factorized as 4ⁿ-1=2²ⁿ-1=(2ⁿ+1)(2ⁿ-1) which clearly is not prime.

But that is true for every n when n\(\displaystyle \ne 1\)

But the truth of the INPUT is not being questioned here.

 

[yoscar04]

But that is true for every n when n\(\displaystyle \ne 1\)

But the truth of the INPUT is not being questioned here.

My mistake.

 

[JeffM]

It is probably my failure, but I thought pka's second answer missed the point.

The second answer goes: the contrapositive of a conditional is logically equivalent to the conditional statement itself. (Of course, the contrapositive of a conditional statement is itself a conditional statement.) Now assume that the negation of the contrapositive of the conditional statement is true. We deduce a contradiction. Therefore the negation of the contrapositive of the conditional statement is false. Therefore the the contrapositive of the conditional statement is true and equivalent to the conditional statement. Therefore, the conditional statement is true.

The logic is fine. But it requires understanding how to negate a conditional statement, which is the general question asked by the OP. Pka's second answer assumes that point rather than explicating it. Pka's first answer addresses the question asked. We should be asking apple what he found confusing in pka's first answer. (I don't know whether apple even knows about truth tables.)

 

[Dr.Peterson]

As I see it, the question is about proof by contradiction, not about contrapositives, which are closely related but not identical. Not knowing whether apple knows anything of symbolic logic, or of contrapositives, the most appropriate thing to do (initially) is to talk only about what proof by contradiction means, not how it relates to anything else.

 

[JeffM]

As I see it, the question is about proof by contradiction, not about contrapositives, which are closely related but not identical. Not knowing whether apple knows anything of symbolic logic, or of contrapositives, the most appropriate thing to do (initially) is to talk only about what proof by contradiction means, not how it relates to anything else.

I do not disagree. But I think apple gets proof by contradiction in general. What he is not sure about is what is the contrary proposition when the proposition to be proved is a conditional statement and why. We have, I believe, given an answer to what, but I am not sure we have provided a rationale.

I am concerned that questions about why be given answers about why, but I am not going to try to compete with pka or you when it comes to explaining logic.

 

[pka]

The fact that \((p\to q) \equiv \neg p \vee q\) means that the negation is:
\(p\wedge \neg q\) in this case, \( 4^n-1\) is prime and \(n\) is even(not odd).

Just trying to interpret the notation here..
So the first line means p implies q is equivalent to either not P or q is true ? So the contradiction is p and not q are both true?

I do not disagree. But I think apple gets proof by contradiction in general. What he is not sure about is what is the contrary proposition when the proposition to be proved is a conditional statement and why. We have, I believe, given an answer to what, but I am not sure we have provided a rationale. I am concerned that questions about why be given answers about why, but I am not going to try to compete with pka or you when it comes to explaining logic.

Come on guys, give me a break. If you read replies #9 & #10 and tell me that apple really understands argument by contradiction then O.K.
The negation of "if P then Q" is "P and not Q". Assume that for some positive integer \(j,~ 4^j-1\) is prime and \(j\) is even. (I will go to the problems with the problems existential instantiation here) Suffice it to say that the argument that I gave in reply #11 leads to a contradiction or a proof by contradiction.

 

[JeffM]

Come on guys, give me a break. If you read replies #9 & #10 and tell me that apple really understands argument by contradiction then O.K.
The negation of "if P then Q" is "P and not Q". Assume that for some positive integer \(j,~ 4^j-1\) is prime and \(j\) is even. (I will go to the problems with the problems existential instantiation here) Suffice it to say that the argument that I gave in reply #11 leads to a contradiction or a proof by contradiction.

I have no problem with the proof in # 11. It is indeed a proof by contradiction. I believe I said that already, but if i was not clear previously, I apologize for being obscure.

My concern is that the point of # 9 was dropped. That answer justifies SK's answer from first principles. I see no reason to believe that the OP does not understand the concept of a proof by contradict. The original question was about the negation of conditionals. Answer # 9 provides the general answer to that question. When the OP said he did not understand the notation, there is probably a clear way to explain it without using the notation of propositional calculus.

 

[pka]

. When the OP said he did not understand the notation, there is probably a clear way to explain it without using the notation of propositional calculus.

Are you telling that my reply #11 is not plain English? If so, I need to quit.