Cute Proofs: The Bolzano-Weierstrauss Property.

March 11, 2011

Small Anecdote.

When I was going through my first proofs class it was my first year in college — needless to say, my mind wasn’t completely in the game.  Because it was a Moore method class (the students would do the proofs on the board, and the students would critique it.  the professors were there to help us stay on task and to provide additional criticism.) a number of students would simply copy proofs from Spivak and present them as their own — and this caused a large number of students (including myself, I’ll shamefully admit) to be in possession of a large number of proofs that they have "written" but did not understand. 

For me, a notable exception was the proof of the Bolzano-Weierstrauss property.  This was not only my favorite theorem at the time (and still is one of my favorites!) but it was one where I did the proof entirely by myself (on a bus, an hour before class).

Now-a-days when I am lying in bed and I’m too sleepy or too cold to move from under my covers, I like to reach around my bed and pick up a math book and read one of the sections.  Recently, after cleaning my room, I had moved my Hatcher which usually sits faithfully at my bedside to the other side of the room; getting up was unthinkable, so, instead, I picked up Armstrong’s Basic Undergraduate Topology.  In it, I found a slick proof of the Bolzano-Weierstrauss property that I haven’t seen before.  So, I thought I’d write it up.

 

The Meat and Potatoes: The Theorem.

I’ll first state the Bolzano-Weierstrauss property, and then I’ll post a few proofs for it. 

 

Theorem (Bolzano-Weierstrauss Property): An infinite subset of a compact space must have a limit point.

 

Proof of the Baby Version.

The first proof is a baby version: if we instead assume that our compact set is the interval [0,1] and our total space is the reals, then we can construct an intuitive and elementary version of this proof which tests a number of good concepts in introductory analysis.  So let’s do this thang.

 

Proof (assuming our space is the reals and our compact set is [0,1]).  First, I will leave it to the reader to prove that for any sequence in the reals, there is either a monotonically increasing or a monotonically decreasing subsequence.  Without loss of generality, let’s assume there is a monotonically increasing subsequence.  Because this sequence is monotonic, if it converges then it converges to its supremum.  Because a set in the reals is compact if and only if it is closed and bounded (this is an equivalent statement of the famed Heine-Borel theorem) we have that the supremum is less than or equal to the upper bound, and since the set is closed it must also be in the set.  Hence we have a limit point.  \Box

 

This set is nice and intuitive since if a student looks at a line with the points of the sequence drawn, they will be able to point out the limit point by simply noting, "these points get really close to this."  The monotonic increasing part simply allows us to state this formally.

 

Another Proof of the Baby Version.

This proof will also assume that we’re working in the reals, though we can easily extend it to {\mathbb R}^{n} for any n.  We will assume our compact subset is the unit cube.  So in {\mathbb R} this is just [-1,1]; in {\mathbb R}^{2} this is the square [-1,1]\times [-1,1]; and so on. 

This is actually one of my favorite proofs, and it’s called, "how to catch a lion in the desert."  I outline the proof below, leaving out a few details the reader can fill in.

 

Proof (again, of the baby version).  Let’s say we’re given an infinite subset of our unit cube; let’s assume without loss of generality that we are working in {\mathbb R} and our unit cube is just [-1,1].  First, cut our interval in half: so we now have two intervals [-1,0] and [0,1].  If both of them had only finitely many elements of our infinite subset, then the union would as well; thus, one of these intervals has an infinite number of elements of our infinite subset.  Let’s suppose it’s [0,1].  Pick one element that’s in [0,1] which is also in our infinite subset and call it a_{1}.  Again, cut [0,1] in half to get [0,\frac{1}{2}] and [\frac{1}{2}, 1].  Again, we must have an infinite number of elements in one of these halves, so pick that half and choose some random element from our infinite subset which is in that half and call this element a_{2}

Continue this process.  For every n-th iteration will have intervals of size \frac{1}{2^{n-1}} and we’ll have elements \{a_{1}, a_{2}, \dots, a_{n}, \dots\} where these elements are getting closer and closer to each other.  In fact, the reader can prove these elements are Cauchy.  Since {\mathbb R} is complete, this converges.  Since our compact set is closed, it must converge to an element a which is in our compact set.  Thus, a is a limit point of this infinite subset.  \Box

 

The reason this is called, "how to catch a lion in the desert," is the following game: player 1 draws a square and secretly puts a "lion" at some point in the square but does not show player 2 where the lion is.  Now, player two can cut the square into any two pieces he wants and player 1 must tell him which piece the lion is on.  The picture looks kind of like this:

lion As you can see, player 2 cut the square in half at first and player 1 crossed off the left half.  Then player 2 cut the right half in two again and player 1 crossed off the bottom.  Notice that this continues until player 2 has a very small space to work with (in the picture, all that remains is that little spot by the upper right corner).  And, in fact, this is the exact same process we have used in the proof above.  We have simply taken a single point from our subset that is in the "winning side" every time player 1 crosses off the "losing side"; this allows us to construct a sequence which quickly becomes trapped in a tight space — or, in more mathy words, the sequence is almost forced into being Cauchy.  Sad.

 

Armstrong’s Proof of the General Theorem.

This proof requires us only to be in a compact space — ANY compact space!  This is significantly stronger than the previous two cases, but the proof is actually significantly less involved than the previous two.  It really only uses the definition of a limit point which we restate here for reference:

Definition: For some topological space X and a subset E\subseteq X, a point p\in X is a limit point for E if for every open set U which contains p the following is true: E\cap (U\setminus \{p\}) \neq \emptyset

In other words, if we intersect an open set containing p with our set E, then the intersection is not just the point p.  Note further that a limit point of a set need not be in that set.

 

Proof.  Let X be a compact space and S be a subset of X which has no limit point.  We will show that S cannot possibly be infinite; in other words, we will show that if S has no limit point, it must be finite.  (This statement is called the contrapositive and it is equivalent to proving that if S is infinite, then it must have a limit point.  Think about this for a second.)  Given a point p\in X we can find some open set U_{p} which contains p such that

U_{p}\cap S = \begin{cases} \emptyset & \text{if} \, x\notin S \\ \{x\} & \text{if}\, x\in S \end{cases}

or else we would have p be a limit point of S.  But then consider \displaystyle \bigcup_{p\in X}U_{p}, the union of all such sets for every p\in X.  Since X is compact, there exists a finite subcover; let’s call this \{U_{p_{1}}, U_{p_{2}}, \dots, U_{p_{n}}\}.  But each of these balls contains at most one point of S (specifically, they’ll contain p_{j} if p_{j}\in S or they’ll contain no points if p_{j}\notin S) and so since this set is a cover of X it is also a cover of S, which implies that S can have no more than finitely many points.  \Box.

 

This proof is neat because it’s full of these nice "more advanced" techniques like using the contrapositive and the negation of the definition of limit points.  At the very least, I thought it was pretty cool.

Advertisements

3 Responses to “Cute Proofs: The Bolzano-Weierstrauss Property.”

  1. peter said

    very clever. i never have seen that either.

  2. bubbloy said

    The truth comes out!

    I refused to read Spivak because I signed up for the class thinking it would be really cool, instead of everyone pretending they had came up with brilliant time honored proofs in the span of a weekend. I remember hating that class for the second two semesters but refusing to switch out on principle.

    Fucking Moore’s method. Cannot be taught with grades.

  3. James said

    We were really good the first two semesters with Luke, but then the proofs got way too hard way too fast. Sad but true. If that class didn’t have grades, I think I would’a cared less about who else had the right proofs and more about myself getting the right proofs. Damn GPA, yo.

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: