Two examples of schemes that may not work were given last time. Although Cleo might be lucky, there's no way to be sure she isn't heading in the wrong direction, or just too slowly to catch Tony up. But what if he weren't moving? In other words, what if he has velocity v = 0? Then the second method will eventually catch him, although the first still might not. In this case, Tony is fixed, unmoving, at a point x. Suppose Cleo checks slab 0 first, then 1, then -1, then 2, then -2, and so on. Here is that diagram from last time, with step-numbers labelled:
Whatever x may be, she will eventually reach it in a finite number of steps. She checks 0 on the initial try (call this time t = 0), then 1 at time t = 1, then a positive slab every 2 attempts. So if x is positive, she checks slab x at time t = 2x - 1. Similarly if x is negative, the time is t = -2x + 1. Although Cleo can't be sure at what time she'll find Tony, she knows that it is finite.
What all of the above comes down to is the notion of 'counting' an infinitely-large set. Colloquially, 'infinity' is often used to refer to an unimaginably large quantity, such as the size of the universe, and has a connotation of 'going on forever'. This is similar in spirit to the mathematical meaning, but here infinity has a very precise definition - in fact, several very precise definitions, since there is more than one kind of infinity!
First, think of the set of whole numbers {1, 2, 3, ..., n} with no numbers missed out. Call this set [n]. Unsurprisingly, the size of [n] is n. This is a set with finite size. But this is only a smaller part of the full collection of positive whole numbers {1, 2, 3, ...} going on forever. This collection is referred to as the set of 'natural numbers', denoted N. How big is this set? Since [n] is contained in N, we know N has at least n elements, since that is the size of [n]. But there is no limit to how large we could take n. If we tried to claim the size of N to be some number m, we could immediately disprove that claim by taking n = m + 1. This is what it means to say that N is infinite: for any number we choose, we can find a quantity of elements of N that exceeds that number.
You could say the same of other sets of numbers, such as the negative and positive whole numbers (including 0) - referred to as the integers Z - or just the even integers, 2Z. What is the size of the set of positive square numbers, {1, 4, 9, 16, ...}? It's infinite again, since however big you choose m, the set {1, 4, 9, ..., (m+1)²} contains only square numbers and has m + 1 elements. But what all these sets have in common is that they are 'countably' infinite. This means that they can be written down in a list without missing a single element of the set. For the natural numbers, this list could simply be 1, 2, 3, ... . For the integers, it could be Cleo's 'motionless Tony' algorithm 0, 1, -1, 2, -2, ... . We could explicitly label the step at which each number appears:
1. 0
2. 1
3. -1
4. 2
5. -2
...
This is precisely the meaning of countably infinite: there is what's known as a bijection between Z and the natural numbers: each element of N is coupled with precisely one of Z. In this sense, the two sets are 'the same size'. This seems counter-intuitive! It seems that Z should be 'twice as big' (at least) as N, because it contains every element of N as well as its negative counterpart. Another strange phenomenon is that the order in which you count the same set can determine whether or not you 'hit' all of it: compare the above method of counting Z with simply counting in the ascending order 1, 2, 3, ... . The second version misses all the negative numbers, no matter how far you go.
This is something first-year undergraduates at university have to get used to, which they often do kicking and screaming. The thing is, there's just no sensible meaning to the term 'twice as infinite', because infinity isn't a number, but the concept of a magnitude a number can't possibly exceed. It can be dangerous trying to apply an intuitive notion of what 'size' means in a situation where that idea breaks down, and our definition of infinity doesn't attempt to do that. The vital thing is that our results are consistent under this paradigm, however weird they occasionally seem, and mathematicians define infinite sizes as described above because it's the convenient way to think about maps from one set to another*. If they want to know whether it's possible for a function to take a value in N and spit out a value in Z, the answer is 'yes', because the sets are both countably infinite. And this is useful, because it's precisely the property of Z that Cleo uses to guarantee than she can scan through it without missing a value. Notice that even though Z is infinite, because it is countably infinite, there is no value that cannot eventually be reached, given enough time. Conversely, it's impossible to 'search' the entire set of decimal numbers in such a way, so this set (known as the 'real numbers', R) is called uncountably infinite.
So Cleo has used her understanding of infinite cardinalities to determine that if Tony is motionless, she can find him so long as she persists long enough (and they say the education system is being dumbed down!). Unfortunately, Tony probably is moving. It's no good being able to check every integer exactly once if Tony appears at that slab of pavement before or after Cleo checks it. Is there a way to get around this?
The answer, amazingly, is yes! Remember that Tony has two unknown parameters: his velocity, v, and his initial position x. If she knew what both of these were, Cleo would know exactly where along the pavement Tony is at time t: it's his initial position, plus his velocity times the number of minutes that have passed. So if we call his initial position x(0) = x, and denote by x(t) his position at time t, then
x(t) = x + t*v.
Knowing this, Cleo can 'try out' a pair (x,v) of parameters to see whether they are correct, by keeping track of the passage of time and checking slab x(t) for the current t. So long as she has a way of checking every possible combination of parameters, she will find Tony. One way to do this is to imagine a grid of numbers, with the x parameter along the horizontal axis and the v parameter along the vertical axis. Now starting with t = 0 at coordinate (0,0), Cleo checks the parameters x = 0, v = 0, then moves in a spiral pattern to (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (1,2), (0,2), (-1,2), and so on. What she is actually doing is 'counting' the infinite number of points as shown in this two-dimensional grid (numbers indicate the time this coordinate is visited).
The first time you see it, I think it's kind of intriguing that adding a whole new dimension doesn't prevent the new set of points from being counted just like the one-dimensional number line (of course, this would be considered a banality for seasoned mathematicians!). The diagram, however, makes it apparent that every single coordinate will eventually be enveloped by the spiral**. To be clear, the diagram doesn't explicitly indicate spatially where Cleo should search: she is navigating an imaginary parameter space which she then converts into a point on the pavement using the formula for x(t). The result of this method is that Cleo would check the following squares:
(0,0), t = 0: x(0) = 0 + 0*0 = 0
(0,1), t = 1: x(1) = 0 + 1*1 = 1
(-1,1), t = 2: x(2) = -1 + 2*1 = 1
(-1,0), t = 3: x(3) = -1 + 3*0 = -1
(-1,-1), t = 4: x(4) = -1 + 4*(-1) = -5
(0,-1), t = 5: x(5) = 0 + 5*(-1) = -5
(1,-1), t = 6: x(6) = 1 + 6*(-1) = -5
(1,0), t = 7: x(7) = 1 + 7*0 =1
(1,1), t = 8: x(8) = 1 + 8*1 = 9
(1,2), t = 9: x(9) = 1 + 9*2 = 19
(0,2), t = 10: x(10) = 0 + 10*2 = 20
(-1,2), t = 11: x(11) = -1 + 11*2 = 21
...
Notice that Cleo may check the same square many times, even staying put for several consecutive minutes. By following this strategy, she can be sure of finding Tony the moment she picks the correct pair of parameter values. So we're done!
I like this problem for a couple of reasons. Firstly, it is fairly simple to describe, but the answer gets to the heart of some fairly chewy thoughts about the nature of infinity and the unusual way in which it's traversed. Secondly, to solve the problem it's enough to describe the method of checking pairs of parameters and prove that this two-dimensional parameter space can be explored with a diagram like the one above, but this graphically simple answer hides a level of complexity that is revealed only if you work out the exact values of x(t) at each time point. The sequence 0, 1, 1, -1, -5, -5, -5, 1, 9, 19, 20, 21, ... doesn't, at first glance, appear all that predictable, in spite of the simple mechanism behind it. Part of what mathematicians come to love about their field is the hidden complexity behind ideas that can be expressed very simply. Because the answers can behave in ways that cannot be anticipated, the process is a lot like exploring a new and unknown land, created the moment a new concept is imagined (or perhaps it 'existed' all along - ask a mathematical philosopher!). Even the natural numbers, so simply defined, burst almost immediately into a cornucopia of properties, the unpredictable nature of the prime numbers being one example.
So, will Cleo actually find Tony? If she persists indefinitely, the answer is yes, but although the success time is finite, she doesn't know how large it is and would have to live indefinitely to be certain of success! The weird thing about a countable infinity is that every given element can be reached in finite time, but no matter how far you count, there will always be infinitely-many that remain untraversed. If you tried to express the progress you'd made as a percentage, the only sensible answer would be 0%, because to have any other value, such as 0.0001%, would be to suggest that you only had to carry on (for this example) 999,999 times as long as you already had done to reach the end. You won't! Infinity defies any attempt to visualise its magnitude.
Actually, Cleo's patience lasted even less time than her mother's, and after half an hour's trundling up and down the road she gave up and went inside to paint fractals on the walls. Tony had a near miss with a chef from the Insectivoracious restaurant, but escaped with the help of a vegetarian spider and went on to become one of the great forefathers of the insect-arachnid peace movement. If you see him giving a speech on a little podium, try not to step on him.
* Sometimes when asked 'why does maths work this way?', the boring answer is that it's a matter of definition, rather than some mysterious, universal truth. A definition might be chosen because it seems to extend our intuition in the most logical way without causing contradictions, or because it is the most useful choice when it comes to answering related questions. You might come up with a different notion of 'infinity' that didn't behave this way, but it would be best to call it something else, since the results you prove using it won't be the same. As I note later in the article, the mystery is what follows once you've laid down your definitions and start to see what you can do with the ideas that spring from them.
** It would also be possible, however, to choose a path that went on forever but didn't cover the entire grid. Imagine going up one from (0,0) to (0,1), then diagonally down to (1,0), then across to (2,0), then diagonally up through (1,1) and (0,2), up to (0,3), and so on, following all the diagonals with positive coordinates. This only covers a quarter of the whole grid. The path (0,0), (1,0), (2,0), always moving horizontally to the right, is a truly pathetic effort!
No comments:
Post a Comment