| Without Loss Of Generality |
Article Index for Without |
Website Links For Without |
Information AboutWithout Loss Of Generality |
| CATEGORIES ABOUT WITHOUT LOSS OF GENERALITY | |
| mathematical terminology | |
Next to WLOG there must be present an assumption. To check that there is no loss of generality, write out the entire proof (without making the simplifying assumption) and then see if the proof which you wrote out follows out of a proof of just a part of the premise. EXAMPLE Consider the following Theorem (the simplest case of Ramsey's Theorem and also an example of Dirichlet 's Pigeonhole Principle ): Three objects are each painted either red or blue; there must be two objects of the same color. The proof: Assume without loss of generality that the first object is red. If either of the other two objects is red, we are finished; if not, the other two objects must both be blue and we are still finished We begin the full proof by listing all the permutations:
of which there are eight, as we expect (2 × 2 × 2). We now see that the separated lists are equivalent under our assumptions, so we reduce the list:
Now we scan the shorter list with our eyes and see that there are two objects of the same color in every case. We reduced the premise as we did by noticing, first, that the order of the objects doesn't matter; second, that we are interested not in the ''kind'' of color but in its ''count''. Both assumptions are consistent with our conclusion, which required that two objects be ''of the same color'' -- a loose requirement. SEE ALSO EXTERNAL LINK |
|
|