Monday, January 21, 2013

Monoid action

Given a set $S$ of elements the monoid action on that set is defined by a collection of functions $S \to S$ that are closed under iteration and composition. Places form their own monoid actions on a set because there is a set of endofunctions that we can apply to a place using the zap function that is closed under composition and that includes the identity which doesn't effect that place at all.

Every single place on a set has $n^n$ transformations of the place where $n$ is the size of the place. The full transformation monoid on a set is defined by the operations on the top level place of the set and the trivial monoid is the set of transformations on the empty place.

It is often useful to use group actions on a set rather then monoid actions because the group actions partition the set into a set of orbits. This can be used to enumerate all the group actions on a set which is an invaluable technique in numerous combinatorial problems. We can use this to enumerate permutations, multiset permutations, permutations of a certain cycle type, equivalence relations, and many other combinatorial structures.

Sunday, January 13, 2013

Multiset partitions

Every multiset can be partitioned into a multiset of parts . The mathematical structure of a multisets partition system is determined by the collection of its multiplicities:
{:x 2, :y 2, :z 3}
{2 2, 3 1}
Multiplicity sets of {1 n} describe sets and multiplicity multisets of {n 1} describe additive partitions.

Additive partitions:
Additive partitions are partitions of the multiset {1 n}.
{1 4}, {1 2, 2 1}, {1 3}, {2 2}, {4 1}
Every multiset that contains only a single element has partitions isomorphic to the additive partitions.

Set partitions:
Multisets whose multiplicities are all one can be described as sets:
{:x 1, :y 1, :z 1}
#{#{:x} #{:y :z}}
In Clojure, sets can be described using the pound sign # leaving out the multiplicity values of one.  

Multiplicative partitions:
Every positive integer can be factored into a multiset of prime numbers. The multiplicities multiset of the prime factorization is known as the numbers prime signature.
(= (factors 24) {2 3, 3 1})
Multiplicative partitions can be used to describe association structures in terms of the size of each place in the structure.

Saturday, January 12, 2013

Weak orders

Weak orders are isomorphic to ordered partitions:
(#{0 1} #{2 3} #{4 5 6})
(#{0 1 2} #{3 4 5} #{6 7 8})
Total orders are weak orders with singleton equivalence classes:
(#{0} #{1} #{2} #{3})
Reductions are built out of weak orders with a single well defined maximal element:
(#{0 1 2} #{3})
(#{0 1 2 3} #{4})
We can weakly order the vertices in a binary relation by connectivity, then refine that with degree characteristics, and other vertex invariants, and so on to canonize the relation.

Thursday, January 3, 2013

File structure of my computer algebra system

I now have ten files in my computer algebra system. The organization of my computer algebra system is bound to change as 2013 goes on. places.clj defines place forms which are a partially ordered system, bidirectional variant of functional lenses based upon historical Lisp places such as car and cdr. enums.clj defines enumeration of sets, multisets, integers, rational numbers, and other mathematical structures. adj.clj implements graph theory functions using adjacency matrices and graph canonization.

Abstract algebra:
monoids.clj defines iteration types, monoids, and groups which lays the foundation for lattices.clj and rings.clj. lattices.clj defines partitions with respect to an arbitrary lattice and rings.clj defines polynomials with respect to an arbitrary ring.

Linear algebra:
lin.clj defines linear transformations and gaussian elimination and lodes.clj defines linear ordinary differential operators and other differential equations.

Data structures:
Well enum.clj allows us to define enumerated data structures such as rational numbers and strings, lists.clj allows us to define dynamic lists which associate values with a set of places enumerated by nth. ds.clj defines hashes which associate any set of values with any other set of values without an enumeration for the keys or values.

Tuesday, January 1, 2013

2012 year in review

Most functional programming languages provide functions that convert input arguments into output arguments without any means of converting outputs back to inputs. I have been working on instead building a system of reversible computing.

In 2012 I found two types of reversible functions that are considerably important: place forms and enumerations. Enumerations are bijections that use the natural numbers as inputs and place forms are bijections that like the cons function split up and put together objects. I have a sophisticated system of places in place.clj and enumerations in the enum.clj file.

Lists, which are an essential structure in Lisp, combine both of these two principles by defining data structures that associate values with an enumerated set of places. The nth function enumerates the places of the Lisp list structure.