Without loss of generality: Difference between revisions
→Example: rm "notice that" |
Add Dijkstra ref; standardize on CS1 |
||
Line 1: | Line 1: | ||
{{redirect|WLOG|the radio station|WLOG (FM)}} |
{{redirect|WLOG|the radio station|WLOG (FM)}} |
||
'''''Without loss of generality''''' (often [[Acronym|abbreviated]] to '''WOLOG''', '''WLOG'''<ref>{{Cite web|url=https://artofproblemsolving.com/wiki/index.php/Without_loss_of_generality|title=Without Loss of Generality|website=Art of Problem Solving|access-date=2019-10-21}}</ref> 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 indicate the assumption that follows is chosen arbitrarily, narrowing the premise to a particular case, but does not affect the validity of the proof in general. The other cases are sufficiently similar to the one presented that proving them follows by essentially the same logic.<ref>{{ |
'''''Without loss of generality''''' (often [[Acronym|abbreviated]] to '''WOLOG''', '''WLOG'''<ref>{{Cite web|url=https://artofproblemsolving.com/wiki/index.php/Without_loss_of_generality|title=Without Loss of Generality|website=Art of Problem Solving|access-date=2019-10-21}}</ref> 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 indicate the assumption that follows is chosen arbitrarily, narrowing the premise to a particular case, but does not affect the validity of the proof in general. The other cases are sufficiently similar to the one presented that proving them follows by essentially the same logic.<ref>{{cite book|first1=Gary|last1=Chartrand|author1-link=Gary Chartrand|first2=Albert D.|last2=Polimeni|first3=Ping|last3=Zhang|author3-link=Ping Zhang (graph theorist)|title=Mathematical Proofs / A Transition to Advanced Mathematics|edition=2nd|publisher=Pearson/Addison Wesley|year=2008|isbn=978-0-321-39053-0|pages=80–81}}</ref><ref name=":0">{{Cite web|url=https://mathvault.ca/math-glossary/#wlog|title=The Definitive Glossary of Higher Mathematical Jargon — Without Loss of Generality|date=2019-08-01|website=Math Vault|language=en-US|access-date=2019-10-21}}</ref> As a result, once a proof is given for the particular case, it is [[Trivial (mathematics)|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 number]]s 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 ''x'' ≤ ''y''. There is no loss of generality in this assumption, since once the case ''x'' ≤ ''y'' [[Material conditional|⇒]] ''P''(''x'',''y'') has been proved, the other case follows by interchanging ''x'' and ''y'': ''y'' ≤ ''x'' ⇒ ''P''(''y'',''x''), and by symmetry of ''P'', this implies ''P''(''x'',''y''), thereby showing that ''P''(''x'',''y'') holds for all cases. |
In many scenarios, the use of "without loss of generality" is made possible by the presence of [[symmetry]].<ref>{{cite book | last = Dijkstra | first = Edsger W. | author-link = Edsger W. Dijkstra | editor1-last = Broy | editor1-first = Manfred | editor2-last = Schieder | editor2-first = Birgit | contribution = WLOG, or the misery of the unordered pair (EWD1223) | doi = 10.1007/978-3-642-60858-2_9 | pages = 33–34 | publisher = Springer | series = NATO ASI Series F: Computer and Systems Sciences | title = Mathematical Methods in Program Development | url = https://www.cs.utexas.edu/~EWD/ewd12xx/EWD1223.PDF | volume = 158 | year = 1997}}</ref> For example, if some property ''P''(''x'',''y'') of [[real number]]s 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 ''x'' ≤ ''y''. There is no loss of generality in this assumption, since once the case ''x'' ≤ ''y'' [[Material conditional|⇒]] ''P''(''x'',''y'') has been proved, the other case follows by interchanging ''x'' and ''y'': ''y'' ≤ ''x'' ⇒ ''P''(''y'',''x''), and by symmetry of ''P'', this implies ''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" is incorrect and can amount to an instance of [[proof by example]] – a logical fallacy of proving a claim by proving a non-representative example.<ref>{{Cite web|url=https://www.cut-the-knot.org/m/Algebra/AcyclicInequalityInThreeVariables.shtml|title=An Acyclic Inequality in Three Variables|website=www.cut-the-knot.org|access-date=2019-10-21}}</ref><ref name=":0" /> |
On the other hand, if such a symmetry (or other form of equivalence) cannot be established, then the use of "without loss of generality" is incorrect and can amount to an instance of [[proof by example]] – a logical fallacy of proving a claim by proving a non-representative example.<ref>{{Cite web|url=https://www.cut-the-knot.org/m/Algebra/AcyclicInequalityInThreeVariables.shtml|title=An Acyclic Inequality in Three Variables|website=www.cut-the-knot.org|access-date=2019-10-21}}</ref><ref name=":0" /> |
Revision as of 22:39, 30 September 2021
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 indicate the assumption that follows is chosen arbitrarily, narrowing the premise to a particular case, but does not affect the validity of the proof in general. The other cases are sufficiently similar to the one presented that proving them follows by essentially the same logic.[2][3] As a result, once a proof is given for the particular case, it is 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.[4] 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 x ≤ y. There is no loss of generality in this assumption, since once the case x ≤ y ⇒ P(x,y) has been proved, the other case follows by interchanging x and y: y ≤ x ⇒ P(y,x), and by symmetry of P, this implies 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" is incorrect and can amount to an instance of proof by example – a logical fallacy of proving a claim by proving a non-representative example.[5][3]
Example
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.
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, or, similarly, that the words 'red' and 'blue' can be freely exchanged in the wording of the proof. As a result, the use of "without loss of generality" is valid in this case.
See also
References
- ^ "Without Loss of Generality". Art of Problem Solving. Retrieved 2019-10-21.
- ^ Chartrand, Gary; Polimeni, Albert D.; Zhang, Ping (2008). Mathematical Proofs / A Transition to Advanced Mathematics (2nd ed.). Pearson/Addison Wesley. pp. 80–81. ISBN 978-0-321-39053-0.
- ^ a b "The Definitive Glossary of Higher Mathematical Jargon — Without Loss of Generality". Math Vault. 2019-08-01. Retrieved 2019-10-21.
- ^ Dijkstra, Edsger W. (1997). "WLOG, or the misery of the unordered pair (EWD1223)". In Broy, Manfred; Schieder, Birgit (eds.). Mathematical Methods in Program Development (PDF). NATO ASI Series F: Computer and Systems Sciences. Vol. 158. Springer. pp. 33–34. doi:10.1007/978-3-642-60858-2_9.
- ^ "An Acyclic Inequality in Three Variables". www.cut-the-knot.org. Retrieved 2019-10-21.