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.

Isn't the use of "without loss of generality" in math proofs a bad formulation?

To me it's sound similar as someone saying: "Without getting personal, I think you're jerk."

I mean, when the writer uses WLOG in a math proof, it's always followed with the actual loss of generality. Wouldn't it be more accurate to write something like:

"Take the case _" and then say "and the other cases follow similarly".

share|improve this question
1  
Sure, lots of language is precise. If you want precise language, prove everything in a formal system. But nobody wants to do that. I dislike your language because it doesn't prefix the statement with what you are doing. "WLOG: Assume $x\leq y$" is clearer because it prefixes the type of argument we are making to allow the assumption. Your language is thus, not very prcise either. What you really mean is: "Take the case _" and then say "and other cases follow." –  Thomas Andrews Dec 13 '12 at 14:18
7  
At least when I use it, say to solve an inequality symmetric in $x, y, z$, I say that "We can assume, without loss of generality, that $x\leq y\leq z$", and what I mean is "If this is not the way it is, I will rename the variables so that this is the case, and this renaming will not change the problem." –  Arthur Dec 13 '12 at 14:19
12  
The point of the phrase is to draw the reader's attention to the idea that the "apparent" loss of generality is an appearance only. It's an abbreviation, obviously, but useful precisely because of the frequency with with proofs are shortened by this technique (of dealing with a manageable special case, to which others may be reduced). –  hardmath Dec 13 '12 at 14:25
2  
If you want to make your version a prefix, make it "All cases can be reduced to the case ...". –  Thomas Andrews Dec 13 '12 at 14:31
2  
This seems more like a personal opinion than a question. –  Andrew Uzzell Dec 13 '12 at 14:52

3 Answers 3

up vote 4 down vote accepted

In general, if we have sets $T\subset S$, and a statement $P$ about elements of those sets, and we are trying to prove: $\forall s\in S: P(s)$, it suffices to prove:

$$\forall t\in T: P(t)$$ $$\forall s\in S: \exists t\in T: P(t)\implies P(s)$$

Usually, when a person says "Without loss of generality," the second statement is in some sense obvious - either symmetry or some other argument. Or sometimes the writer has just proven the second statement, and then will often write, "Thus, without loss of generality..."

So the statement:$\forall t\in T:\dots$ is obviously less general than $\forall s\in S:\dots$, but WLOG is making an assertion that the second statement is true, thus showing that proving just for $T$ doesn't "lose generality," because we can get it back.

Most of the examples I'm seeing seem to be about symmetry, but there are other cases where WLOG comes into play.

For example, in a calculus $\epsilon$ proof, where you are trying to prove: $$\forall \epsilon>0:P(\epsilon)$$

It might be obvious that if $0<\epsilon_1<\epsilon_2$ then $P(\epsilon_1)\implies P(\epsilon_2)$. In that case, we would say "Without loss of generality, we can assume $\epsilon<1$."

I think "without loss of generality" is a useful phrase in part because it is a prefix. It alerts the reader: "I am about to make a certain type of argument that you've seen before, and that you will want to verify because I usually skip a few steps when I make this sort of argument."

It might be more precise to write, "It can easily be shown that this statement reduces to the case..." but that is less pithy. There is something about "without loss of generality" that also seems very distinctive, so it jumps out of the page, whereas your more precise forms read as generic.

Consider "Without loss of generality" an assertion, and it makes more sense. It is an assertion that: $$\forall s\in S: \exists t\in T: P(t)\implies P(s)$$ is true. It might have just been proven, or it might be "obvious" in some way.

share|improve this answer

Without being critical, I think you're completely wrong. It is a concise way of expressing your last sentence, with the added virtue that it explains in advance that the other cases follow similarly. With your formulation, I would have to work out why you want to assume whatever it is that you're assuming; "WLOG" tells me why.

share|improve this answer

Saying "without loss of generality we can assume [some condition]" means that one supposes it clear that the claimed result in the special case (where the condition is added to the hypothesis) will imply the result generally (without adding that hypothesis). It is somewhat lazy in that the burden of verifying that the special case implies the general case is left to the reader, but assuming this implication is sufficiently clear, this kind of formulation can make an argument more transparent. An alternative would be to state the special case as a lemma, and then afterwards deduce the full result almost trivially from the lemma; the added length and apparent weight of the proof may be considered a drawback, especially if it is clear right away that the final step will be straightforward.

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.