📂Lemmas

Maintaining Generality in Mathematics

Terminology ¹

The expression “"Without loss of generality assume $P$"” is mainly used in mathematical proofs to mean that, even if one specifically assumes $P$, it does not affect the overall argument.

Examples

Simple example

As a very simple example, consider proving the proposition “For two real numbers $x, y$, if $xy = 0$ then $x = 0$ or $y = 0$”. Since this is only an example to understand why WLOG is necessary and how it is used, I will explain it with as few omissions as possible.

$x$ and $y$ each have two possibilities: whether they are $0$ or not, so the total number of cases is the product, namely $4$. Let us examine all cases.

Case 1. $x = y = 0$

In this case, both $x$ and $y$ are $0$.

Case 2. $x = 0, y \ne 0$

In this case, $x$ is $0$.

Case 3. $x \ne 0, y = 0$

In this case, $y$ is $0$.

Case 4. $x \ne 0, y \ne 0$

If we divide both sides of $xy = 0$ by $xy$, we obtain $1 = 0$. This indicates that the case $x \ne 0, y \ne 0$ is problematic, so this case must be excluded.

Consequently, if $xy = 0$ then $x = 0$ or $y = 0$ must hold.

■

In this short proof we instinctively feel that Case 2 and Case 3 are actually the same condition. Since $x$ and $y$ represent the same real number and the order of multiplication is irrelevant, it is pointless to separate these cases merely because the symbols are written differently. In such a situation, saying “Without loss of generality, assume $x = 0$ and $y \ne 0$” means that one can simply swap $x$ and $y$ and apply the same argument.

• For the purpose of this post, intended to inform readers not yet familiar with mathematics who wonder what “without loss of generality” means, I have omitted discussions such as proof by contradiction or the field axioms that would show that $x$ and $y$ are not both $0$, and thus omitted talk about multiplicative inverses.

Common examples

As easier examples commonly found in textbooks, consider the following:

• Without loss of generality, assume $A$ is an upper triangular matrix: this means the subsequent proof would be the same if $A$ were a lower triangular matrix.
• Without loss of generality, assume the lengths of the three sides of a triangle are $a \le b \le c$: this means the subsequent proof remains the same if the order in $a, b, c$ is permuted.
• Without loss of generality, assume $\left\| \mathbf{v} \right\| = 1$: for convenience in the proof one sets the norm (magnitude) of the vector to $1$, and if the norm is not $1$ one can scale/divide as in $\mathbf{u} = \mathbf{v} / \left\| \mathbf{v} \right\|$, so there is no problem.