My lastest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:
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.
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:
1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, ...
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.
So in this case we're done.
But can that limit be a rational?
So the limit of the left-most points cannot be a rational. It's an irrational, inside your original interval.
There's more about the Wilf-Calkin tree on Wikipedia:
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.
Links on this page