Why Any Telephone Directory is too Small

[Jagella]

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

Bef

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?

Jagella

 

[SteveL27]

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

Bef

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?

Jagella

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.

 

[Jagella]

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.

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."

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.

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?

Jagella

 

[micromass]

In any case, this argument demonstrates that any set of possible names, even if it is an infinite set, cannot be complete.

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:

baaaaaa...
abaaaaa...
aabaaaa...
aaabaaa...
aaaabaa...
...

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

aaaaaa...

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

aaaaaa...
baaaaa...
abaaaa...
aabaaa...
...

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.

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?

Certainly correct!

 

[SteveL27]

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."

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.

 

[Jagella]

...consider the following directory:

baaaaaa...
abaaaaa...
aabaaaa...
aaabaaa...
aaaabaa...
...

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

aaaaaa...

then the diagonal is bbbbb...

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?

...and when we change every letter we get aaaaa... which is contained in our directory.

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.

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

aaaaaa...
baaaaa...
abaaaa...
aabaaa...
...

In this case the proof works.

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

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.

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

Jagella

 

[Jagella]

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?

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.

You can do Cantor's proof using binary sequences consisting of just the symbols 0 and 1.

Like...

011111...
101111...
110111...
111011...
111110...

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?

If the strings have infinite length, they can't be put into bijection with the natural numbers.

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

Jagella

 

[SteveL27]

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.

Good point.

Like...

011111...
101111...
110111...
111011...
111110...

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?

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.

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

Jagella

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.

 

[Jagella]

The set of binary sequences can NOT be put into bijective correspondence with the natural numbers. That's Cantor's diagonal argument.

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.

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/dp/0465026567/?tag=pfamazon01-20. A book that will take me a long time to read and much longer to understand.

Jagella

 

[SteveL27]

OK, but again, what is the significance of doing this? Are there implications for some computer technologies like artificial intelligence?

Jagella

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.

 

[Jagella]

Before Cantor, "infinity" was a philosophical concept that was not handled rigorously in math.

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.

For example, are there infinite sets in the physical world?

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.

How about uncountable sets?

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

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.

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.

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?

They exist as ideas.

Jagella

 

[SteveL27]

By the way, I first learned of Cantor's diagonal in Douglas R. Hofstadter's, https://www.amazon.com/dp/0465026567/?tag=pfamazon01-20. A book that will take me a long time to read and much longer to understand.

Then you'll definitely appreciate this ...

http://xkcd.com/917/

You can learn a lot from xkcd!

 

[Jagella]

Then you'll definitely appreciate this ...

http://xkcd.com/917/

You can learn a lot from xkcd!

"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?

Jagella