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, 02 and 56.
We write:
(1 \belongs-to {1, 2, 56}), or (1 \belongs-to A), or simply 01 \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 05
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 04 elements:
- the number 34
- the number 54
- the human person Paul
- the set {3, 4}
Two key remarks:
1) the number 03 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 00 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 08 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.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 Tue Jul 14 2009 - 10:40:23 PDT