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