My experience in the Google ̶̶S̶w̶e̶a̶t̶s̶h̶o̶p̶ Workshop

I recently attended GDD 2011 (Spoiler alert: the Android Ice Cream Sandwich OS has some nifty features. Beam for instance), which took me down memory lane and reminded me of the Google workshop I attended during my CS BA studies, back in 2010. I posted a link to our project in this blog.

not available for iPhone

The ‘workshop’ is a project every CS graduate from Tel-Aviv University is required to complete. You usually have a choice of around 10-20 workshops (there are more workshops during the 2^nd semester), with workshops varying from creating a small robot which will be able to traverse an obstacle course (with a real robot), to more complicated optimal-path finding algorithms, computer vision related projects, machine learning, various mobile-based applications and much more. A relatively new workshop that was available was the Google workshop.

Obviously it was in great demand for having ‘Google’ in its name (the TAU method of getting the courses you want each semester is based on a bidding system. You receive points according to your XP, i.e. how many courses you already completed, and then use those points to bid on courses).

After talking with some of my classmates who completed other workshops, I realize that the Google workshop was one of the only workshops that placed emphasis on Milestones. Milestones were meetings we had about once a month, during which each team held a 15-20 minutes presentation, first discussing its project, and later on its progress on what it promised to complete by that milestone, as well as what we intend to complete next (our objectives). In most other workshops the groups met a couple of times when the semester began, and then the professor pretty much left you alone until you were required to hand in the project at the end of the semester, usually a couple of months after finals ended.

Looking back on it now, the Google workshop, in many ways, prepares its students much better for the scary ‘outside world’. As a programmer you need to be able to write elegant code, but also to give proper estimates as to how long it will take you to write that code. Give an ‘easy’ estimate (“Create a ‘contact us’ form? Oh, about a month’s worth of work”) and you’ll quickly be marked as an inefficient worker. Provide a ‘hard’ estimate (“Design the application’s database? I can whip that up in a day!”) – and it’ll quickly backfire on you. Just like goldilocks, you have to find that sweet spot in the middle. As someone with little or no experience that might prove difficult, but no one said it would be easy.

Another real-world aspect of the workshop was that we got very little ‘references’ from the team. That might seem unfair, unprofessional or perhaps plain old cruel, but in reality – it isn’t too far off from what you’ll face when you start working somewhere. Sure, there’ll probably be more experienced developers on your team who could offer you pointers, and if it’s a big company it might even have an organized system of training new recruits, but your autodidacticism skills will always be put to the test.

We also had to decide how to implement everything ourselves, even in terms of which platform to use. For instance, the workshop instructors introduced us to GWT (when I say introduced I mean that they let us know of its existence and where we can read about it), but didn’t require us to use it. If you haven’t heard of GWT, I recommend reading a little bit about it. It’s an interesting concept. I currently develop using the GWT platform, and I believe it is here to stay. I might even write a post about it soon (if I get around to it). We eventually opted against using it, and I’m pretty sure it was the right thing to do (it was probably “over-kill” for our purposes). But had we chosen to use it, and were to fall behind on our schedule as a result – we would have to face the consequences, or pull very long all-nighters. We couldn’t blame the instructors if it turned out that GWT was unsuitable for our purposes. It was our responsibility to properly research the technology we chose before using it.

Like I said, our workshop conditions were somewhat more difficult than that of the real world, but like we say in the IDF: “Kashe Ba’Imunim, Kal Ba’Krav”, which translates to “The harder the training, the easier the battle”, or to quote General George S. Patton – “Pressure makes diamonds”.

Clientside JavaScript goodness

As part of the hiring process to a certain company, I was asked to create a basic RIA (Rich Internet Application), with the primary focus on the client side (there doesn’t even have to be any actual communication with the server – all data can be created as mock data inside the js). Feeling a bit inspired, I decided to document how I went about it. First off, the assignment stated that if I use HTML5 for storage, I’ll get bonus points. I think I should lose points for using it, since it appears it’ll make my life so much easier. HTML5 allows you to save data on the client end, either for the current session (i.e the current window/tab) or for the entire time the user’s browser is open (i.e. across all pages in your domain). No need to send data back to the server or use other hacks. Yes, a cookie does the exact same thing, but a cookie’s “destiny” (and as a result – its size and robustness) is to save small stuff, like preferences or a user ID (which entails going back to the server for additional data. Every time, on every page). HTML5 lets you save almost any data structure inside a mapped data structure (a dictionary). Now obviously this raises quite a few security concerns. But you just have to think a bit about what you decide to save on the client side. Since this is a “mock” project, that will not be an issue. So first things first, let’s set up a quick web site. I’ll use Google WebAppEngine – it’s fast and easy. So you can see what I did here. We also need somewhere to host the code. Google to the rescue once more. Since my server side is going to be meaningless (I only load static HTML pages, with no content provided from the server), I better see how to configure app.yaml so it’ll route my urls properly:

