# Clarification on Without Loss of Generality

Suppose we have the following proposition:

Suppose $$a$$ and $$b$$ are integers. If $$a$$ is odd or $$b$$ is odd, then $$ab$$ is odd or $$a+b$$ is odd.

The solution key I am looking at broke the proof into three cases: 1) if $$a$$ is odd, 2) if $$b$$ is odd, and 3) if $$a$$ and $$b$$ are odd. For each case, they prove that either $$ab$$ is odd or $$a+b$$ is odd. However, I feel as though this was unnecessary. In this context, $$a$$ and $$b$$ are indistinguishable because of the commutative properties of addition and multiplication. As such, the process to prove the first two cases is nearly identical.

In my proof, I broke the explanation into two cases: 1) if one integer ($$a$$ or $$b$$) is odd, and 2) if both integers are odd. For the first case, I stated, "Without loss of generality suppose $$a$$ is odd and $$b$$ is even...."

I write all of this to say: is this a responsible use of WLOG? I currently understand WLOG as a simplification step that allows us to condense our proof if several cases employ the same logic, varying only in the literal representation of x's and o's (in this case the a's and b's). Is this the right way of understanding WLOG, or is there a better way?

This question has also brought up the nuance of WLOG. That is, the appropriate use of WLOG not only depends on the hypothesis but also on what we are trying to prove. Suppose, instead, that we were proving a statement related to division (like $$\frac{a}{b}$$). Even if our hypothesis remained the same, the cases would no longer be interchangeable, since division is not commutative. This seems like a trivial realization, but, to this point, most of the examples that I had seen seemed to imply that WLOG seemed to apply in any circumstance where we had interchangeable elements in the premise.

• As you said, the perfect symmetry of the problem allows you to proceed like you did. PS: probably you meant "division is not commutative" Commented Jul 21 at 18:34
• Thank you. I apologize for the misspell! @DavideMasi Commented Jul 21 at 18:39
• In a proof of Y, WLOG X means "I'm going to prove $X \vdash Y$, and it is obvious that if I can prove that, then Y is provable". What's obvious varies from person to person. Commented Jul 21 at 19:10
• You invoked WLOG appropriately (and asked a good question overall), but I just wanted to mention that one can prove the result without cases. Note: $$ab+(a+b)+1=(a+1)(b+1)$$ If either (or both!) of $a$ or $b$ is odd, then the right-hand side is even, hence $ab+(a+b)$ is odd. We may conclude that exactly one of $ab$ and $a+b$ must be odd.
– Blue
Commented Jul 21 at 19:23
• @Blue this is a very elegant solution! Commented Jul 21 at 19:24

I write all of this to say: is this a responsible use of WLOG?

Yes, you are using WLOG here exactly as it is intended to be used.

I currently understand WLOG as a simplification step that allows us to condense our proof if several cases employ the same logic, varying only in the literal representation of x's and o's (in this case the a's and b's). Is this the right way of understanding WLOG, or is there a better way?

Although using WLOG can sometimes indeed result in the proof being more condensed, I think it's mostly a "simplification" in the sense that it makes the proof easier to read and understand (by a human who is versed in the conventions of mathematical writing, that is). Brevity is not always the goal, nor is it always the result, of using WLOG.

