Set theory (review)
P.J. Drongowski
11 September 2004
This review was derived from the sources cited below.
* G. Cantor, German mahematician, 1845-1918
* Cantor's definition: A set S is any collection of objects to be regarded
as a single entity ("perceived as a whole.") The objects are called
"elements" or "members" of set S.
* Membership relation
+ Given a specific object x and a specific set S, it must be possible to
determine if x is a member of S.
+ A unit set consists of a single member, {x}
+ The empty set does not have any members.
+ Two sets are equal if and only if (iff) they have the same members.
+ The membership relation for sets is the principle concept of set theory.
+ Intuitive principle of abstraction: A formula P(x) defines a set S by the
convention that the members of S are exactly those objects s such that
P(s) is a true statement, { x | P(x) }. P is called the "defining
property."
* Inclusion relation
+ If A and B are sets, then A is included in B if and only if each member
of A is a member of B. A is said to be a "subset" of B.
+ If A and B are sets, set A is "properly included" in B if and only if
A is a subset of B and A does not equal B.
+ The subset relation is reflexive and transitive.
+ For sets X and Y, if X is a subset of Y and Y is a subset of X, then
X and Y are equal.
+ the empty set is a subset of every set.
+ The principle of abstraction can be used to define subsets.
* Power set
+ Every non-empty set A has at least two subsets, the empty set and A.
+ The power set of A is the set of all subsets of A. Power(A) is an
abbreviation for { B | B is a subset of A }.
+ If A is a finite set with N members, then the power set of A has
2 to the power of N (2**N) members. Example: If A = {1,2,3} then
Power(A) = { {1,2,3}, {1,2}, {1,3}, {2,3}, {1}, {2}, {3}, empty }
where "empty" denotes the empty set.
+ The subsets of A (above) can be paired with all sequences of 0's and
1's of length 3. This pairing holds for all finite sets.
+ The power set, Power(S), of any set S is a Boolean algebra.
* Operations on sets
+ Venn diagrams
+ The union of sets A and B is the set of all objects which are
members of either A or B.
+ The intersection of sets A and B is the set of all objects which are
members of both A and B.
+ Two sets A and B are disjoint if and only if the intersection of
A and B is the empty set.
+ A collection of sets is a disjoint collection if and only if each
distinct pair of its member sets is disjoint.
+ A partition of a set X is a disjoint collection of nonempty and distinct
subsets of X such that each memeber of X is a member of some (exactly
one) member of the disjoint collection.
+ The absolute complement of a set A is { x | x is not an element of A }.
+ The relative complement of a set A with respect to a set X is
{ x in X | x is not an element of A }. This is notated X - A.
+ The symmetric difference of two sets A and B is the union of
A - B and B - A.
* Relations
+ The cartesian product (X cross Y) of two sets X and Y is the set
of ordered pairs { (x,y) | x is in X and y is in Y }.
+ If rho is a relation and rho is a subset of X cross Y, then rho is
a relation from X to Y.
+ A relation in a set, rho, is an equivalence relation if it is:
- Reflexive: x rho x for all x in X
- Symmetric: x rho y implies y rho x
- Transitive: x rho y and y rho z implies x rho z
* Characteric functions
+ A characteristic function can be assigned to each subset A in S:
e (x) = 1 if x is an element of S
S
e (x) = 0 if x is not an element of S
S
+ Example: Consider the set S = {1,2,3}. The characteric functions of S
make the following assignments:
empty -> (0,0,0)
{1} -> (1,0,0)
{2} -> (0,1,0)
{3} -> (0,0,1)
{1,2} -> (1,1,0)
{1,3} -> (1,0,1)
{2,3} -> (0,1,1)
{1,2,3} -> (1,1,1)
* References:
+ "Sets, Logic and Axiomatic Theories," Robert R. Stoll, W.H. Freeman, 1961
+ "Modern Applied Algebra," G. Birkoff and T.C. Bartee, McGraw-Hill, 1970