Mathematics for Game Developers 6: Real Numbers part 2

John-McKenna 8:14 pm on January 9, 2012 Counting comments...

Last time we discovered that the rational numbers, despite appearing to be densely packed with infinitely many packed in between any two, they aren’t enough to represent many things that intuition says should be numbers.

Our first example is the square root of 2.  Now, because there are so many rationals, and they’re so densely packed, we can easily find ones that get as close as we like.  It is obvious that 1 is a poor approximation, since |2-(3/2)^2| = 1.4.  4/3 is a little better, 7/5 better still.  We can keep going for as long as we like, getting a sequence of numbers whose squares get closer and closer to 2.

Can we use that sequence as our definition of this new number?  We could define addition and multiplication as the sequences that we get by adding or multiplying each element of the sequence, so (1, 3/2, 4/3, 7/5, \ldots)\times(1, 3/2, 4/3, 7/5, \ldots) = (1, 9/4, 16/9, 49/25, \ldots).

That’s not bad, but it has a problem.  We’d like there to be just one way of representing a number, and there are many sequences that would do.  The square root of 2 could just as easily be represented by (1, 14/10, 141/100, \ldots).  Which sequence do we choose?

The answer is to choose all of them.  We find a way of determining when two sequences represent the same number, and declaring our new numbers to be the equivalence classes under this relation.

But first, we need to identify which sequences we’re allowing.  A sequence like (1, 2, 3, \ldots) won’t do, because that just heads off into the distance, and never looks like it’s settling down on anything.  We don’t care what happens near the start of the sequence – all we’re interested in is its long term behaviour.  We want elements of the sequence to get closer together the further we look along, and eventually get as close together as we’d like.

What we’re looking for are Cauchy sequences, named after the French mathematician Augustin-Louis Cauchy, who was one of the early pioneers of the study of infinite sequences.  For any positive difference we care to name (as small as we like, but never zero), there is a point in the sequence after which every pair of elements is less than that difference apart.  That is, for any |a_n - a_m| < \epsilon (here, latex a_n$ is the nth element of the sequence.

For example, the sequence 3.14159 - 3.14 = 0.00159 < 0.1, say.

What we need now is a way of deciding whether two sequences are equivalent.  What about subtracting them, term by term, and seeing if the difference heads towards zero?  Would that work?  Intuitively it should – we don’t care what happens at the start, but eventually they should both settle down in the same vicinity.  So we say that two sequences are equivalent if their difference is a null sequence – a sequence that heads towards zero.

We can tighten up the definition of a null sequence in a similar way to that of a Cauchy sequence.  A sequence a_n < \delta.

For example, \delta.

It isn’t obvious, but the relation we’ve defined here (two Cauchy sequences are equivalent if their difference is a null sequence) is an equivalence relation.  The proof isn’t difficult, but it isn’t very interesting, so I’ll skip it.

So now we have the real numbers: they’re the equivalence classes of Cauchy sequences of rationals.  And we can define addition and multiplication fairly simply: to add (or multiply) x and y, take one sequence from x and one from y, add (or multiply) each pair of terms to give a new sequence, and then find the equivalence class containing it.

Of course, there’s no way you could actually do that: it requires infinitely many operations.  But if we want the real numbers (and they are useful sometimes), we don’t have a choice.  We work symbolically, and whenever we have to do calculations we resort to rational approximation.