7

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?

rookie
  • 409
  • 5
  • 16
  • Vsauce?${}{}{}$ – Ben Grossmann Aug 24 '15 at 12:20
  • 1
    I went googling after I saw the video :) – rookie Aug 24 '15 at 12:30
  • 2
    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. – Ben Grossmann Aug 24 '15 at 12:41
  • The Vsauce video referred to is here https://www.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
  • I read a portion of the book in Google Books, and it may be that infinite-length strings are included. It's hard to tell. I've added a discussion of this to my answer. – Brian Tung Jan 11 '17 at 22:05

4 Answers4

11

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.

Hagen von Eitzen
  • 374,180
  • 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
  • 2
    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. – Ben Grossmann Aug 24 '15 at 13:12
  • 1
    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
  • An intuitive way to demonstrate that the Hyperwebster is countably infinite is to order it by increasing word length: A, B, C, ... X, Y, Z, AA, AB, AC, ... . Now it's a bit easier to see that all finite words are enumerated. – Jonathan Lidbeck Sep 26 '15 at 08:40
2

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.

Philip Cunetto
  • 21
  • 1
1

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.

Brian Tung
  • 34,160
-3

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.

José Carlos Santos
  • 427,504
Konner Paquin
  • 1
  • 1
    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: https://en.wikipedia.org/wiki/Cardinality – Ethan Bolker Mar 15 '17 at 15:28