application: apple-of-israel version: 1 runtime: python api_version: 1 handlers: – url: /stylesheets static_dir: stylesheets – url: /static static_dir: static – url: /js static_dir: js – url: /index static_files: static/index.html upload: static/(.*) – url: /employees static_files: static/employees.html upload: static/(.*) – url: /.* script: helloworld.py

this configuration means that when I navigate to localhost:8080/index – I get referred to my index.html file. The same for employees. For now I left the helloworld routing – which means that localhost:8080/ routs to a phython script, which prints an html of hello world. I could have used that routing to create my html in python, but that just seems silly, and also defeats the purpose of taking the load off the server and having the client due all the work. The static redirection is needed for hrefs inside the html pages that link to other static html pages in the site. The stylesheets redirection is needed for when my html pages request the css file inside the stylesheets folder. “Which css?” you ask? The one I got for free here. The js folder routing is for javascript files. obviously. OK, let’s attempt and store some data between pages using our newfangled HTML5. We’ll add this code to index.html:

<script type=”text/javascript”>

sessionStorage.setItem(‘userName’, ‘tom’);              // defining the session variable

alert(“Your user is: ” + sessionStorage.getItem(‘userName’));   // accessing it

alert(“Hello ” + sessionStorage.userName);                   // another way of accessing the variable

</script>

and the following code to districtNorth.html:

<script type=”text/javascript”>

sessionStorage.setItem(‘userName’, ‘tom’);              // defining the session variable

alert(“Your user is: ” + sessionStorage.getItem(‘userName’));   // accessing it

alert(“Hello ” + sessionStorage.userName);                   // another way of accessing the variable

</script>

Well, that was pretty easy. So I am now able to move around different static HTML pages, and I also have a local datastore. Awesome. Time to create my mock data, find some cool javascript libraries and start using and manipulating that data. Well, the mission mostly required me to display a list of people who pick apples in different sectors of Israel. The actions which a user could perform were listed. So naturally, I started with creating mock data of bunch of apple pickers.

Late edit – due to having to finish the task on time, I kinda stopped writing about what I’m doing at this point. For some reason I haven’t published this post right away (probably felt ashamed at not completing it).

also , if anyone is interested in knowing – I got the job

Research Assistant – organize your papers

As part of a Computer Science project, some friends and I built a site which helps you (the Google Scholar user), manage your research, stay updated and collaborate with colleagues.

http://research-assistant.appspot.com/

You log in using your Gmail account (the site is hosted on Google’s servers), so no need to register and fill out any details.

I hope you find it useful!

Exam period

One of the subjects on which I’ll be tested soon is computational complexity . This great short story by Isaac Asimov turns out to be linked to this subject. A very interesting read:
http://www.multivax.com////last_question.html

Getting in touch with your inner log()

Neuroscience is on the rise. Every other week you hear about a new discovery, or simply the next step in computing, gaming and… board-games (???).

I have always been fascinated by the human brain (well, consider the source being fascinated ), so when I saw a class opening up on the subject in my university, I immediately signed up for it.
The basic goal of neuroscience is to reverse-engineer a complete blueprint of the brain. I am not simply referring to its actual physical makeup:

The interesting part is how it actually works. Its API if you will, or “instructions”. One of the main topics covered in this class was sight. Most of us are familiar with the “lies-to-children” version of how vision works:

(click to enlarge)

Well, the human brain does perform some sort of transformation, but it is a much more useful one.
To simplify matters, let’s consider the surface of the human eye (more specifically, the cornea) to be a round disc (like a vinyl music record). I assume all of you are familiar with Cartesian coordinates, or more commonly known as X-Y coordinates. Well, Cartesian coordinates are very convenient when working with square surfaces (like a map or graph), but not so well when the surface is circular. A more appropriate approach would be to use a Polar coordinate system. Instead of the two values X and Y, we have R and θ (Theta); R being the length of the straight line between the center of the circle and the point, and Theta indicating the angle between that straight line and the horizon. For example:

Everybody knows that the right part of the brain controls most of the left side of the body and vice versa. Well, in the field of vision it’s a bit more complicated. The left side of the brain does not handle visual information from the right eye, but from the right field of vision. So it will handle data from the right side of the right eye, and from the right side of the left eye. But that is less relevant for what I want to talk about, and we could just as well assume we are all Cyclops, i.e. we only have one eye (the second eye is important for detecting depth, but that’s a whole other subject by itself). That means the left side of the brain handles information from the right side of that eye and vice versa.

The part which is first in line to handle information from the eyes and is in charge of sending the most “raw” data about what we see to the rest of the brain is called the visual cortex. Again, we simplify its surface area to make things clearer. With that in mind, one could consider the visual cortex to be rectangular.

So suppose a beam of light hit our eyes. What happens now? The same image will be replicated on the visual cortex, but it will do so after undergoing a transformation along the way. That transformation will take the parameters R and Theta, and will display them on the visual cortex, in Cartesian coordinates – the Y value will be equal to Theta (in radians), and the X value will be equal to log(R). That’s right. The function log(). The one in your calculator.

After you get over the initial shock of realizing that your brain is carrying out log calculations as you are reading these words (Yes, even now. And now. ), you start thinking – “why log?”; “what makes it so special?”; The only possible answer comes to mind – evolution.

First you must realize that we do not see 3 dimensions. Sure, we’re all experts at not bumping into things, but we have no receptors for depth. Our eye is flat, and everything we see can be considered to be a 2D image, just like the ones on television. So how come we still have fighter pilots? Our brain uses very elegant algorithms to determine parameters such as depth from the image it receives. One of the algorithms relies on this log transformation – it helps us detect movement. Consider a 2D surface (we’ll consider a circular 2D area – the surface of our eye). A 2D object on that flat surface can transform in three ways:

(if you don’t see any animation, click on the images)

Scaling:

Rotating:

and Transitioning:

Think about what each of these transformations mean in the real world. Suppose something is becoming bigger and bigger in your field of vision… you should probably duck for cover. Rotation is another good indicator that something is being hurled at you, or simply moving in a manner which you should pay attention to, unless you want to finish your day as fast food. Meaning you would probably want to decide to duck/run/attack as fast as you can. That’s where log comes in. Suppose you were the programmer of the human brain. And you need to build an algorithm which detects objects growing in size. Remember – we don’t see things getting closer. We just see them getting bigger. Look at the animated scale gif. Your algorithm needs to detect that the same object is growing in all directions. That will probably not be such a time efficient algorithm. The same goes for detecting rotation (we will get to transition later). This is where the beauty of log comes in. The mathematical qualities of this function dictate that if someone throws a wrench in your direction, the image shown on your visual cortex will resemble this:

(left side – what your eye “sees”. right side – what your visual cortex “sees”.)

In general, scaling will be transformed into movement of the same sized object along the X axis, while rotation will be transformed into movement of the same sized object along the Y axis. The algorithm for detecting such change is much more time efficient. The reason our brain uses the log function stems simply from evolution – it’s a good way to detect danger, so we use it (when I say “we”, I obviously don’t mean just human beings. This didn’t happen overnight ).

I haven’t discussed the last possible movement – transition. But we get over that obstacle using our eyes themselves. Place your finger between you and your monitor. Focus on your finger. Now start moving it in front of you. Almost instinctively, your eyes will follow your finger, leaving it in the middle of your field of vision, effectively nullifying its transition. So that’s how we deal with transition.

Bear in mind: “If the brain were so simple we could understand it, we would be so simple we couldn’t.” – Lyall Watson

Why do we dream?

Some people claim that our dreams are the manifestations of our subconscious, i.e. the brain’s way of telling us what we “really want”. However, I see no logical reasoning behind this claim. In reality, I think it mimics the same way of thinking that leads to religion, astrology, new-age “medicine”, and the likes – human beings like to “personify” things. This claim is explained in Richard Dawkin’s book, the God Delusion.

When giving our dreams meaning, we personify our brain, giving it a separate entity from our own, believing that it somehow “guides” us in our life, bestowing on us its “mystic” wisdom. It is a comforting thought, since it provides us with hope that there is a bigger plan, or that we have a guiding force in our life, a guardian angel if you will, that watches over us and guides us. I see it as a romantic idea, wishful thinking. A human need.

However, scientific doctrine aims to remove humans from the equation, reaching conclusions which do not rely on the human observer. Therefore, if there is no logical explanation for this subconscious, which (or maybe I should say “who”?) tells us what we should do with our life, but only through dreams that we need to interpret using unscientific methods, i.e. intuition, I must look for an explanation which relies on known scientific axioms.

An axiom which immediately comes to mind is evolution.

I will not go into the whole evolution vs. intelligent design debate, since you can find plenty of websites which discuss it, and since frankly I could just as well debate evolution vs. the Flying Spaghetti Monster.

If you “believe” in evolution, and more importantly, if you understand it, you realize that each living organism on this planet looks the way it is today since, quite simply, all the other ways were not good enough. In other words – its current state is dictated by whichever changes that allowed it to survive better. This survival is not an inner mechanism or something that drives it. There is no “force” which makes evolution exist. Things which are best suited to survive do just that because they are best fitted to do so. Kind of recursive

So let us go back to the title of this blog entry – “Why do we dream?“

I offer an evolutionary point of view, combined with computer science thinking.

The human brain is composed of connections. The more we think in a certain way, the more certain connections become stronger, reinforced. That is why astronauts undergo extensive underwater training before going on missions. It takes time for the human brain to adjust to new points of reference in space. Astronauts in microgravity usually lose their sense of direction and feel uncoordinated or clumsy. Because inner ear and muscular sensors seek terrestrial clues, astronauts must learn to rely on visual cues for balance and orientation. But even visual cues can be confusing – astronauts in microgravity need to adjust to the fact that up and down don’t really matter in space like they do on Earth. They need to “force” their brain to think differently, and that takes time.

The same goes for human emotions. If for example you are a person who is always depressed, you will not be able to change overnight. Changing your way of thinking and behaving will take time, since you are “re-wiring” your brain (however, if you want a “quick fix”, you can always get a brain pacemaker transplant – http://en.wikipedia.org/wiki/Brain_pacemaker). The more you think differently, the more these connections become stronger, and the other become weaker. It is a very elegant code if you think about it from a programming point of view. It makes itself more efficient and streamlined, according to the relevant needs. Human emotions might not relate to evolution so clearly, but if we consider other brain functions such as moving about, breathing, or recognizing a lion in the bushes – it is vital for our survival that we carry out these actions successfully and as quickly as possible. Our brain has evolved in a manner which makes sure that whatever we do the most – i.e. whatever we need to do to survive more, we do as efficiently as possible. Assuming of course that whatever it is that we do the most is beneficial for our survival – perhaps not so true in the 21^st century (for instance, I don’t think that reading this article improves your chances for survival, although I’ll be flattered if you think so), but most definitely true in most of our evolution, which took place in the wild, in much more harsh conditions.

[peek-a-boo]

So the connections in our brain constantly grow stronger in various ways, according to what we do and how we think. It has been known for quite some time that the augmentation of these connections mostly happens when we sleep, as corroborated by a recent study (http://www.eurekalert.org/pub_releases/2008-01/uow-sbc011808.php). This is known as plasticity (http://en.wikipedia.org/wiki/Neuroplasticity). It also makes sense – as every person with a computer knows – it isn’t very smart to install/uninstall computer programs while they are running.

So why do we dream? Well, my hypothesis is that our dreams are a “system-check” carried out by our brain. When you go to sleep, your brain shifts synapses in your brain, making some connections stronger, some weaker and perhaps even creating new connections or completely severing old ones. After making each change – it is a good idea to run a system-check, don’t you think? That is also why our dreams seem so real. As far as we are concerned, the messages in our brain when we dream are identical to the ones we get when we are awake – or else it wouldn’t be a very good systems-check, now would it? Also, that is why dreams relate to memories – that is the information the brain has available to use for its systems-check. Furthermore – dreams usually relate to recent events, since those are usually the areas which get modified.

But the most important part in my hypothesis is why I think my argument is true. After all, I can find lots of explanations for why we sleep, why is mine more logical than the rest? Well, I suggest that this systems-check is a direct result of evolution.

Consider that our brain evolved, and we started making more and more connections. Obviously, these connections were augmented in our sleep, since if you started making changes in your brain while you are awake and running away from a cheetah – well, let’s just say your survival chances were not very good.

But some individuals also started having dreams. Those dreams were the systems-check carried out by their brain, making sure that all of these new connections were OK.

So those who had dreams one-upped their fellow tribe-members evolutionary-wise. They had less chance of suffering the consequences of “faulty-wiring”. And we all know how one bug in a program can wreak havoc…

No rest for the wicked

I am currently SWAMPED under the workload from the university (finals period), so I’ll continue writing new posts as soon as I finish. Should be around early-October.

On the Abundance of Information

If I lived 50 years ago, I think I would have been very frustrated (although I probably wouldn’t be, since I wouldn’t know any better. So allow me revise my previous statement: if you were to send me to live 50 years in the past, I would have been very frustrated. Wait, should I say “would have been” or “would be”? Grammar is always so difficult when you time travel )

The reason I would be so frustrated is the lack of available information. We live in an age, that if unless you are looking for something very confidential, you are able to find the information you need and fast. How does the old saying go? If you looked for something on Google and came up with no results, then it means you have a very specific fetish

However, this plethora of data has its own inherit problems, the greatest one being able to determine which information is relevant and correct. A lot of people claim that this new abundance of information is actually a “wolf in sheep’s clothing”, saying that you can’t really trust anything you read, and nothing is reliable.

To which I reply: “baloney!”

Lets review the evolution of information:

1) Information is not free and it is controlled (i.e. the writers and editors of encyclopedias, newspapers, etc.) by a small group of people, and the only way to attain this information is to be born into royalty or other form of high class - except for newspapers, which is usually a means for the small group to convey their idea of the truth to the masses (pretty much the way things were up until the mid 20th century).

2) Information is free, monitored by a bigger group of people (i.e. gives room to different opinions), but attaining it is cumbersome and not easily available to everyone (think 1950′s-1980′s).

