Without loss of generality

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Without loss of generality (often abbreviated to WOLOG, WLOG[1] or w.l.o.g.; less commonly stated as without any loss of generality or with no loss of generality) is a frequently used expression in mathematics. The term is used to foreshadow the making of an assumption in a proof which narrows the premise to some special case, but which will not deter the validity of the proof in general since the proof for that case can be easily applied to all others by symmetry — or some other kinds of equivalences or similarities.[2][3] As a result, once a proof is given for the special case, it is often trivial to adapt it to prove the conclusion in all other cases.

In many scenarios, the use of "without loss of generality" is made possible by the presence of symmetry. For example, if some property P(x,y) of real numbers is known to be symmetric in x and y, namely that P(x,y) is equivalent to P(y,x), then in proving that P(x,y) holds for every x and y, one may assume, "without loss of generality", that xy. There is no loss of generality in this assumption, since once the case xy P(x,y) has been proved, the other case follows by yx[4] P(y,x) ⇒[5] P(x,y), thereby showing that P(x,y) holds for all cases.

On the other hand, if such a symmetry (or other form of equivalence) cannot be established, then the use of "without loss of generality" can amount to an instance of proof by example — a logical fallacy of proving a claim by proving a non-representative example.[6][3]

Example[edit]

Consider the following theorem (which is a case of the pigeonhole principle):

If three objects are each painted either red or blue, then there must be at least two objects of the same color.

A proof:

Assume, without loss of generality, that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.

Here, notice that the above argument works because the exact same reasoning could be applied if the alternative assumption, namely, that the first object is blue, were made. As a result, the use of "without loss of generality" is valid in this case.

See also[edit]

References[edit]

  1. ^ "Without Loss of Generality". Art of Problem Solving. Retrieved 2019-10-21.
  2. ^ Chartrand, Gary; Polimeni, Albert D.; Zhang, Ping (2008), Mathematical Proofs / A Transition to Advanced Mathematics (2nd ed.), Pearson/Addison Wesley, pp. 80–81, ISBN 0-321-39053-9
  3. ^ a b "The Definitive Glossary of Higher Mathematical Jargon — Without Loss of Generality". Math Vault. 2019-08-01. Retrieved 2019-10-21.
  4. ^ from the just proved implication by interchanging x and y
  5. ^ by symmetry of P
  6. ^ "An Acyclic Inequality in Three Variables". www.cut-the-knot.org. Retrieved 2019-10-21.

External links[edit]