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 00:27

On Apr 24, 8:19 am, anonymous anonymous <anonymous500...(a)gmail.com>
wrote:
> On Apr 23, 8:58 pm, Patricia Shanahan <p...(a)acm.org> wrote:
>
>
>
>
>
> > anonymous anonymous wrote:
> > > Trying to understand the countable set and uncountable in context of
> > > Turing machine. To me it looks like powerset of some countable set
> > > like set of strings is countable. Am I missing something?
>
> > The subject line is a bit weird. If there is a 1 to 1 mapping between
> > set S and a countable set, S is countable.
>
> > > Let us say S1 is set of all strings over alphabet {a,b,c}.
>
> > Are you limiting it to finite strings, or including infinite strings?
>
> > ...
>
> > > Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
> > > {ab},
> > > {ba},{bb},...,{a,a},{a,b}...}
>
> > Are you limiting it to finite subsets, or do you mean the actual
> > powerset, which, if S3 is infinite, includes infinite subsets?
>
> > Patricia
>
> I am including infinite string and infinite subset like
> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
>
> Ok here is the slides from where I was learning Turing machine and
> countable sets.http://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin...
>
> If you look at slide number:
> Slide 14 to 28 there is part of proove that even set of rational
> numbers which have many infinite strings is countable.
> Slide 32-52 will show that powerset of an infinite set is uncountable
> which looks like not true to me.
>
> Anyway I will send a mail to the author's themselves and ask.- Hide quoted text -
>
> - Show quoted text -

