Explanation of "without loss of generality"

Question

I've been doing math for some time now, but I'm starting to get into serious proofs now that I'm taking analysis and such. I'm just confused with what it actually means? Does it infer that although we are showing a specific case, this holds for all particular problems like it?

Answer 1

"Without loss of generality" means that even though the explanation/computation is being done for a specific case or subset of cases, due to some kind of underlying symmetry or generalization that is obvious, the explanation applies to all cases.

For example, suppose I want to prove that some function $f(x,y) \ge 0$ for all $(x,y) \in \mathbb R^2$. If $f(x,y) = f(y,x)$, then it suffices to prove that $f(x,y) \ge 0$ for all $x \ge y$: we need not consider the case $x < y$ because it is handled by the symmetry of the function with respect to its variables.

Answer 2

It means assuming a certain specification does not change the proof. If you are required to prove something with a certain level of generality - say for all pairs of unequal real numbers - and you make a certain restriction - say, assuming one of the two numbers is greater than the other - will not make a difference in your proof. That is assuming thus will not result in the loss of generality.

Take a look at this for an example.

And to illustrate further onthis exaple I've chosen.

You are required to prove $P(x, y)$ for all $x, y \Bbb R$ such that $x \neq y$.

But assuming $x \gt y$ will not result in any harm to your proof. As long as you've proven this you need not prove the case for $x \lt y$ either. Because the case you've chosen is general enough.

Answer 3

Expanding slightly on the answers given so far, "without loss of generality" means (or can mean, depending on the context) that the general case of the theorem can be deduced from the special case being proved. Thus, it will suffice to prove the special case, and then the general case follows by a (presumably) simple argument.

For example, consider the Cauchy-Schwarz inequality, saying (in one of it's many forms) that for complex numbers $a_1,\dots,a_N,b_1,\dots,b_N$: $$ \left| \sum_{i=1}^N a_i \bar{b}_i \right|^2 \leq \sum_{i=1}^N \left| a_i \right|^2 \sum_{i=1}^N \left| b_i \right|^2 $$ If you were trying to prove this, you could assume WLOG that $\sum_{i=1}^N \left| a_i \right|^2 = 1$ - for if you have the theorem under this additional assumption, you can recover the general case by rescaling (i.e. if $\sum_{i=1}^N \left| a_i \right|^2 = A$, apply the special case with $a_i/A$ in place of $a_i$). Likewise, you could assume WLOG that each $a_i$ and $b_i$ are in fact real, for else you could again apply a suitable rescaling. If you like powers of $2$, you could assume that $N$ is a power of $2$, for else you can append a lot of zeros to both sequences $a_i$ and $b_i$. One could also say that we can assume WLOG that $a_i$ are not both zero, for else the claim is trivial.

Note that it is not always the case that "without loss of generality" implies some sort of symmetry - sometimes it's merely that there exists a relatively simple way in which the problem can be transformed into a special case or deduced from the special case.

By the way, one way of doing induction involves such "WLOG reduction". Namely, if the statement of the theorem depends on some parameter $n \in \mathbb N$, you can (when doing a proof by contradiction) always assume WLOG that $n$ is the least number for which the claim fails. This is pretty much equivalent to the "normal" induction, and sometimes it's more natural.