2

I am just reading through Mathematics for Computer Science (https://courses.csail.mit.edu/6.042/spring17/mcs.pdf) and at chapter 1.7 Proof by Cases there is a following theorem as an example:

Theorem. Every collection of 6 people includes a club of 3 people or a group of 3 strangers.

The author(s) state the following:

Proof. The proof is by case analysis
Let x denote one of the six people. There are two cases:
1. Among 5 other people besides x, at least 3 have met x.
2. Among the 5 other people, at least 3 have not met x

The chapter goes on splitting the cases in the 4 subcases (2 for each case). I just can not see how proving these 2 cases proves the theorem. How did stating that 3 other people have met or not met the fourth (making it a group of 4 people proves the original theorem).

What am I missing here?

Edit:

I think I finally understood the example. My problem was that I was constantly thinking that the two cases are like two sub-theorem that have to be proved in order to prove the 'main' theorem but this is actually not the case. The real work is done by the 4 sub-cases. These subcases prove the main theorem but in order for them to function they need to be 'supported' by the two cases.

Special thanks to following people for help:

  • @Bram28 - Your comment that I should not focus on the two cases and focus on the subcases was on the point. I was just blind and could not understand.
  • @Patrick Stevens - Thanks for your nicely written example. It is not quite the same as the theorem proof in the original question but it is a good example nevertheless.
  • @Did - Thank you for taking the time to review and edit my question so that it is better.
Dalibor Čarapić
  • 193
  • 2
    I find it offensive that you would call yourself stupid at the word of others. Offended for your own sake of course. – Simply Beautiful Art Mar 12 '17 at 13:33
  • Sorry but I am not a native English speaker. Why are you offended if I feel stupid? – Dalibor Čarapić Mar 12 '17 at 13:38
  • First, you are not stupid for not immediately grasping this. Second, it's important to remember that the two cases get further subdivided into other cases ... So you really have more than two cases. – Bram28 Mar 12 '17 at 13:39
  • 1
    Feeling stupid is not the same as being stupid. – amWhy Mar 12 '17 at 13:40
  • But it is a hierarchy of cases, the further sub-cases prove the 2 'top'-cases. This part I could understand. I just do not see how proving the two 'top'-cases prove the theorem. Sorry if my title is a bit provoking ... my frustration is getting better of me :) – Dalibor Čarapić Mar 12 '17 at 13:41
  • Those two cases cover all possibilities: suppose you paint each person who knows $x$ Blue, and each person who doesn't know $x$ Red. Then the number of blue people plus the number of red people is $5$ so one of them must be at least three. – lulu Mar 12 '17 at 13:42
  • @amWhy I agree with you. Its just that I read such things I just feel that way. The book is pretty straightforward up to that part and here I went 'what'? – Dalibor Čarapić Mar 12 '17 at 13:42
  • Got rid of offtopic "stupidity" mentions. – Did Mar 12 '17 at 13:43
  • Thank you all for replying but the 'stupidity' mention was kind of a big part of my question. I was never very good in math in school (I am 40 now) and while I would like to improve myself in this area (hence trying to go through that book) I find that I have problems 'overcoming' logical reasoning scenarios such as the one above. Am I below average and most people grasp such questions easily or is it normal? – Dalibor Čarapić Mar 12 '17 at 13:49
  • @lulu As far as I can see 3 people knowing or not knowing x for me does not imply that they know each other ... heh again I might not be understanding you completely. – Dalibor Čarapić Mar 12 '17 at 13:51
  • If the question is about "stupidity" then it should be closed (and you can revert my edit, before the question is closed). If it is about the mathematics in it then it fits the site. – Did Mar 12 '17 at 13:54
  • I think you are missing the point. All the statement you presented claims is that it suffices to address those two cases. Nothing in what you presented even attempts to address either of those two cases. At this stage, all that the authors are saying is that "if we can prove the claim in each of these two cases then we will be done". – lulu Mar 12 '17 at 13:56
  • @DaliborČarapić Again, don't focus on the two main cases: study the 4 subcases and see if you understand how indeed in all those 4 cases the claim holds. – Bram28 Mar 12 '17 at 13:56
  • @Did Thank you for the clarification. – Dalibor Čarapić Mar 12 '17 at 14:01
  • @lulu "if we can prove the claim in each of these two cases then we will be done" - correct - and my question is how does proving these two cases prove the theorem. – Dalibor Čarapić Mar 12 '17 at 14:02
  • @Bram28 I have looked at the 4 sub-cases and for me they prove the two top cases. – Dalibor Čarapić Mar 12 '17 at 14:03
  • Read my first comment. The two cases cover all possibilities! To repeat with different words: suppose neither case holds. Then there are at most two people who know $x$ and at most two people who don't know $x$. Thus there are at most four people, yet we are told we have five. – lulu Mar 12 '17 at 14:03
  • About "feeling stupid" see http://academia.stackexchange.com/questions/83628/asking-questions-in-class-how-can-i-exit-a-qa-when-i-havent-really-understo/83636#83636 – Ethan Bolker Mar 12 '17 at 14:16
  • @DaliborČarapić Ok, so once they prove the two top cases, and since those two top cases are the only top cases, then the claim is proven in general. You may not grasp how the claim is true for any of the top cases, but you have nevertheless proven it. this is not any different from the theorem we end up with: after the proof is done, I still don't immediately grasp why it is true ... My working memory is just too limited. Nevertheless, I will have proven it. I added my Answer below for some further explanation of the reasoning process behind Proof by Cases. – Bram28 Mar 12 '17 at 14:18
  • Thank you all. I think I've finally understood. I've edited my question to reflect this. – Dalibor Čarapić Mar 13 '17 at 20:04

