Why do we use “without loss of generality” when writing proofs?
Is it necessary or convention? What “synonym” can be used?
Answer
I think this is great question, as the mathematical use of “without loss of generality” often varies from its literal meaning. The literal meaning is when you rephrase a general statement
P(x) is true for all x∈S,
using another set (which is easier to work with)
P(z) is true for all z∈T,
where P is some property of elements in S and T, and it can be shown (or is known) that S=T.
For example:
-
We want to show that P(x) is true for all x∈Z. Without loss of generality, we can assume that x=z+1 for some z∈Z. [In this case, S=Z and T={z+1:z∈Z}.]
-
We want to show that P(x) is true for all x∈Z. Without loss of generality, we can assume that x=5q+r where q,r∈Z and 0≤r<q. [In this case, S=Z and T={5q+r:q∈Z and r∈Z and 0≤r<q}.]
In the above instances, indeed no generality has been lost, since in each case we can prove S=T (or, more likely, it would be assumed that the reader can deduce that S=T). I.e., proving that P(z) holds for z∈T is the same as proving that P(x) holds for x∈S.
The above cases are examples of clear-cut legitimate usage of "without loss of generality", but there is a widespread second use. Wikipedia writes:
The term is used before an assumption in a proof which narrows the premise to some special case; it is implied that the proof for that case can be easily applied to all others (or that all other cases are equivalent). Thus, given a proof of the conclusion in the special case, it is trivial to adapt it to prove the conclusion in all other cases.
[emphasis mine.]
So, paradoxically, "without loss of generality" is often used to highlight when the author has deliberately lost generality in order to simplify the proof. Thus, we are rephrasing a general statement:
P(x) is true for all x∈S,
as
P(z) is true for all z∈T, and
if x∈S, then there exists z∈T for which P(x) is true if P(z) is true.
For example:
- Let S be a set of groups of order n. We want to show P(G) is true for all G∈S. Without loss of generality, assume the underlying set of G is {0,1,…n−1} for some n≥1. [Here, T is a set of groups with underlying set {0,1,…n−1} that are isomorphic to groups in S, and the reader is assumed to be able to deduce that property P is preserved by isomorphism.]
My personal preference is to replace the second case with:
"It is sufficient to prove P(z) for z∈T, since [[for some reason]] it follows that P(x) is true for all x∈S."
Attribution
Source : Link , Question Author : Pedro left MSE , Answer Author : Community