tag:blogger.com,1999:blog-40771082014-04-19T13:21:41.203-04:00O Sweet Mr Mathwherein is detailed Matt's experiences as he tries to figure out what to do with his life. Right now, that means lots of thinking about math.Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.comBlogger379125tag:blogger.com,1999:blog-4077108.post-44053187216049528362012-08-30T22:35:00.000-04:002012-08-30T22:35:14.025-04:00Taylor series and Fourier series<p>So, continuing my discussion of the big picture of real analysis, I ended last time talking about sequences of functions, and the idea that under the right conditions (the sequence is uniformly convergent, or the sequences of derivatives is uniformly convergent), the members of the sequence of functions have the same properties as the function which is the limit of the sequence. This means that if you have a function which is computationally ugly, you can potentially rewrite it as a sequence of functions which are easy to work with.</p>
<p>There are two important examples of sequences of functions which converge uniformly. The first is polynomials. Polynomials are easy to work with, so if you can rewrite an ugly function as a polynomial, you can turn hard problems into easy problems. In particular, Taylor series are a particular sequence of polynomials which approximate a function. Taylor series have important limitations, in that the original function must be infinitely differentiable and Taylor series do not always converge, but when they do work, they are a powerful and convenient tool.</p>
<p>The second example of a sequence of functions which converges uniformly is the Fourier series. Given a function which is bounded and periodic (meaning it repeats itself), you can write the function as a sum of sine and cosine functions. Sines and cosines are difficult to evaluate, but they are easy to work with (for example differentiation and integration). Their smoothly undulating curves are also pretty. It's aesthetically appealing to be able to convert an angular, sharp edged function into a sum of beautiful waves.</p>
<p>I've previously encountered Fourier series in other contexts, and while I studied the basic math to some extent, there was an element of, "we are justified in using Fourier series because they give the correct results in practice." I found it personally satisfying to come back to them and be able to say that we are mathematically justified in using them because we can mathematically prove that they give the expected results.</p>
<p>This is as far as I've gone in studying real analysis. It all comes back to using limits as a tool to say that these are the conditions under which we are allowed to do certain mathematical operations, and these are the conditions under which the operations will fail. Along the way, I started with the concept of sequences of numbers, and eventually extended that idea to sequences of functions. The fact that functions can be inserted in a place where I expected to use numbers has also had the effect of changing how I think about functions in general.</p>
<p>Real analysis goes on from here, leading to questions like "what is the mathematical definition of length?" (Think about it. A line segment has some length. But a line is made up of points, and points have no length. So where does the length of the line come from?) This leads to questions like, "can you have a set of points which is not a line but which also has a length?" I'm interested in these questions, which start to have a metaphysical significance, but I'm happy to stop here with my current studies for now.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-273714406477878652012-08-29T21:43:00.002-04:002012-08-29T21:43:53.600-04:00Results from limits<p>I want to continue my thoughts about real analysis from last time. As I said then, the central concept behind real analysis is the limit. But limits aren't the point of real analysis, they are a tool. So what can we do with limits?</p>
<p>First, we can determine continuity. Continuity is the idea that there are no breaks or gaps in something. As applied to functions, continuity means that there are no sudden jumps in the value of the function. In other words, if a particular input produces a particular output, any inputs near the original input will have outputs near the original output. Or mathematically, a function is continuous at a point if the limit of the function at that point equals the value of the function at that point. Being "near" a value is sort of a nebulous concept, and I'm not going to define it precisely here. But I will say that being "near" an output at a particular input has a precise definition, but that it depends on the function and also the input value.</p>
<p>Starting with the statement that a function is continuous at a particular point, we can extend this to say that the function is continuous everywhere. Sometimes we can only say that a function is continuous at most places, but there are some places where it is not continuous. This is nearly as useful as being continuous everywhere. We may also be able to say that a function is uniformly continuous, in which case we <em>can</em> use the same definition for "near" for every point in the domain of the function.</p>
<p>Why do we care about continuity? If we know that a function is continuous, we know a lot about that function. There are a bunch of important theorems from calculus, such as the intermediate value theorem and the mean value theorem, which depend on the continuity of the function. Calculus uses these theorems, but often does not prove them. A calculus textbook will say something like, "this looks like it should be true, and it is true, but for the proof, check an analysis book." Continuous functions are easier to work with than discontinuous functions. The bad news is that most functions are discontinuous, so proving continuity is an important step for working with a function.</p>
<p>Continuity leads to calculus. Again using limits as a tool, we can demonstrate that differentiation and integration actually work. Both concepts are based on approximation, and there's an assumption that the approximations are actually meaningful. Using limits, analysis proves that the approximations are correct.</p>
<p>When approaching limits using sequences, derivatives are based on a sequence of points. Starting with a fixed input point, take a sequence of points near that point, and the limit of the change in outputs between those two points is the derivative of the function. Integrals are based on a sequence of sets. Subdivide the total area into a set of smaller areas which approximate the original. As the sets have more subdivisions of smaller areas, the limit of the approximation of the area is the true area, or the integral.</p>
<p>You can also take the limit of a sequence of functions, and this is where the real fun begins. Start with some function which is hard to work with. Maybe there's no way to directly find the value of the function for a particular input, or you can do it but it's too much work. You can approximate the original function with another function that is easier to use. If you have a sequence of these approximate functions, you may be able to show that the limit of the sequence equals the original function. This justifies using one of the approximations instead of the original function.</p>
<p>How do you prove that these approximations are actually good, useful approximations? With limits, of course. And limits can be very useful. Looking at the continuity of a function, we distinguished between continuity in general, which means that if two inputs are near each other, then their outputs will also be near each other, but the definition of "near" depends on the inputs, and uniform continuity, which states that "near" has the same definition for every input. Likewise, we can define uniform convergence for a sequence of functions.</p>
<p>Take a particular function in the sequence. This function approximates the original function, but is not exactly the same. The difference at a particular input between the approximation and the original is called the error of the approximation at that point. If for the particular function there is a maximum error, and if every function in the sequence has a maximum error, and if the limit of the maximum error is 0 as you progress through the sequence, then the sequence converges uniformly. (For a counter example, picture a function which goes to infinity at one point. Then imagine a sequence of functions which are generally close to the original function at all other points, but have a finite value at that point. If that value grows with each function in the sequence, the limit of the sequence will be the same as the original function, but the error will be infinite at that point for every function in the sequence, so it does not converge uniformly.)</p>
<p>You can use limits to show that every if every function in a sequence is continuous and the sequence converges uniformly, then the function they converge to must be continuous. Likewise, for a sequence of functions which converges uniformly, the limit of the sequence of integrals equals the integral of the limit. However, if a sequence converges uniformly, the limit of the sequence of derivatives does not necessarily equal the derivative of the limit of the sequence. This is one of those cases where it's easy to detect a pattern and assume it continues. Analysis and the application of limits shows that your expectations break down. Applying the same techniques leads to the good news that if the derivatives converge uniformly to a function, then that function <em>is</em> the derivative of the limit. In the case of derivatives, the question isn't whether the functions in the sequence converge uniformly. It's whether the derivatives of the functions in the sequence converge uniformly.</p>
<p>There's a big payoff to sequences of functions and uniform convergence, but this post has gone on long enough, so it will have to wait until tomorrow.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-55965286741333171012012-08-28T16:18:00.000-04:002012-08-28T16:18:06.403-04:00Real Analysis and Limits<p>I had been posting about real analysis. I worked through the definition of the real numbers, then moved on to topology and sets, and finally had started working on sequences and series. Then I stopped. Truthfully, when I started covering this material I hadn't intended to cover things in quite so much detail, but going over all the details did come pretty naturally to me. But when I started, I had been intending to keep pace with my own studying. I ended up falling behind, and then I ran out of time for any blogging at all.</p>
<p>In the meantime I kept studying, and now I have worked through two semesters worth of analysis. While I'd like to return to blogging in detail, I've decided to take advantage of the fact that I've stopped to take a step back and look at the larger picture, now that I have enough understanding to see the larger picture.</p>
<p>The fundamental idea behind real analysis is the limit. Limits are a powerful tool for understanding lots of math concepts, and real analysis is about developing the use of limits and then applying them to various problems.</p>
<p>Loosely speaking, the idea behind limits is that two things are near each other. The things in question could be numbers, or points in space, or sets, or functions. There's a precise mathematical definition for limits, which involves Greek letters (and causes some people to run in terror), but today I just want to talk about the general concept.</p>
<p>In many mathematical contexts, the standard is exact equality. High school algebra is all about showing that the left hand side of an equation is exactly equal to the right hand side. With limits, we say that two things are not exactly the same, but that's okay as long as they are near each other. This can feel like it's a step back from true equality, and it can also feel unfocused.</p>
<p>But there's a tradeoff. Equality can only say that this thing is exactly the same as this other thing. Limits can let you say that everything near this thing is close to everything near this other thing. The ability to speak about lots of things at the same time gives limits more power than strict equality has.</p>
<p>You may be wondering why, if analysis is all about limits, did I spend months blogging about sets and sequences. I did not know the answer at the time, but now I do. Just like limits are a tool used by analysis to talk about other stuff, we need tools to talk about limits. The first tool is sets and topology. One of the fundamental concepts of topology is distance, and so gives us the ability to talk about whether two things are near each other. The theory about sets we developed, for example the properties of compact sets, gives us tools to talk about limits.</p>
<p>Similarly, sequences give us different tools to talk about limits. The important thing here is that although sets and sequences give us different tools, they come to the same conclusions. Anything that can be demonstrated about limits using sets can also be demonstrated using sequences, and which one to use is just a question of convenience. This equivalence can also be used for sets and sequences to say things about each other, so using both tools allows us to get a deeper understanding of each tool individually.</p>
<p>I plan to have another post soon in which I will talk about what limits are useful for, again at a big picture level. I may also post about the big picture with sequences and series. My introduction to the concepts of sequences and series was in Calculus 2, and the idea has always felt a little half-baked. Now that I'm looking at them from the other side of analysis, I have a much better understanding of why we study them the way we do.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-1164152556489539902012-05-07T21:45:00.000-04:002012-05-07T21:45:57.190-04:00Infinite limits<p>We've defined convergence of a sequence. A sequence (in any metric space) converges if there is a point in that space, called the limit of the sequence, such that the points in the sequence stay arbitrarily close to the limit beyond a certain step in the sequence. If you tell me how close you want to be, I can always tell you the minimum step in the sequence to guarantee that you will be that close.</p>
<p>We can basically run this idea backwards, and say that for any point which is not the limit of the sequence, there exists a minimum distance from that point such that there are always some future points which are at least that far away. Okay, that was too many words. Let me try symbols. a<sub>n</sub> is some sequence with limit L. Then for any distance ε, there exists some start point N, so for any n≥N, d(a<sub>n</sub>,L)<ε. You can choose any positive real number for ε, and then you can always find the minimum value of N so the distance inequality holds. Now, suppose p is a point other than L. Then there always exists some ε, such that for any start point N, some n≥N exists such that d(a<sub>n</sub>,p)>ε.</p>
<p>For L, every ε has one fixed N such that every n≥N works. For p, in contrast, there is some fixed ε so every N has at least one n≥N which does not work. For L, you are free to choose ε and n, but N is fixed. For p, you are free to choose N, but ε and n are fixed. I think the reversals are interesting on their own merits, but they're also important to keep in mind if you are setting out to prove that a particular point either is or is not the limit of a sequence.</p>
<p>So what happens if every point behaves like p? For a given sequence, assume that you can show that for any possible point in the space, the sequence spends some time away from that point. In general, these are not useful sequences. Sequences are useful because we can say what they do in the long run. What we like to say is that they converge to a limit. If no point in the space is the limit of the sequence, all we can really say is that the sequence doesn't converge.</p>
<p>However, if the sequence is a sequence of real numbers, we can sometimes say a little more. If the terms of the sequence tend to increase, then the sequence may not converge, but we can still speak of it having a limit. One way of expressing "tends to increase" concretely is to say that for any real number, the sequence eventually gets larger than and stays larger than that number. Pick any real number P. If based on that choice, we can find an N such that for all n≥N, a<sub>n</sub>>P, then we can say that the sequence does not converge, but it has limit +∞. Draw a number line. Start labeling points a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, and so on. The sequence does not have to strictly increase, so a<sub>2</sub> can be less than a<sub>1</sub>, but it has to increase in general. If you choose any point on the number line and call it P, then the sequence must eventually stay on the right side of P. If you choose a bigger value for P, you would expect the sequence to cross to the right of P later, but for any possible value of P, the sequence must eventually cross to the right side and never cross back. In this case, we can say that the limit of the sequence is positive infinity.</p>
<p>Just to clarify, +∞ is not a real number, and the sequence does not converge. However, we can still speak of the sequence having a limit of +∞. If a sequence converges, that means that it eventually gets close to a specific point. If it has limit +∞, that means it eventually gets really big. How big? As big as you want. When will it get there? All we promise is that it will get there eventually, but that after that, it will just keep growing.</p>
<p>Sequences of real numbers can also have a limit of −∞, meaning the same thing in reverse. The sequence travels left on the number line as the terms increase. Infinite limits apply only to sequences of real numbers. Sequences of complex numbers, for example, can get big, but they can get big in lots of different ways, so it's hard to speak of it having a limit. However, if a<sub>n</sub> is a sequence of complex numbers, then |a<sub>n</sub>| is a sequence of real numbers, and it may be useful to speak of |a<sub>n</sub>| having an infinite limit, even if a<sub>n</sub> does not have a limit.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com1tag:blogger.com,1999:blog-4077108.post-45468427010645715152012-05-05T19:09:00.001-04:002012-05-05T19:09:57.471-04:00Bitterblue's 15 hour watch<p>In the novel <cite>Bitterblue</cite>, by Kristin Cashore, one character has a watch which is divided into 15 hours, each of which has 50 minutes. The novel has a brief discussion of how to convert time on that watch to standard time, and I'd like to look at it in a little more detail.</p>
<p>Like a conventional watch, which shows 12 hours of 60 minutes, the watch in Bitterblue shows half a day. However, the number of periods, and therefore the lengths of the periods, that it shows are different. One day has 24 standard hours, but 30 watch hours. (I will refer to times and durations on the watch as w-hours, w-minutes, etc. for clarity.) Therefore, there are 4 hours in 5 w-hours, or 1 w-hour = 4/5 hour (or 48 minutes). With 60 minutes in an hour, there are 1440 minutes in a day, but since there are only 50 w-minutes in a w-hour, there are 1500 w-minutes in a day. This means that 24 minutes = 25 w-minutes, so minutes and w-minutes have a similar duration.</p>
<p>With these relationships, it's possible to convert a time on the watch to a conventional time. One way to do it is to convert w-hours to w-minutes, then convert the total w-minutes to conventional minutes, then convert the minutes back to hours and minutes. If the w-time is h:m, the formula to convert to minutes is (h×50 + m) × 24/25. Divide this number by 60 to get the current hour, and the remainder is the current minutes. In <cite>Bitterblue</cite>, the title character does an example of a similar computation with equivalent results.</p>
<p>After Bitterblue does the calculation, she remarks that "I, for one, would find it simpler to memorize which time signifies what." As a halfway step to memorizing lots of times, it's fairly easy to estimate the time from the w-time. We'll start with a rough estimate that's accurate to about 5 minutes and then tighten it up a bit. 4 hours = 5 w-hours, so 4:00 = 5:00 w-time, 8:00 = 10:00 w-time, and 12:00 = 15:00 w-time. The first step is to find the closest current hour to one of these three points. The second step is to observe that 1 w-hour is 4/5 hour, and that 3/4 is close to 4/5. We're doing some rounding here, but we're used to thinking in quarter hours and we can correct the rounding later if we need to. So we start at 5:00, 10:00, or 15:00, and we add or subtract enough w-hours to be close to the current w-time. For each w-hour added or subtracted, we add or subtract 3/4 hour from the time. The last step is to add or subtract w-minutes. Since we're just estimating, and 1 w-minute = 24/25 minute, we can just add or subtract the number of w-minutes after or before the hour and ignore the conversion.</p>
<p>Let's do an example. Say the w-time is 8:35. 8 is close to 10, so we start there. 10:00 w-time = 8:00. Then we subtract 1 w-hour from 10:00 to get 9:00, so we subtract 45 minutes from 8:00 to get 7:15. Finally, we subtract 15 w-minutes from 9:00 to get 8:35. (The minutes subtraction is the step which throws me. Since there are 50 w-minutes in a w-hour, 8:35 is 15 w-minutes before the hour, not the expected 25.) Subtracting 15 minutes from 7:15 gives our estimate of 7:00. 8:35 on the watch is approximately 7:00 normal time.</p>
<p>We did some rounding, which we can now correct if we need more precision. We approximated 1 w-hour as 3/4 hour, when it's really 4/5 hour. 3/4 is 45 minutes and 4/5 hour is 48 minutes, so we can add or subtract 3 additional minutes per w-hour. In this case, 6:57 is a closer estimate than 7:00. Finally, there's a small rounding error in the minutes. If we add close to 25 w-minutes, we should subtract 1 minute from our estimate, and vice versa. Since we subtracted 15 w-minutes, it's slightly closer to add 1 minute back in, for a final time of 6:58.</p>
<p>Doing the full computation, we get 8×50 + 35 = 435. 435×24 is 10440. 10440/25 is 417.6. 417.6 divided by 60 is 6, with a remainder of 57.6. In other words, the exact time is 6:57:36. I can do 435×24 in my head, but I don't really want to, and estimating that the current time is about 7:00 was much easier and probably accurate enough.</p>
<p>Often, when I look at a watch face, I don't actually need to know the exact time. I'm just looking for a quick estimate, based on the hand position. So what does the hand position on a 15 hour watch tell us about the standard time? On a standard watch, the hour hand travels a full circle in one half day, so the angle from vertical tells us the exact time. It's easy to judge that if the hour hand is pointing down and a little to the left, it's about 7:00, and based on the exact angle it's not hard to judge whether it's closer to 6:30, 7:00, or 7:30, without even referring to the minute hand.</p>
<p>On the 15 hour watch, the hour hand travels a full circle in one half day, exactly the same as a standard watch. So the angle of the hour hand is the same as on the standard watch. You can work out the angles from the example, and you will find that the angle of the hour hand at 8:35 on the 15 hour watch is nearly the same as the angle of the hour hand at 7:00 on a standard watch. This means that a quick glance at the hour hand on a 15 hour watch will give you exactly the same information as a quick glance at the hour hand on a standard watch.</p>
<p>The minute hand is a different story. The minute hand on a 15 hour watch completes one full circle in 48 (standard) minutes, which means that it points all kinds of different directions relative to the standard minute hand. In our example, at 8:35, the minute hand is pointing to the left and slightly down on the 15 hour watch, but at 7:00 on a standard watch it's pointing straight up. It's hard to get useful information out of the minute hand without doing the full time conversion, either estimated or using the exact formula.</p>
<p>One other point about the watch face design on the 15 hour watch: On a standard watch, it's possible for one set of marks to indicate both hours and minutes. The angle representing 1 hour on the hour hand is the same as the angle representing 5 minutes on the minute hand. So you can mark just the hours, and it's easy to read the minutes just off the hour markings. On the 15 hour watch, things don't work out so well. The angle representing 1 w-hour is the angle for 3 1/3 w-minutes. To read this watch with the same ease and precision as a standard watch, you really need two sets of marks, one for w-hours and one for w-minutes.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com1tag:blogger.com,1999:blog-4077108.post-40274096374577014382012-05-04T18:39:00.000-04:002012-05-04T18:39:19.235-04:00Friday Random Ten<p>Friday Random Ten</p>
<ol><li>Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #183, "Sie Werden Euch In Den Bann Tun"</li>
<li>NDR Chorus Hamburg - Johannes Brahms: 12 Lieder Und Romanzen, Op. 44, "Fragen"</li>
<li>Johannes Brahms: Neue Liebeslieder Waltzer, Op. 65, "Nein, Geliebter, Setze Dich"</li>
<li>Wiener Philharmoniker - Ludwig van Beethoven: Fidelio, Op. 72, Overture</li>
<li>Moby - The Sky Is Broken</li>
<li>Birdsongs Of The Mesozoic - Ptinct</li>
<li>Mozart Akademie Amsterdam - Wolfgang Amadeus Mozart: Symphony #36 "Linz", Presto</li>
<li>Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #27, "Willkommen! Will Ich Sagen"</li>
<li>Tori Amos - Cruel</li>
<li>Frank Martin: Mass for Double Choir, Credo</li></ol>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-66104860081272832432012-05-01T22:44:00.000-04:002012-05-01T22:44:56.805-04:00Sequences and limits<p>Sequences have come up previously in the discussion of topology, and they may have also come up back in February when I was discussing real numbers, but I'm not sure if I've ever formally defined sequences. It turns out that the definition is really simple. A sequence is a function which has a domain of the natural numbers. We could write the sequence as f(n), using n to remind us that it's just defined for natural numbers, but we usually write it as a<sub>n</sub> instead.</p>
<p>The codomain of the sequence could potentially be anything. In the development of topology, the codomain of the sequence was often a set in some metric space. In the proof that <a href="http://mattrolls.blogspot.com/2012_04_22_archive.html#7849684071032429864">perfect sets in Euclidean spaces are uncountable</a>, we used two sequences of points in the Euclidean space, a sequence of neighborhoods, and a sequence of closed sets. Now that our focus is on sequences, the codomain will always be individual points in a metric space, and often in a more specific space such as the complex plane or the real number line.</p>
<p>The big question with a sequence is where is it going? As n gets big, does the sequence of points have some tendency? There are three basic possibilities, depending on both the sequence and the space. First, the sequence could become near a single point. Second, for a sequence of real numbers, the sequence could just increase forever. Third, the sequence could never settle down in a single direction.</p>
<p>If the sequence gets and stays near a single point, we can say that the sequence converges to that point. Convergence has a strict definition, which I think is beautiful, even though some people seem to hate it. If we are in some metric space, which has some distance function d(p,q) between any two points in the metric space, any convergent sequence converges to a point L, which is called the limit of the sequence. Just because L is the limit of a sequence doesn't mean that any point in the sequence actually equals L. It just means that the points in the sequence get close to L, and that they get closer as n gets bigger.</p>
<p>For example, consider the sequence defined by a<sub>n</sub>=1/n. We are of course familiar with this as a set from topology, but the set doesn't necessarily have a particular ordering. We are now looking at it as a sequence, which means that it is a function with domain of the natural numbers, and has an order based on the order of the natural numbers. It should be clear, both from the discussion of topology and from general observation, that the limit of this sequence is 0. That is, as n increases, a<sub>n</sub> gets closer to 0. No point in the sequence ever equals 0, but that's okay because the sequence gets as close as you would like to 0.</p>
<p>I keep saying the sequence "gets near" the limit. It's fair to ask, how near? The answer is, as near as you want to get. Pick some distance from the limit, and call that distance ε. Then we are interested in values of n such that d(a<sub>n</sub>,L) is less than ε. In particular, we are interested in a minimum value N, such that for all natural numbers greater than N, d(a<sub>n</sub>,L)<ε. Looking at the sequence a<sub>n</sub>=1/n, if we picked ε=1/100, for example, then d(a<sub>n</sub>,0)<ε for any value of n≥101. If you choose a different ε, there's a different start point, but for any positive distance ε, there is always a minimum value of N, such that for any n≥N, the distance from a<sub>n</sub> to L is always less than ε.</p>
<p>And this is the formal definition of the limit of sequence. A sequence a<sub>n</sub> in some metric space has limit L, if for any positive real number ε, there exists a natural number N, such that for any value of n greater or equal to N, the distance from a<sub>n</sub> to L is less than ε. Symbolically, the last sentence is equivalent to (∀ε>0)(∃N∈ℕ)(∀n≥N) d(a<sub>n</sub>,L)<ε.</p>
<p>A straightforward conclusion from the definition of a limit is that if a sequence has a limit, it must be unique. This can be proved by assuming that the sequence has two limits, and then using ε and the triangle theorem. If a sequence a<sub>n</sub> has limits L and M, then d(L,M)≤d(a<sub>n</sub>,L)+d(a<sub>n</sub>,M)<2ε. Since ε is arbitrarily small, the distance between L and M is arbitrarily small, which means they must be equal, because d(L,M)=0 only if L=M. You can also argue that if L is the limit of the sequence, no other point can be the limit, because the sequence always gets within distance ε of L, and since any other point is a fixed distance from L, you can always choose ε less than the distance to that point.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-23140780883892352372012-04-30T19:43:00.000-04:002012-04-30T19:43:23.998-04:00Sequences and series<p>Now that I've developed enough topology to prove that the <a href="http://mattrolls.blogspot.com/2012_04_22_archive.html#4691729100894357353">real numbers are not countable</a>, I'm ready to move on to the next topic, which is sequences and series. Before I get into the details, I want to talk about some general issues around the subject.</p>
<p>First off, the book specifically develops topology before sequences because it requires topology concepts in order to provide the structure for discussing sequences. On the other hand, I ended up using sequences frequently in my discussion of topology. I didn't rely on a lot of theory of sequences, but I did use an implicit definition of sequences. If you read some of my proofs revolving around sequences of sets and were wondering how exactly sequences were defined, I will clarify that now. At the same time, there were certain proofs where I desperately wanted to use more theory of sequences, and I avoided doing so because I hadn't developed the theory yet. I don't think greater use of sequences would have made my posts about topology more rigorous, but it may have made it easier to understand.</p>
<p>I've previously mentioned the idea that studying any particular subject in math leads inevitably to studying every subject in math. The way that sequences and topology are tangled up with each other leads to the conclusion that not only do you have to study every subject, but you have to study every subject at the same time. They all build each other. As another example, sequences and series are usually introduced as topics in Calculus 2, when you can use concepts based on integration to prove the basic theorems. On the other hand, the proof that integration works is dependent on Riemann sums, which are infinite series. This sort of thing could turn into circular reasoning, but it can also turn into both topics providing scaffolding for the other, where the results are rigorous but dependent on developing both subjects simulateously.</p>
<p>Speaking of Calculus 2, when studying sequences and series in Calculus 2, I felt like the material both didn't do enough and was looking to do too much. The important question is whether or not a particular sequence or series converges, not what that sequence or series converges to. This was frustrating to me, because it feels like we're only solving half the problem. At the same time, the tools for determining convergence feel weak, making applying them difficult. It's like we're choosing to only solve half the problem, and then handicapping ourselves to make the problem hard.</p>
<p>The approach we are now taking to sequences and series doesn't require calculus, which is good. But it doesn't really prove any more than calculus did, which is bad. We're still just asking whether a sequence converges, and we still end up with a similar set of tools. At least the results are consistent with Calculus 2, so there's at least that.</p>
<p>As I've been studying analysis, I've become convinced that sequences are the basis for everything that follows. Even when the presentation feels incomplete or weak, it's important to understand sequences in order to support analysis as a whole. So this will be my next major topic on this blog.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-27653142210559093892012-04-27T18:00:00.000-04:002012-04-27T18:00:16.361-04:00Friday Random Ten<p>Friday Random Ten</p>
<ol><li>Dietrich Fischer-Dieskau, Daniel Barenboim - Johannes Brahms: 6 Gesänge, Op. 6, "Der Frühling"</li>
<li>Dietrich Fischer-Dieskau, Daniel Barenboim - Johannes Brahms: 6 Gesänge, Op. 3, "In Der Fremde"</li>
<li>Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #168, "Kapital Und Interessen"</li>
<li>NDR Chorus Hamburg - Johannes Brahms: 12 Lieder Und Romanzen, Op. 44, "Die Müllerin"</li>
<li>Scars On 45 - Breakdown</li>
<li>Birdsongs of the Mesozoic - The Simpsons</li>
<li>The Doors - Twentieth Century Fox</li>
<li>Luc Devos - Wolfgang Amadeus Mozart: Andantino & Variations in E Flat, K 236</li>
<li>ABBA - He Is Your Brother</li>
<li>Billy Joel - I Go To Extremes</li></ol>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-46917291008943573532012-04-26T20:23:00.000-04:002012-04-26T20:23:07.360-04:00More on uncountable real numbers<p>I've been thinking more about yesterday's proof. The proof showed that <a href="http://mattrolls.blogspot.com/2012_04_22_archive.html#7849684071032429864">any perfect set in a Euclidean space is uncountable</a>, and since the real number line is a perfect set in a Euclidean space, this led to the conclusion that the real numbers are uncountable. The downside of the proof is that it requires a ton of structural framework to get to the conclusion, and that makes it hard to follow. If all we want to do is prove that the real numbers are uncountable, we can simplify the argument while following the same basic structure. I want to go through the details because I think it will make the logic of the proof more clear.</p>
<p>To prove that the real numbers are uncountable, we will look at intervals. If a and b are real numbers and a<b, then the interval I=[a,b] consists of every real number x such that a≤x≤b. If we have two intervals, I<sub>1</sub>=[a<sub>1</sub>,b<sub>1</sub>] and I<sub>2</sub>=[a<sub>2</sub>,b<sub>2</sub>], and a<sub>1</sub>≤a<sub>2</sub> and b<sub>2</sub>≤b<sub>1</sub>, then I<sub>2</sub> is a subset of I<sub>1</sub>.</p>
<p>This means that we can construct an infinite sequence of subintervals. For any natural number n, the interval I<sub>n</sub> includes the points between a<sub>n</sub> and b<sub>n</sub>, and the interval I<sub>n+1</sub> is a subset of I<sub>n</sub>, meaning that a<sub>n</sub>≤a<sub>n+1</sub> and b<sub>n+1</sub>≤b<sub>n</sub>. We've previously formally proved that given an infinite sequence of subintervals, <a href="http://mattrolls.blogspot.com/2012_04_08_archive.html#5731411562098630689">there must be at least one point which is in every interval</a> in the sequence. We can restate the proof informally by saying that as n increases, a<sub>n</sub> increases but b<sub>n</sub> decreases. They can eventually meet, but they can't cross, so the point where they meet must be in every interval in the sequence.</p>
<p>If we assume that the real numbers are countable, then we could construct a sequence of real numbers, x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, and so forth, which includes every real number. If you specify a natural number n, I could tell you the real number x<sub>n</sub> which corresponds to that natural number, and if you specify a real number x, I could tell you the natural number n such that x=x<sub>n</sub>. This all follows from the definition of <a href="http://mattrolls.blogspot.com/2012_02_26_archive.html#7567454242381803792">countable sets</a>. Essentially, there must be an infinite list which contains every real number.</p>
<p>Now, start with an interval I<sub>1</sub>, which has endpoints a<sub>1</sub> and b<sub>1</sub>. Take a look at the real number x<sub>1</sub> from our list of every real number. If x<sub>1</sub> is not between a<sub>1</sub> and b<sub>1</sub>, then we can just say that I<sub>2</sub>=I<sub>1</sub> and move on. If a<sub>1</sub>≤x<sub>1</sub>≤b<sub>1</sub>, there are two possibilities. If x<sub>1</sub>=b<sub>1</sub>, then we will create a smaller subinterval by moving the right endpoint. Since a<sub>1</sub> and x<sub>1</sub> are real numbers, <a href="http://mattrolls.blogspot.com/2012_01_29_archive.html#185146404921003244">there exists some real number between them</a>, which we can call b<sub>2</sub>. Then a<sub>1</sub><b<sub>2</sub><x<sub>1</sub>. We can then set a<sub>2</sub>=a<sub>1</sub> and we have a new interval I<sub>2</sub>=[a<sub>2</sub>,b<sub>2</sub>].</p>
<p>If x<sub>1</sub><b<sub>1</sub>, then we can move the left endpoint instead. There is a real number between x<sub>1</sub> and b<sub>1</sub>, which we can call a<sub>2</sub>, while keeping b<sub>2</sub> equal to b<sub>1</sub>. Either way x<sub>1</sub> may or may not have been a member of I<sub>1</sub>, but it is not a member of I<sub>2</sub>.</p>
<p>We can now do this with every point on the list, so for every n, if x<sub>n</sub> is a member of I<sub>n</sub>, we can create a smaller interval I<sub>n+1</sub> which does not include x<sub>n</sub>. Otherwise, we can just keep I<sub>n+1</sub> as the same as I<sub>n</sub>. This means that no real number x<sub>n</sub> can be in every interval. However, we know that there is at least one real number which is in every interval, which means that real number can't be on the list. This means that no complete list of real numbers can be constructed, which in turn means that the real numbers are not countable.</p>
<p>This is the same argument as yesterday, but it involves much less overhead involving compact sets and perfect sets and Euclidean spaces. If this argument makes sense but yesterday's didn't, you can look at yesterday's argument again and see how the pieces of this proof can be generalized and turned into the pieces in that proof.</p>
<p>The other argument I want to compare it to is Cantor's diagonalization, which shows that the <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#3259572740137607487">power set of the natural numbers is not countable</a>. Structurally, the argument has a lot of similarities. For the power set, the first step is to assume that the collection of subsets is countable and make a list of all of the subsets. In this case, we assume that the real numbers are countable and make a list of all of the real numbers. We then use this list to construct either a subset or a real number which both must exist but cannot be on the list. We then conclude that the assumed list cannot exist, so the power set and the real numbers are not countable.</p>
<p>The funny thing is that even though I can see that the two arguments are equivalent, the argument about power sets feels much more brain warping. I think it's the way the set not on the list is created. With power sets, it feels almost like we're using the concept of power sets against itself, but with the real numbers, the reasoning feels more straight forward. It just comes down to presenting this real number that can't be on the list. It's just like, "so you thought you got them all? Well, guess what. You missed one." The power sets feels more like, "Now that I have a list of all the subsets, I will negate them all and create a new subset by denying all of the others! Mwa ha ha ha!" It just feels much more subversive.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-78496840710324298642012-04-25T23:02:00.002-04:002012-04-26T08:44:03.136-04:00The real numbers are not countable<p>At the beginning of March, I was discussing the cardinality of infinite sets. We showed, for example, that the rational numbers, a set which appears to be much larger than the natural numbers, in fact is <a href="http://mattrolls.blogspot.com/2012_03_04_archive.html#7983479503177195012">the same size as the natural numbers</a>. We also showed that there exist <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#3259572740137607487">infinite sets which are larger than the set of natural numbers</a>. I looked at the question of whether the set of <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#7416235304646387858">real numbers is larger than the set of natural numbers</a>, but I didn't come to a definite conclusion. Today, building on the work we've been doing with set topology, we will answer that question.</p>
<p>Before I start, I want to restate some proofs that we've covered recently and that we will need here. Hopefully this way when I draw some conclusions from these theorems, they won't seem to come from out of nowhere. First, given an infinite sequence of compact sets, such that each set in the sequence is a subset of the previous set in the sequence and none of the sets are empty, the <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#9061556433481751796">intersection of all the sets in the sequence is not empty</a>. (That statement is a mouthful and kind of makes my head spin. And the example in that post is flawed. I also had a <a href="http://mattrolls.blogspot.com/2012_04_08_archive.html#3996699907516922299">follow up post</a> in which the examples work and which hopefully makes more sense, but where I don't restate the proof itself. If you can wrap your head around the example, it should make the logic in this post more clear.)</p>
<p>Another proof which we previously looked at and will need today is the proof that the <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#357107491505370697">intersection of any closed set and a compact set is itself a compact set</a>. This one is a little more straightforward, and can be visualized by drawing two rectangles on a page. Call one rectangle the closed set and the other rectangle the compact set, and then their overlapping area is also a compact set.</p>
<p>Finally, we will need the <a href="http://mattrolls.blogspot.com/2012_04_22_archive.html#5343885006584251246">Heine-Borel theorem</a>. This states that in a Euclidean space, any set which is both closed and bounded is also compact.</p>
<p>Before I begin the proof, here's a useful definition. A perfect set is a closed set in which every point in the set is a limit point of the set. The definition of a closed set is that <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#2196983878016518666">every limit point of the set is a member of the set</a>. Perfect sets go in the other direction and require that every point in the set also be a limit point of the set.</p>
<p>Our standard example of a <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#7180901320908396468">compact set</a>, the set of all numbers of the form 1/n, where n is any natural number, and the number 0, is closed, but is not perfect, because 0 is the only limit point for the set. In comparison, a <a href="http://mattrolls.blogspot.com/2012_04_15_archive.html#2461351970199731287">k-cell</a> is both compact and perfect.</p>
<p>So take some <a href="http://mattrolls.blogspot.com/2012_02_12_archive.html#996324950194249757">Euclidean space</a>. (Note that we are requiring a Euclidean space, rather than a <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#9218205607606235521">metric space</a> in general.) In that Euclidean space, take some nonempty perfect set P. We will now show that P has an infinite number of points, and that those points are not countable.</p>
<p>The first part is obvious. P is not empty, so it has at least one point. That point is a limit point of P, and therefore there must be an infinite number of points in P. To show the second part, we are going to assume the opposite and show a contradiction, so let's assume that the points in P are countable. Let's count them. <b>x</b> is any vector in our k-dimensional Euclidean space. Then <b>x</b><sub>n</sub> will be a point in P, for any natural number n. The points will be all distinct, so if a≠b, then <b>x</b><sub>a</sub>≠<b>x</b><sub>b</sub>. Since P is countable, every point in P can be labeled as <b>x</b><sub>n</sub> for some specific value of n.</p>
<p>Pick some point <b>y</b><sub>1</sub> in the Euclidean space. <b>y</b><sub>1</sub> does not have to be a member of P, but it could be. If it is, <b>y</b><sub>1</sub>=<b>x</b><sub>n</sub> for some particular value of n, but the value of n doesn't matter. Any neighborhood of <b>y</b><sub>1</sub> is the open set of all points <b>y</b> in the Euclidean space such that |<b>y</b>−<b>y</b><sub>1</sub>|<r, for some radius r greater than 0. Choose a neighborhood of <b>y</b><sub>1</sub> which includes some points in P. (It could include all of them, but it doesn't have to.) Call the neighborhood V<sub>1</sub>. V<sub>1</sub> can include points in the space which are not members of the set P, but it must also include an infinite number of points in P. Since it includes any points in P, and every point in P is a limit point of P, it must include an infinite number of points in P.</p>
<p>Now, pick some other point in V<sub>1</sub>, call it <b>y</b><sub>2</sub>. <b>y</b><sub>2</sub> again is a point in the Euclidean space, but does not necessarily have to be a member of P. <b>y</b><sub>2</sub> has a neighborhood around it, V<sub>2</sub>. Let's choose V<sub>2</sub> such that V<sub>2</sub> is a subset of V<sub>1</sub>, and V<sub>2</sub> includes some points in P, but also so the radius of V<sub>2</sub> is strictly less than the distance from <b>x</b><sub>1</sub> to <b>y</b><sub>2</sub>. Therefore, V<sub>2</sub> excludes <b>x</b><sub>1</sub>.</p>
<p>On a piece of paper, representing a Euclidean space, draw some shape and call it P. It could be a rectangle, but it doesn't have to be. It can even extend off the edge of the page. (It doesn't have to be bounded.) The important things are that P is closed, and that P doesn't have any isolated points. Label a bunch of points in P as <b>x</b><sub>1</sub>, <b>x</b><sub>2</sub>, <b>x</b><sub>3</sub>, and so forth. The claim is that we could label every point in P that way, but we want to just do enough to get the idea. Mark a point on the page and call it <b>y</b><sub>1</sub>. It will be cleaner to draw if <b>y</b><sub>1</sub> is not in P, but it could be in P if you want. Draw a circle around <b>y</b><sub>1</sub> which includes some of P and call that V<sub>1</sub>. V<sub>1</sub> could include all of P, but doesn't have to. Now, we are going to mark some other point inside V<sub>1</sub> and call that <b>y</b><sub>2</sub>, and draw a smaller circle around <b>y</b><sub>2</sub>, such that the small circle is entirely inside V<sub>1</sub>. The placement of <b>y</b><sub>2</sub> and V<sub>2</sub> are a little tricky. V<sub>2</sub> should include some points in P, but also should not include the point <b>x</b><sub>1</sub>. You always can pick <b>y</b><sub>2</sub> and V<sub>2</sub> so this is possible, but if you just grab the first point and circle that come to mind you could miss.</p>
<p>Now, keep going. For every natural number n, V<sub>n</sub> is a circle which includes some points in P. V<sub>n+1</sub> is a circle inside V<sub>n</sub> which also includes some points in P, but specifically does not include <b>x</b><sub>n</sub>. (The center of V<sub>n</sub> is <b>y</b><sub>n</sub>, but there is not necessarily a relationship between the <b>y</b>'s and the <b>x</b>'s, which are all the points in P.) Then {V<sub>n</sub>} is an infinite sequence of sets, and each set is a subset of the previous set in the sequence. This sounds suspiciously like the proof I mentioned at the top of the post, but the proof refers to compact sets, and V<sub>n</sub> is an open set instead.</p>
<p>I'm going to come back to that in a moment, but first I want to restate that for any n, <b>x</b><sub>n</sub> is not a member of V<sub>n+1</sub>. This implies that the intersection of all of the sets in the sequence of neighborhoods contains no points in P, even though each set itself does contain points in P.</p>
<p>For any n, V<sub>n</sub> is an open set. But we can turn it into a closed set, by taking the <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#552128625957700368">closure</a> of V<sub>n</sub>. V<sub>n</sub> is an open set with center <b>y</b><sub>n</sub> and radius r<sub>n</sub>, and includes any point <b>y</b> where |<b>y</b>−<b>y</b><sub>n</sub>|<r<sub>n</sub>. The closure of V<sub>n</sub> is the set of any point <b>y</b> where |<b>y</b>−<b>y</b><sub>n</sub>|≤r<sub>n</sub>. And we can work with closed sets. Importantly, the closure of V<sub>n</sub> is also a bounded set. Since the set is both closed and bounded, and we are in a Euclidean space, the Heine-Borel theorem states that the set is also compact. We know from the proof I restated above that the intersection of a closed set and a compact set is a compact set. Since the closure of V<sub>n</sub> is compact and P is closed, the intersection of the closure of V<sub>n</sub> and P is compact, for every n. For a given V<sub>n</sub>, call the intersection K<sub>n</sub>.</p>
<p>Now, look at the sequence of K<sub>n</sub>. K<sub>n</sub> is always a subset of P. K<sub>n</sub> is never an empty set, because of how it was constructed. For each n, K<sub>n+1</sub> is a subset of K<sub>n</sub>. And K<sub>n</sub> is always compact. So now the proof up top does apply, and the intersection of all the sets K<sub>n</sub> is not empty. The point in the intersection is a member of every K<sub>n</sub>, and therefore is also a member of P.</p>
<p>However, we have constructed the sequence V<sub>n</sub> such that the point <b>x</b><sub>n</sub> is not a member of V<sub>n+1</sub>. <b>x</b><sub>n</sub> is also not a member of the closure of V<sub>n+1</sub>, because the radius of V<sub>n+1</sub> is strictly less than the distance from the center of V<sub>n+1</sub> to <b>x</b><sub>n</sub>. K<sub>n+1</sub> is a subset of the closure. Therefore, <b>x</b><sub>n</sub> is never a member of K<sub>n+1</sub>, so the point <b>x</b><sub>n</sub> cannot be in the intersection of all of the K<sub>n</sub> for any value of n.</p>
<p>We have now shown that there exists some point which is a member of P in the intersection of all K<sub>n</sub>, but that no point <b>x</b><sub>n</sub> is in the intersection of all K<sub>n</sub>. Therefore there must be some point in P which is not labeled by <b>x</b><sub>n</sub>. But our starting assumption was that {<b>x</b><sub>n</sub>} included all the points in P, because P is countable. The only conclusion is that P is in fact not countable.</p>
<p>We have just proved that if P is a nonempty perfect set in a Euclidean space, then P is not countable. Some examples of uncountable perfect sets include k-cells, closed intervals, and the entire real number line.</p>
<p>Once more, for emphasis, the real numbers are not countable.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-53438850065842512462012-04-24T22:53:00.001-04:002012-04-24T22:53:47.782-04:00The Heine-Borel Theorem<p>Now that we know that <a href="http://mattrolls.blogspot.com/2012_04_15_archive.html#2461351970199731287">k-cells are compact sets</a> and that infinite subsets of compact sets have a <a href="http://mattrolls.blogspot.com/2012_04_22_archive.html#2351515444048615125">limit point in the compact set</a>, we can establish some relationships between sets in Euclidean spaces in general.</p>
<p>Suppose E is some set in some <a href="http://mattrolls.blogspot.com/2012_02_12_archive.html#996324950194249757">Euclidean space</a>, such that every infinite subset of E has a limit point in E. Last time we showed that for a compact set K, every infinite subset of K has a limit point in K, but we have not shown that this works in the opposite direction. We can't conclude yet that E must be compact. But let's see what we can prove based on this starting point.</p>
<p>Given that every infinite subset of E has a limit point in E, what can we say about E? First question: is E bounded? Well, assume that E is not bounded. (This assumption is a giveaway that we are about to prove the opposite by contradiction.) Then given any starting point p in E, we can choose any distance d, and there is always some point in E at a greater distance from p than d. Pick a point p<sub>1</sub> in E. Pick another point p<sub>2</sub> in E such that the distance from p<sub>1</sub> to p<sub>2</sub> is at least 1.</p>
<p>Then there must exist a point p<sub>3</sub> in E, such that d(p<sub>1</sub>,p<sub>3</sub>) is greater than d(p<sub>1</sub>,p<sub>2</sub>) + 1. (We need the additional distance to ensure that the points are not close to each other.) This allows us to construct an infinite sequence of points, such that the distance from any point to any other point in the sequence is at least 1. (If d(p<sub>1</sub>,p<sub>n+1</sub>)≥d(p<sub>1</sub>,p<sub>n</sub>)+1, then d(p<sub>n</sub>,p<sub>n+1</sub>)≥1 by the triangle inequality.) This sequence is a subset of E, and contains no limit points. This contradicts our premise that every infinite subset of E has a limit point in E, so the conclusion is that E must be bounded.</p>
<p>Next question: is E closed? Again, assume E is not closed, so there exists a limit point of E which is not a member of E. (The limit point is a member of the Euclidean space which contains E, but is not a member of E.) Then for every natural number n, there is a point in E such that the distance from that point to the limit point is less than 1/n. Take the set of these points for every value of n, and this is an infinite set. This infinite set is an infinite subset of E, which has a limit point, but that limit point is not a member of E.</p>
<p>Importantly, the subset has no other limit points. Pick some other point in the Euclidean space. This point is at a distance d from the limit point. There exists an n such that 1/n<d/2. All of the points in the subset which are closer to the limit point than 1/n are farther from the other point than d/2. This implies than that there can only be a finite number of points with distance less than d/2 from the other point, so the other point can't be a limit point of the set. Therefore, the subset is infinite but does not have a limit point which is a member of E. This again contradicts our premise, so E must be closed.</p>
<p>So now we've shown that if E is a set in a Euclidean space such that every infinite subset of E has a limit point in E, then E is both closed and bounded. So, if a set is compact, every infinite subset of the set has a limit point in the set. But also, if a set has the property that every infinite subset of the set has a limit point in the set, it is both bounded and closed.</p>
<p>Continuing the chain, suppose E is some set in some Euclidean space, such that E is both closed and bounded. At this point we are not making any other assumptions about E. Then E is a subset of some k-cell in that space. A k-cell looks like a box, although it can be a multidimensional box, which can be hard to think about. (Check out the iOS app <a href="http://www.fourthdimensionapp.com/">The Fourth Dimension</a> if thinking about what a 4-dimensional box looks like appeals to you.) Since E is bounded, we can set the bounds of the k-cell to the bounds of E, and we have now contained E in the k-cell. Since E is closed, it is a closed subset of the k-cell, which is compact. Therefore, <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#357107491505370697">E is also compact</a>.</p>
<p>And we have completed the loop. Take a set in a Euclidean space. If it has any one of these three properties, it must have the other two. The three properties are:</p>
<ol><li>The set is closed and bounded.</li>
<li>The set is compact.</li>
<li>Every infinite subset of the set has a limit point which is a member of the set.</li></ol>
<p>The proof that a set in a Euclidean space is closed and bounded if and only if it is compact is the Heine-Borel theorem.</p>
<p>The proof as constructed here relies on the set being in a Euclidean space. <a href="http://mattrolls.blogspot.com/2012_04_08_archive.html#3996699907516922299">As I previously encountered</a>, in the space of rational numbers with d(p,q)=|p-q|, sets can be closed and bounded without being compact, so the Heine-Borel theorem does not hold in metric spaces in general. (A set of rational numbers can have a limit point equal to an irrational number. In the real space, this set is not closed. In the rational space, the irrational number does not exist, so the set is closed, but it is no longer true that the set has a limit point at all, so the set does not have the second or third listed properties.)</p>
<p>However, we've shown that if a set is compact, every infinite subset has a limit point in the compact set, and this is true in any metric space. I have not shown, but it is also true, that if every infinite subset of a set (in any metric space) has a limit point in that set, the set is compact.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-23515154440486151252012-04-23T22:57:00.000-04:002012-04-23T22:57:50.948-04:00Infinite subsets of compact sets have limit points<p>Now that we've shown that k-cells, and in particular, closed intervals on the real number line, are compact, I feel like we have actual useful examples of compact sets. Until now we had sort of an abstract definition, and we were working off that definition to prove properties of compact sets, but they weren't really attached to anything. We also had one example which I've used a couple of times, and will use again in this post, but which feels kind of limited. In discussing the proofs I've used a square on a piece of paper, where the paper represents some metric space and the square represents some compact set. It's something of a relief that we can now say that closed rectangles on the complex plane are in fact compact sets.</p>
<p>There's one more fact about compact sets in general that I want to prove, and then we can focus on k-cells some more. Start with a compact set. Take any infinite subset of that set. That subset must have a limit point in the compact set.</p>
<p>I want to go back to the <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#7180901320908396468">first example</a> we had of a compact set to discuss this. Our compact set includes all rational numbers of the form 1/n, where n is any natural number, and also includes the number 0. Our proof that this set is compact is dependent on the fact that 0 is a limit point of the set, so any open set which contains 0 also contains an infinite number of other points in the set. Now we can turn that around and say that any infinite subset of this set must have 0 as a limit point. 0 itself doesn't have to be in the subset, but the only way we can get to an infinite number of points in the subset is by letting n go to infinity, which makes 0 a limit point of the subset. (Looking at the example, I'm happy thinking informally. I can see this is true, so I don't feel a need to work through the details formally. For the general proof, though, I should be a little more formal.)</p>
<p>For the formal proof, take any compact set and call it K. Take any infinite subset of K and call it E. Assume for the moment that E has no <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#2196983878016518666">limit points</a>. Pick a point p in K. Since E has no limit points, there exists a neighborhood of p which contains no points in E, unless p is a member of E. If p is a member of E, there exists a neighborhood of p which contains p and no other points in E. This <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#8155241196997503454">neighborhood</a> of p is an open set. For every point in K, there is an open set which contains that point, and at most one point in E. The union of all of these open sets is an open cover of K. However, no finite subcollection of these neighborhoods can be a cover of K, since there is an infinite number of points in E, and every point in E is in exactly 1 set in the open cover. Since we know that K is compact and therefore a finite subcover must exist, the conclusion is that E must have a limit point in K.</p>
<p>The limit point of E doesn't have to be a member of E, but must be a member of K. From the example, 0 is always the limit point of any infinite subset, but 0 doesn't have to be a member of the subset. However, 0 is a member of the original compact set. If 0 is not a member of the subset in this example, the subset is an open set. If 0 is a member of the subset, the subset is closed, and is therefore <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#357107491505370697">also compact</a>.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-49020543217014049892012-04-20T07:40:00.002-04:002012-04-20T07:40:47.669-04:00Friday Random Ten<p>Friday Random Ten!</p>
<ol><li>Hans Fagius - Johann Sebastian Bach: Gottes Sohn Ist Kommen, BWV 703</li>
<li>Ludwig van Beethoven: Wen Ein Holdes Weib Errungen (from Fidelio)</li>
<li>Rush - Red Sector A</li>
<li>Kammerorchester der Staatskapelle Weimar - Ludwig van Beethoven: Menuets for Orchestra, WoO 7, In G Major</li>
<li>Alain Boublil and Claude-Michel Schönberg: Lovely Ladies (from Les Misérables)</li>
<li>Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #56, "Ich Stehe Fertig"</li>
<li>William Byrd: Ave Maria</li>
<li>NDR Chorus Hamburg - Johannes Brahms: 7 Lieder, Op. 62, "All Meine Herzgedanken"</li>
<li>They Might Be Giants - Solid Liquid Gas</li>
<li>Andrew Lloyd Webber: The Music of the Night (from The Phantom of the Opera)</li></ol>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-28871917635823215902012-04-19T20:12:00.000-04:002012-04-19T20:12:01.801-04:00When proofs fail<p>Today, I learned an important math lesson. Sometimes, you will have a really great mathematical demonstration or proof in mind. You will go to a lot of trouble to write it out in detail, showing how every step works. And then when you get to the last step, you will suddenly realize that it doesn't work after all, and you have to throw everything out.</p>
<p>There was going to be a real post today. Just as I was finishing it up, I realized it doesn't actually work. Since I don't have another post lined up, this is all I can post instead.</p>
<p>This has happened before. This will happen again. This is the way of math. All you can do is hope things go better next time.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-24613519701997312872012-04-18T22:09:00.000-04:002012-04-18T22:11:49.610-04:00k-cells are compact<p>
Now we can use the result from last time to show that k-cells in Euclidean spaces are compact. First, we need to define k-cells.</p>
<p>
On the real number line, an interval is the set of points between two points, including the end points. So if a and b are real numbers, and a<b, then the point x is in the interval [a,b] if a≤x≤b. I tend to refer to "closed intervals" to emphasize that an interval is a closed set, but this is redundant. Intervals include the endpoints, and including the endpoints makes the interval a closed set.</p>
<p>
We can extend this idea to multidimensional Euclidean spaces with k-cells. Suppose we are looking at a Euclidean space with k dimensions. Then each point in the space corresponds to an ordered k-tuple of real numbers, so the point <b>x</b> can be represented by (x<sub>1</sub>,x<sub>2</sub>,…,x<sub>k</sub>) where each x<sub>i</sub> is a real number. A k-cell in this space is a closed box, containing all the points in the interior and on the sides of the box. For each dimension i, there is a minimum value a<sub>i</sub> and maximum value b<sub>i</sub>. If a<sub>i</sub>≤x<sub>i</sub>≤b<sub>i</sub> for every i from 1 to k, then <b>x</b> is a member of the k-cell.</p>
<p>
For a simple example, look at the two-dimensional plane. If (1,2) and (3,4) are opposite corners of a square, then the square is a k-cell and any point (x<sub>1</sub>,x<sub>2</sub>) is in the square if 1≤x<sub>1</sub>≤3 and 2≤x<sub>2</sub>≤4.</p>
<p>
The same reasoning that shows that intervals are closed also shows that k-cells are closed. Likewise, last time we showed that given an infinite sequence of intervals, where every interval in the sequence is a subset of the previous interval, then <a href="http://mattrolls.blogspot.com/2012_04_08_archive.html#5731411562098630689">the intersection of all of the intervals is not empty</a>. (It's either an interval or a single point.) By considering each dimension in a k-space separately, we can show that the intersection of an infinite sequence of k-cells, where each cell is a subset of the previous cell, is also not empty.</p>
<p>
Now we can show that k-cells are compact. Start with an infinite open cover of a k-cell. In two dimensions, the k-cell is a rectangle. I tend to view the sets in the open cover as circles, but they can be any shape, as long as they are open sets. The open cover is an infinite set of circles, and at least one circle overlaps every point in the rectangle. In three dimensions, the k-cell is a box, and again the open cover can be sets of any shape, but I tend to visualize spheres. Note that while we are choosing convenient shapes for the open sets, the k-cells are actually rectangles or boxes, because of how they are defined. They are not arbitrary shapes.</p>
<p>
So, we want to prove that the k-cell is <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#7180901320908396468">compact</a>. That is, given any open cover of the k-cell made of an infinite collection of sets, there is some finite subcollection of those sets which is also an open cover. As we often do, we will assume the opposite and then establish a contradiction. Begin by splitting the k-cell in half in every dimension. In one dimension, split the interval into two equal sized intervals. (A 1 dimensional k-cell is an interval on the real line.) In two dimensions, split the rectangle into four rectangles by drawing lines through the center of the rectangle in each direction. And so forth, so in general a k-cell will be divided into 2<sup>k</sup> subcells, each of which is also a k-cell.</p>
<p>
Now, look at the original open cover of the original k-cell. Since each subcell is a subset of the original k-cell, some subcollection of the open cover must be an open cover of each subcell. (The subcells share points along their borders, so they will also share sets in the open covers. The point isn't to divide the sets in the open cover up, the point is to start with one large set and one large cover, and reduce it to some smaller sets with smaller covers.) Since the open cover is infinite, at least one of the subcells must have an infinite cover. (If they were all finite, then the union of the covers of each of the subcells would be finite, and we are assuming that the open cover must be infinite.)</p>
<p>
Now we can subdivide the cell by cutting it in half in each dimension again, starting with the subcell with an infinite cover. (If there are multiple cells with infinite covers, pick one.) Two important things happen as we create an infinite sequence of subcells. First, based on what we showed last time and the extension this time, the sequence of subcells must contain at least one point from the original k-cell. Second, the size of each subcell, and therefore the distance between points in each subcell, shrinks.</p>
<p>
Look at the original k-cell, and call <b>a</b> the "bottom left" point in the k-cell, or the point (a<sub>1</sub>,a<sub>2</sub>,…,a<sub>k</sub>). Likewise, call <b>b</b> the "top right" point in the k-cell. (The quote marks are there to imply being the top or the right or whatever in every dimension.) The line from <b>a</b> to <b>b</b> is a diagonal of the cell, and the distance from <b>a</b> to <b>b</b> is the maximum distance between any two points in the cell.</p>
<p>
Every time we subdivide the k-cell, the length of the diagonal is cut in half. If the length of the original diagonal is d, then after n subdivisions, the length of the diagonal is 2<sup>−n</sup>d. So, we can construct an infinite sequence of subcells, each of which has a diagonal half the size of the previous cell, each with an infinite open cover (by our starting assumption), and each containing some fixed point from the original k-cell. (Since the intersection of all of the subcells is not empty, take a point from the infinite intersection, and that point must be in every subcell in the sequence.)</p>
<p>
That point must be a member of at least one set from the infinite open cover. (Again, if it's in multiple sets, pick one and move on.) Since that set is an <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#8155241196997503454">open set</a>, there is a neighborhood of some radius r around the point such that every point in the neighborhood is also in the open set. r is fixed, but the size of the diagonal shrinks with each subdivision. This means that eventually, the length of a diagonal of some subcell must be less than r, but the subcell contains the point we are considering, so every point in that subcell must be of distance less than r from the point.</p>
<p>
This means that the single open set which contains the point also contains every point in the subcell, so the subcell has a finite open cover (consisting of one set). Our assumption was the subcell had an infinite open cover. Now that we've shown that the open cover for the subcell is finite after all, that implies that there exists a finite open cover for the entire k-cell. Since the finite open cover exists, the k-cell is compact.</p>
<p>
I mentioned this in passing, but it's worth stating again that closed intervals on the real line are k-cells, so we've now shown that closed intervals are compact sets. I tried to use that fact previously in examples, but nothing I've proved has depended on it, and now I've proved that it is in fact true, so my examples work. In the future I'll try to do things in the correct order.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-70793514451117722992012-04-13T07:36:00.000-04:002012-04-13T07:37:38.612-04:00Friday Random Ten<p>Friday Random Ten</p>
<ol><li>Hans Fagius - Johann Sebastian Bach: Wer Nun Den Lieben Gott Lässt Walten, BWV 642/Alle Menschen Müssen Sterben, BWV 643/Ach Wie Nichtig, Ach Wie Flüchtig, BWV 644</li>
<li>Roger Waters: The Fall of the Bastille (from Ça Ira)</li>
<li>Léon Berben - Johann Sebastian Bach: The Well-Tempered Clavier, Book 2, Fugue #22 in B Flat minor</li>
<li>Eileen Rose - Last New Year's Eve</li>
<li>Coro Della Radio Svizzera - Ludwig van Beethoven: Chants Italiens WoO 99, "Quella Cetra Ah Pur Te Sei"</li>
<li>Deep Purple - Perfect Strangers</li>
<li>Ludwig van Beethoven: Ecossaise in D, WoO 22</li>
<li>Steve Earle - I Ain't Ever Satisfied</li>
<li>Primus - Last Salmon Man</li>
<li>Kris Delmhorst - Tavern</li></ol>
<p>Bonus: Pieter-Jan Belder - Wolfgang Amadeus Mozart: 12 Variations on "Twinkle, Twinkle, Little Star", KV 256. Okay, the tune is listed as "Ah, Vous Dirai-Je, Maman", but "Twinkle, Twinkle, Little Star" is one of several sets of English lyrics that use the same melody.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-57314115620986306892012-04-11T21:19:00.002-04:002012-04-11T21:27:38.539-04:00Infinite closed subintervals<p>Let's look again at the <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#9061556433481751796">theorem from last Thursday</a>, specifically as applied to subsets. Suppose K<sub>1</sub> is a compact set. Look at a closed subset of K<sub>1</sub>. We know that <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#357107491505370697">any closed subset of a compact set is itself compact</a>, so we can call the subset K<sub>2</sub>.</p>
<p>We can generalize this to K<sub>n</sub> as a compact set and K<sub>n+1</sub> as a compact subset of K<sub>n</sub>, for any natural number n, giving us an infinite sequence of compact subsets. If we specify that none of the subsets are empty, then last Thursday's result states that the intersection of all of the subsets, ∩<sub>n∈ℕ</sub> K<sub>n</sub>, is not empty.</p>
<p>On the one hand, this seems like it should be obvious. On the other hand, we had an example of a sequence of closed subsets yesterday where this is not true. It's also easy to construct a sequence of open subsets where this is not true. Let E<sub>n</sub> be the open segment from 0 to 1/n on the real number line. (For example, E<sub>4</sub> = all real numbers x such that 0<x<1/4.) Then for any natural number n, E<sub>n</sub> is not empty. Also, for any any natural number n, E<sub>n+1</sub> is a subset of E<sub>n</sub>. However, if you pick any real number greater than 0, there always exists a natural number n such that 1/n is less than the real number. Therefore, that real number is not a member of E<sub>n</sub>, so the intersection of all possible E<sub>n</sub> must be empty.</p>
<p>After looking at some examples of sequences of non-empty subsets where the intersection of the subsets is empty, it's no longer obvious that the intersection of a particular sequence of subsets must be non-empty. So we've actually proved something useful. If the sets are compact, what we naively expect to happen does in fact happen, and the intersection of the sequence of non-empty compact subsets is itself non-empty.</p>
<p>Today's goal is to show that the same thing is true for closed intervals on the real number line. We have not shown (yet) that closed intervals are in fact compact sets, so we will have to approach the problem from a different direction.</p>
<p>Suppose I<sub>1</sub> is a closed interval on the real number line. That is, for two real numbers a<sub>1</sub> and b<sub>1</sub>, where a<sub>1</sub>≤b<sub>1</sub>, I<sub>1</sub> is the set of real numbers x such that a<sub>1</sub>≤x≤b<sub>1</sub>. Next, suppose I<sub>2</sub> is a closed interval which is a subset of I<sub>1</sub>. Then I<sub>2</sub> is the set of real numbers x where a<sub>2</sub>≤x≤b<sub>2</sub>. Since I<sub>2</sub> is a subset of I<sub>1</sub>, a<sub>1</sub>≤a<sub>2</sub>≤b<sub>2</sub>≤b<sub>1</sub>.</p>
<p>We can generalize to I<sub>n</sub> for any natural number n, and say that I<sub>n+1</sub> is a subset of I<sub>n</sub>, so I<sub>n</sub>={x∈ℝ: a<sub>n</sub>≤x≤b<sub>n</sub>} and a<sub>n</sub>≤a<sub>n+1</sub>≤b<sub>n+1</sub>≤b<sub>n</sub> for all natural numbers n.</p>
<p>Now, look at the set of all a<sub>n</sub>. This set is bounded above, since a<sub>n</sub>≤b<sub>1</sub> for all n. Therefore, <a href="http://mattrolls.blogspot.com/2012_01_22_archive.html#2592851683540607437">the set has a least upper bound</a>, or supremum. Call the supremum x. The claim is that x≤b<sub>n</sub> for all n. Assume there is some number N such that x>b<sub>N</sub>. Then there exists a number y between them, so x>y>b<sub>N</sub>. Now, for all n≥N, a<sub>n</sub>≤b<sub>n</sub>, and b<sub>n</sub>≤b<sub>N</sub>. This means that y>a<sub>n</sub> for all n, so y is also an upper bound for the set of all a<sub>n</sub>. But x is the least upper bound, so y cannot exist. Therefore, x≤b<sub>n</sub> for all n.</p>
<p>This means that for all n, a<sub>n</sub>≤x≤b<sub>n</sub>. Therefore, x is a member of every I<sub>n</sub>, so x is a member of the intersection of all the I<sub>n</sub>. So we have shown what we set out to prove. Given an infinite sequence of closed intervals on the real number line, such that each interval is a subset of the previous interval, the intersection of all of the intervals contains at least one point.</p>
<p>I just want to compare the two proofs. Looking at the compact sets, the proof is dependent on lots of architecture of metric spaces. We have to use the definition of compact sets and the relationship between open sets and closed sets, and do a bunch of juggling back and forth between the different properties.</p>
<p>Looking at closed intervals on the real number line, the entire argument comes down to the facts that the real numbers are ordered, and there is always a real number between any two real numbers. This strikes me as a much simpler argument, in that it requires much less of a framework. You don't have to worry about concepts like distance functions or neighborhoods, never mind higher level abstractions like open, closed, and compact sets.</p>
<p>However, we end up with the same basic conclusion in both cases. Given a particular collection of sets, where the sets are subsets of each other, the intersection of the sets is not empty. I'm not sure if there's a profound insight here, or if all we've done is place another stepping stone toward tomorrow night's, and next week's, goals.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-39966999075169222992012-04-10T22:46:00.002-04:002012-04-10T22:59:08.228-04:00Cleaning up infinite intersections of compact sets<p>I want to clean up last week's post about <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#9061556433481751796">infinite intersections of compact sets</a>. But first I want to complain about the presentation of the material on compact sets in <cite>Principles of Mathematical Analysis</cite>. This book, or at least this chapter of the book, is significantly short on two things: motivation, and examples.</p>
<p>I'm sure Rudin knows why he's presenting all of this material here. I assume that in a few chapters, he'll be discussing continuity and say something like, "this set is compact, so it has this useful property, which allows us to conclude this result," and I'll look at it and think that the result looks like it might be kind of interesting and so I'm glad I spent so much time on compact sets. Except then I probably won't understand why the result is actually important, because he won't provide any motivation there either. And the way it's written will probably be closer to "This result follows from Theorem 2.46" and I will flip back to the theorem and have to figure out why it's relevant to the current situation. Rudin is a man of few words and doesn't feel a need to make things easy for the reader.</p>
<p>It would be easier to figure out what's actually important if I had a sense of where things were going. To a certain extent, it can be easier to follow a chain of mathematical reasoning if you start at the conclusion and work backward from there. This can end up fragmenting the thought process, so it may be necessary to develop all the pieces in reverse order, and then reassemble them in forward order so the whole chain of thinking becomes clear. Right now I don't know what the end goal is, so I'm just hanging on and hoping I pick up the right details so it makes sense when I get there.</p>
<p>In my blogging, I have a short term goal I'm working toward. I'm not saying what it is, so I'm probably as guilty as Rudin about not providing motivations. I know I can get there, but I don't yet have the full picture in my head, so I'm hoping that when I do get there, I will have already included all the necessary details. Once I reach this goal, I plan to move on to a different topic. I currently expect to get there some time next week, but last week, I thought I would get there this week, so it's turning into a moving target.</p>
<p>The second thing Rudin doesn't really bother to provide is examples. He provides the definition of compact sets, and it involves infinite collections of sets. Any time you have to talk about infinite anything in order to define something, actually understanding the definition is hard work. So it would be great to have some concrete examples to make sense of the definition. Instead Rudin launches straight into theorems about compact sets, and we're quickly looking at theorems involving infinite collections of compact sets, and this is way too much infinity to think about.</p>
<p>Which brings me back to Thursday's post. I set out to provide an example of an infinite collection of closed but not compact sets. Unfortunately, the sets in my example were not closed. My sets were based on two rational numbers p and q, taking all rational numbers x such that p ≤ x ≤ q, on the real number line. A moment's thought leads to the conclusion that these may be closed sets on the rational number line, but they are not closed on the real number line. The definition of a closed set is that <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#2196983878016518666">every limit point of the set is a member of the set</a>. Any irrational number between p and q is a limit point of this set. You could say that this is because <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#2541803397618242572">the rational numbers are dense in the real numbers</a>. But it also can be shown pretty directly from the definitions of limit points and closed sets. Since the irrational numbers are excluded from the sets as I defined them, they are not closed.</p>
<p>So let's start over, with a new collection of sets, which are actually closed. Pick a natural number n. On the real number line, take the set of all real numbers x such that x ≥ n. (Just a reminder that as I've been using it, the real number line is the set of real numbers with distance function d(p,q) = |p−q|. The real number line is a <a href="http://mattrolls.blogspot.com/2012_03_11_archive.html#9218205607606235521">metric space</a>.) The set of real numbers greater than or equal to n is a closed set. No point less than n can be a limit point of the set, and the set includes all points greater than or equal to n, so it must be closed.</p>
<p>That's one set. Now, take the collection of all sets with every starting value of n. We can number them, and say that set A<sub>1</sub>={x∈ℝ: x≥1}, A<sub>2</sub>={x∈ℝ: x≥2}, and in general A<sub>n</sub>={x∈ℝ: x≥n} for any natural number n. Since the set of natural numbers is infinite, the collection of sets is infinite.</p>
<p>Now, take some finite collection of these sets, for example, A<sub>1</sub>, A<sub>5</sub>, and A<sub>17</sub>. The real number 2 is in the first set, but not the other two. However, the real number 18 is in all three sets. 18 is a point in the intersection of the three sets, so the intersection is not empty. In general, in any finite collection of sets, there will be a set with a maximum starting point, and all real numbers greater than or equal to that starting point will be in the intersection of the sets. Any intersection of a finite collection of these sets is non-empty.</p>
<p>But let's look at the infinite collection of all the sets. For any real number x, there exists a natural number n greater than x. A<sub>n</sub> is one of the sets in the infinite collection, and x is not a member of A<sub>n</sub>, so x is not a member of the intersection of the infinite collection. This is true for any real number x, so the intersection of the infinite collection of sets is empty.</p>
<p>However, A<sub>n</sub> is closed, but it is not compact. To show that, let's construct an infinite open cover of A<sub>n</sub>, where if we remove any set in the open cover, it will no longer cover A<sub>n</sub>. Therefore no finite subcover of the infinite open cover exists, and A<sub>n</sub> is not compact. For each natural number greater than or equal n, construct an neighborhood of radius 3/4 centered on that number. (The radius has to be greater than 1/2 so all the sets overlap, but it has to be less than or equal to 1 so they don't overlap too much.) The neighborhoods are open sets, each covering part of A<sub>n</sub>. It should be clear that every real number in A<sub>n</sub> is covered by the open set centered on the nearest natural number, so the collection of all the neighborhoods is an open cover of A<sub>n</sub>. Since the set of natural numbers greater than or equal to n is an infinite set, the collection of open sets is infinite. If any set in the cover is removed, the number the set was centered on will not be covered by any other set, so no finite subcover exists. Therefore, A<sub>n</sub> is not compact.</p>
<p>My example from Thursday also failed because we haven't shown yet that closed intervals on the real number line are compact sets. We will show that soon, probably at the beginning of next week, but until then I should use a different example, of sets that we have already shown are compact. So far, we have one example, from the post where I defined <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#7180901320908396468">compact sets</a>. This is the set of all rational numbers of the form 1/n, where n is a natural number, and the number 0.</p>
<p>We can turn this into a collection of compact sets. Call K<sub>N</sub> the set of all rational numbers of the form 1/n, where n is a natural number greater than or equal to N, and the number 0. So K<sub>1</sub> is the original set, and as N increases, we chop off points from the right side of the set. Now, for any finite collection of K<sub>N</sub>, there's a maximum N, and all points of the form 1/n, where n is greater than or equal to that maximum N, are in the intersection of all the sets.</p>
<p>If we look at the collection of all of the sets K<sub>N</sub>, for any number 1/n, there is an N greater than n. Since K<sub>N</sub> is a member of the collection, no point of the form 1/n is in the intersection of the infinite collection. (Question, in case anyone is still reading: is this sufficient, or should I include an example with actual numbers substituted in for the n's and N's? In general, I'm unsure of the level of specificity I should use in my examples to make them comprehensible.) However, every set in the collection also includes the number 0, so the intersection of the infinite collection of sets consists of a single point, 0.</p>
<p>Revisiting my conclusion from last time, every one of the closed sets A<sub>n</sub> is an infinite set. And the intersection of a finite collection of these sets is an infinite set. In a finite collection, there are points which are in some of the sets but not in the intersection of the sets, so in that sense the intersection is smaller. This can be misleading, since the sets are all infinite and the cardinality of the sets is the same, so looking at the cardinality, all of the sets are the same size. In any event, the intersection of all of the infinite sets is empty.</p>
<p>In comparison, the compact sets K<sub>n</sub> are also infinite sets. The intersection of a finite collection of these sets is also infinite. However, the intersection of the infinite collection of sets is not empty. In this case, it is the single point 0. We could also construct collections of compact sets such that the intersection of the infinite collection is any finite size, or any infinite set. The point of the theorem from last time is that unlike with the closed sets, with compact sets the intersection of the infinite collection will never be empty.</p>
<p>One of my goals with my examples from Thursday was that the sets not be subsets of each other. If the compact sets are labeled by K<sub>α</sub>, the values of α don't even have to be ordered, but if they are, K<sub>n+1</sub> does not have to be a subset of K<sub>n</sub>. I abandoned that goal for my example this time, and the compact sets I've used are in fact all subsets of other sets in the collection. This is a useful special case of the theorem, but it is not a requirement of the theorem. Now that I have a working example, I can only hope that it is not overly specific.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-69110745819488610332012-04-09T13:22:00.001-04:002012-04-09T13:24:45.607-04:00Hoover completeHoover complete.Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-74525663430499382052012-04-06T07:51:00.000-04:002012-04-06T09:01:48.326-04:00Friday Random Ten<p>Friday Random Ten</p>
<ol><li>Lorraine Hunt Lieberson - Johann Sebastian Bach: Cantata #82 "Ich Habe Genug"</li>
<li>Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #29, "Wir Danken Dir, Gott, Wir Danken Dir"</li>
<li>Stephen Preston, Trevor Pinnock, Jordi Savall - Johann Sebastian Bach: Flute Sonata in E Minor, BWV 1034, Adagio Ma Non Tanto</li>
<li>The Last Goodnight - Pictures of You</li>
<li>Drain sth - Crave</li>
<li>Asuka Sakai, Ado Mizumori - A Crimson Rose and a Gin Tonic (from Katamari Fortissimo Damacy)</li>
<li>The Sixteen Choir & Orchestra - Johann Sebastian Bach: Mass in B minor, BWV 232, Et Incarnatus Est</li>
<li>Alexandre Tharaud - Erik Satie: Heures séculaires et instantanées</li>
<li>Anekdoten - King Oblivion</li>
<li>Freiburg Baroque Orchestra - Johann Sebastian Bach: Cantata #151, "Lobt Gott, Ihr Christen Allzugleich"</li></ol>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-90615564334817517962012-04-05T21:36:00.003-04:002012-04-06T07:50:58.348-04:00Intersections of compact sets<p>I have to take compact sets in small steps, which means I'm spending more time on them than I expected. There is a particular payoff that I'm working toward, but it may be a while before I get there. It feels to me like things will start being more challenging with today's post and going forward, but hopefully I'll still be able to makes sense out of it. Lots and lots of overexplaining incoming. You may be reading this and thinking, "duh, we get it. Move on." I will explain things in excessive detail to make sure that <em>I</em> get it.</p>
<p>It can't hurt to start by checking in with what we know. We know the <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#7180901320908396468">definition of compact sets</a>. We know that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#2005506085890903544">compact sets are always compact in any metric space</a>. From there, we showed that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#221896247938846024">compact sets are closed</a>. And this led to showing that <a href="http://mattrolls.blogspot.com/2012_04_01_archive.html#357107491505370697">closed subsets of compact sets are compact</a>.</p>
<p>Okay, I can't figure out a good way to get into this next fact about compact sets. I want to start with a counterexample involving closed sets in general, and then show that this counterexample does not apply to compact sets, but my counterexample feels really contrived. I don't have a good answer for why you would do this in the first place, but we're going to build an infinite set of closed, but not compact sets, such that while the intersection of any finite subcollection of these sets is non-empty, the intersection of all of the sets is empty.</p>
<p>[UPDATE: The example used in this post has several problems. First, the sets of rational numbers used in this post are not closed sets. Second, we haven't yet established that closed intervals of real numbers are compact, and that fact is what makes this example useful. Third, the sets I'm using are really ugly, which makes this example feel unmotivated. Fourth, the concluding paragraph, as written, may be misleading. I don't want to take the space to deal with all of this here, so I plan to discuss these issues in my next post.]</p>
<p>I have approximately two tools to work with, so I'm going to use them. This is one of those moments where I wish I had more tools, and I wonder if studying topology in more depth would give them to me. But I'm going to press on, and look at closed sets of rational numbers in the real number line metric space. And if I'm using rational numbers, I'll need an irrational number, and as always I'll grab the first one at hand, which is √<span style="text-decoration: overline">2</span>.<p>
<p>The goal is to build two infinite collections of sets. The sets in one collection will be mostly less than √<span style="text-decoration: overline">2</span>, but will always have some members greater than √<span style="text-decoration: overline">2</span>. The sets in the other collection will be mostly greater than √<span style="text-decoration: overline">2</span>, but will always have some members less than √<span style="text-decoration: overline">2</span>. The idea is that when we merge the two collections together, if we pick some finite collection of sets and look for where they overlap, there will always be a small overlap around √<span style="text-decoration: overline">2</span>, so any finite intersection will contain points where they overlap. However, when we take all of the sets, we can show that every point will be excluded, so the intersection of all of the sets is empty.</p>
<p>√<span style="text-decoration: overline">2</span> is an irrational number, which means that it can't be expressed as a fraction. However, we can approximate it with fractions, so we're going to look at the approximations. For any denominator, there is a largest rational number less than √<span style="text-decoration: overline">2</span>, and there is a smallest rational number greater than √<span style="text-decoration: overline">2</span>. The first few examples are: 1/1 < √<span style="text-decoration: overline">2</span> < 2/1. 2/2 < √<span style="text-decoration: overline">2</span> < 3/2. 4/3 < √<span style="text-decoration: overline">2</span> < 5/3. And so on. The important things are that we can bracket √<span style="text-decoration: overline">2</span> between two rational numbers, and that the size of the bracket gets smaller as the denominator increases.</p>
<p>Now, for each bracket, we will make two closed sets. In a particular bracket, call the smaller number p and the greater number q. p and q are both rational numbers, and both have the same denominator, n. The first closed set is the set of all rational numbers x where 1 ≤ x ≤ q. The second set is the set of all rational numbers where p ≤ x ≤ 2. Create one pair of sets for every possible denominator n.</p>
<p>Since p is always less than √<span style="text-decoration: overline">2</span>, and q is always greater than √<span style="text-decoration: overline">2</span>, if we pick any two sets and take the intersection, there will always be a set in the middle, of rational numbers greater than or equal to p and less than or equal to q, so the intersection is never empty. If we take some finite collection of sets, there will always be a greatest p and a least q, and the points between these will be in the intersection of the sets.</p>
<p>However, if we take the intersection of the infinite collection of all possible sets, then we can look at any rational number x. If x is less than √<span style="text-decoration: overline">2</span>, then there exists a rational number between x and √<span style="text-decoration: overline">2</span>, and x is not a member of the set greater than or equal to that rational number and less than or equal to 2. Likewise, if x is greater than √<span style="text-decoration: overline">2</span>, there is a set mostly less than √<span style="text-decoration: overline">2</span> which excludes x. So the intersection of all the sets does not contain any points.</p>
<p>That was a long set up to say that we can't do this with compact sets. Suppose {K<sub>α</sub>} is an infinite collection of compact sets, and the intersection of any finite collection of these sets is always nonempty. If the intersection of the infinite collection were empty, we could choose a set K from the collection, and say that the intersection of all of the other sets must have no points in common with K.</p>
<p>Okay, it's time to draw squares on a piece of paper again. Draw a square and call it K. Draw some other squares, K<sub>1</sub>, K<sub>2</sub>, …. For the sake of visualization, all of the numbered Ks should overlap at the same point, but K should not overlap that point. Strictly speaking, K should overlap all of the numbered Ks, but it's easier to draw if we ignore that, because what we really want to look at is the set where all of the other Ks overlap. This set is the intersection of all the other Ks. Now, look at the entire rest of the page. The rest of the page is a set, of course, and is the complement of the intersection of the numbered Ks. K is obviously a subset of the rest of the page.</p>
<p>Now DeMorgan's laws kick in. Symbolically, K ⊂ (∩K<sub>α</sub>)<sup>c</sup>. But (∩K<sub>α</sub>)<sup>c</sup> = ∪(K<sub>α</sub><sup>c</sup>). For any particular set K<sub>α</sub>, K<sub>α</sub> is compact, so it is closed. Therefore K<sub>α</sub><sup>c</sup> is an open set, so the union of open sets is an open cover of K. But K is compact. So a finite subcollection of the open cover is also an open cover of K. Run the sets in this finite open cover back through DeMorgan's law, and we get back to a finite subcollection of {K<sub>α</sub>}, such that the intersection of the finite subcollection does not have any points in common with K.</p>
<p>But our starting assumption was that the intersection of every finite subcollection was nonempty, and we've now constructed an empty finite intersection. This contradiction means that the infinite intersection must also be nonempty.</p>
<p>Going back to our counterexample, we haven't shown yet that closed intervals on the real number line are compact sets. We will eventually, but until then this doesn't really count as a demonstration of an infinite intersection of compact sets. However, I'm going through with it anyway. Instead of sets of rational numbers between 1 and q, and between p and 2, look at the sets of real numbers. Now every set includes √<span style="text-decoration: overline">2</span>, so the intersection of the infinite collection of sets includes √<span style="text-decoration: overline">2</span>, and is not empty.</p>
<p>The proof is constructed around arbitrary infinite collections of sets, as long as every intersection of a finite subcollection is nonempty. The particular case which is easy to visualize is a sequence where each set is a subset of the previous one. K<sub>1</sub> is a square on a page, K<sub>2</sub> is a square inside K<sub>1</sub>, K<sub>3</sub> is in K<sub>2</sub>, and so forth. With an infinite collection of squares, if the sets are compact, the squares can shrink down to a point. If the sets are closed but not compact, they can shrink down to nothing.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-3571074915053706972012-04-04T18:17:00.002-04:002012-04-04T18:24:56.044-04:00Subsets of compact sets<p>Okay, enough distractions. Let's get back to compact sets. We know that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#2005506085890903544">a compact set is compact in any metric space which contains it</a>. We also know that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#221896247938846024">compact sets are closed</a>. By implication, compact sets are closed in any metric space which contains them, which is not true of closed sets in general. This gives a relationship between a compact set and the world around it. Let's go the other direction and look at the interior of compact sets, by considering subsets of compact sets.</p>
<p>Since compact sets are closed, let's look at a closed subset of a compact set. Now it becomes important to clarify what we mean by that. Suppose X is a metric space, and K is a compact set in that metric space. If F is a subset of K, F could potentially be closed relative to K but not be closed relative to X. So let's be clear that F is closed relative to X (and therefore also closed relative to K).</p>
<p>(I don't have an example at hand of a subset of a compact set which is closed relative to the compact set but not closed relative to the space. The discussion earlier this week of closed sets on the rational number line gave examples of sets which are closed relative to the rational number space, but not closed relative to the real number space. On the other hand, the set of rational numbers is not a compact set in the real number space. I'll have to give some thought to whether it's possible to for a set to be closed relative to a compact space but not closed in the surrounding metric space.)</p>
<p>Take an open cover of F, call it {G<sub>α</sub>}. {G<sub>α</sub>} may be infinite, in which case we can use the following process to find a finite subcollection. Since F is closed in X, F<sup>c</sup> is an open set. Add F<sup>c</sup> to {G<sub>α</sub>}, and this is clearly an open cover of X. Since K is a subset of X, this is an open cover of K. Since K is compact, there is a finite subcollection of {G<sub>α</sub>} and F<sup>c</sup> which is an open cover of K. Since F is a subset of K, this finite subcollection is also an open cover of F. If F<sup>c</sup> is part of the finite open cover of K, we can remove it from the open cover of F since F<sup>c</sup> does not intersect F. The resulting finite open cover of F is a subcollection of {G<sub>α</sub>}. This is true for any possible starting open cover of F, so F is compact.</p>
<p>There's a little added bonus. Suppose F is any closed set in X. It does not have to be a subset of K. If K is a compact set in X, then K is closed in X. Then we know that <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#4841297117885384060">the intersection of F and K, F∩K, is closed in X</a>. Furthermore F∩K is a subset of K, so since it is a closed subset of a compact set, it is itself compact. If X is a metric space, F is any closed set in X, and K is any compact set in X, then F∩K is also a compact set.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-51294696593378787312012-04-03T17:48:00.001-04:002012-04-03T17:50:32.426-04:00Connected sets<p>While I'm taking an interruption from discussing compact sets, I want to pick up one more topic that I overlooked when I was talking about <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#552128625957700368">closure</a>. This is the idea of connected sets. Connectedness has an intuitive meaning, but we want to define it formally so we can use it mathematically. And as often happens, it's easier to define it by defining the opposite.</p>
<p>Let's look at separated sets. If A and B are two sets in some metric space X, they are separated if they don't touch each other. Formally, what does "don't touch each other" look like? Two sets are separated if, for both pairs of sets, the intersection of one set with the closure of the other contains no points.</p>
<p>Here are some examples on the real number line. Suppose set A is all real numbers greater than or equal to 0, and set B is all real numbers less than or equal to 0. A and B are pretty clearly not separated. For one thing, they both contain the point 0. For another, the union of the two sets is the entire real number line, and if they were separated, you would expect to be able to say that there is a gap of some kind between them.</p>
<p>Let's keep A as the set of real numbers greater than or equal to 0, but exclude 0 from B, so B is now the set of real numbers strictly less than 0. Now the sets don't have any points in common (the intersection of the two sets is the null set), but the union of the two sets is still the entire number line. There's no gap. So, the closure of B includes the point 0, and the intersection of A and the closure of B now does contain a point, so the sets are not separated.</p>
<p>Note that the closure of A is A, so the intersection of the closure of A and B still does not contain any points. That's okay. Either A∩<span style="text-decoration: overline">B</span> contains a point, or <span style="text-decoration: overline">A</span>∩B contains a point. They do not both have to contain points in order for the sets to not be separated.</p>
<p>Finally, exclude 0 from A as well. Now A is the set of real numbers strictly greater than 0, and B is the set of real numbers strictly less than zero. The union of the two sets is not the real number line, and the point 0 is a gap between the two sets. The gap has a radius of 0, but mathematically, it still exists. Now <span style="text-decoration: overline">A</span>∩<span style="text-decoration: overline">B</span> includes the point 0, but that doesn't matter. Neither A∩<span style="text-decoration: overline">B</span> nor <span style="text-decoration: overline">A</span>∩B contain any points, so the sets are separated.</p>
<p>Really, this all makes intuitive sense, and it doesn't really get more complicated with more complicated spaces or more complicated sets. Two sets do not have to overlap in order to touch each other, but there can't be a gap between them. If two sets don't touch each other, then they are separated.</p>
<p>Now that we have defined separated, we can define connected. A set E, in some metric space X, is connected if it cannot be represented as the union of two separated sets. If some sets A and B exist, such that E = A∪B and A and B are separated, then E is not a connected set. If for any two sets A and B, such that E = A∪B, A and B are never separated, then E is a connected set.</p>
<p>This definition is obvious, but it's also useful, so it's good to go through the trouble of formally defining it now.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0tag:blogger.com,1999:blog-4077108.post-18742804349108377042012-04-02T19:52:00.002-04:002012-04-02T20:07:13.528-04:00Real number line vs. rational number line<p>Last week we introduced the idea of compact sets, and we started to explore the properties of compact sets. There's more to say about compact sets, and I expect to spend most of this week discussing them. However, before I do that, I want to explore some ideas I've been kicking around comparing metric spaces of real numbers and metric spaces of rational numbers.</p>
<p>Most of my examples when discussing metric spaces for the past couple of weeks have been based on spaces of real numbers, although that has been implied in some cases. My examples involving a piece of paper and sets marked out as squares or circles on the paper are effectively a visualization of a 2 dimensional Euclidean space. Every point on the page corresponds to an ordered pair of real numbers, and the distance function for the space is the straight line distance between the two points.</p>
<p>(An aside which I'm not going to develop right now, but maybe I should someday: Roll the piece of paper into a cylinder, and measure the distance as the straight line distance through the cylinder, rather than along the surface of the cylinder. Is this a valid metric space? I assume it is, but I'd have to actually work through the math to make sure. Anyway, back to the topic at hand.)</p>
<p>The other space I've used in various examples is the real number line, which you could also call the 1 dimensional Euclidean space. I think I've also referred a couple of times to the set of rational numbers, with distance measured as the absolute value of the difference. This space is of course a subspace of the real number line, but because it has holes, it has some different properties.</p>
<p>I want to compare some sets on the real number line with sets on the rational number line, so we can see how they behave differently. Let's start on the real line with the set of real numbers greater than −2 and less than 2. This is an open set. If it included the endpoints, i.e., the set of real numbers greater than or equal to −2 and less than or equal to 2, it would be a closed set. Neither set is a valid set in the space of rational numbers, since both sets include irrational numbers.</p>
<p>On the other hand, we can look, on the rational number line, at the set of rational numbers greater than −2 and less than 2. On the rational number line, this is an open set. However, on the real number line, this set is not open. The holes in the set guarantee that in the real number space, every neighborhood of every point in a set of rational numbers is missing some points, so no set of rational numbers can ever be an open set in the real space. (Note that the set is also not closed in the real space. There is one sense in which open and closed are opposite concepts, and another in which they are not.) This gets back to the previous discussion about how <a href="http://mattrolls.blogspot.com/2012_03_18_archive.html#2578488697426485409">sets are only open or closed relative to the space in which they are defined</a>.</p>
<p>Likewise, the set of rational numbers greater than or equal to −2 and less than or equal to 2 is a closed set in the rational number line space, but is not closed in the real number line space. Closed sets are slightly different than open sets, however. It is possible for a set to be closed on both the rational number line and on the real number line. For example, a set of isolated points can have no limit points, and will therefore be closed in either space.</p>
<p>Okay, now let's look on the rational number line at the set of numbers which is greater than −√<span style="text-decoration: overline">2</span> and less than √<span style="text-decoration: overline">2</span>. The critical thing is that since √<span style="text-decoration: overline">2</span> is not a rational number, this set is both open and closed on the rational line. It should be obvious that it is open. It is closed because every rational number which is a limit point of the set is a member of the set. Since √<span style="text-decoration: overline">2</span> is not a rational number, it does not exist in the rational number space, and therefore cannot be a limit point of the set. Once again, of course, this set is neither closed nor open on the real line. Sets of real numbers between −√<span style="text-decoration: overline">2</span> and √<span style="text-decoration: overline">2</span> can be either open or closed, depending on whether the set includes the end points. If the set includes one endpoint but not the other, it's neither open nor closed, but it can't be both open and closed.</p>
<p>Bringing this back to more recent topics, let's look at whether the set of rational numbers greater or equal to −2 and less than or equal to 2 is compact. We know that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#2005506085890903544">if it is compact in one space, it is compact in every space</a>. We also know that <a href="http://mattrolls.blogspot.com/2012_03_25_archive.html#221896247938846024">if it is compact, it is closed</a>. Since it is not closed on the real number line, it can't be compact, but I want to take a look at the reason why.</p>
<p>Let's look at the set on the real number line. Once again, we're going to make use of our favorite irrational number, √<span style="text-decoration: overline">2</span>. We are going to build an open cover of the set which does not cover √<span style="text-decoration: overline">2</span>, and we are going to build it specifically so that no finite subcollection of the open cover is also an open cover.</p>
<p>We are going to define the open cover inductively. We are going to start by creating a neighborhood of the number 2. For the radius of the neighborhood, we will pick some rational number less than half the distance from 2 to √<span style="text-decoration: overline">2</span>. We can try to be greedy and pick a number which is close to half the distance, but we can pick a smaller number too. It will work out the same. Let's pick 1/4. Now, the point 2 − 1/4 is a rational number, and is not included in the neighborhood of 2. (Neighborhoods are open sets, and don't include points on the edge of the set.) However, the neighborhood includes all the points greater than 1 3/4. So let's do it again. Set 1 3/4 as the center of a neighborhood and set the radius to a rational number less than half the distance to √<span style="text-decoration: overline">2</span>.</p>
<p>It should be clear that after any finite number of neighborhoods is created, there will be some maximum rational number greater than √<span style="text-decoration: overline">2</span> which is not in any of the neighborhoods, but for which all rational numbers greater than that number are in one of the created neighborhoods. (If the words don't make sense, draw a picture and it should be clear.) However, for any rational number greater than √<span style="text-decoration: overline">2</span>, there is also a finite number of neighborhoods after which the number will be included in one of the sets.</p>
<p>We could build a similar collection of sets coming from the other direction, but we don't even have to. We can just take the neighborhood of −2, with radius 2+√<span style="text-decoration: overline">2</span>, and we'll pick up all of the rational numbers greater or equal to −2 and less than √<span style="text-decoration: overline">2</span>. So now we have an open cover of the set of rational numbers greater than or equal to −2 and less than or equal to 2. This collection of sets was constructed to exclude √<span style="text-decoration: overline">2</span>, which is not a problem because √<span style="text-decoration: overline">2</span> is not rational. But the collection was also constructed to be infinite, and so that no finite subcollection would be an open cover of the set of rational numbers greater than or equal to −2 and less than or equal to 2. Therefore, the set of rational numbers greater than or equal to −2 and less than or equal to 2 is not a compact set.</p>
<p>Note that the same definitions of neighborhoods, each with the same center and radius, also builds an open cover of the set on the rational line. There's a slight conceptual difference, because the neighborhoods on the real line are of all real numbers, but the neighborhoods on the rational line are just of rational numbers. It also doesn't quite make sense to say that the open cover on the rational line excludes √<span style="text-decoration: overline">2</span>, since √<span style="text-decoration: overline">2</span> is not a point on the rational line, but it is true that all of the neighborhoods with centers greater than √<span style="text-decoration: overline">2</span> overlap, and all of the neighborhoods (if we constructed more than one) with centers less than √<span style="text-decoration: overline">2</span> overlap, but no neighborhood with a center greater than √<span style="text-decoration: overline">2</span> overlaps a neighborhood with a center less than √<span style="text-decoration: overline">2</span>. And this is a topic which leads us to tomorrow's digression.</p>Matthewhttp://www.blogger.com/profile/10856242890984796481noreply@blogger.com0