On 14 Jul 2009, at 10:40, Bruno Marchal wrote:

<snip>

> So the subsets of {a, b} are { }, {a}, {b}, {a, b}.
>
> But set have been invented to make a ONE from a MANY, and it is  
> natural to consider THE set of all subsets of a set. It is called  
> the powerset of that set.
>
> So the powerset of {a, b} is THE set {{ }, {a}, {b}, {a, b}}. OK?
>
> Train yourself on the following exercises:
>
> What is the powerset of { }
> What is the powerset of {a}
> What is the powerset of {a, b, c}


I give the answer, and I continue slowly.

1) What is the powerset of {a, b, c}?

By definition, the powerset of {a, b, c} is the set of all subsets of  
{a, b, c}.
I go slowly.

Is the set {d, e, f} a subset of {a, b, d}? No. None of the elements  
of {d, e, f} are elements of {a, b, c}. The question was ridiculous.

Is the set {a, b, d} a subset of {a, b, c}? No. One element of {a, b,  
d}, indeed, d, does not belong to {a, b, c}, so {a, b, d} cannot be a  
subset of {a, b, c}. The question was ridiculous again, but less  
obviously so.

Is the set {a, b, c} a subset of {a, b, c}. Yes. All elements of {a,  
b, c} are elements of {a, b, c}. {a, b, c} is included in {a, b, c}.

Can we conclude from this that the powerset of {a, b, c} is {{a, b,  
c}}. No. We can conclude only that {{a, b, c}} is included in the  
powerset. It is very plausible that there are other subsets!

Indeed,

Is {a, b} included in {a, b, c}? Yes, all elements of {a, b} are  
elements of {a, b, c}. This take two verifications: we have to verify  
that a belongs to {a, b, c}. And that b belongs to {a, b, c}.

Can we conclude from this that the powerset of {a, b, c} is {{a, b, c}  
{a, b}}. No, we could still miss other subsets.

I accelerate a little bit.
Is {a, c} a subset of {a, b, c}? Yes, by again two easy verification.

Is there another doubleton (set with two elements) having elements in  
{a, b, c}? Yes. {c, b}. It is easy to miss them, so you have to be  
careful. All two elements of {c, b} are elements of {a, b, c}, as can  
be verified by two easy verification.

  Is {b, c} a subset of {a, b, c}. Yes, but we have already consider  
it. Indeed the set {b, c} is the same set as {c, b}.

Is there another doubleton? No. Why? I search and don't find it.

is there yet some subset to find?

Yes, the set with one element, notably. They are called singleton.

Here it is easy to guess that there will be as many singletons  
included in (a, b, c} that there is elements in {a, b, c}. So the  
singletons are {a}, {b}, and {c}. This can be verified by one  
verification for each.

Are there still subset? Yes. We have seen that the empty set { } is  
included in any set. This can be (re)verify by 0 verifications, given  
that there is 0 element in { }..

Conclusion:
There are 8 subsets in {a, b, c}, which are { }, {a}, {b}, {c}.{a, b},  
{a, c}, {c, b} and {a, b, c}. And thus,

The powerset of {a, b, c}  is the set { { }, {a}, {b}, {c}.{a, b}, {a,  
c}, {c, b} {a, b, c}}.


2) What is the powerset of {a}?

Answer {{ } {a}}. It has two elements.

3) What is the powerset of { }
We could think at first sight that there are no subsets, given that  
{ } is empty. But we have seen that { } is included in any set. So { }  
is included in { }. Again you can verify this by zero verification!  
But then the powerset of { }, which is the set of sets included in { }  
is not empty:  It has one element, the empty set. It is {{ }}. Think  
that {{ }} is a box containing that empty box.


Attempt toward a more general conclusion.

The powerset of a set with 0 element has been shown having 1 elements,  
and no more.
The powerset of a set with 1 element has been shown having 2 elements,  
and no more.
The powerset of a set with 2 elements has been shown having 4  
elements, and no more. (preceding post)
The powerset of a set with 3 elements has been shown having 8  
elements, and no more.
The powerset of a set with 4 elements has been shown having 16  
elements, and no more. (older post)

In math we like to abstract things. Let us look at the preceding line  
with all the words dropped! This gives

--- 0 ---- 1 ---
--- 1 ---- 2 ---
--- 2 ---- 4 ---
--- 3 ---- 8 ---
--- 4 ---- 16 ---

On the left, we see, vertically disposed, the natural numbers,  
appearing with their usual order.
On the right, we see, vertically disposed, some natural numbers, which  
seems to depend in some way from what numbers appears on the left. It  
looks like there is a functional relation, that is a function.

The notion of function is the most important and pervading notion in  
math, physics, science in general, and we will have to come back on  
that very notion soon enough.

The idea that there is a function lurking there, is the idea that we  
can guess a general law, capable of providing the answer to the  
general line:

   "The powerset of a set with n element has been shown having ?  
elements, and no more."

Can we determine ? from n. Surely it depends on n.

In this case, a simple guess can be made, by meditating on the  
sequence of numbers which appear on the right. Those are, when written  
horzontally:

1, 2, 4, 8, 16, ...

I guess you see what happens. Each number in that sequence is the  
double of the preceding one. So the next one can be obtained, by just  
continuing the multiplication by two.

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384,  
32768, 65536, 131072, ... that is,

1, 2x2, 2x2x2, 2x2x2x2, 2x2x2x2x2, 2x2x2x2x2x2, ...

We will write a possibly lengthy expression like 2x2x2x2x2x ... x2, as  
2^n, where n is the number of occurence of "2" in the expression.

So you can guess that in the "general line":

   "The powerset of a set with n elements has been shown having ?  
elements, and no more."

? does indeed depend on n, and is actually equal to 2^n.

Here is the general law, that we have guessed by experience (counting  
in the simple case) and generalized by intution:

The powerset of a set with n elements has been shown having 2^n  
elements, and no more.

When we found a law in such a way, we could ask if we couldn't prove  
it from facts we are already believing (or guessing).

Here, the theory is the intuitive basic  knowledge of logic, numbers  
and sets. And the question is really: can you prove, or justify, or  
explain WHY the powerset of a set of n elements has 2^n elements?

What happens which could explain why, when we add an element to a set,  
its powerset becomes two time bigger. is there a reason for that  
special happening. Can I convince myself that it has to be like that?

I let you think.

Hints. We have already see a "doubling scenario". Indeed, I often  
mention at the step 3 of the UDA, the iterated self-duplication. Some  
is cut and paste in Brussel, and copy at place W and M. Then both  
individuals come back, by train, in Brussels and both do the  
duplication experience again, and again, and again. The number of  
individuals grows like 2, 4, 8, ... that is 2^n, with n the number of  
iteration of the experience. After n iteration, each has written in  
its "first person diary" the sequence of places they have visit, which  
look like a string of W and M of length n.

No question? If everything is clear, I continue asap.

Oh! I have a question myself. If the law above is correct, it looks  
like 2^0 = 1. It is the laws applied to the first line---the case of  
the powerset of the empty set. Is it true that 2x2x2x...x2 is equal to  
1 in case the number of occurence of 2 is 0? How come?

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
-~----------~----~----~----~------~----~------~--~---

Reply via email to