We 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 were 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. Lets get started with the fundamentals, starting with how they are created.
The creation of sets
A set is an unordered collection of distinct itemsany 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 doesnt. Thats 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 doesnt matter, Maxima internally keeps them sorted, and hence displayed accordingly, as in the above examples. Also, note the last examplethe 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(). Heres 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});
(%o7)
{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, thats enough about the creation of different varieties of sets. Lets 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 lets 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();
