Finite lattices

I have implemented the means to get the greatest upper bound and lowest upper bound of elements of a finite partial ordering relation. This can be used to completely define finite lattices such as the boolean lattice:

(transform-lattice
 (enum false true)
 (finite-lattice 
  [[0 1]
   [1 1]]))

The partial ordering relation of a set is described by its adjacency matrix. This implies that the lattices module requires the adjacency matrices library as a dependency.

Representations of monoid elements

Using place forms data structures may have different representations with respect to different monoids, for example, with respect to or the false value is equal to nil and the true value is a collection with a single element. Exclusive disjunction uses the same representation except its single generator is an involution rather then an idempotent element:

{false {}
 true {1 1}}

Logical conjunction uses the negation of logical disjunction because these are the two elements of the boolean algebra with two distinct elements. Integers may be represented as the multiplicity of a single generator in an additive monoid, but in a multiplicative monoid they are a multiset with prime numbers as keys and exponents as values:

{1 12}
{2 2, 3 1}

Polynomials also have their on additive and multiplicative representations based upon factorization. The essential point here is that there may be many different representations of a single data structure depending upon the monoid that it is currently being handled by and these representations can be described by place forms.

Collections of monoid elements

All collections can be produced by monoids, for example, the concat operation produces ordered collections:

(= (concat '(1 2 3) '(4 5))
   '(1 2 3 4 5))

Although monoids describe how to build these collections, places are needed in order to describe how to represent them. The nth place is used to describe ordered collections:

(= '(1 2 3)
   {(nth 0) 1
    (nth 1) 2
    (nth 2) 3})

Multisets are produced by commutative monoids, and sets are produced by idempotent commutative monoids. Unordered collections are described by multiplicities. Furthermore, nil represents the empty collection.

(= (list-to-multiset '(1 1 2 3))
   {1 2, 2 1, 3 1})

In partially commutative monoids unordered collections and ordered collections can be combined together to form a partially commutative collection.

Logical operations

The values true and false form a boolean lattice with logical disjunction and logical conjuction as meet and join operators and not as complement: (lattice. #{false true} or and not). This lattice induces the total ordering relation false < true which corresponds to logical implication. There is a dual lattice based upon the ordering relation true < false which uses converse implication.

The disjunction and conjunction operators are commutative monoids with a single non-trivial idempotent element. We can also form abelian groups with a single non-trivial involution element: logical biconditional and exclusive disjunction.

These abelian groups can be extended with a multiplication operation to form the finite field. The logical biconditional uses disjunction as multiplication and the exclusive disjunction uses conjunction as multiplication.

Exponentation has no effect in this finite field, so all polynomials can be reduced to binomials. Using zero as false and one as true all the polynomials in this field can be expressed as 0, 1, x, and x+1.

Local extrema of continuous functions

Reversible continuous functions such as the increment function and the cube function have no extrema and therefore they are either monotone increasing or monotone decreasing on their entire domain. The square function has a single extrema at the origin because it is monotone increasing on the positive numbers and monotone decreasing on the negative numbers.

Local extrema can be determined by the first derivative of a function. For example, polynomials with positive coefficients always have derivative with positive coefficients so they can never have any positive extrema. For example, the exp function we has coefficients that are all positive reciprocals of the factorial numbers, is always reversible on the positive real numbers by the ln function.

Monotone increasing sequences

Monotone increasing functions preserve some ordering relation. In this case, we will consider functions and sequences that are increasing in quantity such as those produced by range:

(= (range 4) '(0 1 2 3))

Ranges are all increasing by one. However, some values may be increasing to an increasing extent. This can be determined by the antireduce function:

(= (antireduce - '(0 1 3 6 10))
   '(0 1 2 3 4))

The triangular numbers are produced by additively reducing over the range and tetrahedral numbers are produced by using the same process on the triangular numbers. The fibonanci numbers are the additive reductions of themselves. Furthermore, the factorial function is produced by the multiplication reduction over the range.

Ordering relations

The nodes a preorder can be partitioned into sets of equivalence classes such that for any ordered pair of nodes in an equivalence class there is a path between the two nodes. Every preorder is determined up to isomorphism by a partial ordering of its equivalence classes. Here are several types of preorder relations:

• Equivance relation: the partial ordering relation is empty
• Partial order: every equivalence class is trivial

If the partial ordering relation doesn't contain any undirected cycles that are greater then size two then it forms a tree. It is relatively easy to canonize directed trees and equivalence relations up to isomorphism by describing their shape. However, canonizing ordering relations that contain oriented cycles like the reachability partial order on {A -> B, A -> C, B -> D, C -> D} is a relatively complicated process.

Every relation has a reachability relation associated with it that preorders all nodes in terms of rather or not there is a path between them. Functions have a reachability relation between elements that is a tree of equivalence classes, and since permutations are the union of disjoint cycles their reachability relation is an equivalence relation.