Theorem 18: the rational numbers are countable

One of the intriguing facts about infinity mentioned in that Horizon programme (the one on recently that I disliked) is that there are different sizes of infinity.  I thought that this week I’d start discussing that fact.  (There might be another theorem of the week on this subject!)  Here are two questions for you to consider.  Are there the same number of integers (whole numbers) as natural numbers (positive whole numbers)?  And are there the same number of rational numbers (fractions) as natural numbers?

The idea is that there can be infinite sets that don’t have the same size.  To make sense of that statement, we have to know what it means to say that two sets have the same size (and what an infinite set is).  Let’s try to make sense of this.

I think this really goes back to our earliest ideas of what it means to count the elements of a set.  When I look out of my window to a field of sheep, I count the sheep by matching each sheep to a number: 1, 2, 3, 4, ….  And if I count the books in the bookcase, I do the same thing: I match each book to a number: 1, 2, 3, 4, …. I’d say there are 10 sheep (or books) if I can match each sheep (book) to a number from 1 to 10 in such a way that each number gets used, and no two sheep get the same number.  We say that the set of sheep in this field has the same size as the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, because we can match sheep to numbers.  (We could imagine painting numbers on sheep.  Not sure my artistic skills are up to that.)

When would we say there are more than 10 sheep?  If we match the sheep to the numbers 1 to 10 and still have some sheep left over, there must be more than 10 sheep.  And if we match the sheep to the numbers 1 to 10 and still have numbers left over, there must be fewer than 10 sheep.

We use much the same idea with infinite sets.  (An infinite set is one that cannot be matched to any finite set.)  We use the natural numbers as our counting set, and try to match numbers to the naturals.  If we can do that, we say that the set is countable; if we can’t, we say that the set is uncountable.  (There is a slight ambiguity about whether a finite set is countable.  Sometimes people use the phrase countably infinite to help clarify.  For the purposes of this post, finite sets are countable.)

Here’s another way to think about countability.  A countable set can be listed: we write the element matched to 1 first, the element matched to 2 second, and so on.  And if we’re given a list, we can get a matching (the first element gets matched to 1, the second to 2, and so on).  Sometimes that can be a useful way of thinking about things.

Let’s try to think of some examples of countable sets.  Any finite set is countable (because I just said that).  The natural numbers are countable, because I can match each natural n to itself.  Let’s try to think of some more interesting examples!

Are the integers countable?  Can we write them in a list?  We might write them as …, -3, -2, -1, 0, 1, 2, 3, …, but that doesn’t count because the list doesn’t have a first element.  So we need another strategy.  We need to be sure that we list everything (and that we don’t list anything twice).  Here’s one possibility: 0, 1, -1, 2, -2, 3, -3, ….  We `start in the middle and work outwards’.  So yes, the integers are countable.

Are the rationals countable?  Can we list the rationals?  It turns out that we can, and that’s this week’s theorem.

Theorem The rational numbers are countable.

Let’s see how to prove this.  One way of thinking about our proof that the integers are countable is that we wrote them in a line (…, -3, -2, -1, 0, 1, 2, 3, …) and then drew a path that took us through them all.  (I’ll let you see this by drawing it for yourself.)

If we could do something similar for the rationals, that would be great.  But it’s not quite as obvious how to write them in a line.  In fact, thinking about it for a bit it seems more natural to write them in a grid:

1/1   2/1   3/1   4/1   5/1   …

1/2   2/2   3/2   4/2   5/2   …

1/3   2/3   3/3   4/3   5/3   …

1/4   2/4   3/4   4/4   5/4   …

1/5   2/5   3/5   4/5   5/5   …

………………………………..

Now, how can we plot a path through these?  We can imagine working through each diagonal in turn.  So we might get something like 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, ….  This isn’t quite allowed, because we’ve counted some rationals twice (e.g. 2/2 = 1/1).  But that’s easily fixed: we say that we’ll follow this path, simply missing out anything we’ve seen before.  This gives us a listing of the positive rationals.  To include the negative rationals, we can do something very similar to what we did for the integers — I’ll leave that for you to think about.

You might like to think about whether some other sets are countable.  Is the set of pairs (m,n) of natural numbers countable?  Is the set of all subsets of the naturals countable?  Is the set of all finite subsets of the naturals countable?  More on this topic later (when I’ll say something about uncountability).

Further reading

There’s an NRICH problem inspired by this idea that the rationals are countable (although it isn’t phrased that way).  There’s also a very nice NRICH article about infinity and countability.  The formal way of talking about matchings is to talk about bijections, closely related to injections and surjections.  There is also, of course, a Wikipedia page about countability.

About these ads

9 Responses to “Theorem 18: the rational numbers are countable”

  1. Theorem 19: there is a transcendental number « Theorem of the week Says:

    [...] Theorem of the week Expositions of interesting mathematical results « Theorem 18: the rational numbers are countable [...]

  2. Theorem 21: the real numbers are uncountable « Theorem of the week Says:

    [...] 21: the real numbers are uncountable By theoremoftheweek In my post about the countability of the rational numbers, I said that I’d come back to the topic and prove that the real numbers are uncountable.  [...]

  3. Four Dimensions: Objection, Refutation, Objection, Refutation, Confusion « Mathematical Multicore Says:

    [...] many particles there actually are, but if there are finitely many, then we can use logic similar to Cantor’s proof that rational numbers are countable to prove that we only need one additional [...]

  4. John Williamson Says:

    Why does infinity have so many sizes,
    Something with sets and operations
    john

  5. natalie Says:

    my teacher say that when an element ends with (…) it means that it is uncountable so we called it infinite.

  6. avijit Says:

    Posted proofs are great.
    They are perfect to satisfy the curiosity.

  7. Sutton Trust summer school 2012 « Theorem of the week Says:

    [...] We mentioned that there are many more irrational numbers than rational; that’s because the rationals are `countable’, whereas the irrationals are `uncountable’.  A couple of the problems on the examples sheet [...]

  8. Conditions for Countability « mathwizzards Says:

    [...] showing that the set of rational numbers Q is countable.  A traditional proof of this fact is seen here.  However, it would be easier to show if we have a different condition for countability: A set S [...]

  9. Igborigbo joseph Says:

    Nice proof,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 148 other followers

%d bloggers like this: