10
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I would not use your logical formula with first year students. Your informal introduction looks fine, and I'm looking forward to seeing the examples and non-examples people give for this. $\endgroup$
    – Sue VanHattum
    Nov 22, 2022 at 22:49
  • $\begingroup$ Yes, I agree. The formalization of the symmetry argument is nice for "us teachers" (or for more advanced students). I guess that for first year students that would be a bit too complicated to grasp, especially in the more formal, general, and abstract way I presented it, using a general property $Q$, instead of just writing a concrete example $x \le y$. $\endgroup$ Nov 23, 2022 at 7:35
  • 3
    $\begingroup$ I was tempted (only in my mind) to revise your title to the following: How to explain the concept "Without loss of generality" through examples without loss of generality? The idea being that you want to explain this idea by using specific examples, but you want to choose the examples so that they are obviously generalizable enough to explain the idea in general. One example I sometimes did in class (gifted high school students, not college algebra / precalculus college students) was to prove the rational root theorem for cubic polynomials, which is enough to see how it goes in general. $\endgroup$ Nov 23, 2022 at 10:12
  • $\begingroup$ Here are other relevant discussions: math.stackexchange.com/questions/129137/… , math.stackexchange.com/questions/4579626/… and math.stackexchange.com/a/4154170/104576. $\endgroup$ Nov 23, 2022 at 17:56
  • $\begingroup$ I always treated "without loss of generality" as a subclass of "left as an exercise to the reader" where "without loss of generality" implies the reader can crib much of their work directly from the paper after some initial transformation. So if a paper offered steps a, b, c, d, e, f, g, h, i, j, k, l, m, and n, a step near "c" that was "an exercise for the reader" might look like "c, X, Y, Z" while "without loss of generality" might look like "c, X, d, e, f, g, h, i, j, k, l, m , n" $\endgroup$
    – Cort Ammon
    Nov 25, 2022 at 20:13

1 Answer 1

6
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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