Without loss of generality

Without loss of generality

Without loss of generality (abbreviated to WLOG or WOLOG and less commonly stated as without "any" loss of generality) is a frequently used expression in mathematics. The term is used before an assumption in a proof which narrows the premise to some special case; it is implied that the proof on this subset can be easily applied to all others (or that all other cases are trivial). Thus, given a proof of the special case, it is trivial to show that the conclusions follow from the full premise.

This often requires the presence of symmetry. For example, if two numbers are called "x", "y", and it is known that "x" < "y", then any relationship proved based on this assumption will hold for the complementary relation, "y" < "x", because "the roles of" x "and" y "are interchanged", but the proof is symmetric in the two variables. In other words, if we know that "P"("x", "y") is true if and only if "P"("y", "x") is true, then without loss of generality it is enough to show "P"("x", "y") is true (since "P"("y", "x") then immediately follows, by symmetry). (In this context, we call "P" symmetric.)

Next to WLOG there must be present an assumption. To check that there is no loss of generality, write out the entire proof (without making the simplifying assumption) and then see if the proof which you wrote out follows out of a proof of just a part of the premise.

Example

Consider the following theorem (the simplest case of Ramsey's theorem and also an example of Dirichlet's pigeonhole principle):

Three objects are each painted either red or blue; there must be two objects of the same color.

The proof: :"Assume without loss of generality that the first object is red. If either of the other two objects is red, we are finished; if not, the other two objects must both be blue and we are still finished".

We begin the full proof by listing all the permutations, separating those with R first from those with B first:

# RRR
# RRB
# RBR
# RBB
# BRR (inverse of #4)
# BRB (inverse of #3)
# BBR (inverse of #2)
# BBB (inverse of #1)

of which there are eight, as we expect (2 &times; 2 &times; 2). We now see that the separated lists are equivalent under our assumptions (the first half can be converted to the second half by converting all Rs to Bs and vice versa), so we can apply our analysis to the simpler half-list of permutations beginning with R.

We scan the shorter list (permutations 1-4) and see that there are two objects of the same color in every case. In permutations 1-3, at least one object beyond the first is red, and in permutation 4 both of the non-first objects are blue.

We reduced the premise as we did by noticing, first, that the order of the objects doesn't matter; second, that we are interested not in the "kind" of color but in its "count". Both assumptions are consistent with our conclusion, which required that two objects be "of the same color" -- a loose requirement.

ee also

* up to
* mathematical jargon

External links

*planetmath reference|id=2946|title=WLOG


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • without loss of generality — adverb Making a constraining assumption that makes it clear how to apply the proof performed under this assumption to the general case unconstrained by the assumption …   Wiktionary

  • WLOG — Without Loss Of Generality (Academic & Science » Mathematics) * Waveney Light Opera Group (Community » Music) …   Abbreviations dictionary

  • Charlieplexing — is a technique proposed in early 1995 by Charlie Allen at Maxim Integrated Products for driving a multiplexed display in which relatively few I/O pins on a microcontroller are used to drive an array of LEDs. The method utilizes the tri state… …   Wikipedia

  • Perturbation theory (quantum mechanics) — In quantum mechanics, perturbation theory is a set of approximation schemes directly related to mathematical perturbation for describing a complicated quantum system in terms of a simpler one. The idea is to start with a simple system for which a …   Wikipedia

  • Noncentral chi-squared distribution — Noncentral chi squared Probability density function Cumulative distribution function parameters …   Wikipedia

  • Generalized mean — In mathematics, a generalized mean, also known as power mean or Hölder mean (named after Otto Hölder), is an abstraction of the Pythagorean means including arithmetic, geometric, and harmonic means. Contents 1 Definition 2 Properties 2.1 …   Wikipedia

  • Order topology — In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets. If X is a totally ordered set, the order …   Wikipedia

  • Cnoidal wave — US Army bombers flying over near periodic swell in shallow water, close to the Panama coast (1933). The sharp crests and very flat troughs are characteristic for cnoidal waves. In fluid dynamics, a cnoidal wave is a nonlinear and exact periodic… …   Wikipedia

  • LTI system theory — or linear time invariant system theory is a theory in the field of electrical engineering, specifically in circuits, signal processing, and control theory, that investigates the response of a linear, time invariant system to an arbitrary input… …   Wikipedia

  • Sturmian word — In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word. Contents 1 Definition 2 Discussion 3 History 4 Re …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”