So far, we have talked about how “big” a set is in terms of whether it has an infinite number of elements, and (if infinite) how big that infinity is. There are other kinds of “size” to sets though - for example, if we are looking at subsets of the real line, we can ask, “How long is that subset”? “How long” is in some ways a strange question to ask. For example, if we ask how long the set of real numbers between 0 and 1 is (including 0 and 1,) our answer seems pretty obvious - it is of length 1.
Some problems arise however when we change it up even a little bit. How long, for example, is the set of numbers between 0 and 1, not including 0 and 1 [Set A]? Or how long is the set of numbers between 0 and 1 and between 2 and 3 (including all of those end points) [Set B]? How long is the set just consisting of the number 1 [Set C]?
Intuitively, we would guess that the length of Set A is 1, the length of Set B is 2, and the length of set C is 0. One way we could answer this is to just assign a length to an interval on the real line - an interval is any set of numbers between two real numbers a and b, either including the endpoints a and b or not - to be the number a-b. This gives us all of our intuitively guessed lengths for the Sets A, B, and C above.
However, sometimes we’ll still run in to sets that we can’t deal with! How big, for example, is the set 1, 1/2, 1/4, 1/8, 1/16, etc? (Just in case you missed the pattern, these are all of the reciprocals of powers of two!) If we look at it, we see that it’s not an interval, but it does seem to have a size - specifically, we can put it inside open intervals (where “open” just means that our set doesn’t include the end points,) that are as small as we want. For example, let’s say we want to put this set inside intervals whose lengths sum up to only 1/100. Here’s what we could do:
Since 1/2^8=1/256, and every single fraction in our set with a power higher than 8 is smaller than that, let’s take part of our set to be an open interval from 0 to 1/200. This has covered 1/256, 1/512, 1/1024, etc. The only numbers in our set that aren’t in that interval are 1, 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, and 1/128. However, we’ve only used up half our our allowed interval - we’ve got another length of 1/200 that we can break up and cover these numbers however we want! We only have eight of them, so we make eight intervals, each of length 1/8th of 1/200 (for the curious, 1/1600, which is getting quite small!) and put them so that these remaining 8 numbers are at the center of these 8 intervals.
Voila! We’re done! We’ve covered our entire set with intervals whose lengths sum up to only 1/100.
Exercise 1: Repeat this, but trying to get all of the numbers in this set to fit inside a set of intervals whose lengths sum to only 1/1000. Can you do this for any number? How?
The term that mathematicians use for this kind of “size” is called the “measure” of a set - specifically, at least for this kind of measurement, the measure of a set is the sum of the lengths of the smallest set of open intervals that we can fit the set inside. If we can keep making this smaller and smaller and smaller, getting really close to some number (in the example above, that number was zero, by the way,) that is the “length” or measure of our set.
This was somewhat interesting, but not incredibly difficult. There are a few other interesting questions to ask, but all of them are a little difficult to prove here, so we can leave you with one bizarre fact - try to prove it!
The natural next question to ask is whether or not, if a set has length zero, does it have to be countable? Surprisingly, the answer is no, and this answer will lead us to a much, much more bizarre paradox.
The Cantor Set:
You might have heard of the Cantor set before - it is also called “the Middle Thirds” set. We can construct finite approximations of the set (we can’t really draw it, as we’ll see in a minute,) by doing the following:
1. Draw a line.
2.Remove the middle third.
3.Remove the middle third of both of the two remaining pieces.
4.Remove the middle third of all four of our remaining pieces.
5.Remove the middle third of all eight of the remaining pieces.
6.Remove... You get the idea.
Here’s a picture of the first four stages of our drawing the Cantor set:
Why would this set be interesting?
Well, for starters, let’s consider it’s length. At each stage, it looks like the sum of 2^{n} intervals, all of length (1/3)^{n}.
Exercise 2: Knowing that, how long is our Cantor set at the zeroth stage? How about the first stage? Second stage? Third stage? What is the general formula for our length of the Cantor set at any stage n?
Okay, if you worked out the formula (or looked at the picture,) you realize that as we get to larger and larger stages, the length of our set gets very, very small. If we went on forever, the lengths of our sets would get as close as we want to zero - so the Cantor set, which is the set we’d get if we did this forever, must have length zero.
Exercise 3: How many end points for our set at the nth stage? Just to make it clear, looking at the pictures, you can see that at the zeroth stage there are two, at the first stage there are four, at the second stage there are eight, and so on. Write a quick formula.
You’ll notice that once we have an endpoint, it never goes away - since we’re always removing the MIDDLE thirds, our endpoints are going to stay in our Cantor set. This gives us a minimal number of points that must be there - if you figured out the formula, you probably realize that the number of endpoints, by the end, is going to be countably large. Are these endpoints our entire Cantor set, at the end?
Surprisingly, the answer to that is no. We are going to show this by giving ourselves an injective map from our set of decimals between 0 and 1, written in base 2 (so every number like 0.11101000100... or 0.00001000....) We already know from our previous lesson that there are uncountably many of these (more of them than the natural numbers.) Also, from our previous lesson, we should remember that if we can make a map from one set A to another set B which doesn’t send any two elements of A to the same element of B, then the set B must be larger than or equal to our set A in size.
So let’s get started.
To begin, let’s be careful. When we are writing out our base 2 decimals, we need to remember that 0.001111111.... (repeating) is the same as 0.010000 (repeating) - much the same way as, in base 10 decimals, 0.9999999=1. To prevent us from accidentally sending the same decimal to two different points in our Cantor set (which would mean we didn’t really have a function!) we will always assume that we don’t have infinitely many 1’s repeating in our representation of our number.
We now will define our map from our decimals x in [0,1] to our Cantor set C.
Let x=a_1a_2a_3...., where a_1, a_2, a_3, and so on are all just 0 or 1. We will figure out where in our Cantor set to map x by following this sequence. Put x in the left half if a_1=0 and x in the right half if a_1=1. (We are just going to get closer and closer to our point x by following this chain.) Whichever side x ended up on, put x in the left half of THAT side if a_2=0 and in the right half of that side if a_2=1. We keep doing this, figuring out which side of our smaller interval x will be mapping in to by considering the next decimal in our expansion of x.
If we kept doing this, at each new stage, x must be in an interval 1/3 as long as the previous stage. This means, by stage n, we know within (1/3)^{n} where x must map to. In this limit, this number will go to zero - so we know EXACTLY where x must be!
While this sounds a little handwavy, try it yourself - write out a number up to the fifth decimal place (imagine there are zeroes after that) - and see if you can figure out where x would be in your Cantor set. You should see pretty quickly that we can’t get to the same point in the Cantor set with two different decimals - so our map must be injective, and the Cantor set is at LEAST as big as the decimals between 0 and 1, and hence, must be UNCOUNTABLE!
The Devil’s Staircase:
This next part will have us encountering one of the strangest functions you may ever come across - the Devil’s Staircase, also sometimes referred to as the Cantor function. It is part of a much larger class of functions called “singular functions” - functions which are continuous (we could draw them without ever picking up our pencil from the paper) but still have a large number of points where their slope isn’t defined.
We will try to steer clear of any heavy calculus, as all we need to understand this example is the idea of something with slope zero - a flat, non-increasing function which has a constant value between some pair of points.
Seems simple enough!
We will build our Staircase iteratively (in stages, just like our Cantor set.) At stage 1, we will just draw in the values of our function at the endpoints 0 and 1. Their values, surprisingly enough, will be 0 and 1.
So far, we have that f(0)=0 and f(1)=1, and that’s it.
For stage 2, it’s a little harder, but not much. We will look at all of the points we REMOVED from our line in the first stage of our construction of the Cantor set, along with their endpoints - all of the points in the interval [1/3,2/3]. We will set our function’s values to 1/2 between those two points.
Now we have f(0)=0, f(1)=1, and f(x)=1/2 for all x in [1/3, 2/3].
We can see a natural way to continue, giving our function the value 1/4 on [1/9, 2/9] and the value 3/4 on [7/9,8/9]. Continuing, you can see the fourth iteration as well immediately below.
Exercise 4: What are the exact domain of our function at the fourth stage (i.e. where is f defined so far) and what are the values of the function? What would we do next?
If we continued this forever, we still wouldn’t define our entire function - remember, we are only defining it on all of the pieces we removed while making our Cantor set, as well as on all of the endpoints of the Cantor set. We have already showed that we have more points in the Cantor set than just the endpoints, so there must be (uncountably) many points left over that we haven’t defined our values for yet.
Everywhere we DID define our function though, if we weren’t on an endpoint, had a slope of zero. Now all that remains is to “fill in the blanks.” There is something called “continuous completion” of a function, which is where we “fill in the blanks” in a natural way. We can do that here, giving us a continuous function with some bizarre properties: (1) continuous and (2) a slope of almost everywhere zero, but (3) increasing from 0 to 1 on the interval!
Lesson 3: The Devil's Staircase & Other Uncountable Problems
7/31/09
After we talk about the Cantor Set (a special, very famous subset of numbers between 0 and 1,) we can talk about an amazing function that is continuous and has slope zero everywhere the slope is defined, but somehow gets bigger and bigger as we go to the right!