# An infinite dictionary: countably infinite or uncountably infinite?

This question concerns Ian Stewart's "Hyperwebster", an uncountable dictionary.

Say a publishing company wants to publish every possible permutation (of any length) of the characters A-Z. The dictionary might look like this:

A, AA, AAA, ..., AB, ABA, ABAA, ..., AC, ..., AZ, AZA, ... B, BA, BAA, ..., BB, BBA, BBAA, ..., BC, ..., BZ, BZA, ... C, CA, CAA, ..., CB, CBA, CBAA, ..., CC, ..., CZ, CZA, ... Z, ZA, ZAA, ..., ZB, ZBA, ZBAA, ..., ZC, ..., ZZ, ZZA, ...

The publishing company realizes that the dictionary can be reorganized into 26 volumes, with each volume corresponding to one of the 26 characters:

• Volume A: A, AA, AAA, ..., AB, ABA, ABAA, ..., AC, ..., AZ, AZA, ...
• Volume B: B, BA, BAA, ..., BB, BBA, BBAA, ..., BC, ..., BZ, BZA, ...
• Volume C: C, CA, CAA, ..., CB, CBA, CBAA, ..., CC, ..., CZ, CZA, ...
• Volume Z: Z, ZA, ZAA, ..., ZB, ZBA, ZBAA, ..., ZC, ..., ZZ, ZZA, ...

The company can save some ink by dropping the first letter, since it can be inferred from each of the 26 volumes.

• Volume A: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
• Volume B: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
• Volume C: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
• Volume Z: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...

Since each volume is now identical, the company decides to publish only the first volume, which is the same as the list we started with.

In the linked article, the author remarks that this is an analogy of the real line. Can someone explain how this dictionary is uncountably infinite? Is it because of the fact that we can keep repeating the above steps, subdividing our dictionary infinitely many times, each time arriving at a set the same size as the one we started with?

• Vsauce?${}{}{}$ Aug 24 '15 at 12:20
• I went googling after I saw the video :) Aug 24 '15 at 12:30
• In fact, an important part of the Banach-Tarski proof seems to be that this "Hyperwebster" is countably infinite, and enumerates a countably infinite subset of the sphere. Aug 24 '15 at 12:41
• The Vsauce video referred to is here youtube.com/watch?v=s86-Z-CbaHA Aug 24 '15 at 13:28
• The analogy to the real line is (perhaps) that it can be partitioned into proper subsets, each of equal cardinality to the whole set--for example, into intervals $[n,n+1),$ where $n$ ranges over the integers. Aug 24 '15 at 17:25

The dictionary is countable (as words have finite length). If there is an analogy with the real line it does not extend to the cardinality.

• Did Ian Stewart say it is uncountable, or just this computer scientist? This seems to come from Stewart's book From Here to Infinity Aug 24 '15 at 12:44
• Don't know (haven't read his book). I saw this idea referenced in a Vsauce video (see the exchange in the question commentes) and searched for more information. Aug 24 '15 at 12:49
• In the Vsauce video he says the last word in the dictionary is an infinite string of Z's. So is the dictionary supposed to contain infinite strings or not? Aug 24 '15 at 13:04
• The maker of the video is not a mathematician, and says a few things in the video that are at best a bit misleading. It wouldn't surprise me if the maker of the video assumed that the strings should be infinite. However, for the purposes of the Banach-Tarski construction, the "hyperwebster" is used to index the elements of the free group on two generators, which is made of finite strings. Aug 24 '15 at 13:12
• Agreed. The Hyperwebster (for purposes of the video at least) contains only finite strings, and thus is countable. Aug 24 '15 at 13:26

I have Dr. Stewart's 1996 edition of "from here to infinity" in front of me now. He nowhere explicitly says that the words are of finite length nor does he explicitly say infinite length strings are allowed. However he does say "... the analogy is closer than might appear, because the Banach-Tarski paradox is proven by using sequences of rigid motions in much the same way as I have used sequences of letters". Now if you look at a proof of the Banach-Tarski theorem you'll see that it uses FINITE sequences of rotations of the 2-sphere (based on Hausdorff's paradoxical decomposition of the 2-sphere). To me that makes it very clear that Dr. Stewart meant to define the hyperwebster as all strings of finite length. And hence the hyperwebster is countable.

But I have a problem with the common description of the hyperwebster. It's often described as

A, AA, AAA, ..., AB, ABA, ABAA, ..., AC, ..., AZ, AZA, ... B, BA, BAA, ..., BB, BBA, BBAA, ..., BC, ..., BZ, BZA, ... Z, ZA, ZAA, ..., ZB, ZBA, ZBAA, ..., ZC, ..., ZZ, ZZA, ...

Where is AAB in this list?

In fact alphabetical ordering (i.e., lexicographic ordering) is not a well ordering of the finite strings over 26 characters. See lexicographic ordering is not a well ordering. That makes it hard to write out a complete list of the hyperwebster in alphabetical order even using ... .

A better way is alphabetical within groups of increasing string length:

a,b, ... z aa,ab, ..., az, ba, ..., bz, ... za, ... zz aaa, ..., zzz, ...

Now volume A is:

a, aa, ..., az, aaa, ..., azz, aaaa, ..., azzz, ...

And you can see that removing the first a in each of these gives you the original full list.

It depends on what "of any length" means. If it includes strings of infinite length, then the number of strings is uncountable. If it only includes strings of finite (but arbitrary) length, then the number of strings is countable. This is analogous to the number of real decimal values between $0$ and $1$, as opposed to the number of truncating decimal values, which are a subset of the rationals, which are countable.

In the original book, From Here to Infinity, Ian Stewart introduces the notion of the Hyperwebster as an analogy to the Banach-Tarski paradox: Each volume of the Hyperwebster includes a first-letter-prefixed copy of the entire dictionary in the same way that each piece in the Banach-Tarski paradox contains a rotation-prefixed copy of several pieces of the sphere. On that basis, one might argue that the Hyperwebster, if it really is to be treated as analogous to the sphere, should include infinite-length strings so as to be uncountably infinite in the same way that the sphere is. However, I was not able to read enough of the book in Google Books preview to be sure this is the way Stewart intends it.

Try matching the letters with countable infinity. A, AA, AAA, AAAA, AAAAA... 1, 2, 3, 4, 5... This will extend to an infinite amount of As using up every countably infinite number. By the time we get to AB, ABAA, ABAA... we will have already run out of natural numbers because they were all used up in the set of infinite As. Because we cannot match each word to a corresponding natural number. The amount of words must be unaccountably infinite.

• You can't "use up" the natural numbers this way and say you've no more places for the $B$'s. Suppose you put the $A$'s in just the even places? You should read about some standard arguments like this. Try wikipedia: en.wikipedia.org/wiki/Cardinality Mar 15 '17 at 15:28