The Hyperwebster Dictionary
A simplified version of the Banach-Tarski paradox, explained without numbers
A publishing house in the far future wants to generate a dictionary that contains all the possible strings that can be generated with the 26 letters of the English alphabet.
This book would contain words that vary from ‘hydrophilic’ to ‘rdfjbedzx’ to an infinite string of a’s.
To do this, they first create a master set which contains all these words.
(Wait, why not the usual ordering of S = {a, aa, aaa, …. ab, aba, abb,…} ?)1
Due to the system of generation of the words and the fact that the words of infinite lengths are allowed, the set must have an infinite number of elements.
Next, the publishing house splits this master set into 26 volumes, one for each letter.
and so on...
In order to save space2 the publishers decide to remove the first letter from every word in for all the volumes, since it is known that all the words in the chosen volume start with that letter itself, so all that the reader would have to do is prefix the letter with whom that volume is associated in order to obtain the original volume.
However, as soon as they do this for Volume A, they notice something astounding. The modified volume exactly matches the master set!
Delighted, the publishers decide to publish only Volume A, with instructions to prefix the letter of their choice to get the corresponding volume.
However, they also realize that no matter how many times they perform the same process of ‘optimization’, they always end up obtaining the master set.
In fact the size of all of the volumes that start with a specific string would have the exact same members, i.e. Volume A = Volume YAK = Volume AAAA…. (Infinite a’s).
Our dictionary is uncountably infinite and a direct analogue to the uncountability of real numbers, as replacing a-z with 0-9 in the master set gives back all the reals.
This concept was devised by Ian Stewart in “From Here to Infinity” as an analogue to the Banach-Tarski paradox: Just as how a sphere can be ‘broken up’ and rejoined to obtain an two exact copies of the original, the dictionary contains an infinite number of copies of itself that can be broken up and rearranged to obtain the counterintuitive result of ‘something from nothing’.
Extra:
Can’t we do the same with the set of natural numbers?
Sure, we can try the same style of attack.
Let N be the set of natural numbers and let N(2) be the set of even natural numbers. Since there exists a bijection between N and N(2), they have the cardinality (and thus the same “size”).
Now, dividing each element of N(2) by 2 gives us N back, but here we have performed an operation on a subset of N that alters the elements to obtain N. On the other hand, Banach-Tarki and the Hyperwebster dictionary involve nothing more than the rearrangement of the elements to obtain copies of the original. Similarly, we can show that it is impossible to create a subset of N that contains N itself, while we can clearly do so with our dictionary here. The set of natural numbers are countably infinite.
If naturals are smaller in size than reals, then I suppose that we can come up with sets whose cardinality (size) is in between both of them? Will such a set be competent to undergo the treatment above?
You have now reached the famous “Continuum Hypothesis”, which states that there is no set whose cardinality is between that of the integers and the real numbers. It’s a pretty deep rabbit hole to fall into; a fulfilling journey nonetheless.
References:
Online document (Unknown author)
Blog post by Ravi Bhide (Only other comprehensive source I found)
This is because lexicographic ordering does not happen to be a well ordering. This is clearly seen by the counter example and the corresponding proof posted here. In short, this is because one would not be able to define the position of ‘ab’ in the set rigourously as it follow the infinite sequence of terms that have only ‘a’s, which would defeat the purpose of the dictionary. (I hope to follow up on this later.)
Aren’t we dealing with an infinite number of words here? How could any possible action save space? That’s where ‘the far future’ comes into play.