Another Casual Coder

Infinity is a fascinating topic. When we start taking a close look at infinity (as if this was possible) we realize that infinity is actually something much more tangible than one may think. First, it is amazing to see that some infinite sums actually converge. Counterintuitive, isn't it? Starting with something like this:

1 + 1/2 + 1/4 + 1/8 +....

There is a very simple technique to solve this problem. Here it is:

S = 1 + 1/2 + 1/4 + 1/8 +.... Now multiply both sides by 2 and you get:

2S = 2 + 1 + 1/2 + 1/4 + .... Take a look closely at this:

2S = 2 + 1 + 1/2 + 1/4 + .... Well, this is S, right? Hence:

2S = 2 + S which leads to S = 2. One way to think about the above sum is as follow: suppose that you want to cross a bridge that is a mile long, and you want to cross it and come back. So you cross it first, travelling 1 mile. On your way back, first you have to cross half of the bridge (1/2). Then the half of the half (1/4). And so on. Hence the distance that you're going to traverse is:

D = 1 + 1/2 + 1/4 + 1/8 + ..... If no incidents happen, you'll eventually cross the bridge on your way back and you'll have covered 2 miles.

Using the same technique you can solve other similar problems such as:

S = 1 + 1/3 + 1/9 + 1/27 + ...

Or if you want to make it generic:

S = 1 + 1/N + 1/N^2 + 1/N^3 + .....

But then when we think that we got a hold of it, funny things happen: the famous harmonic series:

S = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + .....

Does not converge, it keeps growing indefinitely. Why do some series converge and others don't? That's when you get into real theory of infinity, theory that I don't know myself. Then comes the funny thing about the size of an infinite set. How do we count sets? Suppose that you have these two sets: S1 = {a, b, c} and S2 = {flowers, computers, table}. Do S1 and S2 have the same size? Yes, and one way to prove it is by mapping each element of S1 to one (and only one) element of S2:

a maps to flowers
b maps to computers
c maps to table.

So as long as there is a one-to-one mapping between the two sets, they must have the same size. Back to infinite sets, and use the mapping theory, we can prove that:

S1 = {set of all natural numbers}
S2 = {set of all natural even numbers}

Have the same size. The mapping is simple: for each number N in S1, map it to the number 2N in S2. Hence:

1 maps to 2
2 maps to 4
3 maps to 6

And so on. The mapping is one-to-one unique. Hence the two sets have the same size, which is very, very counterintuitive as one would think that S1 is at least twice as large as S2. They have the exact same size.

Great, then we get into the territory of infinite sets that are larger than other infinite sets, and we can start with a very small set (or so you think), the set of all the real numbers between 0 and 1, or for short:

S3 = [0..1]

Let's compare S1 (the set of all natural numbers) against S3 (the real numbers between 0 and 1). Which one is the largest? The intuition will trick your brain to think that S1 is bigger, after all S1 contains numbers such as 2^9999999999999999999999999 which is really, really big, and S3 is just a tiny set of numbers between 0 and 1. OK, so let's try to find a mapping between S1 and S3. Let's assume it exists and we'll prove by contradiction. Suppose that there is a mapping, so let's list the mapping:

1 maps to 0.245361563
2 maps to 0.563829109
3 maps to 0.876493022
4 maps to 0.532768209
5 maps to 0.263926497
6 maps to 0.435352190
7 maps to 0.748231533
8 maps to 0.536112322
9 maps to 0.056283949

And so on. To prove that such a mapping is impossible, we'll find a number that none of the natural numbers maps to. Let's look at the diagonal of the above table, here is its diagonal:

1 maps to 0.245361563
2 maps to 0.563829109
3 maps to 0.876493022
4 maps to 0.532768209
5 maps to 0.263926497
6 maps to 0.435352190
7 maps to 0.748231533
8 maps to 0.536112322
9 maps to 0.056283949

Look at the bold number above:

0.266722529

Now for each one of the digits in this number, add one module ten (if the digit is 9, it becomes 0). You'll end up with the following number:

0.377833630

What's so special about this number? Well, clearly 1 doesn't map to it because the digit 2 was changed to 3. 2 doesn't map to it either, because the digit 6 was changed to 7. 3 has no luck either, since the digit 6 (the third one) was also changed to 7. None of the natural numbers maps to it since at least one digit was changed. What this tells us is the following:

We can map every number from S1 to S3
But there is at least one number in S3 that cannot be mapped from S1

Hence, Size(S3) > Size(S1). Two infinite sets, but one is larger than the other.

And finally, comes one of the weirdest properties of infinity - when infinity meets geometry, and that really messes things up because now we can see objects and our brain is going to be tricked pretty badly. Take a look at the pictures below: there is one square of dimension 1x1, and a line of length 1:

The question is, which object has more points, the square or the line? Our eyes are telling us that the square has way more points. But let's see, let's use the concept of sets again:

S4 = {set of points in the 1x1 square}
S5 = {set of points in the line}

Every point in S4 then can be represented by a tuple of X and Y coordinates, hence each point can be represented by two numbers in the interval [0..1]:

A point in S4 is represented by: 0.n1 n2 n3 n4.... and 0.m1 m2 m3 m4.... where the Ns and Ms are digits. S5 is represented by single numbers in the interval [0..1]. We can actually find a one-to-one mapping between these two sets:

Every number (0.n1 n2 n3 n4.... , 0.m1 m2 m3 m4....) maps uniquely to the following number:
0.n1 m1 n2 m2 n3 m3 n4 m4......

Hence, Size(S4) = Size(S5). And we have just scratched the surface of infinity. Btw, no code in this post (otherwise it would run infinitely.........)