How Many Cases Do I Need to Consider for Proof by Contradiction?

In summary: I think I got it now. No, you don't need to show that both cases aren't possible true, just that P implies (Q and Z). Thanks! I think I got it now. No, you don't need to show that both cases aren't possible true, just that P implies (Q and Z).
  • #1
cris(c)
26
0

Homework Statement



Suppose I want to prove the following statement by contradiction:
[itex] P \longrightarrow (Q \land Z) [/itex]

Homework Equations



If [itex] (Q \land Z) [/itex] is false, then either: (i) Q is false and Z is true; (ii) Q is true and Z is false; (iii) Q and Z are false.

The Attempt at a Solution



Do I need to consider all possible cases in which [itex] (Q \land Z) [/itex] is false and arrive to a contradiction or it suffices to show a contradiction in only one possible of the three possible cases?

Thanks for your help!
 
Physics news on Phys.org
  • #2
If you want to prove the first one is true all you have to do is prove it by only one of the cases, because QandZ is false only if one of those cases occurs, but depending on what your teacher wants you can do all three cases.
 
  • #3
mtayab1994 said:
If you want to prove the first one is true all you have to do is prove it by only one of the cases, because QandZ is false only if one of those cases occurs, but depending on what your teacher wants you can do all three cases.

This means that the proof is complete if I assume (say) case (i) to be true and arrive to a contradiction?
 
  • #4
cris(c) said:
This means that the proof is complete if I assume (say) case (i) to be true and arrive to a contradiction?

Yes because Q and Z could only be true if Q and Z are both true or if Q and Z are both false, therefore all you have to do is prove it using one case. Hope this helps you.
 
  • #5
mtayab1994 said:
Yes because Q and Z could only be true if Q and Z are both true or if Q and Z are both false, therefore all you have to do is prove it using one case. Hope this helps you.

Think I got it. Thanks a lot!
 
  • #6
No Problem.
 
  • #7
mtayab1994 said:
No Problem.

Hi again,

It appears that your answer is not completely correct or I am truly messed up. Negating (Q and Z) means that either (Q and not Z) or (Z and not Q). Hence, to actually show that P implies (Q and Z), don't we need to show that both of the above cases aren't possible true? I mean, showing that P implies (Z and not Q) does not exclude the possibility that (Q and not Z) still is true, does it?

Thanks!
 

FAQ: How Many Cases Do I Need to Consider for Proof by Contradiction?

1. What is proof by contradiction?

Proof by contradiction is a method of proving a statement by assuming its negation and then showing that it leads to a contradiction or an absurdity. This proves that the original statement must be true.

2. When is proof by contradiction used?

Proof by contradiction is often used in mathematics and logic to prove statements that are difficult to prove directly. It is also used in other fields, such as computer science, to prove the correctness of algorithms.

3. How does proof by contradiction differ from direct proof?

In direct proof, we start with the given assumptions and use logical steps to reach the conclusion. In proof by contradiction, we start with the opposite assumption and show that it leads to a contradiction, thereby proving the original statement.

4. What are the steps involved in a proof by contradiction?

The steps involved in a proof by contradiction are as follows:
1. Assume the opposite of what we want to prove.
2. Use logical deductions to show that the assumption leads to a contradiction.
3. Conclude that the original statement must be true.

5. Can all statements be proven by contradiction?

No, not all statements can be proven by contradiction. This method only works for statements that have a logical contradiction when their negation is assumed. In other cases, direct proof or other methods may be needed.

Similar threads

Proof by Contradiction: Converse of A(n) Holds for All n ∈ Z
Replies
5
Views
1K
Is my proof by contradiction valid?
Replies
10
Views
2K
Why Must n Equal 4q or 4q+2 If It Isn't 4q+1 or 4q+3?
Replies
10
Views
1K
Proof by contradiction for simple inequality
Replies
6
Views
2K
Prove Rational Numbers Have Midpoint: x,y ∈ Q
Replies
5
Views
2K
Is the argument sound? Yes, the argument is sound.
Replies
4
Views
1K
Indirect Proof Proof verification: sequence a_n=(−1)^n does not converge
Replies
1
Views
2K
Prove Fibonacci identity using mathematical induction
Replies
4
Views
597
Proving Statements: Square Roots, Even Numbers, and Multiples of 6
Replies
9
Views
3K
Prove by method of contradiction
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top