What exactly does without loss of generality mean

[BicycleTree]

What exactly does "without loss of generality" mean

What exactly does "without loss of generality" mean and how can you formally tell when you are justified in using it? I understand what it means and how to use it informally but is there formal justification for it?

When you say "WLOG let a R b" I know that you can't have already said anything about a or b that affects whether a R b. But that doesn't seem very precise.


It seems like you need to know that a R b "is not ruled out" by what has been said so far. But is there even a formal way to keep track of what "has been ruled out" and what has not?

 

[master_coda]

You can use WLOG when you have a method for converting the general case to a specific case.

For example, if I'm trying to prove something about two arbitrary real numbers a and b, then I can say "WLOG let a <= b" because given any general case (arbitrary a and b) can be converted into a case where a <= b.

The key to justifying this is that you must be able to convert every general case to the specific case.

 

[BicycleTree]

Okay, so basically if you can re-assign names so that the condition is true under any circumstance, you can use WLOG. "If !(a <= b) then let a1 = b and b1 = a, and then refer to a1 as a and b1 as b." But you still need to know if you've already ruled it out. For example:

...
Assume a > b
  WLOG let a <= b
  a > b and !(a > b)
So by contradiction !(a > b)
...

That's incorrect--but logically how would you tell?

 

[Hurkyl]

The relabelling can't change the problem.

If the problem, thus far, is "let A and B be real numbers", then relabelling them doesn't change the problem.

If the problem, thus far, is "let A and B be real numbers with A < B", then relabelling does change the problem, so it can't be done.


The use of "without loss of generality" is to collapse several cases into one case. When we have "let A and B be real numbers", then there are two cases:

case 1: A <= B

case 2: B <= A

But if we relabel case 2, we obtain case 1 exactly.


Another way of saying it might be:

Let A and B be real numbers. We may relabel the variables so that A <= B...

 

[BicycleTree]

If the problem, thus far, is "let A and B be real numbers with A < B", then relabelling does change the problem, so it can't be done.

Okay--so then you have an additional statement, "A < B," that _prevents_ an inference (WLOG let A <= B). I'm thinking either there is another way to describe the rules on WLOG, or there are kinds of formal logic that include one statement preventing the inference of another. That's ringing a bell on existential instantiation, but I'm not sure it applies. Otherwise, WLOG does not have a direct counterpart in formal logic, and all proofs involving WLOG would have to be much longer in formal logic because all possibilities must be considered.

 

[master_coda]

Okay--so then you have an additional statement, "A < B," that _prevents_ an inference (WLOG let A <= B). I'm thinking either there is another way to describe the rules on WLOG, or there are kinds of formal logic that include one statement preventing the inference of another. That's ringing a bell on existential instantiation, but I'm not sure it applies. Otherwise, WLOG does not have a direct counterpart in formal logic, and all proofs involving WLOG would have to be much longer in formal logic because all possibilities must be considered.

My guess is that whether or not you can convert "WLOG let ..." into formal logic depends on whether or not you can express your proof that the general case can be reduced to the specific case in formal logic.

 

[Hurkyl]

I have once seen opinion expressed that people should not use "without loss of generality" or "by symmetry, the same is true for the other cases".


Anyways, they boil down to this, formally:

Suppose you have a proof that \forall a, b \in \mathbb{R}: a \leq b \implies P(a, b).

Then, we can conclude: \forall a, b \in \mathbb{R}: P(a, b) \vee P(b, a).

 

[BicycleTree]

I see... so you don't directly replace the variables, but you make a new proof for general variables which you then apply.

 

[matt grime]

i explain it to students as:

we have two possible choices we could make, either choice results in the same outcome, usually after relabelling variables.