2 Answers2

1

It's not that it proves the theorem by itself, exactly; it tells you which of two sub-proofs is applicable to any given situation. I'll give an analogy that might be clearer. (The proof is a bit silly because it's so simple, but it should demonstrate the idea.)

We prove that the square of a real is nonnegative. Indeed, there are three cases: $x<0; x=0; x>0$. If we specialise to each of those cases, proving the theorem in each limited case, our life is made easier: it is easier than proving the theorem in general, since in each smaller case we know more about $x$.

But you ask, why does this prove the main theorem? Well, any real number must be in one of the three cases above. If someone gives us a real number, we can in principle look at it and see which of the cases it lies in. Then we can perform the steps of the proof which correspond to that case.

For example, here's a toy proof that squares are non-negative:

  • If $x=0$ then $x^2=0$ so we're done.
  • If $x>0$ then we have the product of two positive numbers (namely $x$ and $x$), which must be positive.
  • If $x<0$ then we have the product of two negative numbers, which must be positive.

Why does this prove the theorem? If you give me some $x$ (maybe it's $2$) and ask me to prove that its square is nonnegative, I can look at the cases. I note that $2>0$ so we are in the second case. And then I can apply the proof of the second case to our particular $x$: here, noting that we have the product of two positive numbers (namely 2 and 2), so we're done.

A proof by cases is a collection of several recipes, each one proving the theorem given a bit more information than we started out with. As long as we can demonstrate that we will always have a recipe corresponding to any given example, we can say that the main theorem is proved.

In your theorem, why are the two cases together enough to cover every option? Well, if we're not in the first case, then it's not the case that out of the five others, three have met $x$. So at most two can have met $x$; so at least three must have not. But that tells us we're in the second case! Either we're in the first case or in the second case, so our two recipes will always be enough.

Patrick Stevens
  • 36,135
  • 1
    +1 Perhaps add a sentence pointing out that the two cases in the OP's problem are exhaustive in just the way you describe, and invite him to justify the next steps that break those cases into subcases. – Ethan Bolker Mar 12 '17 at 14:14
  • I'll do that soon; currently a bit busy :) – Patrick Stevens Mar 12 '17 at 14:15
  • Thank you for the reply. I can understand the point of cases. Its just for this particular theorem I do not understand how these two cases 'cover' it:
    1. Among 5 other people besides x, at least 3 have met x.
    • These 3 other people might know each other therefore they are a club
    • These 3 other people might not know each other therefore they are a group
    1. Among the 5 other people, at least 3 have not met x
    • These 3 other people might know each other therefore they are a club
    • These 3 other people might not know each other therefore they are a group
     – Dalibor Čarapić Mar 12 '17 at 15:19
  • @DaliborČarapić Do you agree that at least [in fact, exactly] one of "three know $x$" and "three do not know $x$" must happen? – Patrick Stevens Mar 12 '17 at 15:43
  • @PatrickStevens Yes - I agree that these 2 cases are mutually exclusive (and that only one of them must be 'in effect'). – Dalibor Čarapić Mar 12 '17 at 16:56
  • Thank you. I think I've finally understood. I've edited my question to reflect this. – Dalibor Čarapić Mar 13 '17 at 20:05
0

Let's call the 2 cases 1 and 2, with sub-cases 1A and 1B, and 2A and 2B respectively.

So then the proof structure looks like this:

  1. Cases: 1 or 2

  2. $\quad$ Assume case 1

  3. $\quad $ Cases: 1A or 1B

  4. $\quad \quad $ Assume Case 1A

  5. $\quad \quad $ ... There is either a club or a group of 3 => Claim Holds for 1A!

  6. $\quad \quad $ Assume Case 1B

  7. $\quad \quad $ ... There is either a club or a group of 3 => Claim Holds for 1B!

  8. $\quad $ There is either a club or a group of 3 => Claim Holds for 1!

  9. $\quad $ Assume Case 2

  10. $\quad$ Cases: 2A or 2B

  11. $\quad \quad$ Assume 2A

  12. $\quad \quad$ ... There is either a club or a group of 3 => Claim Holds for 2A!

  13. $\quad \quad $ Assume 2B

  14. $\quad \quad $ ... There is either a club or a group of 3 => Claim Holds for 2B!

  15. $\quad $ There is either a club or a group of 3 => Claim Holds for 2!

  16. There is either a club or a group of 3 => Claim Holds!

The proof by cases steps are 8, 15, and 16. So at step 8, you say: since we know that A1 or A2 (because we work within assumption A), and since both of those two cases leads to the claim, we know that the claim is true in case A. In step 15, you do the same for case B, on the basis of B1 and B2. And so then at the end (step 16) you say: we know that either A or B. but since both lead to the claim, the claim is always true.

So: you may indeed not immediately see how the claim holds in case A ... Indeed, why do you think they further subdivide it into A1 and A2? It is exactly because it really is not easy to see. but once you have shown it for A1 and A2, you know it is true for A ... Even if that is not immediately clear.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Thank you for the reply but it is not a problem of understanding the cases. Rather for this particular theorem I do no understand how it is 'decomposed' into two cases. In other words how do these two particular cases 'cover' the main theorem. Please take a look at my comment for Patrick Stevens answer. – Dalibor Čarapić Mar 12 '17 at 15:36
  • @DaliborČarapić Oh! Well, with 5 people, if you have at least three people that know x, then we are dealing with case 1. If that is not the case, then two or less people have met x ... Which means that three or more have not met x .. Which is case 2. – Bram28 Mar 12 '17 at 15:47
  • Yes. I understand the cases 1 and 2 and I understand how they are 'proven' with sub-cases. What I fail to grasp is how proving these 2 cases proves the main theorem: Every collection of 6 people includes a club of 3 people or a group of 3 strangers. – Dalibor Čarapić Mar 12 '17 at 17:00
  • @DaliborČarapić OK, so you understand that in each subcase of case 1 there is either a club of 3 people or a group of 3 strangers? Or at least: is it true that you are able to prove this claim for every subcase for case 1? – Bram28 Mar 12 '17 at 17:03
  • @DaliborČarapić I was re-reading your post ... at the end you say: "How did stating that 3 other people have met or not met the fourth (making it a group of 4 people proves the original theorem)." ... I am not sure what you mean by this, but it sounds like you are looking to prove that a least 4 people have met or not? But that wasn't the theorem: the theorem is only about 3 people! Indeed, the theorem would not be true for 4 people out of 6. ... Is that maybe what has been your confusion all along? – Bram28 Mar 12 '17 at 17:18
  • Thank you. I think I've finally understood. I've edited my question to reflect this. – Dalibor Čarapić Mar 13 '17 at 20:05
  • @DaliborČarapić Yay! Glad I could help :) – Bram28 Mar 13 '17 at 21:46