Untitled Document


Introduction to Finite Sets

The nset package provides set functions, such as intersection and union, for finite sets that are defined by explicit enumeration. Unlike the package set in Maxima's share library, nset treats lists and sets as distinct objects. This feature makes it possible to work with sets that have members that are either lists or sets.

Installation

Download the archive nset-x.tar.gz, where x is the release identifier, from http://www.unk.edu/acad/math/people/willisb. Under Linux, unpack it using

gzip -d nset-x.tar.gz

tar -xvf nset-x.tar

This will create a directory nset-x (again x is the release identifier) that contains the source file nset.lisp, user documentation in html and texi formats, a sample maxima initialization file nset-init.lisp, a README file, and a testing routine test-nset.mac.

Copy nset.lisp to a directory that Maxima can find. A good location is the same directory that contains set.lisp. Under Maxima release 5.9.0 or higher for Linux, set.lisp is in the directory

/usr/local/share/maxima/<ver>/share/misc/set.lisp

where <ver> is your Maxima release identifier. If you don't have write permission for this directory, or if you want to install nset.lisp in a different location, that is fine as long as you place it in a directory that Maxima can find.

For increased speed, you can compile nset.lisp. To do this, start Maxima in the nset-x directory and issue the command

(C1) compile_file("nset.lisp")$

This will create a file nset.xxx in the nset-x directory. The file extension xxx depends on which Lisp your Maxima uses; under gcl, the extension is "o". Copy the compiled file to the same directory where you put nset.lisp.

If you are using Maxima version 5.9.0 or higher, finish the installation by appending the contents of nset-init.lisp to your own maxima-init.lisp file. The Lisp file nset-init.lisp contains replacements for the Maxima functions setup_autoload and generic_autoload. Unlike Maxima's setup_autload function, the version in nset-init.lisp uses file_search. Without this change, a full pathname must be given to setup_autload. The autoload function in Maxima 5.9.0 and lower does not recognize some file extensions, such as .x86f and .fasl, as valid extensions for compiled code. The version of generic_autoload in nset-init fixes this problem. Additionally, nset-init.lisp contains the command

