The joys of cardinality – part 1

So, here’s an article I’ve been meaning to write for a while. I love Cantor’s diagonal proof of how there are as many rational numbers (of the form a/b, for example 1/5 or 1/2 or 3/5) and yet there are more real numbers (this is the numbers with an infinite expansion of decimals like pi, e, 3.5252353…) than integers.

However, everytime I try to share this with people I get stuck because it’s very abstract thinking, even though it’s really cool. So, this is my attempt to explain it in a few steps so that everyone can understand how thinking rigourously can teach you very cool things about numbers.

So, let’s start with the idea of cardinality. How can we clearly state that two sets of objects are the same size. I want a method that is indisputable. So let’s imagine we have 2 sets of objects, baskets and balls.

|_| |_| |_|   o o o

Now, above we can see, at a glance, that we have the same number of baskets as balls, but how can we prove it to someone who can’t count. Well, we can put one ball into each basket.
|o| |o| |o|

Yep, each basket is full, and each ball is in a basket. So we must have the same number of baskets as balls. This is great.

Now let’s try another set of baskets and balls.

|_| |_| |_| |_|    o o

Putting them into the baskets, we have

|o||o| |_| |_|

Hmmm… we have more baskets than balls. This means that the two sets aren’t the same size as we have empty baskets. Technically, mathematicians would say this is a injective mapping of balls into baskets. However, we’ll avoid the technical terms for now.

One more set, just so we have all cases covered for finite syts.

|_| |_| |_| o o o o o

Putting balls into baskets, gives us:

|o| |o| |o| o o

Now we have 2 lonely balls rolling around without any baskets. Again, this clearly demonstrates that the two sets aren’t the same size, as we have balls that need baskets, and all of the baskets are full. If we were allowed to put more than one ball into a basket, this would be a surjective mapping of balls onto baskets. Again, you can ignore these technical terms. As the key point here is we now have a clear way to determining when we have 2 sets whether they are equal in size, or whether one is larger than the other.

So let’s try with an infinite set of baskets, and an infinite set of balls.

|_| |_| |_| |_| ....

o o o o ....

Now, obviously, we need to find a clear way to represent which ball would go into each basket without having to draw an infinite number of baskets with balls in them to verify. So, let’s number each basket and number each ball in the obvious fashion.

|_| |_| |_| |_| ...
 1   2   3   4 ...

o o o o ...
1 2 3 4 ...

Now, there is an obvious way we can put every ball into every basket. We put Ball 1 into Basket 1, Ball 2 into Basket 2, and so on. Now, how do we test if every basket is full? Well, we check if the basket has a ball in it. So if you were to challenge me by asking (Does basket 34255 have a ball in it?) I can respond, yes, it has ball 34255 in it, by how we filled the baskets. This is true, because we know ball 34255 exists, and we agreed to this method of filling baskets.

Something interesting happens now, you throw a ball to me and tell me to put it into a basket. Well, all the baskets are full, so this should be, in theory, impossible, right?

I look at the baskets, and go ok. I mark your ball as ball 0 and put it into basket 1, moving ball 1 to basket 2, and so on…

|_| |o| |o| |o| ...
1/1 2/2 3/3 4/4 ... (Basket Number / Ball Number)

0 (Ball Number 0, which to make it clearer we'll 
represent as a ball with a slash on it)

So we do this, take ball 1 out of basket 1, and put into basket 2. ball 2 out of basket 2 and put into basket 3, and so on…

|_| |o| |o| |o| ...
 1  2/1 3/2 4/3 ... (Basket Number / Ball Number)

Put in ball 0 into basket 1

|Ø| |o| |o| |o| ...
1/0 2/1 3/2 4/3 ... (Basket Number / Ball NumbeR)

Now, every single ball is in a basket, even though we added one ball to the previous pile. This is one of the more interesting properties of infinity. Adding a finite number of elements to an infinite set does not change how many objects there are overall from this perspective. You could give me 100 balls, and I would only need to shift the first 100 down all the way down the line and there’ll still be enough baskets.

I’ll let everyone think about that one for a bit, and tomorrow I am going to go into how there are just as many even numbers as numbers in general. Hopefully ending with a framework to show how you can see there are just as many rational numbers (ie. fractions) as integers (whole numbers like 1, 2, 3).

Leading to the really weird realization in the following post that there are actually levels of infinity. 🙂

Please if anything here confused you, please ask questions. I’d love to have the chance to clear it up and develop an even better way to show this neat beauty in mathematics.


Enhanced by Zemanta

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s