Proof By Contradiction/Case Analysis

[doubleaxel195]

This may be a really stupid question. So say you're doing a proof by contradiction. So you assume the hypothesis and conclusion are true. There are multiple variables involved and I want to consider the case when one only one variable is negative.

1. Are you allowed to do case by case analysis when doing proof by contradiction? In other words, does doing this make sense?

2. If you can use case analysis, must you find a contradiction in each case or is a contradiction in one case good enough?

Thanks! I'm very appreciative.

 

[alexfloo]

Yes, that is absolutely okay. You're trying to prove something, and your method is to assume the negation and try to prove a contradiction. This "subproof" is just like any other proof, and any proof methods that work elsewhere work here.

 

[doubleaxel195]

Proof by Contradiction/Case Analysis Question

If you use proof by contradiction but have multiple cases to consider, do you need to find a contradiction in each case? Or if one case has a contradiction is that good enough and you can disregard the other cases?

Thanks! I'm very appreciative.

 

[awkward]

If your statement is something like

"If <proposiiton> then <case 1> OR <case 2>."

then in order to show that <proposition> is impossible, you must show that both <case 1> and <case 2> lead to contradictions.

 

[doubleaxel195]

Okay, thank you. That is what I thought. *sigh* now I have to go back to square one. May be a stupid question, but logically, why is this so?

 

[Charles49]

If the statement was

"If <proposiiton> then <case 1> AND <case 2>."

then by refuting one case you are done. Since it is an or, you have to show that both cases are impossible.

Use the truth table:

http://en.wikipedia.org/wiki/Truth_table#Logical_NOR

 

[doubleaxel195]

Hm. I reread the replies and now I'm starting to wonder if I properly phrased my question.

I want to use proof by contradiction. So I assume the conclusion is false. There are multiple real variables involved. So they can be any combination of positive, negative, or zero. If I consider just one case when one of them is negative and find a contradiction, does this work or no?

 

[muzak]

What is the thing you're taking to be false? If the statement you're taking to be false is something made up of bunch of 'or' statements, then you have to show that one negation of your conclusion leads to a contradiction, I guess what I mean to say symbolically is (using ~ for not):

If this is the thing you're taking to be false: P $\cup$ Q $\cup$ R, then symbolically ~(P $\cup$ Q $\cup$ R) = ~P $\cap$ ~Q $\cap$ ~R. I think you have to show that you reach a contradiction for just one of them.

But if the thing you're taking to be false is: P $\cap$ Q $\cap$ R, then making it false you get

~(P $\cap$ Q $\cap$ R) = ~P$\cup$~Q$\cup$~R. I think in this case, you have to show that you get a contradiction for all three cases, i.e. for ~P, ~Q, ~R.

 

[doubleaxel195]

Well the thing I'm taking to be false does not involve and or or statements.

It's just that one quantity is less than or equal to another. So the negation would be the first quantity is greater than the other.

What I want to say is that the right side is always positive but there is a possibility that the left side be negative. Am I going completely crazy and making illogical conclusions?

 

[Dick]

Well the thing I'm taking to be false does not involve and or or statements.

It's just that one quantity is less than or equal to another. So the negation would be the first quantity is greater than the other.

What I want to say is that the right side is always positive but there is a possibility that the left side be negative. Am I going completely crazy and making illogical conclusions?

If you aren't going to spell out what you are trying to prove and how you are trying to do it it's going to be really hard to say how crazy you are :).

 

[doubleaxel195]

Haha, I just wanted guidance on proof writing. I really don't want to post the problem, otherwise I feel like I'm cheating. And I know it will be hard to help without seeing the problem, so I guess I'll just try to do it by direct proof. Thanks for all the replies though! Here's to spending hours on a problem only to find the answer is ridiculously simple...

 

[Dick]

Haha, I just wanted guidance on proof writing. I really don't want to post the problem, otherwise I feel like I'm cheating. And I know it will be hard to help without seeing the problem, so I guess I'll just try to do it by direct proof. Thanks for all the replies though! Here's to spending hours on a problem only to find the answer is ridiculously simple...

Your choice. I definitely don't think it would be cheating to show a proof and ask for comments, though.