80
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Who introduced WLOG? Was it Koosis? $\endgroup$ Commented Apr 11, 2012 at 14:05

5 Answers 5

57
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Good answer, but there is not "set" of groups of size $n$. This collection is a proper class. $\endgroup$
    – Asaf Karagila
    Commented Apr 7, 2012 at 23:33
  • 1
    $\begingroup$ 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... $\endgroup$ Commented Apr 8, 2012 at 0:31
27
$\begingroup$

It means that no generality is lost by making a particular simplifying assumption, that is, 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.

$\endgroup$
5
  • 14
    $\begingroup$ "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. $\endgroup$ Commented Apr 7, 2012 at 22:36
  • 8
    $\begingroup$ @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. $\endgroup$ Commented Apr 7, 2012 at 22:38
  • 4
    $\begingroup$ 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." $\endgroup$ Commented Apr 7, 2012 at 23:51
  • 2
    $\begingroup$ @MichaelGreinecker : Assuming those theorems are already proved, it may be trivial to see that the conclusion follows from them. $\endgroup$ Commented Apr 8, 2012 at 1:05
  • 2
    $\begingroup$ @MichaelHardy: Sure, it is trivial given the additional information. It might not be without. $\endgroup$ Commented Apr 8, 2012 at 1:13
16
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .