archive/share/trash/set.usg

   1
   2
   3 a SET THEORY package for MACSYMA
   4 ================================
   5
   6
   7 The file  SET FASL DSK SHARE2 provides
   8 Macsyma with the basic primitives  of set theory.
   9
  10
  11 For our purposes, we define a set to be a sorted irredundant list.
  12
  13 Thus [2,3,x,1] is not a set since it isn't sorted
  14 and [2,3,x,x,y] is not a set since it has a redundancy,
  15 however [1,2,3,x] and [2,3,x,y] are sets.
  16
  17 Here is a list of the functions provided:
  18
  19 INTERSECT UNION
  20 COMPLEMENT SETDIFFERENCE SYMMDIFFERENCE
  21 POWERSET
  22 SETIFY SUBSET
  23 SETP SUBSETP DISJOINTP
  24
  25 The functions above are mostly self-explanatory,
  26 so the following brief descriptions should be sufficient:
  27
  28
  29 INTERSECT(A,B) returns the intersection of A and B.
  30
  31 UNION(A,B) returns the union of A and B.
  32
  33 COMPLEMENT(A,B) returns the relative complement of A in B,
  34   That is, the set of elements of B which are not in A.
  35
  36 SETDIFFERENCE(A,B) returns the set of elements of A which are not in B.
  37   Note that SETDIFFERENCE(A,B) is just COMPLEMENT(B,A).
  38
  39 SYMMDIFFERENCE(A,B) returns the symmetric differrence of A and B,
  40   which is equal to UNION(SETDIFFERENCE(A,B),SETDIFFERENCE(B,A)).
  41
  42 POWERSET(S) returns the set of all subsets of S.
  43
  44 SETIFY(L) converts the list L to a set.
  45   For example  SETIFY([2,x,2,3,8,x]) yields [2,3,8,x].
  46
  47 SUBSET(A,F) returns the set of elements of A which satisfy the condition F.
  48   For example  SUBSET([1,2,x,x+y,z,x+y+z],atom) yields [1,2,z].
  49   The argument F should be a function of one argument
  50   which returns TRUE or FALSE. Another  example:
  51   SUBSET([1,2,7,8,9,14],evenp) yields [2,8,14].
  52
  53
  54 SETP(L) returns TRUE if L is a set, FALSE otherwise.
  55
  56
  57 SUBSETP(A,B) decides whether or not A is a subset of B
  58   and returns TRUE or FALSE accordingly.
  59
  60 DISJOINTP(A,B) decides whether A and B are disjoint
  61   (have no common elements) and returns TRUE or FALSE accordingly.
  62
  63
  64 ============
  65
  66 Remarks:
  67
  68
  69 1. We reemphasize that a set is a list.
  70    Thus the notation for both input and output
  71    is  [ ... ]  rather than  { ... } .
  72    We feel that this ambiguity is desirable.  It allows
  73    list processing on sets and set processing on lists
  74    without conversion.
  75
  76 2. However, not every list is a set.
  77    A set must satisfy two additional conditions. It must be
  78              (1) sorted
  79              (2) irredundant.
  80    Implied is a notion of order and a notion of equivalence.
  81    We choose order as the fundamental notion.
  82    The user can specify an order by resetting the value of CANONLT.
  83    Initially, CANONLT has the value ORDERLESSP which is Macsyma's
  84    canonical order. The value of CANONLT must be a strict total
  85    preorder (a function of 2 arguments which returns true or false
  86    and such that the associated relation is transitive an irreflexive).
  87    It need not be universally well-defined so long as it is
  88    well-defined for the arguments it receives. The notion of
  89    equivalence is derived from the order notion by the
  90    familiar law of trichotomy:
  91    Given objects a,b we require that exactly one of the following holds:
  92              (1) a is less than b
  93              (2) b is less than a
  94              (3) a and b are equivalent
  95    Note that equivalence is, in general, weaker than equality.
  96
  97
  98 3. Consider the following example:
  99      In a Macsyma suppose we define a function h by:
 100           h(n):=for i do if n=(2^i)*ENTIER(n/(2^i)) then return(i-1);
 101      Thus h returns the largest positive integer e such that
 102      n is divisible by 2^e (n is assumed to be a positive integer).
 103
 104      Next define an order function f by:
 105           f(a,b):=is( h(a) < h(b) );
 106      For example, with this order, 9 is less than 2
 107      and 6 is equivalent to 10.
 108
 109      Next we set CANONLT by:
 110            CANONLT:f;
 111
 112      Then all functions in the SET package will
 113      return sort and eliminate redundancies (equivalences)
 114      using the function f.
 115
 116      For example, SETIFY([6,20,2,9,8,12]) returns [9,2,12,8].
 117
 118
 119 4. As mentioned above the default value of CANONLT
 120    is ORDERLESSP. It follows that the default notion of
 121    equivalence is equality.
 122
 123
 124 5. The functions UNION and INTERSECT can take any
 125    number of arguments.
 126
 127
 128 6. The arguments to functions in the SET package
 129    need not be sets - arbitrary lists are OK
 130    (i.e. possibly unsorted and/or redundant).
 131
 132    Thus, functions such as INTERSECT
 133    accept arbitrary lists  but always return a set.
 134    For example,
 135        INTERSECT([2,3,2,y,x],[2,z,y,y]) yields [2,y].
 136
 137
 138 =============
 139
 140
 141          -- David A. Spear    (DAS),    (1-21-78)