Abstract Algebra: Theory and Applications

Subsection Creating Partially Ordered Sets

Example 19.6 in the text is a good example to replicate as a demonstration of Sage commands. We first define the elements of the set \(X\text{.}\)

One approach to creating the relation is to specify every instance where one element is comparable to the another. So we build a list of pairs, where each pair contains comparable elements, with the lesser one first. This is the set of relations.

We construct the poset by giving the the Poset constructor a list containing the elements and the relations. We can then easily get a “plot” of the poset. Notice the plot just shows the “cover relations” — a minimal set of comparisons which the assumption of transitivity would expand into the set of all the relations.

Another approach to creating a Poset is to let the poset constructor run over all the pairs of elements, and all we do is give the constructor a way to test if two elements are comparable. Our comparison function should expect two elements and then return True or False. A “lambda” function is one way to quickly build such a function. This may be a new idea for you, but mastering lambda functions can be a great convenience. Notice that “lambda” is a word reserved for just this purpose (so, for example, lambda is a bad choice for the name of an eigenvalue of a matrix). There are other ways to make functions in Sage, but a lambda function is quickest when the function is simple.

Sage also has a collection of stock posets. Some are one-shot constructions, while others are members of parameterized families. Use tab-completion on Posets. to see the full list. Here are some examples.

A one-shot construction. Perhaps what you would expect, though there might be other, equally plausible, alternatives.

A parameterized family. This is the classic example where the elements are subsets of a set with \(n\) elements and the relation is “subset of.”

And random posets. These can be useful for testing and experimenting, but are unlikely to exhibit special cases that may be important. You might run the following command many times and vary the second argument, which is a rough upper bound on the probability any two elements are comparable. Remember that the plot only shows the cover relations. The more elements that are comparable, the more “vertically stretched” the plot will be.

Subsection Properties of a Poset

Once you have a poset, what can you do with it? Let's return to our first example, D. We can of course determine if one element is less than another, which is the fundamental structure of a poset.

Notice that 6 and 8 are not comparable in this poset (it is a partial order). The methods .is_gequal() and .is_greater_than() work similarly, but returns True if the first element is greater (or equal).

We can find the largest and smallest elements of a poset. This is a random poset built with a 10%probability, but copied here to be repeatable.

Elements of a poset can be partioned into level sets. In plots of posets, elements at the same level are plotted vertically at the same height. Each level set is obtained by removing all of the previous level sets and then taking the minimal elements of the result.

If we make two elements in R comparable when they had not previously been, this is an extension of R. Consider all possible extensions of one poset — we can make a poset from all of these, where set inclusion is the relation. A linear extension is a maximal element in this poset of posets. Informally, we are adding as many new relations as possible, consistent with the original poset and so that the result is a total order. In other words, there is an ordering of the elements that is consistent with the order in the poset. We can build such a thing, but the output is just a list of the elements in the linear order. A computer scientist would be inclined to call this a “topological sort.”

We can construct subposets by giving a set of elements to induce the new poset. Here we take roughly the “bottom half” of the random poset P by inducing the subposet on a union of some of the level sets.

The dual of a poset retains the same set of elements, but reverses any comparisons.

Taking the dual of the divisibility poset from Example 19.6 would be like changing the relation to “is a multiple of.”

Subsection Lattices

Every lattice is a poset, so all the commands above will perform equally well for a lattice. But how do you create a lattice? Simple — first create a poset and then feed it into the LatticePoset() constructor. But realize that just because you give this constructor a poset, it does not mean a lattice will always come back out. Only if the poset is already a lattice will it get upgraded from a poset to a lattice for Sage's purposes, and you will get a ValueError if the upgrade is not possible. Finally, notice that some of the posets Sage constructs are already recognized as lattices, such as the prototypical BooleanLattice.

An integer composition of \(n\) is a list of positive integers that sum to \(n\text{.}\) A composition \(C_1\) covers a composition \(C_2\) if \(C_2\) can be formed from \(C_1\) by adding consecutive parts. For example, \(C_1 = [2, 1, 2] \succeq [3, 2] = C_2\text{.}\) With this relation, the set of all integer compositions of a fixed integer \(n\) is a poset that is also a lattice.

A meet or a join is a fundamental operation in a lattice.

Once a poset is upgraded to lattice status, then additional commands become available, or the character of their results changes.

An example of the former is the .is_distributive() method.

An example of the latter is the .top() method. What your text calls a largest element and a smallest element of a lattice, Sage calls a top and a bottom. For a poset, .top() and .bottom() may return an element or may not (returning None), but for a lattice it is guaranteed to return exactly one element.

Notice that the returned values are all elements of the lattice, in this case ordered lists of integers summing to \(5\text{.}\)

Complements now make sense in a lattice. The result of the .complements() method is a dictionary that uses elements of the lattice as the keys. We say the dictionary is “indexed” by the elements of the lattice. The result is a list of the complements of the element. We call this the “value” of the key-value pair. (You may know dictionaries as “associative arrays”, but they are really just fancy functions.)

The lattice of integer compositions is a complemented lattice, as we can see by the result that each element has a single (unique) complement, evidenced by the lists of length \(1\) in the values of the dictionary. Or we can just ask Sage via .is_complemented(). Dictionaries have no inherent order, so you may get different output each time you inspect the dictionary.

There are many more commands which apply to posets and lattices, so build a few and use tab-completion liberally to explore. There is more to discover than we can cover in just a single chapter, but you now have the basic tools to profitably study posets and lattices in Sage.