∫ Welcome to WLOG Blog: the technical explanation

“Hello. What on earth is a WLOG blog?”

“Hello, it’s nice to meet you. And I’m glad you asked.”

There are basically two reasons why this is called the WLOG blog, a technical one and a personal one. I’ll cover the technical one here, and we’ll have to get to the personal one in a subsequent post.

Basically, WLOG is an acronym that pops up from time to time in a mathematical proof, and it stands for “Without Loss Of Generality.” I know what you’re asking yourself right now: “What on earth does that mean, and who in the world gave mathematicians the right to use prepositions in their acronyms?” Well I can only answer the first question, so here goes.When you’re doing a proof, sometimes you have to make a few assumptions to make the proof easier. Often, this means the proof is no longer general. For example, if I want to prove something is true about any number X, and I assume that X is an even number, then I’ve still got a perfectly good proof, but now, of course, I’ve only proved the property applies to even numbers.

Sometimes, however, you can get away with making a sneaky assumption without having to narrow the scope of the proof, i.e., without loss of generality. Almost always, this just means taking advantage of something arbitrary in the proof, but especially when the proof in question gets long and complicated, making good use of some assumptions without loss of generality can be absolutely crucial.

Here’s two examples, one kind of trivial, and the other more realistic but more complicated.

First, suppose I want to prove something about my sock drawer. And trust me, mathematicians will happily try to apply their skills to things much weirder than socks. But today, lets imagine a poor mathematician with two types of socks in his dresser: “type A” socks, and “type B” socks.

It doesn’t really matter what these types are, but if it makes you feel better, lets say “type A” socks are white, and “type B” socks are black. Well, our mathematician wants to have as much time as possible to  do math during the day, so he doesn’t want to waste time looking around for matching socks. Instead, he want’s to prove that if he picks three socks randomly out of his sock drawer, he’s guaranteed to have a pair.

So here’s the proof he gives me: “Let’s assume that the first sock I pull out of the drawer is ‘type A,'” says the mathematician. Then, if the second sock I pull out is also type A, I’ve got a pair, and I’m done. But if it’s not, then it’s type B, and I have one of each type. If that happens, then no matter what I pull out the third time, I’m guaranteed to make a pair with one of the first two.”

“That sounds pretty good,” I say to the mathematician, “only there’s a problem. You said ‘let’s assume the first sock is type A,’ and there’s no reason to think that should happen. What if it’s a black sock.”

“Well in that case,” says the mathematician, “then I’ll just change my definition of ‘type A’ and ‘type B.’ I’ll call black socks ‘Type A,’  and then the exact same proof I used before still applies.”

“Gotcha,” I tell him. “So I guess what you really meant to say was ‘Lets assume, without loss of generality, that the first sock is type A.'”

“Exactly!” says the mathematician. “That’s why WLOG is cool. Now if you’ll excuse me, I’ve got to go find a matching pair of shoes…”

So that’s the idea. When you’ve got something arbitrary like “which type of sock should I call type A,” then you can always assume one way or the other without hampering your proof, and that way, you don’t have to do the proof once for when you start with a white sock, and a second time for when you start with a black sock. But lest you think this kind of thing is only useful in the world of dresser drawers and undergarments, here’s an application of it that actually gets used quite a bit in physics:

Suppose I’m trying to prove the statement “Electric charge is Lorentz invariant.” Don’t worry; that’s not as complicated a statement as it sounds like. It just means that if I’m sitting still and looking at a bunch of electric charges someplace, and you come running past me at some random speed, you and I are going to agree on how much charge is there*.

Well in general, as a physicist, here’s what I would try to do: I would write down an equation for how much charge the stationary guy sees, and an equation for how much charge the moving guy sees, and then try to do some fancy math to prove that the two equations are equal no matter what. Well, it’s actually harder than you would think, but it would be many times harder still if we weren’t prepared to make a few WLOG assumptions.

For example, you might think I need to prove that the equations are equal no matter how fast the moving guy is going. Well, that’s true. That’s part of what makes it hard. But you might also think that I have to prove it no matter what direction the guy is traveling, and thank goodness, that’s not true. I only have to prove it’s true for a guy moving in one specific direction, and what’s more, if I play my WLOG cards right, then I can also pick whatever direction makes the math easiest.

The key lies in the fact that coordinates are arbitrary (I told you most WLOG things relied on some sort of arbitrary choice). So let’s say I’m starting this proof; what I want to do is imagine a piece of graph paper, like this one:

Now that I’m doing the problem on graph paper, you can see why I might prefer one direction over another. If the moving guy is flying straight along one of the horizontal lines (ideally, along the X-axis), then it’s easy to describe his motion mathematically. But if he’s going along some other random line, cutting across squares all willy-nilly, then I’m going to have a much worse go of it. So I claim, that, WLOG, I can assume the moving guy is moving along the X-axis, like this:

But let’s say some jerk comes along and insists on flying along some other trajectory, like this twerp:

Well in that case, I’ll just rotate my graph paper. Remember, the coordinates were arbitrary. It doesn’t matter what my graph paper looks like, or how it’s rotated; I just have to have some kind of graph paper somewhere so I can keep track of where things are. So now the picture looks like this:

And you can see, the gentleman is once again flying along the X-axis in a nice, orderly fashion.

So that’s the power of WLOG. I can deal with a special, convenient case, and then claim that my proof works for all the other cases too if I just change my definitions. If I assume I pull out a type A sock first, and you say “what if it’s a black sock?” then I just tell you to pretend that “type A” means “black” and I can hand you the exact same proof. Similarly, if I assume the moving guy is traveling along the X-axis, and you say, “what if he’s headed in some other direction?” then I just rotate my graph paper until that direction IS the X-axis, and I can hand you the exact same proof. Ta Daa! Isn’t it awesome?

Oh, right, and that reminds me, welcome to WLOG blog. It’s awesome that you’re here.

*You might think this is obvious, and moreover, you might be thinking that probably everything is Lorentz invariant. After all, why should it matter how fast someone is moving? Shouldn’t they see all the same things?

Well, you’re wrong, but don’t feel too bad about it. You’re just thinking what everyone on the planet thought for thousands of years, and it took no less than Albert Einstein to come up with a theory that said otherwise. It turns out that some things do look different to moving people and stationary people. The classic example is “length.” If you go past something really fast, you’ll notice it looks a lot skinnier than it does to a person standing still right next to it. Moral of the story: next time you’re feeling down on your self for having eaten that whole tub of ice cream, go hit on some of the people running laps at the track.

Advertisements

About Colin West
Colin West is a graduate student in quantum information theory, working at the Yang Institute for Theoretical Physics at Stony Brook University. Originally from Colorado (where he attended college), his interests outside of physics include politics, paper-folding, puzzles, playing-cards, and apparently, plosives.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: