Next: Functions and Variables for Sets, Previous: Sets, Up: Sets [Contents][Index]

### 35.1 Introduction to Sets

Maxima provides set functions, such as intersection and union, for finite sets that are defined by explicit enumeration. Maxima 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.

In addition to functions for finite sets, Maxima provides some functions related to combinatorics; these include the Stirling numbers of the first and second kind, the Bell numbers, multinomial coefficients, partitions of nonnegative integers, and a few others. Maxima also defines a Kronecker delta function.

#### 35.1.1 Usage

To construct a set with members `a_1, ..., a_n`, write `set(a_1, ..., a_n)` or `{a_1, ..., a_n}`; to construct the empty set, write `set()` or `{}`. In input, `set(...)` and `{ ... }` are equivalent. Sets are always displayed with curly braces.

If a member is listed more than once, simplification eliminates the redundant member.

    (%i1) set();
    (%o1)                          {}
    (%i2) set(a, b, a);
    (%o2)                        {a, b}
    (%i3) set(a, set(b));
    (%o3)                       {a, {b}}
    (%i4) set(a, [b]);
    (%o4)                       {a, [b]}
    (%i5) {};
    (%o5)                          {}
    (%i6) {a, b, a};
    (%o6)                        {a, b}
    (%i7) {a, {b}};
    (%o7)                       {a, {b}}
    (%i8) {a, [b]};
    (%o8)                       {a, [b]}

Two would-be elements x and y are redundant (i.e., considered the same for the purpose of set construction) if and only if `is(x = y)` yields `true`. Note that `is(equal(x, y))` can yield `true` while `is(x = y)` yields `false`; in that case the elements x and y are considered distinct.

    (%i1) x: a/c + b/c;
                                  b   a
    (%o1)                         - + -
                                  c   c
    (%i2) y: a/c + b/c;
                                  b   a
    (%o2)                         - + -
                                  c   c
    (%i3) z: (a + b)/c;
                                  b + a
    (%o3)                         -----
                                    c
    (%i4) is (x = y);
    (%o4)                         true
    (%i5) is (y = z);
    (%o5)                         false
    (%i6) is (equal (y, z));
    (%o6)                         true
    (%i7) y - z;
                               b + a   b   a
    (%o7)                    - ----- + - + -
                                 c     c   c
    (%i8) ratsimp (%);
    (%o8)                           0
    (%i9) {x, y, z};
                              b + a  b   a
    (%o9)                    {-----, - + -}
                                c    c   c

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

    (%i1) setify ([b, a]);
    (%o1)                        {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,

    (%i1) {x, rat(x)};
    (%o1)                          {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

    (%i1) {(x - 1)*(x + 1), x^2 - 1};
                                           2
    (%o1)               {(x - 1) (x + 1), x  - 1}

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

    (%i1) {(x - 1)*(x + 1), x^2 - 1};
                                           2
    (%o1)               {(x - 1) (x + 1), x  - 1}
    (%i2) map (rat, %);
                                  2
    (%o2)/R/                    {x  - 1}

To remove redundancies from other sets, you may need to use other simplification functions. Here is an example that uses `trigsimp`:

    (%i1) {1, cos(x)^2 + sin(x)^2};
                                2         2
    (%o1)                {1, sin (x) + cos (x)}
    (%i2) map (trigsimp, %);
    (%o2)                          {1}

A set is simplified when its members are non-redundant and sorted. The current version of the set functions uses the Maxima function `orderlessp` to order sets; however, future versions of the set functions might use a different ordering function.

Some operations on sets, such as substitution, automatically force a re-simplification; for example,

    (%i1) s: {a, b, c}$
    (%i2) subst (c=a, s);
    (%o2)                        {a, b}
    (%i3) subst ([a=x, b=x, c=x], s);
    (%o3)                          {x}
    (%i4) map (lambda ([x], x^2), set (-1, 0, 1));
    (%o4)                        {0, 1}

Maxima treats lists and sets as distinct objects; functions such as `union` and `intersection` complain if any argument is not a set. If you need to apply a set function to a list, use the `setify` function to convert it to a set. Thus

    (%i1) union ([1, 2], {a, b});
    Function union expects a set, instead found [1,2]
     -- an error.  Quitting.  To debug this try debugmode(true);
    (%i2) union (setify ([1, 2]), {a, b});
    (%o2)                     {1, 2, a, b}

To extract all set elements of a set `s` that satisfy a predicate `f`, use `subset(s, f)`. (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

    (%i1) subset ({x + y + z, x - y + 4, x + y - 5},
                                        lambda ([e], freeof (z, e)));
    (%o1)               {- y + x + 4, y + x - 5}

The section Functions and Variables for Sets has a complete list of the set functions in Maxima.

Categories: Sets ·

#### 35.1.2 Set Member Iteration

There two ways to to iterate over set members. One way is the use `map`; for example:

    (%i1) map (f, {a, b, c});
    (%o1)                  {f(a), f(b), f(c)}

The other way is to use `for x in s do`

    (%i1) s: {a, b, c};
    (%o1)                       {a, b, c}
    (%i2) for si in s do print (concat (si, 1));
    a1
    b1
    c1
    (%o2)                         done

The Maxima functions `first` and `rest` work correctly on sets. Applied to a set, `first` returns the first displayed element of a set; which element that is may be implementation-dependent. If `s` is a set, then `rest(s)` is equivalent to `disjoin(first(s), s)`. Currently, there are other Maxima functions that work correctly on sets. In future versions of the set functions, `first` and `rest` may function differently or not at all.

Maxima’s `orderless` and `ordergreat` mechanisms are incompatible with the set functions. If you need to use either `orderless` or `ordergreat`, call those functions before constructing any sets, and do not call `unorder`.

#### 35.1.3 Authors

Stavros Macrakis of Cambridge, Massachusetts and Barton Willis of the University of Nebraska at Kearney (UNK) wrote the Maxima set functions and their documentation.

Next: Functions and Variables for Sets, Previous: Sets, Up: Sets [Contents][Index]