The Complete Magazine on Open Source

Learn the Concept of Set Theory with Maxima

, / 176 0
Student-reading-booksWe have been experimenting with Maxima, a powerful Computer Algebraic System (CAS) for quite a while now in this series of articles. Maxima is a free and open source project that is continually being developed and improved upon. It evolved from Macsyma, which is now almost defunct. This is the 18th article in this series and it touches upon the fundamentals of  set theory, through Maxima.

Most of you have definitely heard about set theory and may already know quite a bit about sets. Let us then go about getting the maths done by the computer. In this series, we have mostly been picking up mathematical concepts we’re familiar with and then figuring out how we can work with these on the computer, with very little or no programming knowledge. The same holds true for sets. Let’s get started with the fundamentals, starting with how they are created.

The creation of sets
A set is an unordered collection of distinct items—any item, in any order, but unique. An item is commonly referred to as an element. If an item is contained in a set, it is commonly referred to as a member of the set. A set is typically represented by its members enclosed in braces {} and separated by commas. {6, -5, 9, 0}, {dog, cat, donkey, cow, buffalo}, {Kiran, Kasturi, Karan}, and {6, horse, sapphire} are some examples. Notice that the first three sets have related items in them, but the last one doesn’t. That’s perfectly fine. However, if the items in a set have relation(s) or condition(s), the set can also be expressed with that relation(s) or condition(s) mentioned within braces {}. For example, {All human beings younger than 35 years}, {All positive even numbers, All multiples of 3}. In Maxima, we can straight away represent the sets in the first notation, as follows:

$ maxima -q
(%i1) {6, -5, 9, 0};
(%o1)                           {- 5, 0, 6, 9}
(%i2) {dog, cat, donkey, cow, buffalo};
(%o2)                  {buffalo, cat, cow, dog, donkey}
(%i3) {Kiran, Kasturi, Karan};
(%o3)                       {Karan, Kasturi, Kiran}
(%i4) {6, horse, sapphire};
(%o4)                        {6, horse, sapphire}
(%i5) {axe, knife, spear, axe, scissor};
(%o5)                    {axe, knife, scissor, spear}
(%i6) quit();

Note that as the order of items in the set doesn’t matter, Maxima internally keeps them sorted, and hence displayed accordingly, as in the above examples. Also, note the last example—the duplicates are treated as a single item.
Sets can also be created from ordered lists using setify. Members of sets could be expressions, but may not be automatically simplified. Check out the following:

$ maxima -q
(%i1) setify([x, y, z]);
(%o1)                              {x, y, z}
(%i2) [x, y, z, x]; /* Ordered list */
(%o2)                            [x, y, z, x]
(%i3) setify([x, y, z, x]);
(%o3)                              {x, y, z}
(%i4) string({x^2 - 1, (x + 1) * (x -1)});
(%o4)                         {(x-1)*(x+1),x^2-1}

string() has been used in %i4, to just have the output on a single line. But the important thing to note is that though the two items of the list are mathematically identical, they have been preserved as two distinct items and thus do not form a set in the real sense. Such cases can be actually formed into a set by simplifying the individual items of the set using a corresponding simplification function, e.g., rat() for rational expressions. And operating any function on every item of a set can be achieved using map(). Here’s an example to get all those straight, continuing from the above:

(%i5) string(map(rat, {x^2 - 1, (x + 1) * (x -1)}));
(%o5)                               {x^2-1}
(%i6) string(rat((x + 1) * (x -1)));
(%o6)                                x^2-1
(%i7) quit();

%i6 and %o6 shown above are just to demonstrate how rat() works. I know you are still wondering what this weird map() is and how it works. So, here are a few more examples:

$ maxima -q
(%i1) trigreduce(2 * sin(x) * cos(x));
(%o1)                              sin(2 x)
(%i2) {sin(2 * x), 2 * sin(x) * cos(x)};  /* Identical items */
(%o2)                     {2 cos(x) sin(x), sin(2 x)}
(%i3) map(trigreduce, {sin(2 * x), 2 * sin(x) * cos(x)});
(%o3)                             {sin(2 x)}
(%i4) string({apple / fruit + mango / fruit, (apple + mango) / fruit});
(%o4)            {(mango+apple)/fruit, mango/fruit+apple/fruit}
(%i5) string(map(rat, {apple / fruit + mango / fruit, (apple + mango) / fruit}));
(%o5)                        {(mango+apple)/fruit}
(%i6) quit();

In fact, the power of map() lies in its ability to take a function created on-the-fly, using the lambda notation. Here are a few examples to demonstrate lamda() first, and then map() using lambda():

$ maxima -q
(%i1) f: lambda([x], x^3)$
(%i2) f(5);
(%o2)                                 125
(%i3) lambda([x], x^3)(5);
(%o3)                                 125
(%i4) lambda([x, y], x+y)(4, 6);
(%o4)                                 10
(%i5) map(f, {0, 1, 2, 3});
(%o5)                            {0, 1, 8, 27}
(%i6) map(lambda([x], x^3), {0, 1, 2, 3});
(%o6)                            {0, 1, 8, 27}
(%i7) map(lambda([x, y], x+y), {a}, {3});
                              {a + 3}
(%i8) map(lambda([x], x^4), {-2, -1, 0, 1, 2});
(%o8)                            {0, 1, 16}
(%i9) map(g, {-2, -1, 0, 1, 2});
(%o9)                {g(- 2), g(- 1), g(0), g(1), g(2)}
(%i10) quit();

lambda() takes two arguments. First, a list of arguments of the function being defined, and second, the expression for the return value of the function using those arguments. %i1 defines a function ‘f’ with one argument, returning its cube. %i2 calls f(). However, the whole point of using lambda is to use it without defining an explicit function like f(). So, %i3 and %i4 demonstrate exactly that. %i6, %i7 and %i8 show how to use lambda() with map(). Note the elimination of duplicates in %o8. %i9 is another example of map().
Basic set operations
Now, that’s enough about the creation of different varieties of sets. Let’s do some set operations. For starters, the  union of sets is defined as a set with the items of all the sets, the intersection of sets is defined as a set with items common to all the sets, and the difference of two sets is defined as a set with items from the first set, but not in the second set. And here is a demonstration of these concepts:

$ maxima -q
(%i1) union({1, 2}, {1, 3, 4}, {1, 2, 6, 7});
(%o1)                         {1, 2, 3, 4, 6, 7}
%i2) intersection({1, 2}, {1, 3, 4}, {1, 2, 6, 7});
(%o2)                                 {1}
(%i3) setdifference({1, 2}, {1, 3, 4});
(%o3)                                 {2}
(%i4) quit();

Other basic set operations provided by Maxima are:

  • cardinality() – returns the number of distinct items in a set
  • elementp() – checks for an item to be a member of a set
  • emptyp() – checks for the emptiness of a set
  • setequalp() – compares two sets for equality
  • disjointp() – checks for no common items in two sets
  • subsetp() – checks for the first set to be a subset of the second set

The following walk-through demonstrates all of these operations:

$ maxima -q
(%i1) S1: {}$
(%i2) S2: {1, 2, 3}$
(%i3) S3: {3, 1, 5-3}$ /* Same as S2 */
(%i4) S4: {a, b, c}$
(%i5) S5: {2, 1, 2}$
(%i6) cardinality(S1);
(%o6)                                  0
(%i7) cardinality(S2);
(%o7)                                  3
(%i8) cardinality(S3);
(%o8)                                  3
(%i9) cardinality(S4);
(%o9)                                  3
(%i10) cardinality(S5);
(%o10)                                 2
(%i11) elementp(b, S3);
(%o11)                               false
(%i12) elementp(b, S4);
(%o12)                               true
(%i13) emptyp(S1);
(%o13)                               true
(%i14) emptyp(S2);
(%o14)                               false
(%i15) setequalp(S1, S2);
(%o15)                               false
(%i16) setequalp(S2, S3);
(%o16)                               true
(%i17) disjointp(S1, S2);
(%o17)                               true
(%i18) disjointp(S2, S3);
(%o18)                               false
(%i19) disjointp(S3, S4);
(%o19)                               true
(%i20) disjointp(S3, S5);
(%o20)                               false
(%i21) subsetp(S1, S2);
(%o21)                               true
(%i22) subsetp(S2, S3);
(%o22)                               true
(%i23) subsetp(S3, S2);
(%o23)                               true
(%i24) subsetp(S3, S4);
(%o24)                               false
(%i25) subsetp(S5, S3);
(%o25)                               true
(%i26) subsetp(S3, S5);
(%o26)                               false
(%i27) quit();

Playing with set elements
After clearing the fundamentals, mostly through numerical examples, it is now time to have some fun with symbol substitution of Maxima. So let’s play around some more:

$ maxima -q
(%i1) S: {a, b, c, a};
(%o1)                             {a, b, c}
(%i2) S: {a+b, b+c, c+d, d+a};
(%o2)                   {b + a, c + b, d + a, d + c}
(%i3) subst(a=c, S);
(%o3)                          {c + b, d + c}
(%i4) subst([a=c, b=d], S);
(%o4)                              {d + c}
(%i5) subst([a=c, b=d, c=-d], S);
(%o5)                                {0}
(%i6) subst([a=1, b=2, c=-3], S);
(%o6)                       {- 1, 3, d - 3, d + 1}
(%i7) T: {S, {S}};
(%o7)   {{b + a, c + b, d + a, d + c}, {{b + a, c + b, d + a, d + c}}}
(%i8) subst([a=c, b=d, c=-d], T);
(%o8)                            {{0}, {{0}}}
(%i9) subst([a=1, b=2, c=-3], T);
(%o9)         {{- 1, 3, d - 3, d + 1}, {{- 1, 3, d - 3, d + 1}}}
(%i10) quit();