On the incompleteness of the Library of Babel

[E]ach book is made up of four hundred and ten pages; each page, of forty lines; each line, of some eighty black letters—this last is plainly impossible, since the symbol set of the Library consists of twenty-two letters, the period, the comma, and the space.  (We will ignore incompleteness deriving solely from symbol set incompatibility as too trivial to take notice of.)  Suffice it then to say that each line consists of eighty characters, and those lines that seem to terminate with fewer are in fact padded with spaces.  Thus each book consists of 1,312,000 symbols (call this number s), in some order or another, and there are 25**s=a big honkin' number (1,834,098 digits!) different books.  (There are also titles on the spines, but no further information is given than that they exist.)

Now it is not exactly said that all works are to be found in the library, though it is said that

the Library is total and that its shelves contain all the possible combinations of the twenty-odd orthographic symbols … that is, everything which can be expressed, in all languages.  Everything is there: the minute history of the future, the autobiographies of trhe archangels, the faithful catalogue of the Library, thousands and thousands of false catalogues, a demonstration of the fallacy of these catalogues, the Gnostic gospel of Basilides, the commentary on this gospel, the commentary on the commentary of this gospel, the veridical account of your death, a version of each book in all languages, the interpolations of every book in all books.

There couldn't be all works because there would be no way to distinguish between the Don Quixote of Cervantes and that of Menard (I have always thought that Menard's story is an allegory of reading or reception, and not a delineation of a certain kind of conceptual work, but no matter) (except, perhaps, but title, actually, now that I think of it, though the narrator of the story doesn't seem to consider the titles as possible differentiators of books in his discussion later) and we will suppose that these are different works.  (Just as a gallery containing all possible arrangements of paint on canvas couldn't distinguish between the visually identical illustrations of Newton's three laws in The Transfiguration of the Commonplace, except, of course, by caption.) We can accomodate texts whose length isn't s quite simply: if they are shorter than s, there will be a book in the library consisting of the text in question, followed by some number of spaces; texts of length t > s are divided into ⌈t/s⌉ volumes, the last of which will be padded with s-(t%s) spaces.  With respect to very long works, then, the books of the library form something like an alphabet with extremely cumbersome letters.

But this means two things: first, some books will be part of multiple texts (which, perhaps, cannot therefore be in the library simultaneously), and second, some texts can't be in the library at all.  I mean "be in the library" in the following sense: if there is a multivolume set in a library, one ought in some sense to be able to have all the volumes together.  Otherwise the set isn't really in the library. Obviously in the Library of Babel it is practically impossible, for most sets, to assemble all the volumes together, because of its unwieldy hugeness (and, of course, because although a catalogue exists—which is presumably itself many many volumes long—it's impossible to tell if you've found the right one).  But in most cases of long texts with which we are acquainted (say Gibbon) there will be some set of volumes which make it up to be found somewhere in the library.

Suppose, though, that there is some text that has at least s consecutive characters in common with a different text, starting in the one book at symbol number sn and in the other at symbol sm (these books are zero-indexed, of course).  Then it will be impossible to have both sets simultaneously, since, each book occuring only once in the library, there will be only one book corresponding to the intersection.  (This becomes much clearer when the number of symbols making up the units of the alphabet is smaller.  With a one-symbol alphabet, in which there would only be 25 books, you couldn't simultaneously have act and bad.)

And it gets worse!  Just as one couldn't have baa in the one-symbol case, so too one could not have, in the Library of Babel, a text which had two identical sequences of s (or more) consecutive symbols starting at character positions sn and sm, n ≠ m.  Such a text is not inconceivable. One could take as one's model "Franz Kafka in Riga", a story the reading of which is a postrequisite for all those who have read or intend to read "Pierre Menard, Author of Don Quixote" (and indeed, should I be fortunate enough to be the TA for this course, and should this most recently mentioned Borges story remain on the syllabus, I intend to force the Mathews on my students all unwary, and that even though it quite plainly isn't on the syllabus, and even though I myself don't have anything to say about it, but rather merely find it interesting, or perhaps even merely "neat"—anyway, it's short).  If the text between "I decided to climb these steps" and "threatened to blow away my" were in each case much, much longer, and the text before the first appearance of the string, and the text between the two, were of precisely the right length, each bit could fall at precisely the right position to occupy the entirety of a Library of Babel volume.

Comments

[Paul Gowder]

Ben, your philistinism will not avail you against Borges. For there are clearly non-standard books in the Library. For one, the library contains "books in the Crimson Hexagon: books whose format is smaller than usual, all-powerful, illustrated and magical."

Moreover, perhaps the Library is understood to extend through space as well as time, in which case any possible non-repetitive multivolume sets may be brought into existence simply by rearranging the order of books, through human agency. And then the Library is truly complete over its entire time line.

Selah.

[ben wolfson]

Philistinism? Surely this is just the sort of attention that Borges would have appreciated.

Saying that overlapping sets of nonrepetitive multivolume texts can coexist because you can have first one at time t0, then the other at time t1, and the texts coexisted in the range (t0,t1) is such blatant sophistry I'm not surprised it came from a political scientist.

The existence of nonstandard sets is only tolerable so long as they are relatively few in number, on pain of making the whole thing too silly to bear (or undermining the interest of the story—you may say either). Hence Borges' wise limitation of such things to particular hexaga.

[Paul Gowder]

But the library is ever-changing! ("the senseless perdition of millions of books") Books are being destroyed, and, perhaps books are even being created anew? All claims about the vast extent of what the library "contains" become trivially false if we limit the scope of the claim to one point in space-time. Piffle! (And of course the library, being the universe, doesn't have a discrete point in time at which it began, when it could be said to be complete.)

Relatively few in number! But the Library is (possibly) infinite. A billion hexaga would be relatively few... perhaps even a countably infinite hegaga... I feel an invocation of Cantor coming on...

[ben wolfson]

The library can't be infinite, even if the narrator calls it "perhaps infinite", because "the fundamental law of the library" is that "There are not, in the whole vast Library, two identical books" (italics in original). Given the composition of the books, this already allows us to put an upper bound on the number of books: 25**s + C, C being a comparatively small number equal to the number of books in the Crimson Hexagon and what similar other hexaga there might be. It really does have to be comparatively small. Take a moment to convince yourself of this. Note also that it's far from clear that there is such a hexagon in the library; the narrator says that those who destroyed some of the books were "spurred by the delirium of storming the books in the Crimson Hexagon". There is no direct endorsement of the existence of such a place. Upper bound because, as you correctly point out, some books have been destroyed. And in this same place the narrator says that "the library is so enormous [sc. it is not infinite] that any reduction undertaken by humans is infinitesimal" (emph. added), and that "each book is unique, irreplaceable" (emph. added).

The uniqueness constraint is all that's necessary to establish the incompleteness of the library as described in the post, anyway.

[dave zacuto]

I think you misspelled Borges' name.