How to explain the concept "Without loss of generality" (through examples)?

Question

This is not a precise question. I am curious to know how do you present to your students the (imprecise) concept of "without loss of generality", and how to use it correctly/incorrectly.

I got curious after a student of mine (in calculus $I$), while trying to prove that for every $a \in \mathbb{R}$ $$ \big(\frac{a+|a|}{2}\big)^2+\big(\frac{a-|a|}{2}\big)^2=a^2, $$ wrote that without loss of generality, we may assume that $a \ge 0$.

I decided not to accept this usage of the concept as legitimate. Both sides of the equations are invariant under the transformation $a \to -a$, so one can appeal to symmetry here, but this appealing to symmetry needs to be stated (especially since it is not immediately obvious for the LHS).

Anyway, this got me thinking about how to explain to students the slippery concept of WLOG.

I think that a good way is using examples, so I am asking for elementary examples (suitable for first semester math courses) which illustrate the concept. "Anti-examples" where this usage is less appropriate (in a non-trivial way) will also be nice, in order to warn the students from making mistakes.

---

To start the ball rolling, here is a classic example:

We want to prove some property $P(x,y)$ holds for every real numbers $x,y$, and $P$ is symmetric, i.e. $P(x,y) \iff P(y,x)$.

Let $Q(x,y)$ be some "property" (logical formula) satisfying $$\mathbb{R}^2=\{ (x,y) \in \mathbb{R}^2 \, | \, Q(x,y) \} \cup \{ (x,y)\in \mathbb{R}^2 \, | \, Q(y,x) \}. \tag{1}$$

Then we can assume W.L.O.G that $Q(x,y)$ holds, i.e. it suffices to prove that $Q(x,y) \Rightarrow P(x,y)$:

Indeed, $Q(y,x) \Rightarrow P(y,x) \Rightarrow P(x,y)$, and by our assumption $(1)$, this justifies the reduction. (A common choice for $Q$ is $Q(x,y):=x \le y$).

---

Here is a summary of an informal introduction to the concept:

The term W.L.O.G is used to indicate the assumption that follows is chosen arbitrarily, narrowing the premise to a particular case, but does not affect the validity of the proof in general. The other cases are sufficiently similar to the one presented that proving them follows by essentially the same logic, or follows by a symmetry argument.

Ultimately, it is intentionally introducing an easy-to-fill gap in a proof and relying on the reader to fill the gap.

Answer 1

I disagree with your definition of WLOG. In my opinion, WLOG is synonymous to

"[Obviously, ]the general case can be reduced to the following particular case."

Usually the reduction is done by some sort of symmetry, but it does not have to be the case. On the other hand, in the following situation you describe

The other cases are sufficiently similar to the one presented that proving them follows by essentially the same logic.

the use of WLOG is not appropriate, one should rather say "We only do [...], the other cases are similar". WLOG really conveys that the omitted cases are not just similar, but can be reduced to the treated one.

If used in this sense, there's nothing special about WLOG that makes its use correct or incorrect: it's just a part of the argument presumed obvious and skipped. Whether you are convinced that the level of details is appropriate and that the student would know how to fill them out depends entirely on context.

That said, here are some examples:

• permutational/relabeling symmetry: assume WLOG that $a_1\leq \dots\leq a_n$ when the statement you are required to prove does not depend on the order;
• shifting symmetry: assume WLOG that $x_0=0$ (e.g., when considering the Taylor series of a function at $x_0$). Assume WLOG $\mathbb{E}X=0$ (when the statement is unchanged under subtraction of a constant from a random variable $X$) such as $\mathrm{Var}\,(X+Y)=\mathrm{Var}\,X+\mathrm{Var}\,Y$ for independent $X,Y$.
• scaling: assume WLOG $||x||=1$ when proving a statement about a vector $x$ invariant under scaling. Assume WLOG that $[a,b]=[0,1]$ (e.g., when proving the intermediate value property.)

The usage is not really limited to symmetry arguments:

• Assume W.L.O.G. that all elements of a list are distinct or all numbers in the list are non-zero, when adding repetitions or zero entries obviously does not affect the problem;
• Assume WLOG that [a graph/space/set] $X$ is connected, when the disconnected case is done by considering each connected component separately;
• Let us prove that $f:\mathbb{R}\to\mathbb{R}$ is continuous at $a$. Let $a_i\to a$. WLOG, $a_i$ is decreasing or increasing.