2
$\begingroup$

I already asked this question on Stack Overflow and people kept voting me down and telling me it's "more of a maths question" so I will ask the question again:

Assuming a finite alphabet, (eg: A,B), can we construct an infinite set of finite strings? Obviously we'll start with the empty string, then A, then B, then AB, AA BA, BB... etc

I made the claim (with much disagreement and voting-down) that it's impossible to have an infinite set of finite strings, because if we take out alphabet as 0,1,2,3,4,5,6,7,8,9, and make our strings have a 1-to-1 correspondence with the natural numbers starting with 0, (so each string is a natural number), then there must be a maximum-length of a string in this set (a finite number, we'll call it N). If this is so, we may take the highest number in the set of length N (which will also be the highest natural number) and count down to 0, removing each number from the set, until we have the empty set. On the other hand if N=Infinity then the set contains infinite strings.

I've been met with much disdain for saying this, intuitively I find impossible to believe that there's such thing as an infinite set of finite strings.

$\endgroup$
2
  • 2
    $\begingroup$ Note that the natural numbers have the property that each number has a greater number (successor) wich is also a natural number. Thus, there is no greatest natural number. $\endgroup$
    – AlexR
    Jan 11, 2015 at 22:07
  • 1
    $\begingroup$ "On the other hand if N=Infinity then the set contains infinite strings." No, if $N=\infty$ (as in Sal's example) then that only implies that there are arbitrarily long strings, not necessarily strings of infinite length. $\endgroup$ Jan 11, 2015 at 22:09

3 Answers 3

8
$\begingroup$

Even simpler,$$\{A, \quad AA,\quad AAA,\quad AAAA,\quad\ldots\}$$ Compare this to the observation that $\mathbb{N}=\{1,2,3,4,\ldots\}$ is an infinite set of numbers, each of which is nevertheless finite. There is no reason that a set of numbers must have a maximum number, just like there is no reason that a set whose elements are finite length strings must have maximum length string.

Reading your question further, you seem to be under the impression that there is a largest natural number. I can't imagine what you might think it would be, much less what you think the result would be if you added one to it (gasp!).

$\endgroup$
2
  • 2
    $\begingroup$ To make this even more blunt: is the set of finite natural numbers infinite? $\endgroup$
    – Nitin
    Jan 11, 2015 at 22:09
  • 1
    $\begingroup$ To your final comment, I recall a documentary about infinity (I think by the BBC) where they interviewed Doron Zeilberger, a renowned ultrafinitist, and he said that it is his belief that there is a largest natural number and when you add $1$ to it, you get $0$. Of course, he added, this number is larger than anything we can even begin to imagine (which is in some sense not different than infinity as most mathematicians would perceive it, in my opinion). $\endgroup$
    – Asaf Karagila
    Jan 11, 2015 at 22:21
4
$\begingroup$

Belief has nothing to do with it.

Either you accept the "classical" (and somewhat implicit) rules of mathematics, which permit an infinite set of finite strings. Or you reject them, in which case you have to tell us what you think is true or false.

Your argument completely fails, because there is no "maximal length finite string" of digits, since in that case there would only be finitely many natural numbers. Remember that mathematics is an ideal space, it is not bounded by memory or running time. Since every natural number has a successor, there are infinitely many of them, all of which have a finite decimal expansion that eventually gets longer and longer and longer... but still finite.

(Let me add that infinite sets, which are an integral part of modern mathematics, are far far stranger than you could begin to imagine. An infinite set of finite strings is merely the tip of the quark of the edge of the electron of the edge of the hydrogen atom of the water molecule of the tip of the iceberg. It gets much crazier as you proceed. But it's the good kind of crazy!)

$\endgroup$
13
  • $\begingroup$ Ok. I see what you mean. I'm not going to attempt to "argue with mathematics" I'm just giving my intuition on the subject along with an argument. I'm studying computer science not maths, and if you say there's no maximal length of a string in this set, then that's great. Personally I think I've provided an argument that leads to some kind of contradiction (or at least some doubt) but all these maths snobs are quick to silence me and I've better things to do. Oh well... $\endgroup$
    – nodger
    Jan 11, 2015 at 22:27
  • 1
    $\begingroup$ @nodger: It really doesn't mean anything to say that something "is" or "is not" infinity (not without a lot more discussion of which of the many meanings of the word infinity is being used). The opposite adjective of finite, the word that means "not finite", is infinite. Thus the correct version of what you said that "$\mathbb{N}$ is finite or infinite". As it happens, the set $\mathbb{N}$ is infinite. $\endgroup$
    – Sal
    Jan 11, 2015 at 22:37
  • 1
    $\begingroup$ @nodger: This is an important distinction, not only because it will help focus on what precisely your disagreement is on, but because there are in fact other infinite sets ($\mathbb{R}$, the real numbers, for example), and you would be additionally confused by saying "$\mathbb{N}$ is infinity" and $\mathbb{R}$ is infinity" since it would seem to follow somehow that $\mathbb{N}$ is $\mathbb{R}$, which is both intuitively and rigorously incorrect. However, it is no contradiction at all to have an adjective that applies to two different entities, such as "That car is red" and "That apple is red". $\endgroup$
    – Sal
    Jan 11, 2015 at 22:44
  • 1
    $\begingroup$ @nodger: To say that a set contains finite strings that are arbitrarily long doesn't mean it contains strings of unspecified length. Indeed, that wouldn't really make sense - once you have a given, specified string in mind, you can find its length right then and there. The concept of arbitrarily long only applies to a collection of strings, and it means for any finite length, there is at least one string in the collection that's at least that long. $\endgroup$
    – Sal
    Jan 11, 2015 at 23:06
  • 1
    $\begingroup$ @nodger: It's really hard to explain these topics to someone that is not planning on opening up a book and reading about them. Because at some point it boils down to "You're just gonna have to trust me on this one". Sal is doing a wonderful job trying to explain this to you, but unless you're really interested to walk the extra mile and learn all that stuff properly (which is not hard, just requires some time and dedication), I really think that we need to part as friends. Sal: Thank you for the effort in those comments, I know that those are not easy to write! $\endgroup$
    – Asaf Karagila
    Jan 11, 2015 at 23:09
2
$\begingroup$

Your argument seems to revolve around the length of the members being finite. Note that in a set of finite strings, each string must have a finite length, but this length ($N$) need not be the same for all members. This means:

  • Given a number $N$, the set $\Sigma^{\le N}$ of strings with length at most $N$ is finite (you argue about such sets)
  • The set $\Sigma^\ast$ of strings of finite length ($\Sigma^\ast = \bigcup_{n\in\mathbb N} \Sigma^{\le n}$) is infinite because to any string with "maximal length" you could append a member of $\Sigma$ to obtain a longer element of $\Sigma^\ast$, so since there are strings of arbitrary length in $\Sigma^\ast$ and since $\mathbb N$ is inifinite, so is $\Sigma^\ast$
  • In fact you gave a sketch proof that $\Sigma^\ast$ is countably infinite for any finite alphabet $\Sigma$ by (a) seeing that $\Sigma^\ast$ is infinite and (b) giving an enumeration of $\Sigma^\ast$, i.e. a systematic way to assign a natural number to any finite string in $\Sigma^\ast$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .