A simple illustration of a proof using "without loss of generality." On this page, "number" means positive integer. A composite number is defined to be a number which is the product of two smaller numbers, and a prime number is defined to be a number which is not composite. We will analyze the proof of the following theorem, which has been known since the idea of prime number was first invented. Theorem: Given a number n, suppose that, for any number m > 1 such that m^2 <= n, n is not divisible by m. Then n is prime. [standard] Proof: Suppose that n is not prime. Then n = pq where p and q are numbers which are both smaller than n. Without loss of generality, p <= q. (a) Since q < n, p = n/q > 1. Since p <= q, p^2 <= pq = n, and p divides n. (b) Thus n has a divisor greater than 1 whose square is no greater than n. This contradicts the hypothesis. You understood that proof, right? Now let's analyze the role of "wlog." The short answer is that the statement that "wlog p <= q" is justified by the fact that multiplication is commutative. However, this simple answer skips over the deep logical issues. Here is how we would write the proof without using the "wlog" phrase. [unrolled] Proof: Suppose that n is not prime. Then n = pq where p and q are numbers which are both smaller than n. There are two cases: p <= q and p >= q. Either p <= q or p >= q. Case 1: p <= q. Since q < n, p = n/q > 1. Since p <= q, p^2 <= pq = n. (a) Since q < n, p = n/q > 1. Since p <= q, p^2 <= pq = n, and p divides n. (b) Thus n has a divisor greater than 1 whose square is no greater than n. Case 2: p >= q. Since p < n, q = n/p > 1. Since q <= p, q^2 <= pq = n. (c) Since p < n, q = n/p > 1. Since q <= p, q^2 <= pq = n, and q divides n. (b) Thus n has a divisor greater than 1 whose square is no greater than n. In either case, we contradict the hypothesis of Theorem 1. This is pointlessly redundant, of course. Let's try again, first separating out the portion of the proof that needs the "wlog" argument. We first rephrase the Theorem, by replacing it by the statement that every composite number n has a divisor greater than 1 whose square is not greater than n. It is helpful to give that statement a name, so we call it Claim A. The fact that Claim A is equivalent to Theorem is trivial. We also give names to the hypothesis and the conclusion of Claim A, "HypA" and "Con." Claim A now reads: Claim A: If (HypA) n = pq, where both p and q are smaller than n, then (Con) n has a divisor greater than 1 whose square is no greater than n. [usual] Proof of Claim A: Without loss of generality, p <= q. Then (a) Since q < n, p = n/q > 1. Since p <= q, p^2 <= pq = n, and p divides n. (b) Thus n has a divisor greater than 1 whose square is no greater than n. (Page 2) Now the careful analysis. What is really happening is that we are implicitly using another claim that appears to be stronger than Claim A: Claim B: If (HypB) n = pq, where both p and q are smaller than n and p <= q, then (Con) n has a divisor greater than 1 whose square is no greater than n. The proof of Claim B is then just lines (a) and (b), and does not use "wlog." Our "wlog" statement in the standard proof is merely the claim that (Claim A => Theorem) => (Claim B => Theorem), which expands to ((HypA => Con) => Theorem) => ((HypB => Con) => Theorem) Using formal logic, we reduce this to (HypB => Con) => (HypA => Con) which further reduces to HypA => HypB. (No, this is not a typo.) In the final step, we see how commutativity of multiplication is used. Proof that HypA implies HypB: Suppose that n = pq, where p and q are both smaller then n. If p <= q, we are done. Otherwise, n = qp and q <= p, and we are done. Summary: In a published proof of the original theorem, "wlog" would be used, even in the most elementary textbook, which means that the reader is assumed to be able to not only follow the logic given here, but to come up with it himself. Is this assumption warranted? Given the complexity of this explanation, I am skeptical. My experience is that many (most?) students are unable to make the leap, and get discouraged.