What exactly does without loss of generality mean

509
0
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?
 
Last edited:
590
0
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.
 
509
0
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:
Code:
...
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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...
 
509
0
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.
 
590
0
BicycleTree said:
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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 [itex]\forall a, b \in \mathbb{R}: a \leq b \implies P(a, b)[/itex].

Then, we can conclude: [itex]\forall a, b \in \mathbb{R}: P(a, b) \vee P(b, a)[/itex].
 
509
0
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

Science Advisor
Homework Helper
9,394
3
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.
 

Related Threads for: What exactly does without loss of generality mean

  • Posted
Replies
4
Views
872
Replies
10
Views
3K
Replies
2
Views
4K
  • Posted
Replies
10
Views
1K
  • Posted
Replies
8
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top