## Saturday, July 16, 2011

### Remembering how to count

Today, rummaging through the boxes of books that follow me from house to house, I stumbled on a first edition, 1940 hardbound copy of Mathematics and the Imagination by Edward Kasner and James Newman that my mother gave me years ago.  Kasner is probably best known for having come up with the name - or more precisely goading a child into inventing the name - "googol."  The book begins with a delightful account of how the very large, but finite is sometimes confused by adults and "moderns" with the infinite, but small children and the ancient Greeks could see things more clearly.  I like this quote:
The Greeks had very definite ideas about the infinite.  Just as we are indebted to them for much of our wit and learning, so are we indebted to them for much of our sophistication about the infinite.  Indeed, had we always retained their clear-sightedness, many of the problems and paradoxes about the infinite would never have arisen.
The authors do a really nice job motivating what was to me as a student just a definition - that cardinality is based on one-to-one correspondences.  What they bring out really nicely is how this really is just counting.

Another great point that comes out in many places in the book is how mathematicians often choose what turn out to be stupid names for things, because we can name them before we know them.  A great example is "transcendental numbers."  Such a name suggests something exotic or rare.  It turns out that almost every real number is transcendental.

What does that mean, exactly?  I am going to try to explain this in less time than it takes you to get bored - in just a short walk through a truly beautiful neighborhood built by Georg Cantor.

A transcendental number is a number that cannot be expressed as a solution to a polynomial equation with rational coefficients.  The square root of two, for example, is not transcendental because it is a solution to the equation x2 - 2 = 0.   It turns out that both e and π are transcendental. Initially mathematicians thought this was a very special property worthy of such an exalted name.

Cantor saw two things: 1) algebraic numbers (the complement of transcedental numbers) can be put into one-one correspondence with the set of natural numbers (i.e., they are countable) 2) the whole set of real numbers is uncountable (cannot be put into 1-1 correspondence with the natural numbers).  That means that all but a comparatively tiny set of real numbers are transcendental!  You can take away all of the algebraic numbers without affecting the size of the set of real numbers (or leaving any "holes" in the real line).

Imagine a spreadsheet with an infinite number of rows and columns:
A0 A1 A2 A3 ...
B0 B1 B2 B3 ...
C0 C1 C2 C4 ...
D0 D1 D2 D3 ...
...
Cantor realized that as long as the row and column indexes were all natural numbers,  the entire set of cells could be put into 1-1 correspondence with the natural numbers (i.e. "counted") by just starting in the top left corner and following a path that snakes outward along the diagonals:  A0, A1, B0, C0, B1, A2, A3, B2, C1, D0, D1, C2, B3, A4, ...

Since the rational numbers are just numerator/denominator pairs of integers, the technique above can be used to count them - i.e., to show that the rationals are countable.  But really, what it shows is that 1) the set of ordered pairs of any countable set is countable and 2) the union of countably many countable sets is countable.  The second is clear when you think of the rows of the spreadsheet as enumerations of the elements in the sets over which the union is taken.

Now imagine a "spreadcube" - a rubix-cube like thing that has little subcubes for cells.  Again, imagine it as countably infinite in all three dimensions.  The "pick a corner and snake out" game works there too.  So the set of ordered triples (a, b, c) from any countable set is also countable.  To get to the next dimension, you can either just test your 4-dimensional intuition (too hard for me) or just look at (a, b, c, d) as ((a, b, c), d) and use the fact that there are only countably many (a, b, c) (note that we could have done this for n = 3 instead of imagining the spreadcube).  Obviously, there is no stopping us here, so we see that for each n, the set of n-tuples of elements from any countable set is countable.   Since the coefficients of a polynomial determine the polynomial, that means that for each n, there are only countably many polynomials of degree n with rational coefficients.  By 2) above that means that there are only countably many polynomials with rational coefficients.  Each of these has only finitely many roots, so the union of all of the sets of roots of all of the polynomials with rational coefficients is countable - i.e. there are only countably many algebraic numbers.

Now the coup de gras.  Since we seem to be able to count everything, lets suppose that via snakes, pairing or some other ruse we have managed to enumerate the real numbers - i.e., we have put them in a list that goes r0, r1, r2 ... and eventually hits every real number.   Every real number has a decimal expansion.  Some terminate, like 5.2, some repeat, like 0.333333 and some, like π do exotic things that keep computers busy for indefinite amounts of time; but all have decimal representations and two real numbers are equal if and only if they have exactly the same values in their decimal expansions in every digit .   Suppose that our enumeration looked like this:

r0 = 12.238769045
r1 =  3.1415923988888
r3 = 23.1783459823999
...
Consider the number r = 0.359 in relation to the three numbers above.  It is obviously not equal to any of them.  It was constructed to be different from any of them as follows.  Put a 3 in the first decimal digit because r0 has a 2 there; put a 5 in the second decimal digit because r1 has a 4 there; put a 9 in the third decimal digit because r3 has an 8 there.   Now imagine the list continuing.  We continue to define the decimal expansion of our "special" number r making it different from the nth element in the list in the nth decimal place.  The result will be a number that differs from every number in the list.  This is a contradiction,  proving that no such enumeration can exist.

This is not a satisfying place to leave Mr. Cantor's neigborhood, since we have not succeeded in counting the real numbers at all.  So even though you are likely, like my dog Casper, getting a little tired of this walk, I need to stop by one more place on the way home.   To count the real numbers, lets start by convincing ourselves that it suffices to count the elements of the open interval (0, 1).  Look at the middle section of the graph below of the tangent function

The middle section of this graph shows that (-π/2,π/2) can be mapped onto the full real line. Every y value in the graph corresponds to some x value in the bounded open interval above.   The graph depicts a one-to-one correspondence between the whole real line (the y axis) and the little π-length interval in the middle of the picture along the x axis. Just squishing the picture a little and moving it to the right shows that (0, 1) could similarly be mapped onto the whole real line.

Now, similarly to decimal representation, every real number has a binary expansion.  The number 1/2 is 0.1 in binary, 0.11 is 1/2 + 1/4 = 3/4, 0.101 is 1/2 + 0/4 + 1/8 = 3/8 and so on.  Like decimal expansions, binary expansions are unique, some terminate and some don't and two numbers between 0 and 1 are equal iff their binary expansions have 1's (or 0's) in all the same places.   Therefore, there is a one-one correspondence between the real numbers between 0 and 1 and the set of subsets of the natural numbers.  Let each real number correspond to the set of natural numbers where its binary expansion has a "1".  So 1/2 corresponds to {0}, 3/4 corresponds to {0, 1}, 3/8 corresponds to {0, 2} and so on.  The set of all subsets of a set is called the power set of the set.  The above shows two important things: 1) the power set of the natural numbers in uncountable and 2) the power set of the natural numbers has the same cardinality as the real numbers.   An interesting question is does there exist a size in between the natural numbers and the real numbers.  We are not going to see an answer to that question in this neighborhood.

 Strictly speaking, some numbers have two infinite decimal expansions.  For example 0.9999999 (repeating indefinitely) equals 1.  We are assuming above that all of the representations selected are minimum length (i.e. if there is a finite representation, choose that).