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