Subscribe!

• Colins Blog

• Multiple Choice Probability Puzzle
• Random Eratosthenes
• Wrapping Up Square Dissection
• Dissecting A Square Part 2
• Dissecting A Circle
• Dissecting A Square
• An Oddity In Tennis
• Decision Tree For Tennis
• Decision Trees In Games
• A Matter Of Convention
• Do You Nourish Or Tarnish
• Binary Search Reconsidered
• Two Equals Four
• The Lost Property Office
• The Forgiving User Interface
• Setting Up RSS
• Withdrawing From Hacker News

• Random Writings.
• Colins Blog 2010
• Colins Blog 2009
• Colins Blog 2008
• Colins Blog 2007
• Colins Blog Before 2007

Irrationals Exist - 2011/12/20

For this post I thought I'd have a quick diversion into talking about the so-called "Real Numbers." Upon reflection, however, I found that there was so much I wanted to say that there was no way to fit it sensibly into a single post.

So instead I'll put some preliminary comments here, and then expand on them later.

I'm going to assume we all know and love the rational numbers, those numbers that can be expressed as the ratio of two whole numbers. For the sake of simplicity I'll just deal here with positive numbers, and I won't even consider 0. We can deal with 0 and the negative numbers later if necessary, but we might not even get to that.

The Wilf-Calkin tree, named after Neil Calkin and Herbert Wilf

It turns out that there's a really cool way to write down all the rational numbers so that every rational appears in the list, and no value ever appears more than once. I say that because the way people usually list the rationals includes duplicate values - it includes 1/2 and 2/4 and 3/6 and 4/8 and so on. In fact, every value occurs infinitely many times.

Which is annoying.

The Wilf-Calkin tree, however, lists every value exactly once, and in lowest terms. You start with 1/1, and then given a/b you have two descendents. The left child is a/(a+b) and the right child is (a+b)/b. You might like to have a go at proving that every fraction we write down is in lowest terms, and that every rational value does turn up at least once.

We can now create a list of rationals by using a breadth-first search of that tree, as per the spiral in the diagram:

OK, so we can list all the rationals.

Now you pick any interval you like. You might choose [5,7] or [1023/3,6345/4], I don't mind. Pick any interval of non-zero length. That is, any interval where the end-points are not the same. I'm now going to generate a number inside that interval, and the number I generate will not be a rational.

So here we go. Most likely the first several rationals in the list won't be in your chosen interval, so we run down the list until we find two rationals inside your interval. (We'll worry later about the possibility of there being none or only one.)

When we find two rationals inside the interval, we use them as the end-points of a new interval, contained within the one we have. So now we have a smaller interval.

And repeat. Run down our list until we find two rationals inside our latest interval, and use them to define a new, smaller, nested interval. Lather, rinse, repeat.

There are now two possibilities.

In truth, this can't happen. The end-points are rational, call them a and b. Then (2a+b)/3 and (a+2b)/3 are both rational and inside the interval.

It might be that there comes a point when we don't get two rationals in our interval. In that case we have at most one rational in our interval, and everything else must be non-rational. Since our interval is of non-zero length, it contains infinitely many numbers, and so we have produced infinitely many non-rationals.

So in this case we're done.

We are using here the property that the reals are complete. More precisely, we are using the property that every bounded set of reals has a least upper bound.

The other possibility is that this process goes on forever, and so now I invite you to consider the left-most end of our infinitely many nested intervals. The left-most end-points form a strictly increasing sequence of rationals that is bounded above. Therefore it has a limit.

But can that limit be a rational?

For those who are interested, this is a constructive proof, and you can write a program which, for every interval, constructs and prints (although perhaps slowly) the decimal expansion of an irrational in that interval to any required precision. Which is cool.

No, it can't. Every rational has at some point either been excluded as outside our interval, or as the end-point of an interval, and hence outside the next interval. Every rational has at some point (so to speak) been "left out" of the intervals we have, whereas the limit of the left-most points is inside every interval.

So the limit of the left-most points cannot be a rational. It's an irrational, inside your original interval.

As required.

• http://en.wikipedia.org/wiki/Calkin–Wilf_tree

<<<< Prev <<<< Multiple Choice Probability Puzzle

:

>>>> Next >>>> The Ant And The Rubber Band ...

---

You should follow me on twitter

Comments

There have been a couple of comments, which have improved the above. I'll mention them here later today.

I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate.

If the number of emails/comments gets too large to handle then I might return to a semi-automated system. We'll see.