- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Mon, 20 Jul 2009 21:17:48 +0200

On 20 Jul 2009, at 15:34, m.a. wrote:

*> Bruno,
*

*> I don't know about Kim, but I'm ready to push on. I'm
*

*> waiting for the answer to problem 2) see below. And could you please
*

*> retstate that problem as I'm not sure which one it is? Thanks,
*

*> marty a.
*

*>
*

Let us see:

*>>> >
*

*>>> > 1) What is common between the set of all subsets of a set with n
*

*>>> > elements, and the set of all finite sequences of "0" and "1" of
*

*>>> length
*

*>>> > n.
*

*>>> > 2) What is common between the set of all subsets of N, and the
*

*>>> set of
*

*>>> > all infinite sequences of "0" and "1".
*

*>>> >
*

*>>
*

Let me restate by introducing a "definition" (made precise later). The

cardinal of a set S is the number of elements in the set S.

The cardinal of { } = 0. All singletons have cardinal one. All pairs,

or doubletons, have cardinal two.

Problem 01 has been solved. They have the same cardinal, or if you

prefer, they have the same number of elements. The set of all subsets

of a set with n elements has the same number of elements than the set

of all strings of length n.

Let us write B_n for the sets of binary strings of length n. So,

B_0 = { }

B_1 = {0, 1}

B_2 = {00, 01, 10, 11}

B_3 = {000, 010, 100, 110, 001, 011, 101, 111}

We have seen, without counting, that the cardinal of the powerset of a

set with cardinal n is the same as the cardinal of B_n.

And then we have seen that such cardinal was given by 2^n.

You can see this directly by seeing that adding an element in a set,

double the number of subset, due to the dichotomic choice in creating

a subset "placing or not placing" the new element in the subset.

Likewise with the strings. If you have already all strings of length

n, you get all the strings of length n+1, by doubling them and adding

zero or one correspondingly.

This is also illustrated by the iterated self-duplication W, M. Mister

X is cut and paste in two rooms containing each a box, in which there

is a paper with zero on it, in room W, and 1 on it in room M. After

the experience, the 'Mister X' coming out from room W wrote 00 in his

diary, and the 'Mister X' coming out from room M wrote 1 in his diary.

And then they redo each, the experiment. The Mister-X with-0-in-his-

diary redoes it, and gives a Mister-X with-0-in-his-diary coming out

from room W, and adding 0 in its diary and a Mister-X with-0-in-his-

diary coming out from room M, adding 1 in its diary: they have the

stories

00

01,

and then the Mister-X-coming-from room W, and with 1 written in the

diary, similarly redoes the experiment, and this gives two more

Misters X, having written in their diaries

10

11.

Obviously the iteration of the self-duplication, gives as result

2x2x2x2x...x2 number of Mister X. If those four Mister X duplicate

again, there will be 08 of them, with each of those guys having an

element of B_3 written in his diary. OK.

And we have seen that a powerset of a set with n elements can but put

in a nice correspondence with B_n.

For example: The powerset of {a, b}, that is {{ }, {a}, {b}, {a, b}},

has the following nice correspondence

00 .............. { }

01 .............. {a}

10 ...............{b}

11 ...............{a, b}

Each 0 and 1 corresponding to the answer to the yes/no questions 'is a

in the subset?', is 'b in the subset?'.

Such a nice correspondence between two sets is called a BIJECTION, and

will be defined later. What we have seen, thus, is that there is a

bijection between the powerset of set with n elements, and the set of

binary strings B_n.

And the second question?

What is common between the subsets of N, and the set of infinite

binary sequences. An infinite binary sequence is a infinite sequences

of "0" and "1".

For example: 00000000000..., with only zero is such a sequence. It

could be the first person story of 'the mister X who comes always from

room W. Or, if the zero and one represents the result of the fair coin

throw experiment, it could be the result of the infinitely unlucky

guy: he always get the head.

Another one quite similar is 1111111111111111111111111111..., the

infinitely lucky guy.

A more 'typical' would be 1100100100001111110110101010001000...

(except that this very one *is* typical, it is PI written in binary;

PI = 11. 00100...).

The link with the subsets of N? It is really the same as above, except

that we extend the idea on the infinite.

A subset of N, that is, a set included in N, is entirely determined

by the answer to the following questions:

Is 0 in the subset?

Is 1 in the subset?

Is 02 in the subset?

Is 03 in the subset?

etc.

You will tell me that nobody can answer an infinity of questions. I

will answer that in many situation we can.

Let us take a simple subset of N, the set {3, 4, 7}. It seems to me we

can answer to the infinite set of corresponding question:

Is 0 in the subset? NO

Is 1 in the subset? NO

Is 2 in the subset? NO

Is 3 in the subset? YES

Is 04 in the subset? YES

Is 05 in the subset? NO

Is 06 in the subset? NO

Is 07 in the subset? YES

Is 8 in the subset? NO

Is 09 in the subset? NO

Is 10 in the subset? NO

Is 11 in the subset? NO

Is 12 in the subset? NO

Is 13 in the subset? NO

Is 14 in the subset? NO

... (etc. and we answer NO for all remaining questions ...!)

So, in the same spirit as above we associate the infinite binary

string 000110010000000000000000... to the subset {3, 4, 7}.

Even simpler: the empty set. First, is the empty set a subset of N?But

we have seen that to verify if the empty set is a subset of any set,

we have 0 verification to do: the empty set is included in any set. It

correspond here to

Is 0 in the subset? NO

Is 1 in the subset? NO

Is 2 in the subset? NO

Is 3 in the subset? NO

Is 4 in the subset? NO

Is 5 in the subset? NO

Is 6 in the subset? NO

Is 7 in the subset? NO

Is 8 in the subset? NO

Is 9 in the subset? NO

Is 10 in the subset? NO

Is 11 in the subset? NO

Is 12 in the subset? NO

Is 13 in the subset? NO

Is 14 in the subset? NO

... (and we answer NO for all remaining questions ...!)

the empty set, seen as a subset of N, is determined by the sequence:

000000000000000000000000000000000000000000 ...

All singleton of number, like {0}, {1}, {2}, {3}, {4}, {5}, ...

will have the following "characteristic" sequences:

{0} ---- 1000000000000000...

{1} ---- 0100000000000000...

{2} ---- 001000000000000..

etc.

Doubleton will have characteristic sequences being strings having two

occurences of 1, and thus an infinity of zero.

OK, for finite set, there is a time where all answers become "NO".

But what about infinite sets? Can we still answer the infinity of

question?

Of course, at least for "simple" infinite sets.

First, do we know infinite subset of N? yes, example the set of odd

numbers. {1, 3, 5, ...} is included in {0, 1, 2, 3, ...}.

What is its characteristic sequences, that is the answer to the

questions: is 0 in?, is 1in?, is 2 in?, ...

Is 0 in the subset? NO

Is 1 in the subset? YES

Is 2 in the subset? NO

Is 3 in the subset? YES

Is 4 in the subset? NO

Is 5 in the subset? YES

Is 6 in the subset? NO

Is 7 in the subset? YES

Is 8 in the subset? NO

Is 9 in the subset? YES

Is 10 in the subset? NO

Is 11 in the subset? YES

Is 12 in the subset? NO

Is 13 in the subset? YES

Is 14 in the subset? NO

... (and we answer YES and NO in that way for all remaining

questions ...!)

So the set of odd numbers has the characteristic sequence:

{1, 3, 5, ...} -----------

010101010101010101010101010101010101010101010...

and the even numbers:

{0, 2, 4, 6, ...} ----------

101010101010101010101010101010101010101010...

And ... the prime numbers

{2, 3, 5, 7, 11, ...} ------- 00110101000101000101000100000101...

OK.

Do you see that for EACH subset of N we have a corresponding infinite

binary sequence, and for EACH binary sequence we have a subset.

Exercise: gives the subset (= write some elements of the subset)

corresponding o the sequence "PI"

1100100100001111110110101010001000...

The genius of Cantor has consisted in allowing himself the notion of

"nice correspondence", bijection, to infinite sets, including infinite

sets of infinite objects, like the subset of N and the set B_infinity,

that is the set of infinite binary strings.

And here, I hope you have the feeling that indeed such a nice

correspondence exists between the powerset of N, and B_infinity.

I let you think, and ask some questions. Bijection will occupy us for

awhile. Unfortunately, to make them precise, I have to define what we

have already met a lot, but yet not define, and which is the notion of

function.

Functions are utterly important because they define the crucial notion

of mathematical dependency, on which eventually the mathematical

notion of computation will be a very peculiar particular case.

Bruno

http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~

You received this message because you are subscribed to the Google Groups "Everything List" group.

To post to this group, send email to everything-list.domain.name.hidden

To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list?hl=en

-~----------~----~----~----~------~----~------~--~---

Received on Mon Jul 20 2009 - 21:17:48 PDT

Date: Mon, 20 Jul 2009 21:17:48 +0200

On 20 Jul 2009, at 15:34, m.a. wrote:

Let us see:

Let me restate by introducing a "definition" (made precise later). The

cardinal of a set S is the number of elements in the set S.

The cardinal of { } = 0. All singletons have cardinal one. All pairs,

or doubletons, have cardinal two.

Problem 01 has been solved. They have the same cardinal, or if you

prefer, they have the same number of elements. The set of all subsets

of a set with n elements has the same number of elements than the set

of all strings of length n.

Let us write B_n for the sets of binary strings of length n. So,

B_0 = { }

B_1 = {0, 1}

B_2 = {00, 01, 10, 11}

B_3 = {000, 010, 100, 110, 001, 011, 101, 111}

We have seen, without counting, that the cardinal of the powerset of a

set with cardinal n is the same as the cardinal of B_n.

And then we have seen that such cardinal was given by 2^n.

You can see this directly by seeing that adding an element in a set,

double the number of subset, due to the dichotomic choice in creating

a subset "placing or not placing" the new element in the subset.

Likewise with the strings. If you have already all strings of length

n, you get all the strings of length n+1, by doubling them and adding

zero or one correspondingly.

This is also illustrated by the iterated self-duplication W, M. Mister

X is cut and paste in two rooms containing each a box, in which there

is a paper with zero on it, in room W, and 1 on it in room M. After

the experience, the 'Mister X' coming out from room W wrote 00 in his

diary, and the 'Mister X' coming out from room M wrote 1 in his diary.

And then they redo each, the experiment. The Mister-X with-0-in-his-

diary redoes it, and gives a Mister-X with-0-in-his-diary coming out

from room W, and adding 0 in its diary and a Mister-X with-0-in-his-

diary coming out from room M, adding 1 in its diary: they have the

stories

00

01,

and then the Mister-X-coming-from room W, and with 1 written in the

diary, similarly redoes the experiment, and this gives two more

Misters X, having written in their diaries

10

11.

Obviously the iteration of the self-duplication, gives as result

2x2x2x2x...x2 number of Mister X. If those four Mister X duplicate

again, there will be 08 of them, with each of those guys having an

element of B_3 written in his diary. OK.

And we have seen that a powerset of a set with n elements can but put

in a nice correspondence with B_n.

For example: The powerset of {a, b}, that is {{ }, {a}, {b}, {a, b}},

has the following nice correspondence

00 .............. { }

01 .............. {a}

10 ...............{b}

11 ...............{a, b}

Each 0 and 1 corresponding to the answer to the yes/no questions 'is a

in the subset?', is 'b in the subset?'.

Such a nice correspondence between two sets is called a BIJECTION, and

will be defined later. What we have seen, thus, is that there is a

bijection between the powerset of set with n elements, and the set of

binary strings B_n.

And the second question?

What is common between the subsets of N, and the set of infinite

binary sequences. An infinite binary sequence is a infinite sequences

of "0" and "1".

For example: 00000000000..., with only zero is such a sequence. It

could be the first person story of 'the mister X who comes always from

room W. Or, if the zero and one represents the result of the fair coin

throw experiment, it could be the result of the infinitely unlucky

guy: he always get the head.

Another one quite similar is 1111111111111111111111111111..., the

infinitely lucky guy.

A more 'typical' would be 1100100100001111110110101010001000...

(except that this very one *is* typical, it is PI written in binary;

PI = 11. 00100...).

The link with the subsets of N? It is really the same as above, except

that we extend the idea on the infinite.

A subset of N, that is, a set included in N, is entirely determined

by the answer to the following questions:

Is 0 in the subset?

Is 1 in the subset?

Is 02 in the subset?

Is 03 in the subset?

etc.

You will tell me that nobody can answer an infinity of questions. I

will answer that in many situation we can.

Let us take a simple subset of N, the set {3, 4, 7}. It seems to me we

can answer to the infinite set of corresponding question:

Is 0 in the subset? NO

Is 1 in the subset? NO

Is 2 in the subset? NO

Is 3 in the subset? YES

Is 04 in the subset? YES

Is 05 in the subset? NO

Is 06 in the subset? NO

Is 07 in the subset? YES

Is 8 in the subset? NO

Is 09 in the subset? NO

Is 10 in the subset? NO

Is 11 in the subset? NO

Is 12 in the subset? NO

Is 13 in the subset? NO

Is 14 in the subset? NO

... (etc. and we answer NO for all remaining questions ...!)

So, in the same spirit as above we associate the infinite binary

string 000110010000000000000000... to the subset {3, 4, 7}.

Even simpler: the empty set. First, is the empty set a subset of N?But

we have seen that to verify if the empty set is a subset of any set,

we have 0 verification to do: the empty set is included in any set. It

correspond here to

Is 0 in the subset? NO

Is 1 in the subset? NO

Is 2 in the subset? NO

Is 3 in the subset? NO

Is 4 in the subset? NO

Is 5 in the subset? NO

Is 6 in the subset? NO

Is 7 in the subset? NO

Is 8 in the subset? NO

Is 9 in the subset? NO

Is 10 in the subset? NO

Is 11 in the subset? NO

Is 12 in the subset? NO

Is 13 in the subset? NO

Is 14 in the subset? NO

... (and we answer NO for all remaining questions ...!)

the empty set, seen as a subset of N, is determined by the sequence:

000000000000000000000000000000000000000000 ...

All singleton of number, like {0}, {1}, {2}, {3}, {4}, {5}, ...

will have the following "characteristic" sequences:

{0} ---- 1000000000000000...

{1} ---- 0100000000000000...

{2} ---- 001000000000000..

etc.

Doubleton will have characteristic sequences being strings having two

occurences of 1, and thus an infinity of zero.

OK, for finite set, there is a time where all answers become "NO".

But what about infinite sets? Can we still answer the infinity of

question?

Of course, at least for "simple" infinite sets.

First, do we know infinite subset of N? yes, example the set of odd

numbers. {1, 3, 5, ...} is included in {0, 1, 2, 3, ...}.

What is its characteristic sequences, that is the answer to the

questions: is 0 in?, is 1in?, is 2 in?, ...

Is 0 in the subset? NO

Is 1 in the subset? YES

Is 2 in the subset? NO

Is 3 in the subset? YES

Is 4 in the subset? NO

Is 5 in the subset? YES

Is 6 in the subset? NO

Is 7 in the subset? YES

Is 8 in the subset? NO

Is 9 in the subset? YES

Is 10 in the subset? NO

Is 11 in the subset? YES

Is 12 in the subset? NO

Is 13 in the subset? YES

Is 14 in the subset? NO

... (and we answer YES and NO in that way for all remaining

questions ...!)

So the set of odd numbers has the characteristic sequence:

{1, 3, 5, ...} -----------

010101010101010101010101010101010101010101010...

and the even numbers:

{0, 2, 4, 6, ...} ----------

101010101010101010101010101010101010101010...

And ... the prime numbers

{2, 3, 5, 7, 11, ...} ------- 00110101000101000101000100000101...

OK.

Do you see that for EACH subset of N we have a corresponding infinite

binary sequence, and for EACH binary sequence we have a subset.

Exercise: gives the subset (= write some elements of the subset)

corresponding o the sequence "PI"

1100100100001111110110101010001000...

The genius of Cantor has consisted in allowing himself the notion of

"nice correspondence", bijection, to infinite sets, including infinite

sets of infinite objects, like the subset of N and the set B_infinity,

that is the set of infinite binary strings.

And here, I hope you have the feeling that indeed such a nice

correspondence exists between the powerset of N, and B_infinity.

I let you think, and ask some questions. Bijection will occupy us for

awhile. Unfortunately, to make them precise, I have to define what we

have already met a lot, but yet not define, and which is the notion of

function.

Functions are utterly important because they define the crucial notion

of mathematical dependency, on which eventually the mathematical

notion of computation will be a very peculiar particular case.

Bruno

http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~

You received this message because you are subscribed to the Google Groups "Everything List" group.

To post to this group, send email to everything-list.domain.name.hidden

To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list?hl=en

-~----------~----~----~----~------~----~------~--~---

Received on Mon Jul 20 2009 - 21:17:48 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:16 PST
*