# 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?${}{}{}$ – Omnomnomnom Aug 24 '15 at 12:20
• I went googling after I saw the video :) – rookie 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. – Omnomnomnom Aug 24 '15 at 12:41
• The Vsauce video referred to is here youtube.com/watch?v=s86-Z-CbaHA – GEdgar 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. – Cameron Buie 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 – GEdgar 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. – rookie 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? – GEdgar 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. – Omnomnomnom Aug 24 '15 at 13:12
• Agreed. The Hyperwebster (for purposes of the video at least) contains only finite strings, and thus is countable. – GEdgar Aug 24 '15 at 13:26

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.

The hyperwebster contains an uncountable number of words. This is because it allows strings of infinite length (which is the only way it can have an uncountable number of words).

To help understand the analogy with the real line, simply replace A-Z with 0-9 in the dictionary. This generates all real numbers as we know them (in base-10).

(As an aside, I am the author of the article you reference.)

• As I mention in my answer, "of any length" does not necessary imply the inclusion of infinite-length strings. Does Stewart make this clear, or otherwise imply an uncountable dictionary? – Brian Tung Jan 11 '17 at 21:53
• @BrianTung I do not recall Stewart's statement. However, I do recall that his construction calls for repeating the step of removing the first letter of every word ad infinitum and the output of such an operation being equivalent to its input at every step. This implies that the strings are of infinite length. – Ravi Jan 12 '17 at 18:54
• No, it does not. If I have a list of all strings of finite length, and only those strings, then removing the first letter from all of them leaves me with exactly the original list. Even if I'm able to remove them an arbitrarily large number of times. The process is closed whether the original dictionary was countable or not. I think, however, that it's reasonable to suppose that the dictionary was uncountable, because it was intended as an analogy for Banach-Tarski, but I don't think one can conclude that from just what was posted. – Brian Tung Jan 12 '17 at 19:12

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 – Ethan Bolker Mar 15 '17 at 15:28