This nineteenth article of the mathematical journey through open source, explores the advanced set theory concepts through Maxima.
With the introduction to set theory fundamentals in the previous article, 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 ones provided by Maxima:
- 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 goes a demonstration of each one of them:
$ 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, just by the functionalities provided by it. So now, let’s journey through such interesting advance functionalities:
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 it 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 could 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. Examples follow to make sense out of this:
$ 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() – 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 set of positive integers, 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 size partitions are made equal to the corresponding size by adding the required number of zeroes.
Also, num_distinct_partitions(n) returns number of distinct integer partitions of n, i.e. integer partitions of n with only distinct integers.
Another powerful partitioning function is the function equiv_classes(S, r), which returns a partition of S, elements of which satisfy the binary relation r. Here goes 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 2 sets, one with elements satisfying the predicate p, and the other not satisfying the predicate p. 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
An all-together demonstration 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();