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 1 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 0 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 8 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 2 in the subset? Is 3 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 4 in the subset? YES Is 5 in the subset? NO Is 6 in the subset? NO Is 7 in the subset? YES 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 ... (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@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---