Counting and slashing

As Thomas is doing some maths-blogging, here are a couple of my favourite mathematical proofs. (With apologies to any actual mathematicians for any loose wording or cut corners: it’s well over a decade since I stopped doing this stuff for real.)

What I like about the first one is that it proves something to be true that is (as far as our intuition is concerned) demonstrably false. What I like about the second one is that it proves something that seems self-evidently true, but it does so in a really cool way.

Counting the fractions

First, the proof that the cardinality of the set of rational numbers, Q, is the same as for the set of natural numbers, N. Or, to put it more informally, “there are just as many fractions as there are natural numbers”. This is, to say the least, somewhat counterintuitive, but it can be proved by listing the (positive) rationals as follows (diagram taken from here):

infinity_rationals

The pink line then shows how you run up and down the diagonals, counting the numbers as you go. Since you can count the positive rationals in this way, it follows that the rationals can be put into a one to one correspondence with the natural numbers: that is, “there are just as many (positive) fractions as there are natural numbers”.

The extension of this to cover negative fractions, and hence all rational numbers, is then trivial*. (* That’s maths-speak for, “I can’t be bothered to do that bit right now”.)

Slashing through the real numbers

Now, turning to the set of real numbers, R, which includes both rational and irrational numbers (i.e. those that cannot be expressed as fractions, such as pi or the square root of 2), this can be shown to be uncountably infinite. In other words, “there are more real numbers than there are natural numbers”.

To show this, we will show that the real numbers between 0 and 1 are uncountably infinite (“there are more real numbers between 0 and 1 than there are natural numbers”). To do this, let’s assume the contrary, namely that the real numbers between 0 and 1 are countably infinite. That is, they can, like the rational numbers, be put into a one-to-one correspondence with the natural numbers.

If that’s the case, then we can list them as decimal expansions, say as follows:

0.012347236238734…
0.543254358365473…
0.811389482184398…
0.123948237937498…
0.239487495837948…
0.732841321293472…

Then, going down the main diagonal (highlighted), we can construct a new number x whose decimal expansion consists of 1 (where the corresponding diagonal digit is different from 1) or 2 (where the corresponding diagonal digit equals 1).

So x then equals (say) 0.11211211112112111…

Now, x cannot appear in our list, because it differs from the first item in the list at the first position, the second item in the list at the second position, and so on, right the way down the list. But the list is supposed to include all real numbers between 0 and 1. That’s a contradiction, so our original assumption is false: the real numbers between 0 and 1 are not countable.

Hence “there are more real numbers between 0 and 1 than there are natural numbers”, and it thus follows that “there are more real numbers than there are natural numbers”.

(The above outline is based on Roger Penrose’s The Emperor’s New Mind, pp.110f., with the usual disclaimer that all errors are mine alone.)

Isn’t that a great argument? It’s called Cantor’s diagonal proof, or “Cantor’s slash”. A similar argument crops up in a number of places (e.g. Turing’s proof of the undecidability of the halting problem), and it always leaves me slack-jawed with delighted amazement.

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

5 Responses to Counting and slashing

  1. Phil Walker says:

    And people say we mathematicians are uncreative!

  2. The Scylding says:

    At ‘varsity I enjoyed graph theory especially – the proofs there are somewhat esoteric!

    With maybe one exception, my maths & applied maths lecturers and professors were always some of the more entertaining teachers I ever had. They also tended to be quite cultured people too.

    But maybe I’m biased – after all I love caffeine, and everybody knows a mathematician is a machine for turning coffee into theorems!

  3. Rick Ritchie says:

    “Everybody knows a mathematician is a machine for turning coffee into theorems!”

    Yes. I have my own “stopping problem” with that, and I am not a mathematician. Do you decide how much coffee to drink by algorithm, or by intuition?

  4. Lito Cruz says:

    I have been posting lately on some logical issues that touch on theology. Sorry for the plug, the latest is on negation.

    Another creative proof I have been astounded is the Henkin proof of completeness, when he constructs a canonical model base on the syntax! It was a struck of genius.

    So much fun, on scribles on a piece of paper, ohh, what bliss!

    LPC

  5. The Scylding says:

    Rick, if like Hilbert you’re a formalist, you have aset volume of caffeine per algorith. But after reading Godel you’ll begin to doubt, and will only claim that some caffeine produces some theorems, but that you’ll just have to accept it for things to work. Intuitionists are a subset of these, but the amount of caffeine decreases per theorem depending on the caffeine already in the bloodstream. Since chaos theory came around however, you’d have realised that the amount can change at anytime, with very little predictive power once you’ve passed a certain threshold of caffeine content.

    Of course, can through all overboard, become a philosopher, and drink alcohol.

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