3) Information is free, monitored by everyone and for everyone, which results in a great deal of unreliable information.

I still prefer the third option. Allow me to explain.

The way I see it, the third option is the best because it puts the power in the hands of everyone. Sure, back in the 1950′s the information you received was considered more reliable, but your choices were limited. I prefer that you let me decide what seems reliable and what doesn’t, instead of giving me only one source of information, which you decided to be true.

Yes, there’s a lot of stupid people out there saying plenty of stupid things, passing them off as intelligent data. But it doesn’t mean there isn’t also some useful information out there. For instance, right now I’m a CS (Computer Sciences) student in Tel-Aviv University. Wikipedia and Google are my best friends. If I could add them to my facebook profile, I would :-). Whenever I come across any new mathematical/computer-related term, I simply look it up, see the definition, or read an answer from a forum addressing what I need to find out (e.g.: I need to convert a Double expression to String. This is a relatively simple thing to do in Java, but when you are starting out, you still don’t have all of the syntax down. A simple search of: “java double to string” in Google will yield the proper method) and carry on.  Why, even if I’m in the middle of a lecture, and the teacher mentions something which I don’t understand, I simply use my iPhone to look up the relevant information, get my bearings, and carry on with the lesson. Try to imagine the same situation 10 years ago, when the internet was just starting to grow. Now try to imagine it 50 years ago .

Since the information I’m looking for is mostly mathematical, the degree of “stupidity” I encounter is minimal. Problems start appearing when you are looking for information other than mathematical definitions. Let us say I was looking for a biography on Albert Einstein. Well, the first place I’d probably go to is Wikipedia. And it’s not a bad place to start. It’ll definitely be Google’s first result. People badmouth Wikipedia all the time, but personally I think it is a wonderful source of information. I wouldn’t use it for scientific research (since it is not 100% accurate), but it is a highly reliable and relatively very accurate source of information. The problem is that once you start looking for information such as biographies, history, art, society, etc., the reliabilty of the information decreases. And not because people have got their facts wrong (which is also a problem, but usually not in the websites I’m talking about), the problem is people are confusing facts with opinions.

When I look up the definition of what is a “Kernel” in linear algebra, there isn’t too much room for opinions. It’s a pure mathematical definition, and the only difference (barring any mistakes in the definition itself) between the various sources of information could be in the manner in which the term is explained – which is very useful, since people understand things in different ways (now compare that with the 1950′s, where you had only one textbook, and if you didn’t happen to think like the person who wrote it, your studies just became a whole lot more difficult). However, if I look up a controversial issue, like for example: ”Jerusalem”, the information will not be accurate. I don’t mean that I’ll necessarily see false information, but rather that specific information will be ommitted or mentioned, according to the writer’s point of view. And people consider that a major issue. But now comes my next point – how is that different from the professor writing the article for Britannica? Doesn’t he also have his own opinions, prejudices and view of the world? His only advantage is that he is an expert on the subject. But does that mean he’ll be objective?

This raises the great question of “what is the truth?”, but I think I’ll overextend myself trying to tackle this subject. Maybe another time.

To sum matters up – I believe that the more information, the better. Smart search engines like Google and its ilk, as well as good ol’ common sense, will help us seperate the relevant information from random ramblings of nitwits.

Procrastinators – unite tomorrow!

Yes, I haven’t written in a while. I have something in the works, but once again, the post-lecturers’-strike-university rears its ugly head, consuming every minute of my free time.

So in the meantime, enjoy this fascinating article about how the universe might not only be described by math, but made up of it as well!

The Prettier Side of Math

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