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: [email protected]
> 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}}
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 [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
