Prev: The decision time is bounded by a polynomial in |x| and k.QED
Next: Thank you, Dublin!
From: Jym on 24 Apr 2010 19:41
On Sat, 24 Apr 2010 19:07:56 +0200, anonymous anonymous
<anonymous500081(a)gmail.com> wrote:

> Is the set of natural number countable? As it will have infinite
> strings like {....., 111111......, 2222......., 33333......, }. Or
> when we say set of natural numbers we do not include such infinite
> strings?

[indentifying a number with its decimal representation)
As already pointed, the set of natural numbers does not contain "infinite
strings" (of digits).

The trick is that it can contains arbitrary long strings, but each of them
is finite.
So, the set contains {1, 11, 111, 1111, ...., 111111111111, .... } (and
more) but *does not* contains "1111....." which corresponds to no number.
There is a difference between "infinite" and "finite but unbounded". The
set of natural numbers contains only finite strings but of unbounded
length. You cannot restrict yourself to, say, strings of length less than
1,000,000,000 and get all the natural numbers. But evry single natural
number has a finite representation. The length of such a representation is
unbounded but it is always finite.

--
Hypocoristiquement,
Jym.
From: anonymous anonymous on 24 Apr 2010 23:41
On Apr 25, 4:41 am, Jym <Jean-Yves.Moyen+n...(a)ens-lyon.org> wrote:
> On Sat, 24 Apr 2010 19:07:56 +0200, anonymous anonymous  
>
> <anonymous500...(a)gmail.com> wrote:
> > Is the set of natural number countable? As it will have infinite
> > strings like {....., 111111......,  2222.......,  33333......, }. Or
> > when we say set of natural numbers we do not include such infinite
> > strings?
>
> [indentifying a number with its decimal representation)
> As already pointed, the set of natural numbers does not contain "infinite  
> strings" (of digits).
>
> The trick is that it can contains arbitrary long strings, but each of them  
> is finite.
> So, the set contains {1, 11, 111, 1111, ...., 111111111111, .... } (and  
> more) but *does not* contains "1111....." which corresponds to no number.
> There is a difference between "infinite" and "finite but unbounded". The  
> set of natural numbers contains only finite strings but of unbounded  
> length. You cannot restrict yourself to, say, strings of length less than  
> 1,000,000,000 and get all the natural numbers. But evry single natural  
> number has a finite representation. The length of such a representation is  
> unbounded but it is always finite.
>
> --
> Hypocoristiquement,
> Jym.

You are right. Now when I look at the slides again, I see it only has
finite but unbounded strings.
First  |  Prev  | 
Pages: 1 2 3 4
Prev: The decision time is bounded by a polynomial in |x| and k.QED
Next: Thank you, Dublin!