(add2lnc '$set $props)

This command appends "set" to Maxima's prop list; finally, the setup_autoload command contained in nset-init.lisp makes nset load automatically whenever you enter an expression containing a function from nset.

Maxima versions prior to 5.9.0 do not support initialization files. You may still use nset under these versions of Maxima; you must, however, manually load nset.lisp before you use any functions (especially the set function) that are in nset.

Usage

To use the set functions, begin by loading nset. Provided you have installed the package correctly, load it with the command

(C1) load("nset")$

If Maxima is unable to find nset, use its full pathname. If you have included an autoload statement for all functions in nset in your maxima-init.lisp file, you will not have to manually load nset.

To construct a set with members a1,a2,...,an, use the command set(a1,a2,...,an); to construct the empty set, use set(). If a set member is listed more than once, the simplification processes eliminates the redundant member.

(C1) set();
(D1) 				      {}
(C2) set(a,b,a);
(D2) 				    {a, b}
(C3) set(a,set(b));
(D3) 				   {a, {b}}
(C4) set(a,[b]);
(D4) 				   {a, [b]}

Sets are displayed as brace delimited lists; it isn't possible, however, to define a set by enclosing its members in braces.

To construct a set from the elements of a list, use setify

(C4) setify([b,a]);
(D4) 		     {a,b}

Set members x and y are equal provided is(x = y) evaluates to true. Thus rat(x) and x are equal as set members; consequently,

(C1) set(x,rat(x));
(D1) 				      {x}

Further, since is((x-1)*(x+1) = x^2 - 1) evaluates to false, (x-1)*(x+1) and x^2-1 are distinct set members; thus

(C2) set((x-1)*(x+1),x^2-1);
					      2
(D2) 			   {(x - 1) (x + 1), x  - 1}

To reduce this set to a singleton set, apply rat to each set member

(C3) map(rat,%);
				     2
(D3) 				   {x  - 1}

A set is simplified when its members are non-redundant and sorted according to the Maxima predicate orderlessp. (The only way to change the set ordering is to modify the source code to nset.) Some operations on sets, such as substitution, automatically force a re-simplification; for example,

(C1) s : set(a,b,c)$
(C2) subst(c=a,s);
(D2) 				    {a, b}
(C3) ev(s,a=x,b=x,c=x);
(D3) 				      {x}
(C4) map(lambda([x],x^2),set(-1,0,1));
(D4) 				    {0, 1}

Most functions in nset work either sets or lists; when the function receives a list, but needs a set, the list is automatically converted to a set. Here are some examples that use the set functions setdifference, intersect, and union

(C1) intersect([a,a,b],set(b,c));
(D1) 				      {b}
(C2) setdifference([3,1,4,1,6],[3]);
(D2) 				   {1, 4, 6}
(C3) union([a,b,b],[c,d],set(e,f));
(D3) 			      {a, b, c, d, e, f}

To extract all set elements of a set s that satisfy a predicate f, use subset(s,f). (In Maxima, a predicate is a boolean-valued function.) For example, to find the equations in a given set that do not depend on a variable z, use

(C1) subset([x+y+z,x-y+4,x+y-5],lambda([e],freeof(z,e)));
(D1) 			   {- y + x + 4, y + x - 5}

The section Definitions for Sets has a complete list of the functions in nset

Miscellaneous Functions

The nset package contains the miscellaneous utility functions dupe, flatten, permutations, and a few others.

Bugs

The nset package uses the Maxima function orderlessp to order set members and the (Lisp-level) function like to test for set member equality. Both of these functions have known bugs (versions 5.9.0rc3 and earlier) that may manifest if you attempt to use sets with members that are lists or matrices that contain expressions in CRE form. An example is

(C1) set([x],[rat(x)]);

This command causes Maxima to halt with an error (the error message depends on which version of Lisp your Maxima uses). Another example is

(C2) setify([[rat(a)],[rat(b)]]);

These bugs are caused by bugs in orderlessp and like; they are not caused by bugs in nset. To illustrate, try the commands

(C1) orderlessp([rat(a)],[rat(b)]);
(C2) is([rat(a)]=[rat(a)]);

Until these bugs are fixed, do not construct sets with members that are lists or matrices containing expressions in CRE form; a set with a member in CRE form, however, shouldn't be a problem

(C1) set(x,rat(x));
(D1)/R/ 			      {x}

There are two other minor bugs that may manifest while using nset. Maxima versions 5.5 and earlier had a bug in the tex function that makes the empty set incorrectly translate to TeX; this bug is fixed in the Maxima 5.9.0. Additionally, the setup_autoload function in Maxima 5.9.0 is broken; a fix is in the nset-init.lisp file located in the nset distribution.

If you find something that you think might be a nset bug, please report it to the authors or to the Maxima mailing list.

Future Projects

A ambitious project would be adding support for sets (possibly infinite) with membership determined by a rule; for example

{x in reals | x = n %pi and n in integers}.

Maxima's solver package, as well as others, could be improved by making use of sets like these. A somewhat less ambitious project would be to support symbolic sets and to add rules, such as

union(a,a) => a,

intersect(a,a) => a,

intersect(a, union(a,b)) => a,

for simplifying set functions on symbolic sets.

Authors

Barton Willis of the University of Nebraska at Kearney (UNK) and Stavros Macrakis wrote the nset package and its documentation.

Definitions for Sets

Function: adjoin (x, a)

Adjoin x to the set a and return a set. Thus adjoin(x,a) and union(set(x),a) are equivalent; however, using adjoin might be faster. If a isn't a list or a set, signal an error.

(C1) adjoin(c,set(a,b));
(D1) 				   {a, b, c}
(C2) adjoin(a,set(a,b));
(D2) 				    {a, b}

Function: cardinality (a)

Return the number of distinct elements of the set a.

(C1) cardinality(set());
(D1) 				       0
(C2) cardinality(set(a,a,b,c));
(D2) 				       3
(C3) cardinality(set(a,a,b,c)), simp : false;
(D3) 				       3

In line (c3), we see that cardinality works correctly even when simplification has been turned off. Like most functions in nset, the argument to cardinality may either be a list or a set; when the argument is a list, cardinality still returns the number of distinct elements of the list; for example,

(C4) cardinality([a,a,b,c]);
(D4) 				       3

Function: cartesian_product (a, b1, b2, ... , bn)
Return a set of lists of the form [x0,x1,...,xn], where x0 in a, x1 in b1, ..., and xn in bn. Signal an error when a or any b isn't a list or a set.
(C1) cartesian_product(set(0,1));
(D1) 				  {[0], [1]}
(C2) cartesian_product(set(0,1),set(0,1));
(D2) 		       {[0, 0], [0, 1], [1, 0], [1, 1]}
(C3) cartesian_product(set(x),set(y),set(z));
(D3) 				  {[x, y, z]}
(C4) cartesian_product(set(x),set(-1,0,1));
(D4) 			  {[x, - 1], [x, 0], [x, 1]}

Function: complement (a,b)
Return the set of the elements in b that are not in a. Signal an error if either a or b isn't a list or a set. Notice that complement(a,b) = setdifference(b,a). See also setdifference.

Function: disjointp (a, b)
Return true if the sets a and b are disjoint. Signal an error is either a or b isn't a list or a set.
Function: dupe (e,n)
Return the n element list [e,e,...,e]; signal an error if n isn't a nonnegative integer.
Function: elementp (x, a)
Return true if and only if x is a member of the set a. Signal an error if a isn't a list or a set.

Function: equiv_classes (s,f)
Return a set of the equivalence classes of s with respect to the equivalence relation f. The function f should be a boolean-valued function defined on the cartesian product of s with s. Further, the function f should be an equivalence relation; equiv_classes, however, doesn't check that it is.
(C1) equiv_classes(set(a,b,c),lambda([x,y],is(x=y)));
(D1) 			        {{a}, {b}, {c}}

Actually, equiv_classes(s,f) automatically applies the Maxima function is after applying the function f; accordingly, we can re-work the previous example with the command

(C2) equiv_classes(set(a,b,c),"=");
(D2) 			        {{a}, {b}, {c}}

Here is another example

(C3) equiv_classes(set(1,2,3,4,5,6,7),lambda([x,y],remainder(x-y,3)=0));
(D3) 			  {{1, 4, 7}, {2, 5}, {3, 6}}

Function: extremal_subset (s,f,{min})
Return the subset of the set or list s for which the real-valued function f takes on its greatest value. Given an optional third argument, return the subset for which f takes on its least value.
(C1) extremal_subset(set(-2,-1,0,1,2),abs);
(D1) 				   {- 2, 2}
(C3) extremal_subset(set(sqrt(2), 1.57, %pi/2),sin);
				      %PI
(D3) 				     {---}
				       2

To find the minimizing subset, give the optional third argument a value

(C2) extremal_subset(set(-2,-1,0,1,2),abs, min);
(D2) 				      {0}

Function: flatten (e)
Flatten essentially evaluates an expression as if its main operator had been declared nary; there is, however, one difference -- flatten doesn't recurse into other function arguments. Consider

 (C2) flatten(f(g(f(f(x)))));
 (D2)         f(g(f(f(x))))
 (C3) declare(f,nary);
 (D3)         DONE
 (C4) ev(d2);
 (D4)         f(g(f(x)))

Applied to a set, flatten gathers all members of set elements that are sets; for example

(C1) flatten(set(a, set(b), set(set(c))));
(D1) 				   {a, b, c}
(C2) flatten(set(a,set([a],set(a))));
(D2) 				   {a, [a]}

Flatten works correctly when the main operator is a subscripted function

(C3) flatten(f[5](f[5](x)));

(D3) 				     f (x)
				      5

To successfully flatten an expression, the main operator must be defined for zero or more arguments; if this isn't the case, Maxima can halt with an error.

Function: full_listify (a)
Convert every set in the expression a into a list. To convert just the top-level operator of a set to a list, see listify.

Function: fullsetify (a)
If a is a list, convert a to a set and apply fullsetify to each set member.
(C1) fullsetify([a,[a]]);
(D1) 				   {a, {a}}
(C2) fullsetify([a,f([b])]);
(D2) 				  {a, f([b])}
(C3) 

In line (C2), the argument of f isn't converted to a set because the main operator of f([b]) isn't a list.

To convert just the top-level operator of a list to a set, see setify.

Function: intersect (a1,a2,...,an)
Return a set containing the elements that are common to the sets a1 through an. The function intersect must receive one or more arguments. Signal an error if any of a1 through an isn't a list or a set. See also intersection.

Function: intersection (a1,a2,...,an)
Return a set containing the elements that are common to the sets a1 through an. The function intersection must receive one or more arguments. Signal an error if any of a1 through an isn't a list or a set. See also intersect.

Function: listify (a)
If a is a set, return a list containing the members of a; when a isn't a set, return a. To convert a set and all of its members to lists, see full_listify


Function: partition_set (a,f)
Return a list of two sets; the first set is the subset of a for which the predicate f evaluates to false and the second is the subset of a for which f evaluates to true. If a isn't a list or a set, signal an error. See also subset.
(C1)  partition_set(set(2,7,1,8,2,8),evenp);
(D1) 			       [{1, 7}, {2, 8}]
(C2) partition_set(set(x,rat(y),rat(y)+z,1),lambda([x], ratp(x)));
(D2)/R/ 		     [{1, x}, {y, y + z}]

Function: permutations (a)
Return a set of all distinct permutations of the members of the list or set a. (Each permutation is a list, not a set.) When a is a list, duplicate members of a are not deleted before finding the permutations. Thus
(C1) permutations([a,a]);
(D1) 				   {[a, a]}
(C2) permutations([a,a,b]);
(D2) 		       {[a, a, b], [a, b, a], [b, a, a]}
(C3) 

If a isn't a list or set, signal an error.

Function: powerset (a)
Return the set of all subsets of the set a. If a has n elements, powerset(a) has 2^n members. Signal an error if a isn't a list or a set. See also subpowerset.

Function: setdifference (a,b)
Return a set containing the elements in the set a that are not in the set b. Signal an error if a or b aren't sets. See also complement.

Function: setequality (a,b)
Return true if and only if a and b are equal sets. Signal an error if a or b aren't sets.

Function: setify (a)
Construct a set from the elements of the list a. Duplicate elements of the list a are deleted and the elements are sorted according to the predicate orderlessp. Signal an error if a isn't a list.

Function: setp (a)
Return true if and only if a is a Maxima set. The function setp checks that the operator of its argument is set; it doesn't check that its argument is a simplified set. Thus
(C1) setp(set(a,a)),simp : false;
(D1) 				     TRUE

The function setp could be coded in Maxima as

setp(a) := is(inpart(a) = set).

Function: subpowerset (a,n)
Return the set of all subsets of the set a that have cardinality n; signal an error if n isn't a nonnegative integer or if a isn't a list or a set. See also powerset.

Function: subset (a, f)
Return the subset of the set a that satisfies the predicate f. For example
(C1) subset(set(1,2,x,x+y,z,x+y+z),atom);
(D1) {1,2,z}
(C2) subset(set(1,2,7,8,9,14),evenp);
(D2) {2,8,14}

The second argument to subset must be a Maxima predicate (a boolean-valued function of one argument) if the first argument to subset isn't a list or a set, signal an error. See also partition_set.

Function: subsetp (a, b)
Return true if and only if the set a is a subset of b. Signal an error if a or b aren't lists or sets.

Function: symmdifference (a,b)
Return the symmetric difference of sets a and b. This is the same as union(setdifference(a,b),setdifference(b,a)). Signal an error if a or b aren't lists or sets.

Function: union (a1,a2, ..., an)
Return the union of the sets a1 through an. When union receives no arguments, it returns the empty set. Signal an error when one or more arguments to union is not a list or a set.


This document was generated on 19 December 2002 using the texi2html translator version 1.51a.