Re: infinity

In article <MPG.1d88f149318a1a7298a210@xxxxxxxxxxxxxxxxxxxxxxxxx> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> writes:
> *** T. Winter said:
....
> > > For each L, there are 2^L strings of that length, and sum(x=0->L: 2^x)
> > > strings up to that length. If L is finite, then sum(x=0->L: 2^x) is a
> > > sum of a finite number of terms, each of which is finite, so there
> > > are a finite number of strings in a language with strings of finite
> > > length.
> >
> > The "so" part does not follow, it only follows if there would be a maximal
> > length.
>
> No, it follows that if the length is always finite, then this fact holds.

No, it does not follow. *If* there is a maximal length L, then there are
finitely many strings with length less than or equal to L. There is however
no L such that all strings are in length less than that L, so it does not
follow.

> > Why? You keep asserting this, but you never give a valid proof.
>
> For any finite k, sum(x=0->k:S^x) is finite. Are there any infinite k,
> that is, infinite lengths to strings? No? Then for all lengths of strings
> in the set, it is true that all strings up to and including that length
> comprise a finite number of strings.

That is true.

> There is no string in the set which
> is long enough to allow an infinite set of strings shorter than or equal
> to it.

Also correct. This still does *not* show that in a set of finite strings
where there is no longest string (there are always longer ones available)
is also finite. So your assertion:
> Only when string length is allowed
> to become infinite can the langauge be infinite, unless you have an infinite
> alphabet.
is not yet proven.

> > > You are claiming that if you claim to have allowed enough characters
> > > in your strings to make an infinite language possible. For each
> > > character added, you have multipied your language by a factor of 2.
> > > At which finite L does sum(x=0->L: 2^x) become infinite?
> >
> > Never, it increases without bound.
>
> But it never becomes infinite, unless L is infinite.

That is also not what I have claimed. I only claim that as there is no L
that is a maximum length, that the number of finite strings is unbounded.
And a set with a number of elements that is larger than any finite number
is called infinite.

> > I do not reject them a priory. I only tell you that you do not need
> > infinite strings to get an infinite language.
> But you do. Explain otherwise how sum(x=0->L: S^x) is infinite, without L
> or S being infinite.

A language is named infinite if there is no finite bound on the words in
the language. You do not need either an infinite length, neither an
infinite alphabeth in order to get an infinite language.

> > There is. There is no bound on the size of the strings. That is, there
> > is no L such that all strings have a length <= L, but none of the strings
> > has infinite length. What is the size of such a language?
>
> Finite, but unbounded.

Finite means you can give a particular number k such that there are so many
elements. Unbounded has no mathematical definition for sizes of sets.

Apparently you are using quite new and different definitions.

How do you define "finite" when applied to sets (and a language is a set of
words)?
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast