Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why Any Telephone Directory is too Small

  1. Jun 21, 2011 #1
    An infinite number of different names might be listed in a telephone directory. For any conceivable name, a new and different name can be created by adding one letter.

    Can any phone directory be created to include all conceivable names even if there are an infinite number of names?

    It may be tempting to answer yes to this question by positing an infinite directory that can list an infinite number of names. Problem solved!

    Strangely, even an infinite directory isn't big enough. Here's my reasoning: Consider the first three names listed in that directory.

    1. Aab...
    2. Abc...
    3. Aad...

    These names can be composed of any number of letters, even an infinite number of letters. Even though there may be an infinite number of names, you can always make up a name that's not on the list! How? Make up that name by selected the letters on the diagonal and create a name using different letters than the letters on the diagonal. Say


    Using different letters in this name than the names on the diagonal ensures that it has not yet been included in the directory. Bef cannot be the first name because the first letter differs from the first letter in the first name. Bef cannot be the second name because the second letter differs from the second letter in the second name. Finally, Bef cannot be the third name because the third letter differs from the third letter in the third name.

    No matter how many names are in the directory, using the process of making up a name by replacing the letters on the diagonal with different letters and using those replaced letters in the new name guarantees that the new name will differ from all the names in the directory by at least one letter.

    Am I right?

  2. jcsd
  3. Jun 21, 2011 #2
    If a name can have infinitely many letters, you are right, and this proof is the same as the famous Cantor diagonal proof that the reals are uncountable.

    If a name can have only finitely many letters, you are wrong. The diagonal would have infinitely many letters and would therefore not be a name.
  4. Jun 22, 2011 #3
    Cantor's "diagonal proof" inspired me to apply his kind of reasoning to a more tangible and practical situation. His proof dealt with numbers while my argument deals with a hypothetical "telephone book."

    I thought about this point. I'm arguing that any name can be as long as you like. No matter how many letters it contains, you can always add one letter to come up with a different name.

    Now, the diagonal name would have infinitely many letters if there are infinitely many names in the directory. I'm not sure if it having infinitely many letters disqualifies it as a name, though. Surely it would not be pronounceable.

    In any case, this argument demonstrates that any set of possible names, even if it is an infinite set, cannot be complete. A new and different name can always be created to add to the set. Some infinities are more "intense" than other infinities, would you agree?

  5. Jun 22, 2011 #4
    Let's say that you take the diagonal and change every occurance of an a to b and you change every b to a. But consider the following directory:


    and after this infinite number of names you add one name:


    then the diagonal is bbbbb..., and when we change every letter we get aaaaa... which is contained in our directory.

    Of course, we can solve this by changing the order of our list to let aaaaa... in front. Then we get


    In this case the proof works. But the point hereis that you must assume that the set of all names is countable. I.e. you must assume that you can order all names in such a way that after your infinite list of names does not come other names. This is not always possible.

    Certainly correct!
  6. Jun 22, 2011 #5
    Cantor's diagonal argument applies to a telephone book whose names are infinite strings from the alphabet whose symbols are 0,1,2,3,4,5,6,7,8,9. How does using the symbols, a, b, c, ..., z change anything?

    You can do Cantor's proof using binary sequences consisting of just the symbols 0 and 1. And, using the ASCII code that's standard in computer programming, you can convert each letter of the alphabet to a sequence of eight 0's and 1's, transforming any of your names into a binary sequence.

    How would names made of letters differ from names made of numbers? If the strings have infinite length, they can't be put into bijection with the natural numbers.

    On the other hand if strings have finite length, then there are only 26 possible names of length 1; 26^2 names of length 2; 26^3 names of length 3, and so forth. Adding them all up gives a countable set of names. Any countable set can be put into bijection with the natural numbers. Choose any such bijection and use it to construct a countably infinite telephone book.
  7. Jun 22, 2011 #6
    I think you may have lost me on the last step. Wouldn't the diagonal be bbbbb...a? I believe you're saying that if there's an infinite number of names, then the diagonal name's letters are infinite in number and would never reach the “final” letter a because there is no final letter. Is that correct?

    Hmmm. In this case adding the aaaaaa... beforehand prevented the “diagonal procedure” from coming up with a name that's not on the list. Interesting.

    The diagonal letters are now aaaa... and changing them to bbbb... again results in a name that's not on the list!

    Brilliant work, Micro! I hope that we can discuss this and other topics in the future.

    In closing, I must admit that my “telephone directory” scenario isn't terribly original. It's a direct consequence of Cantor's work. I just wanted to expand a bit on it to include letters in names as well as digits in numbers. Any kind of ordered symbols would work to illustrate the basic idea of incomplete, infinite sets

  8. Jun 22, 2011 #7
    See my response to Micro about my choice of symbols. I should add that Cantor's diagonal procedure may not be as well known as you might think. I just learned about it yesterday. I'm hoping that other members here not acquainted with Cantor can benefit from this discussion.



    Taking the digits on the diagonal, 00000..., and changing them to 11111..., gives us a binary number that's not on the list. What's the significance of doing this?

    Can't you just match each string on the list with a natural number?

  9. Jun 23, 2011 #8
    Good point.

    It shows that any proposed list of such sequences is not the entire list. In other words, that the set of binary sequences is uncountable. The set of binary sequences can NOT be put into bijective correspondence with the natural numbers. That's Cantor's diagonal argument.

    No, that's what we just proved. If we suppose that we have an endless list of binary strings, we can use the anti-diagonal (the string that is different from string n in position n) to show that our list was not complete after all. So there can be no list of binary strings.

    However if we restrict ourselves to finite binary strings, we CAN put them in a list; because then the anti-diagonal is an infinite binary string, and we are only considering finite binary strings.
  10. Jun 23, 2011 #9
    OK, but again, what is the significance of doing this? Are there implications for some computer technologies like artificial intelligence?

    By the way, I first learned of Cantor's diagonal in Douglas R. Hofstadter's, https://www.amazon.com/Gödel-Escher...sr_1_1?s=books&ie=UTF8&qid=1308851215&sr=1-1". A book that will take me a long time to read and much longer to understand.

    Last edited by a moderator: Apr 26, 2017
  11. Jun 23, 2011 #10
    Before Cantor, "infinity" was a philosophical concept that was not handled rigorously in math. Cantor showed two amazing things:

    1. You can have a mathematically rigorous theory of infinity; and

    2. There are different kinds of infinities, in fact there are an infinite number of different levels of infinity.

    Both of those facts were incredibly controversial at the time, and many mathematicians didn't accept Cantor's results. Today his proofs are an accepted part of standard math, but philosophically they are still mysterious. For example, are there infinite sets in the physical world? How about uncountable sets?

    Cantor himself believed that his theory did have implications for the physical world. He believed that the cardinality of the luminiferous aether was the same as the cardinality of the real numbers. However that aspect of his work is not taken seriously today. Set theory is a part of math and math is a vital part of physics, but nobody has any idea what it would mean for there to be an uncountable set in the physical world. Perhaps Cantor's work marked the final break between physics and math. We're in the realm of philosophy now.

    As far as computability, that's another set of interesting questions. There are uncountably many real numbers, but there are only countably many finite-length names (as our discussion has shown). So the vast majority of real numbers can not be described by any algorithm or finite process.

    Computer scientists and logicians have a whole theory of definability, where they study the sets of numbers that can be defined by various types of statements. All of this stems directly from Cantor's work. If there are uncountably many real numbers yet only countably many of them can be produced or described by algorithms, Turing machines, formulas, etc., then in what sense can the entirety of the real numbers be said to exist? Again, we are back to philosophy. Nobody knows the answer to these questions.

    Does any of this bear on whether machines can think? Who knows. In the scheme of things, Cantor's work is very recent -- only 140 years old. Give it another few hundred years. Maybe someone will have figured it out by then.
  12. Jun 23, 2011 #11
    That's interesting. I thought that the idea of infinity in mathematics was older than that. Today, kids from a young age are taught that “there is no largest number.” Infinity seems obvious enough, but then, maybe it isn't so obvious. Zero is also a commonly used mathematical idea in the modern world, but it hasn't been all that long that we've been using it. I believe Muslims in the middle ages developed the idea.

    A Christian apologist and philosopher, William Lane Craig, insists that nothing in the physical world is infinite. He tries to make a case that an infinite past is impossible so that he can insert God into modern cosmology. Aside from the Big Bang, I see no reason why the past cannot be infinite.

    An “uncountable” is a set containing elements that cannot be matched up one-to-one with the natural numbers. Is that correct?

    That shouldn't come as such a surprise considering that there is no reason that I'm aware of that all of mathematics must be applicable to the physical world.

    They exist as ideas.

  13. Jun 27, 2011 #12
    Last edited by a moderator: Apr 26, 2017
  14. Jun 27, 2011 #13
    "I'm so meta, even this acronym"? Yes, that Hofstadter all right!

    Is he really that smart, or is he just trying to fool all of us? :wink:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook