Division by Zero

I recently read the short story collection Stories of Your Life and Others, the first book of Seattle-area resident Ted Chiang, and my one-word summary of it would be 'rocking'. It contains some extremely excellent short science fiction, including 'Understand', which you can read for yourself online thanks to the nice folk at Infinity Plus. 'Understand' is a tale of intelligence augmentation, and it's up there in swellness with Thomas Disch's Camp Concentration. There is also, and this won the collection a special place in my heart, a story, 'Seventy-Two Letters', about golems. Also the more-or-less eponymous tale 'Story of Your Life', which reminded me of, and suggested sharp constrasts with, Kurt Vonnegut's Slaughterhouse-Five, or more accurately vice-versa, since I read Chiang first; Chiang's piece differs primarily in being much less depressing. About all this I may say more in the fullness of time, but for now I wanted to have some words about the one story in the collection that I found less than entirely satisfying: 'Division by Zero'.

The premise of 'Division by Zero' is that a gifted mathematician develops a new formalism which leads her to discover that arithmetic as a system is inconsistent: she finds a way to prove, rigourously, that all numbers are in fact equal, and thus that arithmetic, and by extension pretty much all of pure mathematics, is meaningless. It sends her into bleakest despair and basically ruins her life. Which is understandable; to a mathematician, being told that mathematics just doesn't work would be about the worst thing imaginable. The thing is, I can't bring myself to suspend my disbelief. It's hard to swallow, in a way that golems or Babylonians building a tower all the way to Heaven aren't. With golems, if you make one simple assumption--that Kabbalism can replace the physical sciences--the rest follows logically. (Which is one of the best things about Chiang: everything follows so wonderfully logically!) Here...I think that is not quite the case. Maybe I'm saying that because I am, or hope to be, a mathematician myself; the idea of maths just not being true...Well. It'd be brown trousers time, for sure.

I am, like many mathematicians, a Platonist at heart. I don't believe there is literally a world of idealised mathematics made solid floating around somewhere in the formless void, but I can't help but view mathematics more as a process of discovery than of invention; true theorems weren't any less true before they were formulated and proved, after all. If they are true now, they have always been true, and they're universally true, even multiversally true: true independently of the physical world and any of its parameters. (Modulo the appropriate definitions, of course.) So the idea of maths not holding water...It's like destroying an entire universe, albeit one I perceive only indirectly. A universe, by the way, without George Bush in it.

