With the introduction to set theory fundamentals in the previous article in this series, we are all set to explore the advanced realms of set theory through Maxima.
More set operations
We have already worked out the basic set creation techniques and some basic set operations provided by Maxima. Here are some next-level set operations it provides:
- makeset(expr, vars, varslist) -Sophisticated set-creation using expressions
- adjoin(x, S) - Returns a set with all elements of S and the element x
- disjoin(x, S) - Returns a set with all elements S but without element x
- powerset(S) - Returns the set of all subsets of S
- subset(S, p) - Returns the subset of S, elements of which satisfy the predicate p
- symmdifference(S1, S2) - Returns the symmetric difference between the sets S1 and S2, i.e., the elements in S1 or S2 but not in both
And here is a demonstration of each one of these operations:
$ maxima -q
(%i1) makeset(a+b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o1) {3, 5, 7, 9, 11}
(%i2) makeset(a-b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o2) {- 1}
(%i3) makeset(a*b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o3) {2, 6, 12, 20, 30}
(%i4) makeset(a + 2*a*b + b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o4) {7, 17, 31, 49, 71}
(%i5) quit();
$ maxima -q
(%i1) S: {-4, 6, 7, 32, 0};
(%o1) {- 4, 0, 6, 7, 32}
(%i2) adjoin(3, S);
(%o2) {- 4, 0, 3, 6, 7, 32}
(%i3) adjoin(7, S);
(%o3) {- 4, 0, 6, 7, 32}
(%i4) S: adjoin(3, S); /* Updating S */
(%o4) {- 4, 0, 3, 6, 7, 32}
(%i5) adjoin(7, S);
(%o5) {- 4, 0, 3, 6, 7, 32}
(%i6) disjoin(7, S);
(%o6) {- 4, 0, 3, 6, 32}
(%i7) disjoin(5, S);
(%o7) {- 4, 0, 3, 6, 7, 32}
(%i8) quit();
$ maxima -q
(%i1) S: {-4, 0, 3, 6, 7, 32};
(%o1) {- 4, 0, 3, 6, 7, 32}
(%i2) S1: subset(S, evenp);
(%o2) {- 4, 0, 6, 32}
(%i3) powerset(S1);
(%o3) {{}, {- 4}, {- 4, 0}, {- 4, 0, 6}, {- 4, 0, 6, 32}, {- 4, 0, 32}, {- 4, 6}, {- 4, 6, 32}, {- 4, 32}, {0}, {0, 6}, {0, 6, 32}, {0, 32}, {6}, {6, 32}, {32}}
(%i4) S2: {-35, -26, 0, 7, 32, 100};
(%o4) {- 35, - 26, 0, 7, 32, 100}
(%i5) symmdifference(S1, S2);
(%o5) {- 35, - 26, - 4, 6, 7, 100}
(%i6) symmdifference(S, S2);
(%o6) {- 35, - 26, - 4, 3, 6, 100}
(%i7) quit();
Advanced set operations
With Maxima, much more than this can be done with sets, using just the advanced functionalities provided by it. So now, lets take a journey through them.
Cartesian product: Given n sets, the function cartesian_product() returns a set of lists formed by the Cartesian product of the n sets. The following demonstration explains what this means:
$ maxima -q
(%i1) cartesian_product({0, 1, 2}, {a, b, c});
(%o1) {[0, a], [0, b], [0, c], [1, a], [1, b], [1, c], [2, a], [2, b], [2, c]}
(%i2) cartesian_product({0, 1}, {a, b}, {X, Y});
(%o2) {[0, a, X], [0, a, Y], [0, b, X], [0, b, Y], [1, a, X], [1, a, Y], [1, b, X], [1, b, Y]}
(%i3) cartesian_product({0, 1}, {a, b, c});
(%o3) {[0, a], [0, b], [0, c], [1, a], [1, b], [1, c]}
(%i4) quit();
Set partitions: Given a set S, it can be partitioned into various subsets, based on various mathematical principles. Maxima provides a host of functions for such partitioning the basic one being set_partitions(). It returns a set of all possible partitions of the given set. With a number as the second argument, it gives only the partitions with that exact number of sets in each partition. Shown below are some examples to make sense of this concept:
$ maxima -q
(%i1) S: {a, b, c};
(%o1) {a, b, c}
(%i2) set_partitions(S);
(%o2) {{{a}, {b}, {c}}, {{a}, {b, c}}, {{a, b}, {c}}, {{a, b, c}},
{{a, c}, {b}}}
(%i3) set_partitions(S, 1);
(%o3) {{{a, b, c}}}
(%i4) set_partitions(S, 2);
(%o4) {{{a}, {b, c}}, {{a, b}, {c}}, {{a, c}, {b}}}
(%i5) set_partitions(S, 3);
(%o5) {{{a}, {b}, {c}}}
(%i6) set_partitions(S, 4);
(%o6) {}
(%i7) belln(3);
(%o7) 5
(%i8) cardinality(set_partitions(S)); /* Number of elements */
(%o8) 5
(%i9) belln(4);
(%o9) 15
(%i10) belln(5);
(%o10) 52
(%i11) belln(6);
(%o11) 203
(%i12) quit();
In the above examples, belln() or the nth Bell number is the number of partitions of a set with n members.
integer_partitions(n) is a specific function, which partitions a given positive integer n into a set of positive integers, the sum of which adds up to the original integer. num_partitions(n) returns the number of such partitions returned by integer_partitions(n). Examples follow:
$ maxima -q
(%i1) integer_partitions(1);
(%o1) {[1]}
(%i2) num_partitions(1);
(%o2) 1
(%i3) integer_partitions(2);
(%o3) {[1, 1], [2]}
(%i4) num_partitions(2);
(%o4) 2
(%i5) integer_partitions(3);
(%o5) {[1, 1, 1], [2, 1], [3]}
(%i6) num_partitions(3);
(%o6) 3
(%i7) integer_partitions(4);
(%o7) {[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]}
(%i8) num_partitions(4);
(%o8) 5
(%i9) integer_partitions(0);
(%o9) {[]}
(%i10) num_partitions(0);
(%o10) 1
(%i11) integer_partitions(5, 1);
(%o11) {[5]}
(%i12) integer_partitions(5, 2);
(%o12) {[3, 2], [4, 1], [5, 0]}
(%i13) integer_partitions(5, 3);
(%o13) {[2, 2, 1], [3, 1, 1], [3, 2, 0], [4, 1, 0], [5, 0, 0]}
(%i14) integer_partitions(5, 4);
(%o14) {[2, 1, 1, 1], [2, 2, 1, 0], [3, 1, 1, 0], [3, 2, 0, 0], [4, 1, 0, 0], [5, 0, 0, 0]}
(%i15) integer_partitions(5, 5);
(%o15) {[1, 1, 1, 1, 1], [2, 1, 1, 1, 0], [2, 2, 1, 0, 0], [3, 1, 1, 0, 0], [3, 2, 0, 0, 0], [4, 1, 0, 0, 0], [5, 0, 0, 0, 0]}
(%i16) num_partitions(5);
(%o16) 7
(%i17) num_distinct_partitions(5);
(%o17) 3
(%i18) quit();
Note that like set_partitions(), integer_partitions() also takes an optional second argument, limiting the partitions to partitions of cardinality equal to that number. However, note that all smaller-sized partitions are made equal to the corresponding size by adding the required number of zeroes.
Also, num_distinct_partitions(n) returns the number of distinct integer partitions of n, i.e., the integer partitions of n with only distinct integers.
Another powerful partitioning function is equiv_classes(S, r), which returns a partition of S, elements of which satisfy the binary relation r. Here are a few examples:
$ maxima -q
(%i1) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y], remainder(x - y, 2) = 0));
(%o1) {{0, 2, 4, 6, 8, 10}, {1, 3, 5, 7, 9}}
(%i2) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y], remainder(x - y, 3) = 0));
(%o2) {{0, 3, 6, 9}, {1, 4, 7, 10}, {2, 5, 8}}
(%i3) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y], remainder(x - y, 5) = 0));
(%o3) {{0, 5, 10}, {1, 6}, {2, 7}, {3, 8}, {4, 9}}
(%i4) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y], remainder(x - y, 6) = 0));
(%o4) {{0, 6}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {5}}
(%i5) equiv_classes({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y], remainder(x, y) = 0));
(%o5) {{1, 2, 4, 8}, {3, 6}, {5, 10}, {7}, {9}}
(%i6) quit();
Notice the relation being defined using lamda for the property of divisibility by 2, 3, 5, 6, and among the set elements themselves, respectively.
A closely related function partition_set(S, p) partitions S into two sets, one with elements satisfying the predicate p, and the other not satisfying the predicate p. A small demonstration follows:
$ maxima -q
(%i1) partition_set({-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 19, 26, 37, 100}, primep);
(%o1) [{- 1, 0, 1, 4, 6, 8, 9, 10, 26, 100}, {2, 3, 5, 7, 11, 19, 37}]
(%i2) quit();
Miscellaneous: And, finally, lets look at some general but mathematically interesting operations:
- divisors(n) – returns the set of positive divisors of n
- permutations(S) - returns the set of all permutations of the elements of S
- random_permutation(S) - returns one of the elements of permutations(S), randomly
- extremal_subset(S, f, max | min) - returns the subset of S, for which the value of the function f is maximum or minimum
A demonstration of all the functions mentioned above, follows:
$ maxima -q
(%i1) divisors(9);
(%o1) {1, 3, 9}
(%i2) divisors(28);
(%o2) {1, 2, 4, 7, 14, 28}
(%i3) permutations({a, b, c});
(%o3) {[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]}
(%i4) random_permutation({a, b, c});
(%o4) [c, b, a]
(%i5) random_permutation({a, b, c});
(%o5) [c, a, b]
(%i6) random_permutation({a, b, c});
(%o6) [b, c, a]
(%i7) extremal_subset({-5, -3, -1, 0, 1, 2, 3, 4, 5}, lambda([x], x*x), max);
(%o7) {- 5, 5}
(%i8) extremal_subset({-5, -3, -1, 0, 1, 2, 3, 4, 5}, lambda([x], x*x), min);
(%o8) {0}
(%i9) quit();
