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).


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  

{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  

We say that (A \included-in B) is true when all elements of A are also  
elements of B.

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).



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 
For more options, visit this group at 

Reply via email to