# A library with less information than one of its books

How can a library contain less information than one of the books in it? The library is intended to be a set of books on shelves. The information content is the least number of bits to describe the data.

• When it's Gödel's library. :) – A E Dec 2 '14 at 12:49

The books in the library contains all binary strings of length 1 million, one per book, sorted in lexicographic order. An individual book takes a million bits to specify, but this description of the whole library is much shorter.

• I was prompted to post this after I recalled The Library of Babel, which is the same idea. – Ross Millikan Dec 2 '14 at 17:15
• @RossMillikan now that we have an accepted answer, would anybody care to give a detailed explanation/reasoning/proof? This question is not clear to me at all, still. It is obviously one answer of many, but what is the crucial bit and why (exactly)? Why 1 million bits?, won't it work with 2 books and a single bit as well? – BmyGuest Dec 3 '14 at 6:52
• @BmyGuest: Single bit won't work, one million bits was arbitrary, but it serves the purpose that we can define the library content in under 1 million bits (which is ~128KB), which is xnor's answer (it's only 230 bytes and can be shortened), but we can't describe every single book there in under 1 million bits (read this page) – justhalf Dec 3 '14 at 8:39
• @BmyGuest: The basic idea is that "all books of $x$ length" can describe the library in very few words, so there is little information in the whole library. Since (most of) the books are random gibberish, they cannot be compressed, so an individual book contains many bits. If you made a card catalog (remember those?) it would be as large as the whole library-the easiest way to catalog the books is to give each one a catalog number that is exactly its content. – Ross Millikan Dec 3 '14 at 14:26

This is indeed possible if we define information content as the least number of bits necessary to describe the data. Consider the following example (in human readable language):

• Book 1: Jim knows all animals whose name starts with a letter between A and L.
• Book 2: Jim knows all animals whose name starts with a letter between M and Z.

Then the information in the whole library would be:

• Jim knows all animals.

The paradox is solved if we consider the source of an information as an information itself (i.e. which book contains which information). In this case, the library, if not empty, will always contain at least as much information as any of its books.

The library contains all possible combinations of letters conceivable. (It is a very large library) with no ordering of books at all. Perfect entropy. Each of its book contains a subset only, which therefore contains some order and some information. (The library information is 'complete/all' which can be described with a single bit true)

Sorry if this is not in proper mathematical terms, I am not a mathematician...