2
$\begingroup$

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".

  • 2
    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."2012-12-13
  • 8
    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."2012-12-13
  • 0
    What does the second sentence have to do with anything mathematical?2012-12-13
  • 0
    @ThomasAndrews I agree. I changed it.2012-12-13
  • 15
    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).2012-12-13
  • 0
    Note, "follows similarly" is also a misnomer. Sometimes, it follows as a corrolary. For example, if we are trying to prove some property of all pairs $(x,y)$ of real numbers, and we prove it for $x\leq y$ and we prove that if it is true for $(x,y)$ it is true for $(y,x)$ we don't need to suggest that additional proof is needed - there is no "similarly." Saying "similarly" here means that you think a formal proof would prove each separate case, but that's not necessary.2012-12-13
  • 2
    If you want to make your version a prefix, make it "All cases can be reduced to the case ...".2012-12-13
  • 0
    But I often see proofs, where the writer don't mean "All cases can be reduced to the case ...", but they actually mean, "Take the case _" ... "and the other cases follow similarly".2012-12-13
  • 1
    @Kasper I guess without examples, I can't disagree, but most of the time I see it is in case where it is obvious that $P(x,y)\implies P(y,x)$ so if we prove it when $x\leq y$ it "follows," not similarly when $x\geq y$.2012-12-13
  • 4
    This seems more like a personal opinion than a question.2012-12-13

3 Answers 3

8

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.

  • 0
    +1 Note that this 'WLOG assertion' is equivalent to$$\langle\exists f:\underbrace{f\in S\to T}_{\text{(a)}}:\underbrace{\langle\forall s:P(f(s)):P(s)\rangle}_{\text{(b)}}\rangle$$leaving $\;s\in S\;$ implicit. (Technically, it is slightly weaker except if we have AC or some other form of choice.) What does this mean? It means that we can prove the 'WLOG assertion' by providing $\text{(a)}$ a 'symmetry reducing' function $\;f\;$, and $\text{(b)}$ proving that if $\;P\;$ holds for a 'reduced value', then it also holds for the original $\;s\;$.2015-02-14
  • 0
    @MarnixKlooster Nothing was implicit. I have no idea what you mean by $(\forall s:P(f(s))):P(s)). What is the :? This is not standard logic notation.2015-02-14
  • 0
    Apologies for being unclear. In the notation you use, I just meant$$\exists f\in S\to T:\forall s\in S:P(f(s))\implies P(s)$$ The notations I use are much like ["A Logical Approach to Discrete Math"](https://www.springer.com/computer/theoretical+computer+science/book/978-0-387-94115-8), which is based on notations from Dijkstra, Feijen, et al.: see, e.g., [EWD1300](http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html). By "leaving $\;s\in S\;$ implicit" I just meant "I'm not writing down the '$\;\in S\;$' part since I'm assuming that that is clear from the context."2015-02-14
  • 0
    I'm not reading a whole book to make sense of your comments. If you want to comment on another's answer, use their notation. Again, using the notion of function is detrimental to this discussion, because it might be true that $\forall s\in S(\exists t\in T(\cdots))$ without there being a function, because, in general, we'd need the axiom of choice to have a function. It's *still* not clear what point you are trying to make, because you haven't given the context of what you are complaining about.2015-02-14
  • 1
    (1) There is no need to offended. (2) I already apologized for using a different notation than you used in your post. Sorry! (3) I only pointed to the textbook in response to your question, "What is the :? This is not standard logic notation." And I pointed to EWD1300 as a courtesy, as a readily accessible resource. (4) As you can see, I already made explicit in my comment that AC would be required. (5) I was not complaining about anything, I just liked your (great!) answer, played around with this a bit, and wanted to share an additional viewpoint that the OP might find useful.2015-02-14
7

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.

6

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.