But I think I have some firm, logical basis for my unease, beyond my epistemological and ontological qualms. Renee, the unfortunate mathematician in the story, develops a new formalism which allows her to rewrite unspecified axiom systems, and thereby prove, in essence, that 1=2. I am not a logician (an algebraist, actually, probably a representation theorist), but I do know a little set theory (which no-one else in the department seems to enjoy, damn them) and I'm familiar with the axiomatics of arithmetic. An axiom system for workaday arithmetic, called the Peano postulates, was devised by, of all things, a chap called Peano in 1889. It's possible Renee was working with these, but unlikely: the Peano postulates aren't very fundamental. If you assume ZFC set theory (Zermelo-Fraenkel, with Choice), or an equivalent, which you're more or less obliged to do to do any modern mathematics whatsoever (unless you're some kind of silly Intuitionist) you can prove the Peano axioms as theorems about the set of natural numbers; if the Peano postulates are inconsistent, then ZFC is inconsistent as well. So Renee has discovered that ZFC is self-contradictory, that 1=2 when it is axiomatic that 1 and 2 are, by construction, very different entities. This would be bad. But not that bad. This doesn't mean that mathematics in general or arithmetic in particular are themselves, in their Platonic forms, inconsistent: it means the axiom systems Renee and I have been using are, which is not at all the same thing. You can always replace your axioms. Maths has been bitch-slapped like this before, and come out all the stronger for it. Cantor's original naive set theory was inconsistent, but that didn't destroy set theory; it just meant it needed different foundations, like ZFC. If ZFC were itself inconsistent, while I'd be quite shocked, I'd also be confident that a replacement scheme could be devised. I can't imagine it'd drive anyone to suicide...

I just don't buy it. But do buy the book. The rest is, as I said, very fine.

(And what's so implausible about transfinite induction?)

Anyone interested in learning about set theory from a naive, or non-axiomatic, perspective, which is the best way to see it first, would do well to seek out Paul Halmos's Naive Set Theory, which is accessible to the tenacious layman. For a much shorter and less comprehensive introduction with more sex in it, read on...

(Edited slightly on 17 June for clarity and extra bitch-slapping.)

The most basic area of mathematics, or the most basic interesting area, if you ask me (and I acknowledge in advance that you didn't) is set theory, which is, as you might have guessed, the study of sets. Sets are exactly what you'd think they are, things made up of other things. A set is like a box, filled with these sub-things, which mathematicians like to call elements. There are many sorts of boxes. Boxes may be wooden. They may be cardboard. They can in fact be made of metal, and if you really wanted to you could probably make some sort of a box out of crack. Sets aren't quite like that. To a mathematician, a set is completely defined by its elements, the things it contains. If you have two sets and they both have precisely the same elements, then they're the same set. It's like numbers; you can have one apple or one orange or one orgasm, , and in the real world these are (usually) very different things, but abstractly, it's still just the number one. Sets are usually written as a list of their elements between curly brackets, like this: {1,2,3,4} or as a description of their elements, also between curly brackets, like this: {all positive integers less than five}. While I've described these two sets in completely different ways, you'll notice that they are, in fact, the same set. They both have exactly the same elements: 1, 2, 3, and 4. The fancy math term for this idea, that two sets are the same if they have the same elements, is extensionality. To save time and space, sets will usually be given names, like A={1,2,3,4}, and then the symbol A can be used in any expression in which I want to talk about that set. Having said nothing more, I can already display one interesting set factoid for you: let x be anything you want, a number, a letter, a symbol, a thing. It doesn't matter. Sets don't care what you put in them. Then {x,x} and {x} are equal: they're the same set. Why? Because every element of the first set, which has to be x, is an element of the second set, and vice-versa. Repeating an element doesn't change the set, so I'll just delete any references to repeated elements in my sets. And it's entirely possible to have a set that doesn't have any elements at all: {}. This is called the empty set, and I'll name it 0: 0={}. You'll see why.

There are only a few basic things you can do with sets, according to the very strict rules laid out in the axiomatic version of the theory which I'm not going into here, but as it turns out you don't really need anything complicated. First off, if you have two sets, you can take their union. If A and B are both sets, then their union is written A U B, and this is the set whose elements are all the elements of A, together with all the elements of B, and nothing else. If A={1,2,3,4} and B={1,2,5}, then A U B = {1,2,3,4,5}, since we can ignore repeated elements. We can also take intersections, though there isn't a good way to type them out here, and I won't need intersections for my purposes. The intersection of two sets is the set of all things that are elements of both of these sets at once. You can also construct subsets; a subset of some given set A is a set whose elements are also all elements of A. With my A above, {1,2} is a subset of A, and I'll write this {1,2} < A although normally it's curvier. And we can build new sets from old ones! A set doesn't care what you stick in it, after all, so why not build a set whose elements are other sets? So {A,B} is a set...But be careful. {A,B} is not at all the same set as A U B. The elements of A U B are 1, 2, 3, 4, and 5; the elements of {A,B} are A and B.

But what do I mean by 1, anyhow? How do you know 1 isn't the same thing as this set A? And how do you know that 1 isn't the same thing as 2? It sounds at first like a silly question, but it's important. What do we mean by numbers? I can now tell you exactly what numbers are, in very concrete terms. They're sets. I already defined 0 to be the empty set, {}. It's a set with zero elements, which seems like a sensible thing for zero to be. Now, let's define 1={0}: 'one' is going to be the set whose one element is zero. And we can bootstrap ourselves onwards: let 2={0,1}, and 3={0,1,2}, and so on. If you wanted to write these out more explicitly, we'd have 1={0}={{}}; 2={0,1}={ { },{{ }} }, but that's awfully awkward. Just saying 'and so on' isn't very precise, though, so I'll put it like this: if we've defined a natural number n, define its successor, the next natural number, to be n+1 = n U {n}; the elements of n+1 are going to be all the elements of n, together with n itself. This is just what I did for 1 and 2 and 3, you'll note. And having defined all the natural numbers 0, 1, 2, ... in this way, we can define arithmetic on them, too, using more set theory, and more induction, which I've skipped over entirely and waved my hands at in the above. As I said, this isn't meant to be rigourous. Just fun. For we're right on the cusp of infinity already! Let w={0,1,2,3,...}={all natural numbers}. (This ought to be a lower-case Greek omega, in case you aren't seeing it properly.) w is a set that has infinitely many elements, by which I mean that if you took an element away, you'd still have just as many left as you started with, but w behaves almost as if it were a natural number itself. In particular, we can find its successor, just by using the definition above: w+1 = {0,1,2,3,...,w}. w+1 is the set containing all natural numbers, and also w. This is a perfectly well-defined set. It looks bigger than w, since it contains everything w does and more besides. In fact, they're precisely the same size. And what do I mean by 'size' when talking about infinite sets?

Two sets are said to have the same size, or contain the same number of elements, or, in mathspeak, have equal cardinality (the cardinality of a set is the number of elements it contains, which may be bigger than finite...), if you can cook up a function or rule for associating with each and every element of the one set precisely one element of the other set, and vice-versa: you can think up a way to pair up the elements of the two sets so that you run out of elements of both sets at the same time. For example, {1,2,3} and {5,990,5324635} have the same cardinality since I can pair up 1 and 5, 2 and 990, and 3 and 5324635, and I've used up all the elements of both sets. {1,2,3} and {1,2} do not have the same cardinality. A set is finite if, as you'd expect, it has a finite number of elements, or, to be more precise, it has the same cardinality as one of the natural numbers; that natural number is then said to be the cardinality of the set. {1,2,3} has cardinality 3, since 3={0,1,2}, and we can pair up 1 with 1, 2 with 2, and 3 with 0. If a set is too big to be paired up with any natural number, it is infinite. w and w+1 are both infinite. The cardinality (or size) of w is called À₀, alef-null (or aleph-nought, because aleph or alef is the first letter of the Hebrew alphabet, and has lots of mystic connotations, and the man who invented set theory and the idea of cardinality, Georg Cantor, was an odd sort and wound up going mad, poor chap), and À₀ is the smallest of the transfinite cardinal numbers, that is, cardinalities of infinite sets. For natural, finite numbers, n and n+1 clearly never have the same cardinality; yet infinite sets are much, much odder, and it turns out that the cardinality of w+1 is also À₀, and here's why: look at w+1={0,1,2,3,...,w} and w={0,1,2,3,...}. Pair up w and 0. Now, for each natural number n in w+1, pair it up with n+1 in w. We pair up 1 and 2, 2 and 3, and so on, and so forth. We use each and every element of both sets exactly once. Thus, they both have cardinality À₀. There are lots more...Look at the set of all even numbers, {0,2,4,6,...}. This looks like it should have only half as many elements as w does, but they're actually exactly the same size, À₀. To see this, pair up 0 and 0, 1 with 2, 2 with 4, and so on...Associate to every natural number n in w the even number 2n. Or the set of all perfect squares, {0,1,4,9,16...}. Just match up each number in w to its square in {0,1,4,9,16,...}. Or the set {1,10,100,1000,...}; match up n with 10ⁿ. In fact, any infinite subset of w has À₀ elements, just like w itself. And there are much bigger sets, too, that still have only À₀ elements. Consider the integers: {....,-2,-1,0,1,2,...}, the set of all positive and negative numbers. Pair up all the nonnegative integers with the even numbers: 0 with 0, 1 with 2, 2 with 4, and so on. Then pair up all the negative numbers with the odd numbers: -1 with 1, -2 with 3, -3 with 5, and so on...There's never any danger of running out, since there are À₀ odd number and À₀ even numbers. So there are À₀ integers, too.

One of the standard examples in set theory, a bit like Schroedinger's Cat is in physics, is called Hilbert's Hotel, since it was cooked up by a German named David Hilbert who was one of the greatest mathematicians of his time. This Hotel has À₀ rooms, you see, numbered 0, 1, 2, and so on. This hotel, let's say, is poised on a particularly green and friendly hillside in the Bavarian Alps, and one day a weary hiker comes upon it and decides to stay for their famous chocolate cake. (I'm elaborating a bit.) So the hiker goes up to the desk clerk, and asks for a room. 'I'm sorry, sir,' the clerk tells him, 'but all our rooms are full.' 'Just ask everyone to move one room up,' the hiker suggests. So the clerk sends the man in room 0 off to room 1, the couple in room 1 off to room 2, and so on, leaving room 0 vacant, which the hiker happily takes. Some time later, the entire nation of China stops in. 'I'm sorry,' the clerk says, 'but all our rooms are full.' Chairman Mao suggests that the clerk simply ask everyone to move up 1.2 billion rooms, and then there's plenty of room. And so it was. Some time later, À₀ people turn up for the universe's biggest Star Trek convention. 'Jesus Fuck!' cries the clerk, throwing up his hands. 'Can't you people read? No vacancy!' The infinite number of Trekkies confer for a moment, and then send up Leonard Nimoy. 'It would be most logical if you asked all your guests to move to the room with twice the number of their current room.' So the clerk left the televangelist and the Vaseline-smeared goat where they were in room 0, and sent the blow-up doll in room 1 to room 2, and the party of nuns in room 2 to room 4, and so on, and sure enough there were precisely À₀ rooms open, just enough to fit all the Trekkies in.

At this point you might come to suspect that all infinite sets have À₀ elements, and so where's the point in giving this cardinality a special name? This is not, in fact, true, and this is where it gets fun. Hilbert's Hotel may have infinitely many rooms, but there is a quantity of guests even it can't fit, no matter how it shuffles people around.

Consider the set of all the real numbers between 0 and 1, that is, all the decimals 0.abcde... where a, b, c, and so on are all digits, between 0 and 9. (Where I forbid you from doing anything silly like ending a decimal with an infinite string of 9s.) Suppose there were À₀ of them: then we could pair them all up with the natural numbers, without missing any decimals. Pair them up; let's write the decimal we paired up with 0 as 0.a₁₁a₁₂a₁₃... where all the a_1is are digits. And let's write the decimal we paired up with 1 as 0.a₂₁a₂₂a₂₃a₂₄..., and the decimal we paired up with n-1 as 0.a_n1a_n2a_n3..., for any n. Let's write them out in an array, one above the other, in this order:

0.a₁₁a₁₂a₁₃a₁₄...
0.a₂₁a₂₂a₂₃a₂₄...
0.a₃₁a₃₂a₃₃a₃₄...
...

Now I'm going to write out a new decimal, 0.b₁b₂b₃b₄... where all the b_js are going to be digits. I'm going to do it like this. If a₁₁ is not 6, then let's let b₁ be 6. If a₁₁ is 6, let b₁ be 0. And similarly, if a₂₂ is not 6, then let b₂ be 6, and if a₂₂ is 6, let b₂ be 0. If a_nn is not 6, let b_n be 6, and if a_nn is 6, let b_n be 0. What we get is a perfectly decent decimal number, which is certainly a real number between 0 and 1, and so it must be in our list somewhere since we listed out absolutely all the decimals possible. But it isn't our first decimal, since they have different first digits. And it isn't our second decimal, since they have different second digits. And, continuing onwards, it can't be our n^th decimal for any natural number n, since they have different n^th digits. Therefore, 0.b₁b₂b₃b₄... can't have been in our list after all, and we didn't get them all. See? No matter how we pair up decimals with natural numbers, I can always construct a decimal we missed. Therefore, the set w of natural numbers and the set (0,1) of real numbers between 0 and 1 can't have the same cardinality! There must be more real numbers than natural numbers. (This is called the Diagonal Argument, and was thought up by Cantor.) But there are infinitely many real numbers, and infinitely many natural numbers! There must be, then, different levels of infinity. There's this one infinity, called À₀, to describe the natural numbers, and there must be another, in some sense bigger infinity, called c (for 'continuum', which is what the real numbers are, continuous or without holes), to describe the real numbers...

There are in fact infinitely many different levels of infinity, or transfinite numbers. (How many? It's impossible to say.) And these transfinite numbers are ordered: given any two of them, they're either equal, or the first is bigger than the second, or the second is bigger than the first, and only one of these three possibilities can be true. And as it happens, given any transfinite cardinal number, there's always a next one, too, just like there is for natural numbers. The next larger transfinite cardinal after À₀ is called À₁, and then the next bigger level of infinity after that is called À₂, and so on, and there's an À_w beyond all of those, and so on, ad infinitum as it were. Infinite levels of infinity, all of them very, very different from the ones before or after them. And how does c fit into this hierarchy, you may ask? We know c is bigger than À₀, but how much bigger? Is c equal to À₁? À₂? Or what? That is a question called the Continuum Problem, and Georg Cantor's guess that c might be equal to À₁ is called the Continuum Hypothesis. Not only, in more than a hundred years since then, has Cantor's hypothesis never been proven to be true or false, but in fact in the '30s and '60s two mathematicians, Kurt Godel (another insane genius; he believed aliens were bombarding him with a mind-control ray, so he hid under his desk at Princeton a lot, and he wound up starving himself to death because he believed he was being poisoned; he also wouldn't open his door for his students, and made them shove their papers under the crack) and Paul Cohen, working separately, in different decades even, proved that from what we know about set theory, it is in fact impossible to prove that the Continuum Hypothesis is true or false. This is an example of the phenomenon Godel is most famous for, his Incompleteness Theorem: any logical system (like set theory) sufficiently complicated to include arithmetic, that doesn't contradict itself, must contain questions that the system isn't powerful enough to answer.

And now you know enough about set theory to read and enjoy Rudy Rucker's White Light. See? That didn't hurt at all.

Posted by aloysius at June 16, 2003 11:42 PM | TrackBack |