uncountable set maps 1 to 1 to a countable set [Theory]

Prev: The decision time is bounded by a polynomial in |x| and k.QED
Next: Thank you, Dublin!

From: anonymous anonymous on 24 Apr 2010 04:13

On Apr 24, 10:26 am, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-04-24, anonymous anonymous <anonymous500...(a)gmail.com> wrote:
>
> > I am including infinite string and infinite subset like
> > {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
>
> Then:
>
> 1) Your usage is nonstandard, and
>
> 2) S1 is uncountable.
>
> - Tim

From the PPT of lecture it seemed to me S1 is countable (slide 33, 34
and 35).

From: Patricia Shanahan on 24 Apr 2010 05:41

anonymous anonymous wrote:
> On Apr 24, 10:26 am, Tim Little <t...(a)little-possums.net> wrote:
>> On 2010-04-24, anonymous anonymous <anonymous500...(a)gmail.com> wrote:
>>
>>> I am including infinite string and infinite subset like
>>> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
>> Then:
>>
>> 1) Your usage is nonstandard, and
>>
>> 2) S1 is uncountable.
>>
>> - Tim
>
> From the PPT of lecture it seemed to me S1 is countable (slide 33, 34
> and 35).

The unqualified term "string" usually means a finite sequence of symbols
from the alphabet. That is definitely the case in slide 28 and following
of the lecture notes at
http://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turing.ppt.
Think about "each string is generated in finite time", and the fact that
every Turing machine can be described by a finite length string.

The enumerator sketched on slide 35 generates all the finite length
strings over the alphabet, but not a single infinite string. If it were
intended to be an enumerator for a set including any infinite strings it
would be seriously flawed.

Slide 28's set S is a proper subset of your set S1. S contains only
finite length strings and is countable. S1 contains both finite and
infinite strings and is uncountable.

Patricia

From: anonymous anonymous on 24 Apr 2010 13:07

On Apr 24, 2:41 pm, Patricia Shanahan <p...(a)acm.org> wrote:
> anonymous anonymous wrote:
> > On Apr 24, 10:26 am, Tim Little <t...(a)little-possums.net> wrote:
> >> On 2010-04-24, anonymous anonymous <anonymous500...(a)gmail.com> wrote:
>
> >>> I am including infinite string and infinite subset like
> >>> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
> >> Then:
>
> >> 1) Your usage is nonstandard, and
>
> >> 2) S1 is uncountable.
>
> >> - Tim
>
> > From the PPT of lecture it seemed to me S1 is countable (slide 33, 34
> > and 35).
>
> The unqualified term "string" usually means a finite sequence of symbols
> from the alphabet. That is definitely the case in slide 28 and following
> of the lecture notes athttp://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin....
> Think about "each string is generated in finite time", and the fact that
> every Turing machine can be described by a finite length string.
>
> The enumerator sketched on slide 35 generates all the finite length
> strings over the alphabet, but not a single infinite string. If it were
> intended to be an enumerator for a set including any infinite strings it
> would be seriously flawed.
>
> Slide 28's set S is a proper subset of your set S1. S contains only
> finite length strings and is countable. S1 contains both finite and
> infinite strings and is uncountable.
>
> Patricia- Hide quoted text -
>
> - Show quoted text -

Thanks a lot Patricia for having the patience to explain me.

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?

From: Virgil on 24 Apr 2010 14:58

In article
<43b4cabd-b999-4e7e-b617-2afe2c7473be(a)v12g2000prb.googlegroups.com>,
anonymous anonymous <anonymous500081(a)gmail.com> wrote:

> On Apr 24, 2:41�pm, Patricia Shanahan <p...(a)acm.org> wrote:
> > anonymous anonymous wrote:
> > > On Apr 24, 10:26 am, Tim Little <t...(a)little-possums.net> wrote:
> > >> On 2010-04-24, anonymous anonymous <anonymous500...(a)gmail.com> wrote:
> >
> > >>> I am including infinite string and infinite subset like
> > >>> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
> > >> Then:
> >
> > >> 1) Your usage is nonstandard, and
> >
> > >> 2) S1 is uncountable.
> >
> > >> - Tim
> >
> > > From the PPT of lecture it seemed to me S1 is countable (slide 33, 34
> > > and 35).
> >
> > The unqualified term "string" usually means a finite sequence of symbols
> > from the alphabet. That is definitely the case in slide 28 and following
> > of the lecture notes
> > athttp://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin....
> > Think about "each string is generated in finite time", and the fact that
> > every Turing machine can be described by a finite length string.
> >
> > The enumerator sketched on slide 35 generates all the finite length
> > strings over the alphabet, but not a single infinite string. If it were
> > intended to be an enumerator for a set including any infinite strings it
> > would be seriously flawed.
> >
> > Slide 28's set S is a proper subset of your set S1. S contains only
> > finite length strings and is countable. S1 contains both finite and
> > infinite strings and is uncountable.
> >
> > Patricia- Hide quoted text -
> >
> > - Show quoted text -
>
> Thanks a lot Patricia for having the patience to explain me.
>
> 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?

Every natural number can be represented by a FINITE string, in, for
example, standard decimal notation.

From: Patricia Shanahan on 24 Apr 2010 15:17

anonymous anonymous wrote:
> On Apr 24, 2:41 pm, Patricia Shanahan <p...(a)acm.org> wrote:
>> anonymous anonymous wrote:
>>> On Apr 24, 10:26 am, Tim Little <t...(a)little-possums.net> wrote:
>>>> On 2010-04-24, anonymous anonymous <anonymous500...(a)gmail.com> wrote:
>>>>> I am including infinite string and infinite subset like
>>>>> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
>>>> Then:
>>>> 1) Your usage is nonstandard, and
>>>> 2) S1 is uncountable.
>>>> - Tim
>>> From the PPT of lecture it seemed to me S1 is countable (slide 33, 34
>>> and 35).
>> The unqualified term "string" usually means a finite sequence of symbols
>> from the alphabet. That is definitely the case in slide 28 and following
>> of the lecture notes athttp://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin....
>> Think about "each string is generated in finite time", and the fact that
>> every Turing machine can be described by a finite length string.
>>
>> The enumerator sketched on slide 35 generates all the finite length
>> strings over the alphabet, but not a single infinite string. If it were
>> intended to be an enumerator for a set including any infinite strings it
>> would be seriously flawed.
>>
>> Slide 28's set S is a proper subset of your set S1. S contains only
>> finite length strings and is countable. S1 contains both finite and
>> infinite strings and is uncountable.
>>
>> Patricia- Hide quoted text -
>>
>> - Show quoted text -
>
> Thanks a lot Patricia for having the patience to explain me.
>
> 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?
>

First of all, the normal decimal representation of a natural number is a
finite string over the alphabet 0 through 9. Can you specify the
representation system you are using?

More basically, there are finite, countably infinite, and uncountable
sets some of whose members are infinite strings. The presence of
infinite strings is not, by itself, enough to make a set uncountable.

The set whose only element is the decimal expansion of 1/3 is a finite
set with one element that contains an infinite string. The set of
decimal expansions of rational numbers is a countably infinite set of
strings with some infinite members.

The test for whether a set X is countably infinite or uncountable is
whether there is a bijection between X and N, the set of natural
numbers. There is a bijection for the set of finite strings, the set S
in your lecture notes. The enumeration sketched on slide 35 is the basis
for a bijection that associates a string with the index of its position
in the enumeration.

You cannot depend on the argument for countability of S for your S1
because S1 is a proper superset of S. Even if S1 were countable, it
would need its own proof with its own bijection between S1 and N.

Patricia