Why do we use "without loss of generality" when writing proofs?
Is it necessary or convention? What "synonym" can be used?
Proof Writing – Use of ‘Without Loss of Generality’
proof-writingterminology
Related Solutions
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..." Very occasionally.
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. So a longer form of the statement is, “It would appear we are proving a less general theorem, but we can get the general theorem back, so we don’t lose generality.”
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.
Your usage of "wlog" appears correct. In general, it should be used to make an artificial distinction between two or more otherwise indistinguishable things, for clarity.
For example, if we wanted to prove something about two real numbers, we might say: "let $x,y \in \mathbb{R}, x \leq y$ wlog" and then continue the proof. The point is, the numbers $x$ and $y$ are arbitrary, and one must be bigger than the other so we may as well say $x \leq y$. If someone actually gave me two points, $x = 4$ and $y = 2$ then for our proof to work we simply relabel the points so that $x \leq y$ and we have lost no generality.
On the other hand, it is often used incorrectly. Say we have a monotonic function $f : [0,1] \rightarrow \mathbb{R}$. If we wanted to prove that $f$ was injective for example, it would be wrong to start with "let $f$ be increasing wlog" because we have lost some generality in this assumption. What we should say is something like "consider the case where $f$ is increasing, and the decreasing case is similar".
It's a subtle difference, and not one that should cause too much worry to be honest, I think it's unlikely to cause any mathematical errors, it may just confuse an argument a little.
Best Answer
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
using another set (which is easier to work with)
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:
[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:
as
For example:
My personal preference is to replace the second case with: