Skip to content

Instantly share code, notes, and snippets.

@fj
Created November 3, 2011 20:37
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fj/1337718 to your computer and use it in GitHub Desktop.
Save fj/1337718 to your computer and use it in GitHub Desktop.
Cardinality of the reals and intervals in the reals

So, @deathbob and myself were discussing whether the real numbers have the same cardinality as any interval of the real numbers. That is, if you pick an interval (say [0,1]), is it true that the cardinality of that interval is the same as that of the entire set of real numbers? Here's a defense of that idea.

Theorem 1: Pick any two intervals of the real numbers R. Then their cardinality is the same.

Proof: Let an interval [s,t] (with s < t) be the set of all real numbers between s and t, inclusive. To prove that the cardinality is equal, we need to show that you can write a one-to-one correspondence between any two such intervals -- say, [s,t] and [u,v].

There are lots of ways to do this, but a simple way to do it is just to map them linearly. Let's say you have the two intervals [0,1] and [0,2]. Take any real number in [0,1] -- say, 0.781. Now double it. You have just mapped it to a real number in [0,2], and you can do this for every number in [0,1]. Therefore these two intervals must have precisely the same cardinality.

Consider another example. If you have the intervals [2,4] and [16,32], then some examples for our function f would return f(2) = 16, f(3) = 24, and f(4) = 32. Likewise it would also return f(2.1) = 16.8 and f(3.5) = 28.

More generally, if you have two finite intervals [s,t] and [u,v], you can map the reals in a one-to-one way between them with

         v - u
  f(x) = ----- * (x - s) + u
         t - s

Using our previous example, you can see how f(2.1) works with [2,4] and [16,32]:

           32 - 16
  f(2.1) = ------- * (2.1 - 2) + 16
            4 - 2

         = 16/2 * 0.1 + 16
         =    8 * 0.1 + 16
         =        0.8 + 16
         =              16.8

Since this maps the reals in a one-to-one way, we've shown that any two intervals of reals have the same cardinality.

Theorem 2: The cardinality of any interval is equal to the cardinality of the reals.

Proof: This time we need to construct a one-to-one correspondence between the reals and any specific interval in it. For our interval, let's pick (-1, 1). Just as before, there are lots of functions that will work for this, but let's pick something simple -- say:

            x
  f(x) = -------
         |x| + 1

This maps any real number x and produces another real number which is between -1 and 1. For instance, f(5000) = 5000/5001; f(-296) = -296/297.

Therefore, because this can pair the entire set of real numbers with any number in the interval (-1, 1), the cardinality of the real numbers must be the same as the cardinality of the interval (-1, 1). And earlier we showed that the cardinality of any two intervals is the same, so the cardinality of the real numbers is the same for any interval in it. QED.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment