Thursday, November 29, 2012

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.

Monday, November 26, 2012

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.

Thursday, November 15, 2012

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.

Friday, November 2, 2012

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.