I’m pretty picky about the kind of math I like. Calculus and Linear Algebra? Blech. Discrete Mathematics and Data Structures? Yummy!
My problem with the former is that I believe this kind of math lives up to the famous quote by Charles Darwin, the father of the Theory of Evolution (see previous post): “A mathematician is a blind man in a dark room looking for a black cat which isn’t there.”
At least for me, when I try to solve such problems, when I do manage to solve them, I don’t get a feeling of satisfaction at the end. Either the exercise seems like Greek to me, and then I have to stumble in the dark until I find a solution (just trying different methods), or I just follow a set order of procedures, which makes me feel like an overpriced computer program (hey, you don’t need to feed, dress and house a computer program. Unless you consider electricity as food, an operating system as clothes and a case as a house 🙂 ). Calculus sometimes has its finer moments, especially when you need to prove something fundamental, but most of the time I don’t care too much for it. Obviously, this isn’t a universal truth about math, and is purely a result of the way my mind works, and how I solve problems.
However, if we turn to subjects like Discrete Mathematics, I look at questions as puzzles. Obviously it isn’t all fun and games, and when you’re starting out you have to do a lot of technical work to get everything down, but once you get past that to the interesting stuff – it gets a whole lot nicer :-).
Before we dive into the math, consider the following riddle: You wake up in a room. You look around and all you see is a wall covered with numbers. It’s a list of 499 numbers, all made up of 500 digits. Above the list you see the following message: “You have exactly 10 minutes to write down a new number which is not already on the list. If you write down a number which is already on the list, you will be trapped forever (punch and pie will be served).” What do you do?
First, a basic introduction to set theory (a mathematical branch). I promise – there will be no equations, and everything will be explained in the most intuitive way possible. Let’s call all the Natural numbers N. “What are natural numbers” you ask? Well, simply put, its numbers you can count with your fingers, i.e. 1, 2, 3, 67, 985431, 12341414, etc. You may need to have a lot of fingers, but you get the point – whole numbers, starting from 1 (sometimes zero is considered a natural number, and sometimes it isn’t. For our purposes, it isn’t) and up to infinity (infinity… another very interesting topic which I might tackle in a future post).
Okay, so we know what natural numbers are. We called them N. Now we need to define another group of numbers: Real numbers. We’ll call them… you guessed it: R. What are the real numbers? every number possible. That’s right. Think of a number. It’s real. 1.543? It’s real. 980? Also real. -97234.123401213? Real as they come. Pi? trying to be tricky, huh? (Pi = 3.1415… is an irrational number which describers the ratio between a circle’s diameter and its circumference, but I assume that if you got this far and this kind of stuff actually interests you, you’re probably pretty upset at me for even explaining this. Well, too bad for you. I’m thinking of the poor souls out there who have lived life so far without knowing what pi is :-)) Well, foiled again. It’s also real.
So we defined N and R. Both groups of numbers are infinite in size, but “intuitively” it seems that there are “more” real numbers than there are natural numbers, right? Well, you are correct in assuming that, but how do you prove it? As the famous phrase goes: “It’s not what you know, it’s what you can prove”.
Which brings us to the main subject of this post: Cantor’s diagonal argument. Cantor’s diagonal argument proves just that. Before I explain Cantor’s argument I have to explain one more term: a Surjective function. Suppose I have a group of numbers on one side. And I have a group of bunnies on the other. Now, I want to assign a number to each bunny (hey, I gotta keep track of my bunnies, right?). So I draw a line between each number and each bunny. If there are more numbers than bunnies, i.e. I have some numbers which have no bunny to point to, then the function of numbers-bunnies is called surjective. It means that one group is “bigger” than the other. It’s quite easy to grasp when considering finite groups, but becomes much harder when the groups are infinite.
In order to prove that the group ‘BIG’ has more members in it than the group ‘SMALL’, we need to prove that there is a surjective function from ‘BIG’ to ‘SMALL’, but we also have to prove that there is no surjective function from ‘SMALL’ to ‘BIG’ (if there is, then both groups are the same size).
We wanted to show that there are more real numbers than there are natural numbers. Finding a function from R to N which makes sure each natural number is “covered” is quite easy. Lets just look at the small segmant of real numbers from 0 to 1. We then define a function (a function doesn’t necessarily have to be y=5x+7. A function can just describe some sort of relation between two groups of numbers. Think of it more like a computer program which has an input and an output. For instance, we can define a function that returns 0 if it receives an odd number, and returns 1 if it receives an even number), which takes each real number between 0 and 1, for example 0.12345, and returns the corresponding natural number which is made up of the numbers after the decimal point, only in reverse, i.e. 54321 (why do we flip the numbers? well, 0.12345 is actually 0.1234500000…, which might be hard to transform into a natural number. What natural number should we transform it to? 12345000000…? (how many zeros should the natural number have?) So we just look where the zeros start, and flip it from there). Each natural number will be covered, so the function from R to N is surjective. However, creating such a function from N to R isn’t quite as simple, and is actually impossible. We will prove that 🙂
We won’t prove that the natural numbers can’t “cover” the real numbers. We will prove that they can’t even cover the real numbers between 0 and 1! (and of course that will be enough to claim that it can’t cover all of the real numbers)
Lets assume that there is such a surjective function from N to R. We will call this function f (reminder: f will receive as input any natural number, and will return a real number between 0 and 1). Whenever f receives a natural number it returns it with a 0. at the beginning. So, 7354 becomes 0.7354000… and so on. But I don’t like all those zeros. So what we are going to do is employ an important rule in math which I will not explain here which states that 0.9999… = 1. Therefore, f(7354) will equal 0.735399999…
Now, suppose we got all of f’s values and wrote them on a grid. What we will do now is define a new number: x. This number will be “built” in the following manner: we will go over the diagonal of the grid, and each digit we see, we simply increase it by 1 (9 becomes 0) and add the new digit to x, like so:
(2 becomes 3; 1 becomes 2; 6 becomes 7 and so on and so forth)
Now comes the tricky bit, which is the whole point behind this proof: x is a real number which is not covered by the function f, and therefore f is not a surjective function, which means that there are more real numbers than there are natural ones.
Ok, back up. Why is x not covered by f? After all, one could just say that it is made up of a series of numbers, so a natural number must have created it. But all of the real numbers we created with f, using natural numbers as the source, were listed in the grid. And x is different by one digit from every number we created. Remember that we travel along the diagonal, meaning we make sure that it is different from every number in the grid by at least 1 digit – that’s the beauty of Cantor’s diagonal argument. No matter which numbers we choose to input in f, we can always create an x which is different from all of them. QED.
Now lets return to the riddle this post started with. If you stayed on for this long, and understood Cantor’s diagonal argument, you should be able to escape from the room. If not – well, they did say that punch and pie will be served 🙂