These fields are all optional and need only
be supplied if you would like a direct reply.
Subject
Your email address
Your real name
You must answer this!
If you don't, my spam filtering will
ensure that I never see your email.
What's 8 plus five (in digits only)?
Please make your changes here and then
Editing tips and layout rules.
File: IrrationalsExist ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My lastest posts can be found here: * ColinsBlog ---- Previous blog posts: * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ******** !! 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. [[[> |>> http://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/Calkin-Wilf_spiral.svg/250px-Calkin-Wilf_spiral.svg.png _ 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: |>> 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, _ 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. [[[>50 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. [[[>50 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? [[[>50 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. ---- There's more about the Wilf-Calkin tree on Wikipedia: * http://en.wikipedia.org/wiki/Calkin–Wilf_tree ---- |>> | |>> <<<< Prev <<<< ---- MultipleChoiceProbabilityPuzzle <<| | : | |>> >>>> Next >>>> ---- TheAntAndTheRubberBand ... <<| | ---- ********> ''' <a href="https://twitter.com/ColinTheMathmo">You should follow me on twitter</a> ******** ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ********< <<| ---- !! 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. ********<