Loading search

RDFRS US:

The mission of the Richard Dawkins Foundation for Reason and Science is to support scientific education, critical thinking and evidence-based understanding of the natural world in the quest to overcome religious fundamentalism, superstition, intolerance and suffering.

The Magic of Reality

for the iPad

Sean Faircloth:

Attack of the Theocrats!

Jump to comment 13 by mmurray

If you use the correct notion of two infinite sets being the same size then it turns out that there are infinite sets that are not the same size. For example the infinite set we know best perhaps is the natural (counting numbers).

1 , 2 , 3 , 4 , ...

Defining when two infinite sets are the same size is a bit tricky so let me skip that. Let's instead call a set countable if you can list it out like the natural numbers. So you can (in theory!) count it. This means we have defined a notion of what it means for a set to be the same size as the set of natural numbers. Of course you will never finish counting but I just want a rule for counting that will get to every element of the set if I count for long enough and which never counts anything twice. It's basically what we do when we count the letters of the alphabet and find there are 26 of them. We tap A and say 1, tap B and say 2, until we get to Z. If we have counted everything at least once and nothing twice we will find there are 26 letters.

Consider now the set of all real numbers strictly between 0 and 1. We are going to do the famous Cantor diagonalisation argument. Imagine we have counted all the real numbers between 0 and 1 and the list is

a1 , a2, a3 , ...

Write out their decimal expansions as an array

a1 = 0. a11 a12 a13 ...

a2 = 0. a21 a22 a23 ...

a3 = etc etc

Now manufacture a new number by writing down its decimal expansion

b = 0 . b1 b2 b3 b4

Make the digit b1 the next digit after a11 (do it cyclically so if a11 is 2 make b1 = 3, if a11 is 9 make b1= 0 etc)

So maybe our list looked like

a1 = 0. 0 1 6 4 5 ...

a2 = 0. 5 8 8 9 ...

a3 = 0. 2 4 6 0 7 ...

so b = 0. 1 9 1 ...

Notice that b is a real number between 0 and 1 so it should be in the list. But its decimal expansion is different to the decimal expansion of everything in the list as it disagrees with ai in the ith decimal place. So it isn't there. So we were wrong in thinking we could count all the real numbers between 0 and 1. We say that the real numbers are uncountable.

It doesn't stop there as we then find there are uncountable sets which are not all the same size.

Infinite sets fail some basic things we know about finite sets. For example if you have a bag with 10 coins in it and I take out 10 coins from the bag the bag is empty. But if you have a bag with the natural numbers in it and I take out 2, 4 , 8 I get infinitely many things and you have infinitely many things left. Google the Hilbert hotel for more things like this.

Michael

Permalink Tue, 08 May 2012 00:10:47 UTC | #940455