- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Thu, 16 Jul 2009 15:19:31 +0200

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

Date: Thu, 16 Jul 2009 15:19:31 +0200

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

<snip>

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:16 PST
*