S4 contains infinite subset like:
{ {{a},{b},{aa},{ab},{ba},{bb},...,{a,a},{a,b}...{b,aaaaaaaaaa.....},
{bb,aaaaaaaaaaaaaaaa.......},.......}

Just as S2 will also have infinite strings
{ a,b,aa,ab,ba,bb,...,aca,acb,..., bcaaaaaaaaaa.....,
bbcaaaaaaaaaaaaaaaa......., .......}

Just like rational numbers there are many infinite strings.

From: Patricia Shanahan on 24 Apr 2010 01:22

anonymous anonymous wrote:
> On Apr 24, 8:19 am, anonymous anonymous <anonymous500...(a)gmail.com>
> wrote:
>> On Apr 23, 8:58 pm, Patricia Shanahan <p...(a)acm.org> wrote:
>>
>>
>>
>>
>>
>>> anonymous anonymous wrote:
>>>> Trying to understand the countable set and uncountable in context of
>>>> Turing machine. To me it looks like powerset of some countable set
>>>> like set of strings is countable. Am I missing something?
>>> The subject line is a bit weird. If there is a 1 to 1 mapping between
>>> set S and a countable set, S is countable.
>>>> Let us say S1 is set of all strings over alphabet {a,b,c}.
>>> Are you limiting it to finite strings, or including infinite strings?
>>> ...
>>>> Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
>>>> {ab},
>>>> {ba},{bb},...,{a,a},{a,b}...}
>>> Are you limiting it to finite subsets, or do you mean the actual
>>> powerset, which, if S3 is infinite, includes infinite subsets?
>>> Patricia
>> I am including infinite string and infinite subset like
>> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
>>
>> Ok here is the slides from where I was learning Turing machine and
>> countable sets.http://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin...
>>
>> If you look at slide number:
>> Slide 14 to 28 there is part of proove that even set of rational
>> numbers which have many infinite strings is countable.
>> Slide 32-52 will show that powerset of an infinite set is uncountable
>> which looks like not true to me.
>>
>> Anyway I will send a mail to the author's themselves and ask.- Hide quoted text -
>>
>> - Show quoted text -
>
> S4 contains infinite subset like:
> { {{a},{b},{aa},{ab},{ba},{bb},...,{a,a},{a,b}...{b,aaaaaaaaaa.....},
> {bb,aaaaaaaaaaaaaaaa.......},.......}
>
> Just as S2 will also have infinite strings
> { a,b,aa,ab,ba,bb,...,aca,acb,..., bcaaaaaaaaaa.....,
> bbcaaaaaaaaaaaaaaaa......., .......}
>
> Just like rational numbers there are many infinite strings.
>

Most infinite strings of decimal digits do not represent natural
numbers. The decimal expansion of a rational is a very special
string.

Try to apply the proof of the countability of the rationals to your set
of infinite strings, and see how it breaks down. On the other hand, the
normal proof of uncountability of the real numbers needs very minor
changes to turn into a proof of uncountability of the set of infinite
strings.

Patricia

From: Tim Little on 24 Apr 2010 01:25

On 2010-04-23, anonymous anonymous <anonymous500081(a)gmail.com> wrote:
> Let us say S1 is set of all strings over alphabet {a,b,c}.
>
> So S1 will be something like this:
> {a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac...,aca,acb...}
>
> As we know S1 is countable.

Yes.

> Let us form set S2, from S1 where the strings in S2 are such that:
> 1.They do not start or end with alphabet c. (so ac, bc are not part
> of S2)
> 2. They do not include string where alphabet c occurs consecutively
> i.e. (cc, acc are not part of S2)
[...]
> Now S4 can be easily derived from S2. Replace the alphabet 'c' with
> ','(comma) and put curly braces.

It cannot. Every member of S2 is finite in length. S4 has elements
that cannot be represented by a finite string.

- Tim

From: Tim Little on 24 Apr 2010 01:26

On 2010-04-24, anonymous anonymous <anonymous500081(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: Virgil on 24 Apr 2010 02:26

In article <cvCdnXA9VYzcHU_WnZ2dnUVZ_qSdnZ2d(a)earthlink.com>,
Patricia Shanahan <pats(a)acm.org> wrote:

> anonymous anonymous wrote:
> > On Apr 24, 8:19 am, anonymous anonymous <anonymous500...(a)gmail.com>
> > wrote:
> >> On Apr 23, 8:58 pm, Patricia Shanahan <p...(a)acm.org> wrote:
> >>
> >>
> >>
> >>
> >>
> >>> anonymous anonymous wrote:
> >>>> Trying to understand the countable set and uncountable in context of
> >>>> Turing machine. To me it looks like powerset of some countable set
> >>>> like set of strings is countable. Am I missing something?
> >>> The subject line is a bit weird. If there is a 1 to 1 mapping between
> >>> set S and a countable set, S is countable.
> >>>> Let us say S1 is set of all strings over alphabet {a,b,c}.
> >>> Are you limiting it to finite strings, or including infinite strings?
> >>> ...
> >>>> Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
> >>>> {ab},
> >>>> {ba},{bb},...,{a,a},{a,b}...}
> >>> Are you limiting it to finite subsets, or do you mean the actual
> >>> powerset, which, if S3 is infinite, includes infinite subsets?
> >>> Patricia
> >> I am including infinite string and infinite subset like
> >> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.
> >>
> >> Ok here is the slides from where I was learning Turing machine and
> >> countable
> >> sets.http://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turin.
> >> ..
> >>
> >> If you look at slide number:
> >> Slide 14 to 28 there is part of proove that even set of rational
> >> numbers which have many infinite strings is countable.
> >> Slide 32-52 will show that powerset of an infinite set is uncountable
> >> which looks like not true to me.
> >>
> >> Anyway I will send a mail to the author's themselves and ask.- Hide quoted
> >> text -
> >>
> >> - Show quoted text -
> >
> > S4 contains infinite subset like:
> > { {{a},{b},{aa},{ab},{ba},{bb},...,{a,a},{a,b}...{b,aaaaaaaaaa.....},
> > {bb,aaaaaaaaaaaaaaaa.......},.......}
> >
> > Just as S2 will also have infinite strings
> > { a,b,aa,ab,ba,bb,...,aca,acb,..., bcaaaaaaaaaa.....,
> > bbcaaaaaaaaaaaaaaaa......., .......}
> >
> > Just like rational numbers there are many infinite strings.
> >
>
> Most infinite strings of decimal digits do not represent natural
> numbers. The decimal expansion of a rational is a very special
> string.
>
> Try to apply the proof of the countability of the rationals to your set
> of infinite strings, and see how it breaks down. On the other hand, the
> normal proof of uncountability of the real numbers needs very minor
> changes to turn into a proof of uncountability of the set of infinite
> strings.
>
> Patricia

And , in fact, it was Cantor's original claim and original diagonal
proof that the set of infinite binary strings was uncountable.