On 09 Jul 2009, at 03:05, m.a. wrote: > Here's my third try. I'll continue working on the (power x) > problem. m.a. > ----- Original Message ----- > From: Bruno Marchal > To: everything-list@googlegroups.com > Sent: Wednesday, July 08, 2009 1:31 PM > Subject: Re: The seven step series > > > On 08 Jul 2009, at 15:43, m.a. wrote: > >> Second try: >>> (power {1, 2, 3}) = ? {{ }, {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}} >>> > Third try: > = {{ }, {1}, {2}, {3}, > {1,2}, {2,3}, {1,2,3}, {{ },1,2,3}}

## Advertising

You may be a bit saturated, because this is less correct than your preceding answer. You could, after some good night sleep, see this by yourself. Indeed if { { } 1, 2, 3} was a subset of { 1,2,3}, this would mean, by the definition of subset, that 1, 2, 3 and { } are elements of {1, 2, 3}. But { } is not an element of {1, 2, 3}. The missing subset is just {1, 3}. So instead of ... > I gave you the hint that there are 8 elements. Let us count: > > The empty set { } ..................................1 > Three singletons {1}, {2}, {3}................3 > Two doubletons {1,2 }, {2,3 }................2 > The biggest subset {1,2,3}..................1 > > 1 + 3 + 2 + 1 = 7 > > A subset is missing! Can you see which one? ... we have the much more symmetrical: The empty set { } .........................................1 Three singletons {1}, {2}, {3}.......................3 Three doubletons {1,2 }, {2,3 }, {1,3}..........3 The biggest subset {1,2,3}..........................1 "1 3 3 1" is a row in the so called "Pascal triangle", and I have put those decomposition because the formula you gave me, was the formula giving the value of the number appearing in the Pascal triangle. In french we would say that you are searching the "little beast", making things more complex than they really are. Let me do your, rather complex, reasoning: I have a set A having n elements. A subset of A will have at most n elements. To find how many subsets are in A, I have to count the subset having 0 elements, 1 element, 2 elements; 3 elements, ... i elements, ... up to i = n. Searching in my memory, book or the net, I recall that the number of subsets having i elements taken in a set of n elements, let us write this (i;n), is n(n-1)(n-2) ... (n-i+1)/i! So the number of elements in the powerset of A is the sum from i = 0 to n of (i; n) = sum from i = 0 to n of n(n-1)(n-2) ... (n-i+1)/i! This is a very complex reasoning leading to a rather complex formula. It would have been rather not pedagogical from my part to give you a so difficult exercise, so you could have guessed a simpler reasoning, leading to a simpler formula. Let us to do the "simpler" reasoning. We have already seen that the powerset of a set with 0 element has 1 element. cf (powerset { }) = {{ }} We have already seen that the powerset of a set with 1 element has 2 elements. cf (powerset {a}) = {{ }, {a}} We have already seen that the powerset of a set with 2 element has 4 elements. cf (powerset {a, b}) = {{ }, {a} {b} {a, b}} We have just seen that the powerset of a set with 3 element has 8 elements (cf above). We see that the sequence of numbers on the right grows like 1, 2, 4, 8, .... And we have to guess the sequel, and find a general formula. Of course, if we don't see it yet we can still compute, tediously, the number of subsets of a set with four elements, like S = {a, b, c, d}. Let us do it: The subset of S with 0 element { } .................................. 1 The subsets of S with 1 element {a}, {b}, {c}, {d} ...........4 The subsets of S with 2 elements {a,b} {a,c},{a,d} {b,c} {b,d}, {c,d} ...... 6 The subsets of S with 3 elements {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d} .......4 The subset of S with 4 elements {a,b,c,d} ..........................................1 Thus there are 1+4+6+4+1 subsets of {a,b,c,d}, and this gives 16. Now our sequence of answers is a bit longer: 1, 2, 4, 8, 16, .... Exercise: can you guess how many subsets there are in a set with 5 elements, 6 elements, ...? After that I will help you to get the formula, and we will be able to soon approach a far reaching question: how many subsets are included in the infinite set N = {0, 1, 2, 3, ...}. But some vocabulary will have to introduced, some generalization will have to be done. After that we will come to the machines, and the question of computability, but let us go easy and slowly. We have already done a lot, and you can take some rest when you want. Bravo for the work you have already done. I just give you another little, not so obvious but very pleasant exercise: look at many Mandelbrot set videos on youtube, and try to discover the recurring sequence 1, 2, 4, 8, 16, ... appearing in the zooms. This is experimental mathematics! This is for your enjoyment only. Sort of dessert. BTW, the sequence 1, 2, 4, 8, 16, ... appears also in some of the thought experiments in the comp setting. Perhaps you remember? 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 -~----------~----~----~----~------~----~------~--~---