Say we have a bounded infinite set S on the real line. That is to say, S contains infinitely many points, but all those points are contained within a bounded interval; go out far enough on the real line in either direction and eventually you'll reach a location beyond which there are no more points in S. As it turns out, there has to be a point on the real line such that any open interval containing that point contains infinitely many points in S. Why? Read on.

If you ever take a course in real analysis (please note that 10998521's writeup on this is absolutely wham-bang boffo fantastic), the probability is as high as 75% that your professor will at some point ask you, with a wry smile, "Do you know how to catch a lion?"

In all likelihood, at this point in the course you will be thoroughly tired of being made to put up with such ridiculous shit as proving the (patently obvious, right? Right?) Intermediate Value Theorem and fiddling about endlessly with deltas and epsilons, and you will cringe at the very thought of what horrific and complex concept might be insidiously concealed within the innocuous procedure of catching a lion. You might prefer going to Africa, armed with nothing but a spear, a loincloth, and your wits, to whatever it is your professor is about to subject you to.

Fear not, because not only is the procedure for lion-catching intimately familiar to any computer science major (at least, it should be), it might just give you as much bang (in terms of usefulness in problem solving) for your buck (in terms of difficulty in understanding) as any other concept in real analysis.

To catch a lion in a field, or a desert, or what have you (let's call it a region, just to keep things general), divide the region in half. Pick the half with the lion in it and divide that half in half. Lather. Rinse. Repeat. This process is described in this node (in section 1.4, "The Bolzano-Weierstrass method"), along with several other ha-ha that's funny science-inspired methods of leonine appropriation. This here, however, is serious business.

This is a binary search, but in the context of a continuous rather than a discrete search space. In a discrete search space of size N, you can find the lion, on average, in log2 N steps. In a continuous search space... wellllll.

  • Long story shortest: Keep doing this and you keep narrowing in on the location of the lion. You'll never find it exactly, but you can get as close as you want.1

  • Slightly longer story: After the nth iteration of this search, your region is (1/2n)th of its original size. It's pretty well-known that the sequence given by Sn = (1/2n) converges to 0; the only region with area of 0 is a point. That point is where the lion is. Better nuke it from orbit; it's the only way to be sure.

  • Longest story I'm willing to tell: The fact that there is a lion to find, so to speak, illustrates the Nested Interval Property, one of many equivalent ways of expressing the most fundamental fact about the real numbers. Put simply, this property is that the real line has no holes in it, as opposed to the rational number "line" which has holes at irrational numbers like π and e.

    The Nested Interval Property states that given a sequence of intervals each of which contains the next, such that the size of the intervals gets arbitrarily small (i.e. "as small as we want") if we go out far enough in the sequence, there is a point which is in all the intervals. This property does not hold for the rational numbers or any smaller set. Because the intervals we have here get their sizes halved every time we iterate, we can get them as small as we want, and so the Nested Interval Property applies here. The point it describes is where the lion is.

Commend yourself if you're not asking what the point is by now, no pun intended. To be perfectly honest, the Nested Interval Property was the big idea here. If we look at the example from the beginning of this writeup, however, we see how the Nested Interval Principle makes it trivial.

Trivial how? Well, take the interval containing that set S. It contains infinitely many points of S. Divide it in half. At least one of those halves contains infinitely many points of S; if they both contained only finitely many points, S itself would have only finitely many points; a contradiction. Take the half containing infinitely many points of S and divide it in half. If both contain infinitely many points in S, just pick one.

You know the rest. Thanks to the binary search algorithm, you know how to catch a lion. The lion is the point in "all the halves," and the fact that all intervals containing it have an infinite number of points from S is a direct consequence of the method we used. What we just informally proved is noded somewhat more technically under Every infinite subset of (0,1) has a limit point. At the risk of self-aggrandizement I have to say I prefer the approach described here.

1 "Getting as close as you want" is an important concept in real analysis. What analysts mean when they say something like this (which they won't, because it's so painfully imprecise, but if they did) is "pick any small value (usually ε, epsilon, is used to represent this value); you can get even closer than that." This is one of the contrived-sounding but essential hacks that have been devised to do things like avoid infinity and excise ambiguity from calculus and its ilk.