I'm trying to understand exactly when I can assume something "without loss of generality in a proof." The technical explanation, I believe, is that it's allowed provided that the case that I'm omitted "reduces" to the one I prove, either through interchanging of labels or through a rather trivial extension. I can really only understand this through examples, though.
The example I have in mind, where I'm not totally sure I can use it, is as follows. Suppose I have countable (as in, finite or countably infinite) sets $X_1, \ldots, $ and want to show that $\bigcup\limits_{i \in \mathbb{N}} X_i$ is countable. I want to say "without loss of generality, suppose $X_i \neq \emptyset$ for all $i$," the justification being that if I take $I = \{j \in \mathbb{N} \mid X_j = \emptyset\}$, then I have
$$
\bigcup\limits_{i \in \mathbb{N}} X_i = \bigcup\limits_{i \in \mathbb{N}} X_i \setminus \bigcup\limits_{i \in I} X_i,
$$
i.e., they contribute nothing at all to the union, so having in the union is somewhat "harmless." I don't know if I'm sacrificing generality by making this assumption, though.
I would appreciate any help on understanding this.
Best Answer
There's nothing wrong with this! "Without loss of generality" is an imprecise term and can be used in a wide variety of contexts, so there's no fixed rules on exactly how it can be used or what exactly it means. Ultimately, it is intentionally introducing an easy-to-fill gap in a proof and relying on the reader to fill the gap, giving them a hint that it can be done by some sort of symmetry argument or easy reduction to a special case. Your understanding of the meaning seems pretty much correct.
As for the specific example you're asking about, to justify the "without loss of generality" you have to actually fill in the gap in the proof that it introduces. That is, you have to prove the statement in the general case (where some $X_i$ may be empty) using the specific case (where you assume they are all nonempty). You should never use "without loss of generality" unless you yourself know how to fill in the gap in the proof and trust that your reader can do so as well. There are various ways to do that in this case; here is one. Let $Y_i=X_i\cup\{0\}$ for each $i$. Then each $Y_i$ is nonempty, and is still countable. So now we are in the specific case where none of our sets are empty and we can deduce that $\bigcup_{i\in\mathbb{N}}Y_i$ is countable. But $\bigcup_{i\in\mathbb{N}}Y_i=\bigcup_{i\in\mathbb{N}}X_i\cup\{0\}$, so $\bigcup_{i\in\mathbb{N}}X_i$ is a subset of a countable set and thus countable.
Here, the essence of the "without loss of generality" is that if you changed the setup in some simple way to make the assumption true (e.g. added an element to the $X_i$'s so they can't be empty), then this would still give a conclusion that would be strong enough to deduce what you originally wanted (since you would only enlarge the union, and a subset of a countable set is still countable).