One nuance that often throws off less experienced readers of proofs when they encounter the WLOG idiom (and less experienced writers when they are considering using WLOG in their own proofs) is that the WLOG bit is often inserted without any explanation as to why there is no loss of generality. That part is left to the reader to figure out on their own. (And that might be one of the things that makes the proof more condensed - it's actually omitting some details, which obviously helps to make the proof shorter.) Usually it's quite easy to fill in that explanation if you are following the details of the proof, but sometimes this can require a bit of mental effort, and in any case one needs to acquire the particular mental habit of explaining to yourself why each WLOG assertion is justified. Students in the early phase of their mathematical training, particularly some of them who are used to detailed proofs that spoon-feed them with every little detail, are sometimes quite baffled about how to make sense of a "WLOG" assertion.

In your example, I think the reason for your doubt about whether you are using WLOG correctly is precisely because the convention in mathematical writing allows for making the WLOG claim without explaining why it is justified. If you were forced to add the explanation, you would do so (as you have done when writing this question), and then you would feel more confident that your explanation is correct. I have seen many of those same students who are baffled by WLOGs attempt to use WLOG when writing their own proofs, and, again probably because they have been trained through their reading of textbooks to just say "without loss of generality" with no further explanation, they sometimes end up peppering their writing with random-seeming "WLOG"s that make little sense and are often hilariously wrong.

What this suggests is that it might be good practice to get in the habit of always including an explanation for why there is no loss of generality whenever you make a WLOG claim in your writing. Afterwards, you can go through the text and delete some or all of the explanations if they seem too obvious for the type of readers you are aiming your writing for. For example, I would say the explanation for the example in your question is pretty clearly not needed if you're writing for mature mathematicians. But it might still be helpful to write this explanation for yourself. Moreover, there are occasionally cases when the explanation would be needed, and when just saying "Without loss of generality suppose $$a$$ is odd and $$b$$ is even" could end up annoying and frustrating your readers, to the point where it would not necessarily be what I consider a "responsible use" of the WLOG convention.

@Teepeemm quoted someone else's statement that WLOG means "we prove the claim in a special case and the general case can be logically (and easily) reduced to this special case - hence our proof actually shows the claim in the general case!"

I agree with that description (especially in the context in which it was made where it was correcting someone's misguided idea of what WLOG is meant to be used for). But another way of thinking about WLOG is that it's a convention for organizing our choice of labels. If we have two numbers $$a$$ and $$b$$ and we know that one of them is odd and the other is even, and there is some claim about the two numbers that treats them symmetrically, then WLOG is a kind of notational device that says "we are free to choose which of the labels we use for the odd one and which for the even one because from the point of view of the claim that doesn't make any difference, so let's choose the label $$a$$ for the odd one and $$b$$ for the even one". So it's not so much that we are proving a special case, but rather we are proving the general case but presenting the argument in a way that's pleasant to read and understand.

As another example, a proof of a claim about a sequence of numbers $$a_1,...,a_n$$ might go: "Assume without loss of generality that $$a_1$$ is the maximal number in the sequence. Then [some argument]". An experienced mathematician will understand that this is shorthand for: "Let $$i$$ denote the index for which $$a_i$$ is the maximal number in the sequence. Then [the same argument as before, replacing $$i$$ for each occurrence of 1]." The latter version is more clunky because it adds an index $$i$$ that one needs to keep track of, which increases the cognitive load on the reader (and also adds the potential for error, for example one now needs to be careful not to use the same index 𝑖 anywhere else in the proof). So again, although at a formal level you could say we are proving the special case in which $$i=1$$, in this situation I would say it's more a kind of mental crutch that helps human readers digest the proof more easily through a careful choice of labels. It communicates the idea that "the precise index of the maximal number in the sequence is immaterial to the claim, so we may as well assume it's 1".

• In every case you have mentioned as valid, you could generate the corresponding other proof through a symmetrical substitution. Ie, there is a symmetry in $\{a,b\}$ (swapping them); the facts of the situation are preserved through this symmetry, thus your proof (or sub-proof) is an invariant of the symmetry. The same holds for the $a_i$; the thing required to prove is invariant on reordering the $\{a_i\}$s. Textually, the reader can take the WLOG section and apply the permutation and see if it has no impact.
– Yakk
Commented Jul 22 at 20:39
• @Yakk that’s true. As I said in the edit, one can regard WLOG as a formal argument that relies on symmetry to imply the general case from a special case, or as an informal way to make use of “label-independence” to write the proof of the general case in a more easily digestible form. Those two points of view are basically equivalent (and any experienced mathematician will know how to translate an informal “labels” argument into a formal one if called upon to do so), but I personally prefer the less formal way of thinking about what’s going on. Commented Jul 22 at 22:37
• I think one reason students are often confused by WLOG is that the convention is never explained to them, even in intro proof books. This is why years ago I suggested to George Bergman that he write down explanations of some of these mathematical turns of phrase for students to reference. Commented Jul 23 at 3:28
• @DanRomik I am curious if I have ever seen a WLOG that isn't "this (implicitly stated) lemma's proof is invarient under symmetr(ies) S, so I will prove it for a specific 'permutation' case and thus for the orbit of the symmetr(ies)" under the hood. Every one I can think up off hand seems to be that.
– Yakk
Commented Jul 23 at 21:48
• @Yakk the usage of WLOG can be more general than that. For example section 3 of this paper discusses applications of WLOG in a geometric context, where the type of assumptions that can be made without loss of generality have to do with a choice of origin or coordinate system. So the "degrees of freedom" in a WLOG claim can involve more than a choice of permutation. Commented Jul 25 at 19:09

Note that the statement can be simplified to

Suppose $$a$$ and $$b$$ are integers. If $$a$$ is odd, then $$ab$$ is odd or $$a+b$$ is odd.

An equivalent way to solve problems of this type consists of proving that if $$(a$$ is odd and $$ab$$ is even$$)$$, then $$a+b$$ must be odd.

Another equivalent approach is the following: if $$(a$$ is odd and $$a+b$$ is even$$)$$, then $$ab$$ must be odd.

You can easily check that these two paths are equivalent to the first one. In fact, all you need to check is that $$P \implies (Q \vee R)$$ is equivalent to $$P \land \neg R \implies Q$$ which in turn is equivalent to $$P \land \neg Q \implies R$$ (here $$P =$$ "$$a$$ is odd", $$Q =$$ "$$ab$$ is odd", $$R =$$ "$$a+b$$ is odd")

This might be helpful to understand when this kind of approach is used in proofs.

Let me point out that here, when I simplified the statement, I mean that either $$a$$ or $$b$$ is odd. If you are given two integers and one of them is odd, choose it to be $$a$$ - this is precisely what "without loss of generality" means.

• Or, you may rephrase the statement as "Suppose $a$ and $b$ are integers, if at least one of them is odd then ...... " or "Suppose $a$ and $b$ are integers, if one of them is odd then ......" Commented Jul 22 at 15:13