Hi Kim, Marty, Johnathan, John, Mirek, and all...

We were studying a bit of elementary set theory to prepare ourself to Cantor's theorem, and then Kleene's theorem, which are keys to a good understanding of the universal numbers, and to Church thesis, which are the keys of the seven steps. I intend to bring you to the comp enlightenment :) But first some revision. Read the following with attention! A set is a collection of things, which in general can themselves be anything. Its use consists in making a many into a one. If something, say x, belongs to a set S, it is usually called "element" of S. We abbreviate this by (x \belongs-to S). Example: A = {1, 2, 56}. A is a set with three elements which are the numbers 1, 2 and 56. We write: (1 \belongs-to {1, 2, 56}), or (1 \belongs-to A), or simply 1 \belongs- to A, when no confusions exist. The parentheses "(" and ")" are just delimiters for easing the reading. I write \belongs-to the relation "belongs to" to remind it is a mathematical symbol. B = {Kim, Marty, Russell, Bruno, George, Jurgen} is a set with 5 elements which are supposed to be humans. C = {34, 54, Paul, {3, 4}} For this one, you may be in need of spectacles. In case of doubt, you can expand it a little bit: C = { 34, 54, Paul, {3, 4} } You see that C is a sort of hybrid set which has 4 elements: - the number 34 - the number 54 - the human person Paul - the set {3, 4} Two key remarks: 1) the number 3 is NOT an element of C. Nor is the number 4 an element of C. 3 and 4 are elements of {3, 4}, which is an element of C. But, generally, elements of elements are not elements! It could happen that element of element are element, like in D = {3, 4, {3, 4}}, the number 3 is both an element of D and element of an element of D ({3, 4}), but this is a special circumstance due to the way D is defined. 2) How do I know that "Paul" is a human, and not a dog. How do I know that "Paul" does not refer just to the string "paul". Obvioulsy the expression "paul" is ambiguous, and will usually be understood only in some context. This will not been a problem because the context will be clear. Actually we will consider only set of numbers, or set of mathematical objects which have already been defined. Here I have use the person Paul just to remind that typically set can have as elements any object you can conceive. What is the set of even prime number strictly bigger than 2. Well, to solve this just recall that ALL prime numbers are odd, except 2. So this set is empty. The empty set { } is the set which has no elements. It plays the role of 0 in the world of sets. We have seen some operations defined on sets. We have seen INTERSECTION, and UNION. The intersection of the two sets S1 = {1, 2, 3} and S2 = {2, 3, 7, 8} will be written (S1 \inter S2), and is equal to the set of elements which belongs to both S1 and S2. We have (S1 \inter S2) = {2, 3} We can define (S1 \inter S2) = {x such-that ((x belongs-to S1) and (x belongs-to S2))} 2 belongs to (S1 \inter S2) because ((2 belongs-to S1) and (2 belongs- to S2)) 8 does not belongs to (S1 \inter S2) because it is false that ((2 belongs-to S1) and (2 belongs-to S2)). Indeed 8 does not belong to S1. Of course some sets can be disjoint, that is, can have an empty intersection: {1, 2, 3} \inter {4, 5, 6} = { }. Similarly we can define (S1 \union S2) by the set of the elements belonging to S1 or belonging to S2: (S1 \union S2) = {x such-that ((x belongs-to S1) or (x belongs-to S2))} We have, with S1 and S2 the same as above (S1 = {1, 2, 3} and S2 = {2, 3, 7, 8}): (S1 \union S2) = {1, 2, 3, 7, 8}. OK. I suggest you reread the preceding post, and let me know in case you have a problem. We have seen also a key relation defined on sets: the relation of inclusion. We say that (A \included-in B) is true when all elements of A are also elements of B. Example: The set of ferocious dogs is included in the set of ferocious animals. The set of even numbers is included in the set of natural numbers. The set {2, 6, 8} is included in the set {2, 3, 4, 5, 6, 7, 8} The set {2, 6, 8} is NOT included in the set {2, 3, 4, 5, 7, 8}. When a set A is included in a set B, A is called a subset of B. We were interested in looking to all subsets of a some set. What are the subsets of {a, b} ? They are { }, {a}, {b}, {a, b}. Why? {a, b} is included in {a, b}. This is obvious. All elements of {a,b} are elements of {a, b}. {a} is included in {a, b}, because all elements of {a} are elements of {a, b} The same for {b}. You see that to verify that a set with n elements is a subset of some set, you have to make n verifications. So, to see that the empty set is a subset of some set, you have to verify 0 things. So the empty set is a subset of any set. proposition: { } is included-in any set. 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} Any question? This was a bit of revision, to let Kim catch up. The sequel will appear asap. Be sure everything is OK, and please, ask question if it is not. You can also ask any question on the first sixth steps of UDA ('course). 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 -~----------~----~----~----~------~----~------~--~---