Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What exactly does without loss of generality mean

  1. Jun 11, 2005 #1
    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: Jun 11, 2005
  2. jcsd
  3. Jun 11, 2005 #2
    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.
     
  4. Jun 12, 2005 #3
    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 (Text):

    ...
    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?
     
  5. Jun 12, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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...
     
  6. Jun 12, 2005 #5
    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.
     
  7. Jun 12, 2005 #6
    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.
     
  8. Jun 12, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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].
     
  9. Jun 12, 2005 #8
    I see... so you don't directly replace the variables, but you make a new proof for general variables which you then apply.
     
  10. Jun 13, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: What exactly does without loss of generality mean
  1. What does Ept mean? (Replies: 1)

  2. What does "det" mean? (Replies: 6)

Loading...