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 00 verifications, given
that there is 0 element in { }..
Conclusion:
There are 08 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 01 elements,
and no more.
The powerset of a set with 1 element has been shown having 02 elements,
and no more.
The powerset of a set with 2 elements has been shown having 04
elements, and no more. (preceding post)
The powerset of a set with 03 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.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 Thu Jul 16 2009 - 15:19:31 PDT