Proving an or statement in mathematical proofs

[altcmdesc]

Proving an "or" statement

What is the general procedure when proving a statement like "A implies B or C"? Is it more common to assume A and then split into cases (i.e. case 1: A implies B, case 2: A implies C, therefore A implies B or C)? Or is it more common to assume A and that one of B or C is false and then prove that A implies C or B (depending on which is assumed false)?

 

[rasmhop]

Is it more common to assume A and then split into cases (i.e. case 1: A implies B, case 2: A implies C, therefore A implies B or C)? Or is it more common to assume A and that one of B or C is false and then prove that A implies C or B (depending on which is assumed false)?

Both are common. In my experience the most common is your second approach, i.e. assume A is true and B is false, and then conclude that C is true (interchange B and C if you want to). It's not uncommon either to do contradiction and assume A is true, B is false, C is false and then reach a contradiction, or possibly contraposition where you assume B and C are false and then conclude A is false. Really the approach to use depends on the problem and there is no best general way.

 

[Dragonfall]

If you did it the first way, you would have proven A implies B *and* C.

 

[rasmhop]

If you did it the first way, you would have proven A implies B *and* C.

I took his statement to mean:
Assume A
Show that either P or Q is true.
Case 1: Assume P is true. ... then B is true.
Case 2: Assume Q is true. ... then C is true.

which is valid.

 

[Dragonfall]

Where did P and Q come from?

 

[rasmhop]

Where did P and Q come from?

I introduced them to make the point more easily. When he wrote:
Case 1: A implies B
Case 2: A implies C
I'm reading it as a way of writing that in one case which I call P we prove that A implies B (we don't assume it), and in another case which I called Q we prove that A implies C. That is the only way I see for the argument to make sense.

 

[Dragonfall]

No, you still get A -> (B /\ C) with that approach.

 

[rasmhop]

No, you still get A -> (B /\ C) with that approach.

You must misunderstand me because I'm pretty sure my argument form is correct (whether altcmdesc meant it or not). For instance let:
A be "n is an integer square m^2".
B be "n \equiv 0 \pmod 3".
C be "n \equiv 1 \pmod 3"
Then:
Assume n=m^2 for some integer m.
Case 1 (m \equiv 1 \pmod 3 or m \equiv 2 \pmod 3): Then n=m^2 \equiv 1 \pmod 3 which proves C in this case.
Case 2 (m \equiv 0 \pmod 3): Then n=m^2 \equiv 0 \pmod 3 which proves B in this case.

This doesn't prove that every square is congruent to 0 AND 1 modulo 3, simply to one of them.

Here the conditions in parentheses are what I called P and Q and I think altcmdesc simply omitted them for simplicity. I think we're just understanding altcmdesc in different ways, so I guess we have to wait for him to clear up exactly what he meant.