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

## Advertising

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