The Prettier Side of Math

May 31, 2008

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:

 Cantor\'s diagonal argument

 (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 🙂 

Not writer’s block, more like a time block

May 29, 2008

Haven’t been able to find the time between work, “miluim” (army reserves) and university to write anything new, but I have some ideas, so don’t despair 🙂

My next article will probably cover Cantor’s function, which is a very elegant way of proving that there are “more” real numbers (R) than natural numbers (N), as well as define what exactly constitutes a random number (or more precisely – random sequence). If there’s time, I think I’ll also discuss Berry’s Paradox, another interesting way of looking at math and logic.

The misconception of science, or “what happens when a duck quacks in an opera house?”

May 25, 2008

I am troubled by the manner in which the majority of people assume that the things they hear or read are correct, without subjecting them to any sort of scientific method.

What do I mean exactly? well, one prime example is the story of the non-echoing quacking duck.

For those of you who are unfamiliar with this “hypothesis”, according to all of the wonderfully time-consuming and misinforming PowerPoint presentations we receive in our inbox from people who we consider to be our friends, a duck’s quack does not echo. Now, this statement has all the makings of a psuedo-scientific fact. It involves, hold on to your hats – “sound waves”. As we all know, sound waves are a very “scientific” subject, yet a relatively simple concept to grasp, since we’ve all seen how a pond reacts to a stone thrown inside it. In addition, this “theory” refers to a specific species in the wild kingdom. Since there are so many animals out there, surely one of them interacts with sound waves in this unusual manner. For some reason, when people receive facts that seem to be scientific, something in their brain tells them to automatically treat this new information as correct.

However, when we examine this statement a little closer, using real scientific methods, we see the absurdity of this so called “scientific fact”. Yes, physically, it is possible to create a sound wave which does not echo. You don’t even have to study physics to understand this, you just need to have a basic understanding of the concept, and some good healthy logic. However, it is quite a leap of faith to believe that all the ducks in the world (every last one of the little quacking bastards), in all echo-creating conditions, have the ability to produce the exact sound (e.g. exact wavelength and frequency) that will not echo.

However, I do not wish to dwell specifically on the matter of the quacking duck, but more on the concept of how people tend to agree with what they read/hear without taking a moment to consider what they are being told, and examining this new information with their own brain for a change.

I am not saying that we should question everything. That seems like quite a tedious way to go about life. However, I believe that every person should strive to develop the ability to pick up on psuedo-scientific jibberish such as non-quacking ducks.

After all, most of mankind’s greatest scientific achievements came as a result of someone, somewhere, saying: “this can’t be right…”: Charles Darwin‘s Theory of Evolution (“Do we have to accept the story of how we came to be as told by a group of non-sceintific religious zealots?”), Albert Einstein‘s Special and General Theories of Relativity (“Who decided that time, mass and space have to be constant in all systems?”), and of course, Nicolaus CopernicusDe revolutionibus orbium coelestium (On the Revolutions of the Celestial Spheres), which I perceive to be the catalyst of modern science as we know it, since Nicolaus’ question was not only humble in nature (“Why must we believe that man is the apex of creation?”), but also led to a less romantic and more objective weltanschauung, which is key when one is attempting to analyze the world in a scientific manner.

But perhaps the problem is not in the manner in which people think. Perhaps the problem is thinking at all. Sadly, I tend to believe that the problem lies in the latter.

Hello world!

May 17, 2008

This website is dedicated to Computer Sciences, Physics, Popular Science and Mathematics.