7:33 AM

Friday Random Ten!

1. Coro Della Radio Svizzera - Ludwig van Beethoven: Chants Italiens WoO 99, "Giura Il Nocchier"
2. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #104, "Beglückte Herde, Jesu Schafe"
3. Spin Doctors - What Time Is It?
4. Brian May - Last Horizon
5. Moby - If Things Were Perfect
6. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #85, "Wenn Die Mietlinge Schlafen"
7. Hans Fagius - Johann Sebastian Bach: Prelude and Fugue in E Minor, BWV 548, Fugue
8. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #88, "Was Kann Dich Denn"
9. Léon Berben - Johann Sebastian Bach: The Well-Tempered Clavier, Book 2, Fugue #21 in B Flat
10. Leela James - Tell Me You Love Me

0 comments

7:35 PM

Our goal is to show that there exist infinite sets that are not countable. In other words, there is no one-to-one, onto mapping between the two sets. Since there can be no infinite set smaller than the natural numbers, we are looking at sets larger than the natural numbers, i.e. no function from the naturals to the set can be onto, or no function from the set to the natural numbers can be one-to-one.

Phrased differently, the first statement implies that a function with the domain of the natural numbers and codomain of an uncountable set must have an uncountable subset in the codomain which is not part of the range. Even if the function is one-to-one, so every point in the domain maps to a distinct point in the range, the function can't hit every point in the codomain, and in fact must miss uncountably many points. (If the points that are not in the range are countable, then the uncountable set could be constructed as the union of two countable sets, and would therefore be countable.)

The second statement implies that any function with the domain of an uncountable set and codomain of the natural numbers must match an uncountable set to at least one natural number, even if the range is equal to the codomain. This is more or less the same thing as the first statement read backward. If the uncountable set is the domain of the function, every point in that set must go to one of the natural numbers. If the function is one-to-one, it must run out of natural numbers before it runs out of points in the uncountable set. Furthermore, even if it matches a countable set to every natural number, that can't include all of the points in the uncountable set, because then the set could be written as a union of countable sets, and would therefore be countable.

In order to show that uncountable sets exist, we need to develop a couple of other concepts first. The first concept is the power set, which I've mentioned briefly before. We've looked at various subsets of sets. In particular, when we looked at set functions, the function operates on any subset of the set. The collection of all possible subsets of a set is called a power set.

Let's look at a really simple example. Start with a set with three points, call them 1, 2, and 3. If we call the set A, then A={1,2,3}. The possible subsets of A include each point individually, or {1}, {2}, and {3}. The subsets also include each pair of points, or {1,2}, {1,3}, and {2,3}. Finally, the subsets include the null set, ∅, and A itself. The power set of A, written ℘(A), is a set of sets with 8 members, each member of which is a set. ℘(A)={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.

The power set is obviously bigger than the original set in this case. For any finite set of size n, the size of the power set is 2ⁿ. I could formally prove it with induction, but I'll skip the proof for now. If I decide I have a good reason for it, I might come back to it later.

This has an implication, which I mentioned a couple of posts ago, about unions of finite sets. Start with a finite set of points. List every possible distinct subset of points. This is the power set of the original set, and it is finite. Therefore, as I previously stated, if you have a countable collection of distinct sets, even if each set is finite, the union of all the sets must have a countable number of points. If the union was finite, then the power set of the points would be finite, and we couldn't have started from a countable collection of distinct sets. (To avoid confusion, I will restate that the word countable implies infinite.)

The cardinality of the power set of any finite set is greater than the cardinality of the set itself. The question is, what happens with countable sets? Our previous experience with countable sets might give the expectation that the power set is also countable. On the other hand, I started this post the way I did for a reason.

Unfortunately, I'm out of time. See you next time.

0 comments

6:07 PM

Last time, we showed that if you have a countable collection of sets, and each set has a countable number of members, the union of all the sets is countable. Now I'm going to use this fact to show that the set of all rational numbers is countable. There are multiple ways you could approach this, but I'm going to do it in two steps. This is both to get a little more experience working with infinite sets, and also to reinforce the counterintuitive nature of infinity.

First, I will show that all rational numbers strictly greater than zero and less than or equal to one are countable. By definition, any rational number can be written in the form p/q, where p and q are both integers and q≠0. If we restrict q to the natural numbers (the same as the positive integers) and we restrict p to the natural numbers less than or equal to q, then we have the set of all rational numbers greater than zero and less than or equal to one. Note that we have lots of duplication. This set includes both 1/1 and 2/2, and they are of course the same number. That won't be a problem. The important thing is that we aren't missing any rational numbers in that range.

Now, we are going to divide this set of rational numbers into subsets. The rule is simple. Subset q gets all all the numbers with q as a denominator. So subset 1 consists only of the number 1/1, subset 2 includes 1/2 and 2/2, and so on. There are two important facts here. 1. Every rational number greater than 0 and less than or equal to 1 is in one of these sets. 2. Each set is finite, and the total number of sets is countable.

This means we can use the theorem established last time to immediately state that the union of all the subsets is countable. Since the union is equal to the set of all the rational numbers greater than 0 and less than or equal to 1, that set is countable.

If we want to, we can look at the map in more detail. This is just like running up the diagonals in the ordered pairs of natural numbers, but there are a lot of holes. 1/1 maps to 1. 1/2 maps to 2. 2/1 would map to 3, but 2/1 isn't in our set, so nothing maps to 3. 1/3 maps to 4. 2/2 would map to 5, but again, 2/2 = 1/1, and since 1/1 is already in our set, we will map nothing to 5. And so on. Ultimately, we are mapping this infinite set of rational numbers to a subset of the natural numbers. But since any infinite subset of the natural numbers is countable, and this mapping is one-to-one, we can conclude that this set of rational numbers is countable.

We've shown that this set of rational numbers is countable. But what about the set of all the rational numbers? Well, there are countably many rational numbers greater than 0 and less than or equal to 1, but there is exactly 1 natural number in that range. So the rational numbers have a pretty big head start over the natural numbers.

There are, of course, countably many rational numbers greater than 1 and less than or equal to 2, but when we take the union of the set between 0 and 1 and the set between 1 and 2, we get the set greater than 0 but less than or equal to 2, which is countable, since the union of countable sets is countable. So we haven't actually gained anything.

Meanwhile, the set of natural numbers less than or equal to 2 now has 2 members. It's still a long way off, but maybe it's a little closer? Not really. The difference in cardinality between any finite set and a countable set is essentially the same. One finite set might be larger than another finite set, but they're still both a whole different class than a countable set.

But we know where this is going. A union of a countable collection of sets, each with a countable number of members, is countable. Therefore, the set of all rational numbers is countable. Meanwhile, the union of a countable collection of sets, even if each set contains only one member, is also countable. So if we extend this exercise out to there, the natural numbers are a countable set assembled from a countable number of sets of one member each.

As we are constructing the rational numbers as unions of sets, there are many apparent opportunities for the rationals to show that they are a larger set than the natural numbers, but it never works out. I'm going to run this in the opposite direction for the moment, and point out that this implies than any countable set can be subdivided into countably many disjoint subsets, each of which is countable. (The fact that the subsets are disjoint means that each member of the original set appears in only one subset.) So you can blow your mind by packing down some giant, but countable, set into some smaller countable set. You can also blow your mind by splintering a countable set into countable slivers of sets, and each sliver can be the same size as the original set.

By now you may be wondering if, indeed, any infinite sets are not countable. That's an excellent question, which we will consider next time.

4 comments

6:56 PM

Last time, we showed that the set of all ordered pairs of natural numbers is countable, or that it has the same cardinality as the set of natural numbers. This is true despite the fact that it appears that there should be infinitely times as many ordered pairs. (This is one reason why we don't usually consider infinity to be a number. It breaks the rules we expect for numbers.) Let's turn this into a general principle.

Start with one set of points. Assume that the points in the set are countable, so there's a one-to-one, onto mapping from the set of points to the set of natural numbers. We call the set X, we can call all the individual points x₁, x₂, x₃, and so on. I'm not really specifying what the x's are, but since they are countable, I can use the natural numbers as indexes to specify which point I'm referring to. (I discussed indexes briefly a couple of weeks ago.) The actual x's could be the even numbers, or a different ordering of the natural numbers, or the square roots of all of the natural numbers, or ordered pairs of natural numbers, or something which isn't even number-like, as long as they are countable, whatever they are.

Next, instead of one set with a countable number of points, assume we have a countable number of sets, each with a countable number of points. Instead of X, we have X_λ, where different values of λ correspond to different sets. When specifying a point, we need to specify both which set it came from and which point in that set it is, so we can use the notation x_{λ, n}. λ specifies the set, and n specifies the point in that set.

Now, the sets are countable. That means that the possible values of λ correspond to natural numbers. And the number of points in each set is countable, which means that the possible values for n are the natural numbers. This means that the ordered pair (λ, n) corresponds to the point x_{λ, n}, and the ordered pairs are of natural numbers, so every point in any of the sets corresponds to an ordered pair of natural numbers. This means that the points are countable.

We have just shown that the union of a countable number of sets of a countable number of points is a countable set.

We should explore this in a little more detail. X_α is a member of the collection X_λ, where α is a member of the set of possible values for λ. We don't really have to go into the details of what the set of values for λ look like, as long as the set is countable. The point x_{α, k} is a point in the set X_α, where k is some natural number. Then there exists a function that maps the union of all X_λ to the natural numbers. The first step is the function f(x_{α, k}) = (α, k), which maps each point to an ordered pair. We can then map the ordered pair to a natural number using the mapping described last time.

Looking back at the ordered pairs of natural numbers from last time, the first grouping we looked at was vertical lines. For a given natural number h, take all possible natural numbers k, then the set of (h,k) lies on a vertical line. This is conceptually the same as looking at the set X_α, where α maps onto the natural number h, and all possible values of k for members in that set. By taking a set of lines that are finite length diagonals rather than infinitely long verticals, we can then traverse all of the points in all of the sets.

There has been an implied assumption here that none of the sets have the same points. In other words, if α≠β, then x_{α, h} never equals x_{β, k}, for any values of α, β, h, and k. The problem is that if x_{α, h} = x_{β, k}, we will hit that point twice in the process of traversing all the sets, so we will map that single point to two different natural numbers and we won't have a function at all.

This is not actually a problem. If a point exists in more than one set, we can map that point to a natural number the first time we hit it, and skip it on all future times. When we skip the point, we will also skip the natural number it would be associated with. This means that our mapping will not be onto, since there are some natural numbers we are skipping. But this is not a problem since we have shown that the cardinality of an infinite subset of the natural numbers is the same as the natural numbers.

While we're at it, some or all of the sets can be finite instead of infinite, and everything still works. When we run out of points in a set, we just skip the natural numbers that would correspond to additional points in that set, but we're still good. And as long as some of the sets are infinite, we can have a finite number of sets, and the mapping still works. (To back this claim up, we should show that the union of a countable collection of distinct sets of a finite number of points must have a countable set of points, even if every point appears in multiple sets. I'll come back to this soon, when I discuss power sets.)

However, if we have a finite number of sets, and the number of points in every set is finite, then the total number of points in the union of the sets is also finite. Eventually we'll just run out of points. There are some limits.

In conclusion, the union of a finite or countable collection of sets, each containing a finite or countable number of points, is finite or countable. This means that sets which at first glance are much bigger than the set of natural numbers are in fact the same size as the natural numbers. Next time, we will use this fact to show that the rational numbers are countable.

0 comments

6:13 PM

Last time we looked at infinite sets which seem like they should be smaller than the natural numbers, and concluded that they are actually the same size. Since size is a weird concept applied to infinite sets, it might be better to say that they have the same cardinality instead. This time, we're going to look at some sets which seem like they might be bigger than the natural numbers.

The first candidate is the integers, but I'm not going to waste time with them because I have bigger targets in mind. I'll just point out that the sequence 0, 1, -1, 2, -2, … gives a one-to-one, onto mapping onto the natural numbers, and move on. I could give a formal proof, but I want to look at a more interesting problem instead.

Take the set of all ordered pairs of natural numbers. This includes all pairs of the form (p, q), where p and q are both any natural number. At first glance, this set is way bigger than the natural numbers. The integers looked twice as big as the natural numbers, but turn out to be the same size, but ordered pairs look infinitely bigger. Pick a number n. Then take all of the ordered pairs (n, q), where q is any natural number. We now have a mapping that maps an infinite number of ordered pairs to each natural numbers, so surely this is enough to show that there are infinitely more ordered pairs than natural numbers, right?

Wrong. If we picture the ordered pairs as a grid of points, the points on the left edge of the grid is pairs of the form (1, q), for all natural numbers q, and the bottom edge is pairs of the form (p, 1), for all natural numbers p. The grid extends infinitely far to the right and up, and every pair (p, q) is represented by one point in the grid. The mapping suggested above can be represented by a series of vertical lines, each of which is infinitely long. There are also infinitely many lines, but the end result is that every point on the grid is on one of the lines.

Instead of vertical lines, draw diagonal lines on the grid. Each line starts on the point (n, 1) and continues across the grid to the point (1, n). Each line therefore passes through all of the points of the form (p, q), where p+q=n+1. (If you can't visualize this, draw it on a piece of paper and it should be clear.) Therefore, every point (p, q) is on one of these lines, and there are an infinite number of lines, but now the number of points on each line is finite. That means that we can start with the first line, which only goes through the point (1, 1), and start counting them off. The first line goes through the point (1, 1), the second goes through (2, 1) and (1, 2), the third through (3, 1), (2, 2), and (1, 3), and so on. We have a sequence that will hit every point on the grid, or every ordered pair. We can run it in both directions, so given an ordered pair, we can find which natural number it corresponds to, and given a natural number, we can find the ordered pair it matches. If we wanted to do it formally, we could work out the exact formulas, but I'm comfortable skipping the details here.

We just showed that a set which has one mapping to the natural numbers which maps an infinite number of points to each number also has a different mapping which maps exactly one point to each number. If your head is exploding right now, that's normal. This makes no sense. I know that I had to see this multiple times before I felt like I really understood what's going on here. If you want to play around with the cardinality of countable sets, the Hilbert hotel can give you practice mixing and matching infinite sets.

I'll give you some time to make sense of this. Next time, I'll look at a generalization of what we did here with ordered pairs.

3 comments