Countable Sets

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: OK. So we come to the idea of countable sets, which are the most familiar kind of infinite sets. And a countable set is one where you can list the elements-- a0, a1, a2 and so on. So there's a list of all of the elements of A in which every element in A appears at some point. You can count up to any given element of A, and every element of A you will eventually get to, you'll be able to count up to it. So it's just a matter of listing it.

And the technical definition of "A is countable" is if there's a bijection between A and the non-negative integers. Because this listing, in effect, really is a mapping from the non-negative integers to A. 0 is a0, 1 maps to a1, 2 maps to a2, and implicitly there's a bijection being indicated here. That's assuming that all of the [? a's ?] are distinct for it to be a bijection.

So we also have, as a special case, the finite sets are also considered to be countable. So really, if n is a bijection to A, then A is called countably infinite. The other possibility is that A is finite. And the two together, I just say A is countable.

So what we've just figured out, then, from the previous examples, is that the positive integers are countable. And all the integers are countable, because in both cases we exhibited bijections to the non-negative integers.

Another important and not very hard example is the set of finite binary words. So we use this notation, "0, 1 star," meaning all the finite-- star means all the finite sequences of these elements, 0 and 1. So this is just the finite binary words.

How are they countable? Well, I need a way to be able to list them in some orderly way.

Well, let's just do it by length. Let's begin by listing the empty word, or string, of length zero. And then I'm going to list all the one-bit strings, the strings of length one. And there are two of those.

So let the second element, the next element of the list after the empty string, be 0, and then let the next element after that be 1.

Then let's list all the length two strings. Well, there's four length two binary strings. And let's just list them in some sensible order-- say, by their binary representation. And then keep going. List all the length three binary strings-- there's eight of those. And finally, keep going up until you get to the length n binary strings, of which there are 2 to the n.

And this is a description of a way to list, one after another, all of the finite binary words, or finite binary strings. And that listing is implicitly a description of a bijection from the non-negative integers n to the nth element in my listing. And that's a bijection, so the binary words are countable.

Another example of a countable set is the pairs of non-negative integers. So how can-- now I've got the non-negative integers. I've got to find a bijection of pairs of non-negative integers. How am I going to do that?

Well, it's the same idea as we used with binary strings. There's a bunch of ways to prove it, but let's just propagate the binary string idea. Let's start listing the pairs of non-negative integers. And after 0, 0, I'm going to list two pairs-- 0, 1 and 1, 0. And after them, I'm going to list three pairs-- 0, 2, 2, 0, and 1, 1. And after them, 0, 3, 3, 0, 1, 2, 2, 1.

And if you can see what I'm doing, I'm basically listing the pairs in the order of the sum of their coordinates. So the nth block of pairs that I'm going to list will be the pairs the sum of whose two coordinates is n. There'll be n plus one of those. And I keep going in this way.

This is a nice orderly description of-- or a description of a nice orderly way to list all of the pairs of non-negative integers. Within a block, invent some alphabetical rule for listing the pairs. So I'm going to-- I've hinted at a rule here for listing the finite set of pairs whose sum is n, and you can invent-- any one will do. So that tells us that we have a bijection between the non-negative integers and the pairs of non-negative integers. So that's another important bijection.

Now, when you're trying to prove countability, it's very useful to have the following lemma, which gives an alternative characterization of countability-- namely, a set A is countable if and only if you can list A allowing repeats. Remember, our original definition is that you can list A without repeats if it's infinite, or else it's finite. So that was-- the bijection between the non-negative integers and A, in effect, is saying that that's a listing of all of an infinite set A with no repeats, because it's a bijection we're mapping. If an element appeared twice, we'd have two different non-negative integers mapping to it, which would break the bijection property, the injection property.

And so suppose we allow repeats. And the claim is that that's fine, because you can fix that. So the lemma says that, if there's a surjective function from the non-negative integers to A, then A is countable.

Well, let's just check quickly in one direction. If A is finite, then there's clearly a surjective function from the non-negative integers to A. There's lots of extra non-negative integers you don't need. If it's a finite set, like 10 elements in A, map 0 through 9 to those 10 elements, and map every other non-negative integer, say, to 10th element, or last element, of A.

So there's certainly a surjection if A is finite. Now, suppose that A is infinite, and I have a surjection from the non-negative integers to A. So I'm listing A with repeats. And I'm supposed to have a bijection if it matches the other definition. How do you do that?

Well, if you're a computer scientist, you know how to change a sequence with repeats into a sequence without repeats. You just filter it for duplicates, going from left to right. Take this infinite sequence of elements of A in which there are repeats, and keep only the first occurrence of each element. That will define a bijection with the non-negative integers if a is infinite. And that's how we prove this lemma, which I'm just going to settle for talking through.

So now we have another convenient way to show that a set is countable, just by describing, not a bijection, but a surjection between the non-negative integers in A. Surjections are often easier to describe than bijections, which is why this is a useful lemma.

A corollary of this is that, if I'm trying to show that a set A is countable, all that I really need to do is find some other set that I know to be countable and describe a surjection from that other set C to A. Because I know that if C is countable, then there'll be a bijection between the non-negative integers and C. And since when you combine a bijection with a surjection, you wind up with a surjection, that will implicitly define a surjection from the non-negative integers to A, which by the lemma tells me that A is countable.

So the general way to prove something is countable is just describe a surjection, from something you know to be countable, that hits your target. And let's look at an example of that.

I claim that the rationals are countable, the rational numbers are countable. Well, this is kind of a little bit more striking at first, because you can see how you can count the non-negative integers, the positive integers, all the integers, because there's a nice sensible way to have one come after other.

But with the rationals, it's messy. In between any two rationals, there's another rational. There isn't any first rational. There isn't any obvious way to list them all. But really, if you stop thinking about the rationals of how they are laid out on the real line, but just think of them as pairs of integers, then it becomes clear how to list them, because we already know that the pairs of non-negative integers are countable.

So I'm just going to map a pair of non-negative integers m, n to the rational number m divided by n. Well, n might be zero, so if n is zero, just map all of those pairs to your favorite rational number. Call it a half. And that gives us a nice surjective mapping, because every rational number can be expressed as m over n-- at least every non-negative rational number.

So in effect, what we have is a surjection from the pairs of non-negative integers, which we know is countable, onto the non-negative real numbers-- sorry, the non-negative rational numbers, quotients of integers. Which means that the rationals, sure enough, are countable, even though they seem to be spread out all over the line.

So, again, we saw that if N cross N is countable, and there's a surj, described above, to the non non-negative rationals, so they're countable.

Well, just looking ahead a little bit, it's going to turn out that, in contrast to the rational numbers, the real numbers are not countable. And in fact, neither are the infinite binary sequences that we saw-- there was a bijection between the infinite binary sequences and the power set of the non-negative integers. And both of these are going to be basic examples of uncountable sets, so sets that are not countable, which we will be examining in the next lecture.

Free Downloads

Video


Caption

  • English-US (SRT)