About 2 weeks ago, I decided that I was going to give a talk to the final year IB students on the topic of countable and uncountable sets – basically speaking, on the different sizes of infinity. Whilst I know about the main concepts behind this topic, I wasn’t sure of some of the minor details. One of these ‘minor’ details has frustrated the living daylights out of me since that point 2 weeks ago so I thought that I’d share some of the tribulations I’ve had during this process.
It will certainly help if I put this problem into context first.
If somebody asked you whether the set of natural numbers (i.e. the positive whole numbers 1,2,3,4,…etc) is the same size as the set of even numbers (2,4,6,8,…etc.), what would you say?
There are a lot of people who would say that the set of even numbers is half as big as the natural numbers. Indeed, this was generally considered to be the case until not too long ago when Georg Cantor decided to shake things up a bit and completely change our notion of infinity. He showed that these two sets have exactly the same size (we use the word cardinality instead of size in set theory). If you’ve not encountered this before, you’re probably thinking that I’m talking complete rubbish. I mean, how can they possibly have the same cardinality?
Cantor showed that if every element of the natural numbers could be mapped onto every element of the even numbers then they must have the same number of elements (this means that there exists a bijection between the two sets). It’s easy to show the mapping from the naturals to the even numbers.
Natural numbers, N = (1, 2, 3, 4, 5, …)
Even numbers = (2, 4, 6, 8, 1o,…)
As you can see above, 1↔2, 2↔4, 3↔6, 4↔8, 5↔10, … n↔2n. So every element in the natural numbers has a corresponding element in the even numbers. Hence they must be the same size! Pretty interesting eh!
Whilst I’d love to talk in more depth about Cantor’s discoveries, I think I’ll stop there with the intro and move onto why this is relevant for my ‘minor problem.’
So, once I’ve introduced this notion of countable sets to the students, I wanted to ask them whether they think that the natural numbers and the set of all possible integer co-ordinates have the same cardinality. As mentioned above, this boils down to whether there exists a bijection between the two sets which boils down even simpler to whether both sets can be written down as a list (of course this is theoretically speaking because we wouldn’t be able to write the entire list down but then we could imagine the list). Thus, is it possible to write down all the negative and positive whole number co-ordinates on a grid as a list? If so, where should I start my list? (-100000, -100000), (0,0) or (117, 22)?
Cantor showed that it is possible to write this down as a list starting with the co-ordinate (0,0) and spiralling outwards to (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), etc.
Hence, there does exist a bijection. e.g. 1↔(0,0), 2↔(0,1), 3↔(-1,1), etc. which means that both of these sets have the same cardinality – again, pretty amazing!
Now here comes the problem, I thought it would be a nice little task to try to write a program on geogebra to model this starting at (0,0) and spiralling outwards. The task turned out to be extremely un-nice and not at all little.
I could go through every strategy that I tried out on the post but it would simply take me way too long to explain with the necessary diagrams. I will say though that I was initially convinced it would have something to do with the trigonometric functions because to get from one point to the next, you either add 1 (sin(π/2)), add 0 (sin(0)) or subtract 1 (sin(-π/2) to the x and y coordinates. Anyhow, that turned out to be a little more difficult then expected. I then thought that it may involve a complex number method in which I could continue to multiply each complex number by cos(π/4)+isin(π/4) which would rotate it by 45 degrees (note that π/4 radians is 45 degrees) about the origin. Of course in this case, I wouldn’t actually hit the integer co-ordinates so I had to use the round() function in geogebra to rectify this. The problem with that was that I couldn’t figure out how to increase the distance away from the origin once it’d got to the 8th point in the cycle. Anyway, it turns out that after 4 hours of trying, I was pretty naïve to how complex the problem actually is. I did figure out how to write an easier program using line segments but that completely missed the point of why I wanted to do it in the first place. Hence, I decided to ask for a bit of help.
I posted my problem up on the Ask NRICH forum and got a quick reply from Adam Goucher (check out his blog: CP4 Space). After I didn’t understand his first reply, he ended up posting a solution on the forum. If I inserted a slider (n) into geogebra and then inserted the function below into the tool bar then I would have the program that I desired.
Just a tad bit more complicated than I’d expected! (Don’t be put off by the floor() function. It simply takes a number and rounds it down to the nearest integer) Here’s the geogebra file if you want to see it working in action.
Initially, I wondered how anyone had arrived at this result. I couldn’t see how I’d ever have been able to put this together. Having said that, when Adam broke it down into its main parts for me, it’s not horrendously difficult to see how it all comes together to result in the spiral shown.
The easiest way to look at it is to assign parts of the formula to their physical relevance in the program. Labelling parts of the formula as p and q we have:
So that the formula becomes:
Now, the best way to get a hold of what the individual parts do is to open up the geogebra file, change the value of the slider with the algebra view open and look to see what the connection is between p, q and the program (Look at the right hand side of the applet in the algebra view to see how p and q change as you change the slider).
[Read no further if you want to have a go at figuring out what p and q represent by yourself]
If you do this, you’ll soon notice that p represents which line segment we’re at. Obviously the first line segment is between (0,0) and (0,1), the second is between (0,1) and (-1, 1) etc. The variable q represents at which point on the line segment we’re at. The first point on the line segment being the zeroth point, then the first point, then the second etc.
The floor((p+2)/4) component is the perpendicular distance of the line segment from the origin, which means that it also represents which ‘square’ we’re on in the process.
Since multiplying a number by i represents a rotation of 90 degrees in the plane, by multiplying the entire section [floor((p+2)/4)-floor((p+1)/4))i] by i^(p-1) we can rotate the complex number by 90 degrees every time we arrive onto a new line segment.
Having never really done any programming before, it is great to see how all of the sections work together to produce the final spiral. It gives me a real sense of how a computer programmer has to think when they’re working on a problem by breaking it up into manageable steps bit by bit.
There’s no way that I would have come up with anything close to this, but I do feel that if I come to tackle a similar problem in the future, I’ll be more equipped to ‘think like a programmer’ and be more methodical in my approach rather than simply messing about with it until I’ve had enough and need to ask for help. It was an interesting learning experience and all made possible with the help of Adam Goucher – thanks Adam!