Is the number of finite strings infinite?

Question

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.

Answer 1

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!).

Answer 2

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!)

Answer 3

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