Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why do we use "without loss of generality" when writing proofs? Is it necessary or convention? What "synonym" can be used?

Thanks.

share|improve this question
    
Who introduced WLOG? Was it Koosis? –  AD. Apr 11 '12 at 14:05

5 Answers 5

up vote 10 down vote accepted

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 \in S$,

using another set (which is easier to work with)

$P(z)$ is true for all $z \in 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 \in \mathbb{Z}$. Without loss of generality, we can assume that $x=z+1$ for some $z \in \mathbb{Z}$. [In this case, $S=\mathbb{Z}$ and $T=\{z+1:z \in \mathbb{Z}\}$.]

  • We want to show that $P(x)$ is true for all $x \in \mathbb{Z}$. Without loss of generality, we can assume that $x=5q+r$ where $q,r \in \mathbb{Z}$ and $0 \leq r < q$. [In this case, $S=\mathbb{Z}$ and $T=\{5q+r:q \in \mathbb{Z} \text{ and } r \in \mathbb{Z} \text{ and } 0 \leq 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 \in T$ is the same as proving that $P(x)$ holds for $x \in 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 \in S$,

as

$P(z)$ is true for all $z \in T$, and

if $x \in S$, then there exists $z \in 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 \in S$. Without loss of generality, assume the underlying set of $G$ is $\{0,1,\ldots n-1\}$ for some $n \geq 1$. [Here, $T$ is a set of groups with underlying set $\{0,1,\ldots 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 \in T$, since [[for some reason]] it follows that $P(x)$ is true for all $x \in S$."

share|improve this answer
1  
Good answer, but there is not "set" of groups of size $n$. This collection is a proper class. –  Asaf Karagila Apr 7 '12 at 23:33
    
Ah yes, I suppose $\{e \in G:G \text{ is a group and } e \text{ is the identity of } G\}$ is the set of everything. Hmm... –  Douglas S. Stones Apr 8 '12 at 0:31

It means that no generality is lost by making a particular simplifying assumption, i.e. it is trivial to see that if the proposition to be proved is true in that simple case then it is true in all cases.

share|improve this answer
9  
"it is trivial to see that". It does not have to be. The reduction to the particular case may in itself be a significant part fo the argument. –  Andres Caicedo Apr 7 '12 at 22:36
2  
@AndresCaicedo : If the reduction is a significant part of the argument, then I wouldn't write "without loss of generality". Instead I'd probably write something like: "First we show how to reduce the problem for that of......" etc. –  Michael Hardy Apr 7 '12 at 22:38
2  
I've certainly seen things like: "That we can do this without loss of generality follows from Lemma 2.2 and an application of Ghengis Khan's theorem." –  Michael Greinecker Apr 7 '12 at 23:51
1  
@MichaelGreinecker : Assuming those theorems are already proved, it may be trivial to see that the conclusion follows from them. –  Michael Hardy Apr 8 '12 at 1:05
    
@MichaelHardy: Sure, it is trivial given the additional information. It might not be without. –  Michael Greinecker Apr 8 '12 at 1:13

Consider the proof of the triangle inequality for the real line:

Thm: $\forall x, y \in \mathbb{R}, |x + y| \leq |x| + |y|$.

One popular approach to a proof is to consider cases. We may, for example, consider the case that exactly one of $x \text{ or } y$ is positive. Indeed, it is irrelevant if we pick $x$ to be positive rather than $y$ (or vice-versa). The proof, if our reasoning is valid, works out the same regardless. So, we simply state, "Without loss of generality, assume $x > 0$. " This is the essence of the phrase "without loss of generality" and its usage.

Is it necessary? Not as far as I can see. Simply stating, "Assume $x > 0$," is made possible by the fact that it is irrelevant which variable we pick to be positive. Otherwise, we would state, "Since ..., $x > 0$." So, in a way, if our choice is arbitrary (and correctly so), the phrase "without loss of generality" is implied, and, we may opt to omit it as a "synonym."

share|improve this answer

I often times just do a case "Assume _" and then say "and the other cases follow similarly" which, at least for me, replaces WLOG most of the time.

share|improve this answer

It means we're going to save time by appealing to symmetry. For instance, if $p$ is an irreducible element of a ring and $ab=p$, then precisely one of $a$, $b$ are units. Instead of considering these two cases separately, we might say: "Without loss of generality, assume $a$ is a unit." This is the same as saying: "We will consider the case where $a$ is a unit; the case where $b$ is a unit is similar."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.