Saturday, August 31, 2013

Filling in lists with gaps

As I've mentioned before I believe it is useful to be able to specify lists and other related structures using only selected slots like so:
{third 3, fourth 4}
{first 1, second 2, fourth 4}
This naturally leads to a notion of lists with gaps. The gaps of a list are precisely those slots that aren't presently provided with any value. If a list has gaps it naturally follows that we can provide a function to fill in some of those gaps:
(fillin dup? [1 2 nil nil]) ;-> (1 2 1 2)
(fillin dup? [nil 20 10 nil]) ;-> (10 20 10 20)
The idea of the fillin function is to use conditional functional dependencies to fill in any slots of an element of a relation with their necessary values if such values exist. Gaps without necessary values are unaffected. This can be also be used on general lists with a predicate like palindrome?:
(fillin palindrome? [1 2 3 nil nil nil]) ;-> (1 2 3 3 2 1)
(fillin palindrome? [nil 20 30 nil 10]) ;-> (10 20 30 20 10)
The fillin function over this palindrome? predicate can even be used to reverse a list as demonstrated above. My current thinking is that it would be nice to have a relational lisp that has first class support for lists with gaps but that would probably require that I abandon the most popular lisps which is not something I am ready to do.

Thursday, August 29, 2013

Oriented set systems

Every set of elements such as #{0 1 2 3 4} has a power set which contains all of its subsets whose own subsets form set systems such as the following set:
#{#{0 2} #{0 3} #{0 4} #{1 2} #{1 3} #{1 4}}
Associated with every set system is the notion of a section subsystem corresponding to some subset of the underlying set of the set system. The section subsystem of #{0 1 2 3} for the above set system is:
#{#{0 2} #{0 3} #{1 2} #{1 3}}
Things get to be a bit more interesting once we introduce the idea of an oriented set system which is simply a set system whose every set is associated with some collection of values:
(= (orientation-form #{[0 1] [1 2] [2 0]})
   {#{0 2} #{[2 0]}, #{1 2} #{[1 2]}, #{0 1} #{[0 1]}})
Every oriented set system has oriented section subsystems associated with it corresponding to the section subsystems of its underlying set system. From this we see that the notion of an induced subrelation is isomorphic to the notion of a section subsystem of an oriented set system. If we want to define some notion of subsystems of a transformation system on a set then an obvious option is to use stabilizing set systems:
(= (orientation-form #{[0 1 2 3] [1 0 2 3] [0 1 3 2] [1 0 3 2]})
   {#{} #{()}, 
    #{0 1} #{((1 0)}, 
    #{2 3} #{((2 3)}, 
    #{0 1 2 3}, #{((0 1) (2 3))})
This orientation form for transformation systems such as permutation groups allows us to reason about induced substructures for them as well. We can also represent measures as oriented set systems in the obvious way:
{#{} 0,#{0} 1, #{1} 1, #{0 1} 2}
However, for dealing with structures such as rings that have multiple relations such as addition and multiplication that we need to consider then it is useful to represent such structures as a sort of relation:
#{(:add 0 0 0),(:add 0 1 1), (:add 1 0 1), (:add 1 1 0)
(:mul 0 0 0),(:mul 0 1 0), (:mul 1 0 0), (:mul 1 1 1)}
Using this same technique we can produce an oriented set system for rings such as the field of size two displayed above:
#{#{0} #{(:add 0 0 0)}, 
  #{1} #{(:mul 0 0 0)}, 
  #{0 1} #{(:add 0 1 1), (:add 1 0 1), (:add 1 1 0),
           (:mul 0 1 0), (:mul 1 0 0), (:mul 1 1 1)}}
As we have demonstrated so far oriented set systems allow us to describe the induced substructures of N-ary relations, hypergraphs, transformation systems, semirings, measure spaces, topologies, and a wide variety of other structures. Well this is a pretty extensive approach to substructures sometimes we want to get a family of substructures such as for set systems:
#{#{0 1 2} #{2 3 4} #{4 5 6}}
#{#{1 2} #{2 3}}
Even though the set system #{#{0 1 2} #{2 3 4} #{4 5 6}} does not contain #{1 2} or #{2 3} as elements it produces them as substructures. In this case it may be useful to distinguish this system as a higher set system:
#{#{0 1 2} #{2 3 4} #{4 5 6}}
#{#{#{0} #{1} #{2}} #{#{2} #{3} #{4}} #{#{4} #{5} #{6}}}
I am not currently familiar with any notion of induced substructures that cannot be described by an oriented higher set system.

Tuesday, August 27, 2013

Properties of elements of posets

There are a variety of properties specific to elements of a partial order. Any combination of these properties can be used to define a weak order of the partial order which combined with the lexicographic ordering of matrices can be used to canonize any partial order.

Atomic: (= (count (parts order x)) 1)
Minimal: (= (count (parts order x)) 0)
Maximal: (= (count (parents order x)) 0)
Join irreducible: (every? #(contains % x) (join-representations x)
Meet irreducible: (every? #(contains % x) (meet-representations x)
Irreducible: join-irreducible? and meet-irreducible?
Isolated: (count (ground-set (connected-component x))) = 1

If an element is not isolated it has a connected component, if it is not minimal it has parts, and if it is not maximal it has parents, if it isn't join irreducible it has join representations, and if it isn't meet irreducible it has meet representations:

Parts: (query order ? x)
Parents: (query order ? x)
Proper parts: (clojure.set/difference (query order ? x) #{x})
Proper parents: (clojure.set/difference (query order x ?) #{x})
Connected components: (connected-component x)
Join representations: all elements that whose join is x
Meet representations: all elements whose meet is x

In lattices that aren't necessarily modular we can consider modular elements and in other lattices we consider when those elements are join prime or meet prime. Additionally, a variety of lattices including boolean algebras are complemented so they have specific elements associated with them:

Modular element: specific elements for which the modular law holds
Join prime: if (<= x (join a b)) then (<= x a) or (<= x b)
Meet prime: if (<= x (meet a b)) then (<= x a) or (<= x b)
Complement: in complemented lattices elements may be associated with complements

Related to the notion of parts is the height of an element of a well founded partial order which is defined to be the length of the partial ordering on its parts. Another type of partial order is one whose parts order forms a chain such elements form the lower subforest of a partial order and the dual notion of elements whose parents form a chain forms the upper subforest of the partial order. Related to join and meet representations is the minimal number of elements in a representation which generalizes the dimension of a partial order.

Sunday, August 25, 2013

Forbidding posets with less then four elements

Finite classes:
Every set of more then three forbidden suborders with three elements or less is finite as is every class of partial orders with limited height or width.
Empty class: #{}
Height 1 Width 1: #{[1]}
Height 2 Chains: #{[1],[1 1]}
Width 2 Chains: #{[1], [2]}
Height 2 Width 2: #{[1],[1 1], [1 2], {[1] 1, [1 1] 2}, [2], [2 1], [2 2]}
Height 2 Width 2 Weak Orders: #{[1], [1 1], [1 2], [2], [2 1], [2], [2 2]}
Height 2 Width 2 Upper Forests: #{[1],[1 1], {[1] 1, [1 1] 2}, [2], [2 1], [2 2]}
Height 2 Width 2 Lower Forests: #{[1],[1 1], {[1], [1 1] 2}, [2], [1 2], [2 2]}
Weak sets of lists: #{[1], [1 1], [2]}
Restricting the set of weak sets of lists to height two or width two has no effect on its set of values.

Classes with a single forbidden element:
Once we consider classes of partial orders with infinite elements things get to be much more interesting. To begin with lets consider classes defined by a single forbidden element:
Antichains: [n]
Total orders: T_n
Weak orders: e.g [1 2 1], [1 2 2 1], [1 3 3 1]
Upper/Lower Forests: e.g [{[1] 1, [1 1] 1} 1]
Height 2: e.g [1 2], {[1] 2, [1 1] 1}
Width 2: e.g [1 1 1], [2 2]

Classes with two forbidden elements:
Here are the sets defined by two forbidden elements rather then a single one:
Sets of lists: e.g {[1] 2, [1 1] 1}, {[1 1] 1, [1 1 1] 2, [1 1 1 1] 4}
Height 2 Weak Orders: [n k]
Width 2 Weak Orders: e.g [1 1 2 2 1 2 1 2 1 1 1 2 1 2 1 1 1 ... ]
Reductions/Antireductions: e.g {[1] 2, [2 1] 1, [3 1] 2, [4 1] 1}
Weak upper/lower forests: [n 1 1 1 1 ...] or [... 1 1 1 1 1 n]
Width 2 Upper/lower forests: [{T_a, T_b} T_c]

Classes with three forbidden elements:
All infinite classes with three elements are forests of some sort because the width 2 height 2 class is finite:
Width 2 sets of lists: {T_n, T_k}
Height 2 sets of lists: {[1] n, [1 1] k} Width 2 weak upper/lower forests: [2 T_n] or [T_n 2]
Height 2 weak upper/lower forests: [n] and [n 1] or [1 n]

Wednesday, August 21, 2013

Set producing functions

A wide variety of preordering relations can be derived from set producing functions such as the relations of connectivity, reachability, and targeting on any binary relation and the orderings of closure and reachability of any binary operation among others:
  • Reachability: the set of nodes reachable from any node produces a preordering relation parent to any binary relation.
  • Targets: the set of targets of any node also produces a preordering relation for any binary relation. This preordering relation can also be used to reason about certain simple graphs like threshold graphs unlike the reachability relation which is primarily useful for non-strongly-connected components.
  • Closure: the closure ordering on any binary operation produces a preorder which in the case of monoids is the ordering of cyclic submonoids.
Such preordering relations derived from set producing functions appear all over the place in mathematics. Similar concepts can be defined for rings and other related algebraic structures.

Partial function systems

Families of partial functions can be used to represent many of the most important algebraic structures: given a standard of keys (like 0,1,2) that are reused partial function systems can be used to represent the n-ary relations of database tables. Given a single output value (like true) a partial function system can be used to represent a set system by associating each partial function with its set of keys.

Besides relations partial functions can be used to represent all transformation systems including systems of partial symmetries, transformation monoids, and transformation groups by associating the system of partial functions with some compositional properties such as closure and associativity. Partial function systems are therefore one of the most generally applicable structures available to use in modern mathematics.

Tuesday, August 20, 2013

Four valued logic

Given a preordering relation there are four possible results of a comparison between two elements: they are incomparable, the first value is less then the second, the first value is greater then the second, and they are both equal. Given that the comparison is less then there are four possible logical values corresponding to these comparison results: none, false, true, and both.

There is a knowledge order corresponding to these four truth values [#{none}, #{false true} #{both}]. We can intersect the comparison results of preorders under the knowledge ordering to get another preorder. When we cannot produce an exact comparison like with irrational numbers the none value can be used to represent our uncertainity.

In general the values of none, false, true, and both can be used to deal with uncertain and/or non-monotonic reasoning. One advantage of four valued logic over three valued logic is that it is still binary so each truth value can be represented as two bits in this system.

Monday, August 19, 2013

Functional relational programming

I have long had an appreciation for one to one correspondences which like functions can be called but unlike ordinary functions they have also an inverse. An example of such a one to one correspondence is the increment function:
(inc ? 10) ; 9
(inc 10 ?) ; 11
Ordering relations like the total ordering relation on numbers and the inclusion relation on sets are of an unmatched level of importance to my algebra system. The first and second parts of a partial ordering relation are the parts and parents respectively:
(subset ? #{0 1}) ;  #{#{} #{0} #{1} #{0 1}}
(subpartition {1 2} ?) ; #{{1 2} {2 1}}
Equivalencies are another fundamental type of relation that together with partial ordering relations can be used to define preordering relations. Equivalence relations return the equivalence class of an element when subjected to a query. All binary operations including categories, magmas, quasigroups, loops, semigroups, monoids, semilattices and groups can be defined as ternary relations:
(+ ? 15 25) ; 10
(+ 10 15 ?) ; 25
A wide variety of simple graphs like forests, cographs, permutation graphs, interval graphs, and comparability graphs are also of interest to us as well as other binary relations that generalized directed cycles that haven't been mentioned so far. The key means by which I will relate my functional programming with the theory of relations is through the use of a system of functional dependencies based upon armstrongs axioms.

Sunday, August 18, 2013

Reversible binary operators

Given that a binary operation is a partial function $S \times S \to S$ a reversible binary operation is a bijection from a subset of $S \times S$ to another subset of S. The key reason that reversible binary operations are so interesting to me is that they can be used as a means of describing any irreversible computation in a reversible framework.

If we take the result of an irreversible computation and put it into the first slot of $S \times S$ and we put the information lost in the second slot then we will have a reversible decomposition of a structure into parts that are relevant and non-relevant to the current computation.

Every reversible binary operation has a complement in which the slots of $S \times S$ are reversed. The two slots of $S \times S$ induces two partitions of the output set that taken together cover it. Of particular interest to us are covering partitions that are independent and divisions.

The well known cons operation is a reversible binary operation because given any list like '(1 2 3) we can decompose it into first and rest parts '((1) (2 3)). We can clearly take the complement of the cons decomposition operation to get '((2 3) (1)).

The two parts first and rest of the operation are not only independent but divisions as well so we can for example use setf on the first and rest places to modify the value of a given list. We can define a special type of composition for reversible binary operations by taking the composition of the first parts and appending the trash parts together in the second part of the operation. This is a way of composing irreversible computations well also maintaining all the information we need to maintain reversibility.

Saturday, August 17, 2013

Partial binary operators

A partial binary operator is a function $S \times S \to S$ which is implemented on a subset of $S \times S$ which being a subset of the cartesian product is a binary relation. A subset R of S induces a substructure of the partial binary operator $R \times R \to R$ that only involves the elements of R.

Like the number of partial functions on a set $(n+1)^n$ the number of partial binary operators $(n+1)^{n^2}$ has a base of $n+1$ which adds an additional term to $n$ corresponding to nil. Partial binary operations can be described as ternary relations with one or more functional dependencies.

When I took an abstract algebra class at the university the first thing the first algebraic structures were studied were groups because they were so simple. We learned for example that finite abelian groups have a simple classification.

However, I quickly realized that groups weren't general enough for me so I looked into monoids instead. Even monoids weren't general enough for me because I needed to go to semigroups to describe non-bounded semilattices, categories to describe compositional properties, and magmas to describe operations like exponentiation. Despite the considerable level of generality I can get from structures like magmas and categories neither of those are general enough for me either because they aren't closed under the operation of taking induced substructures.

Since I have decided that my computer algebra system should be founded on order theory (e.g partial ordering relations) and we can use the idea of induced substructures to create partial orders of substructures classes of structures like partial binary operators that are closed under the operation of taking induced substructures are of particular interest to me. With such structures I can take induced substructures without having to change datatypes.

Therefore, I have decide that partial binary operators will be the fundamental operational algebraic structure in my computer algebra system. Properties like commutativity, associativity, identity and closure will all be described in terms of partial binary operators.

Thursday, August 15, 2013

Functional data dependencies

Given an N-ary relation on slots 0,1,2,3,4,... we can consider the potential existence of a function that goes from one slot to another. The identity function maps any slot back to itself and if there is a function mapping one slot to another and another function mapping that other slot to yet another slot those two functions can be composed to get a function between the first and the last one so this relation is also transitive.

The combination of transitivity and reflexivity means that this functional dependency relation forms a preorder which is of course particularly nice for us as we can use all the tools of order theory to reason about these dependencies.

Tuesday, August 13, 2013

Endomorphisms of a finite total order

The number of endomorphisms of a finite totally ordered set is given by the sequence 1, 1, 3, 10, 35, 126, 462, 1716, 6435, ... as specified by the sequence A088218. Here is a function that generates these endomorphisms:
(defn monotone-functions
  [size minimum maximum]
   (= size 0) (list [])
   :else (mapcat
          (fn [i]
             (comp vec (partial cons i))
             (monotone-functions (dec size) i maximum)))
          (range minimum (inc maximum)))))
For monotone functions on an infinite total order we can study the rate in which the function grows towards infinity but for a finite total order we know that finiteness implies that the monotone function converges to a single maximal constant. We can weakly ordered monotone functions by their eventual maximal value with gradings described by the following number triangle:
(1 2)
(1 3 6)
(1 4 10 20)
(1 5 15 35 70)
(1 6 21 56 126 252)
Another possibility is that we can partially order the monotone paths by the product order. This poset produces the following grading instead:
(1 1 1)
(1 1 2 2 2 1 1)
(1 1 2 3 4 4 5 4 4 3 2 1 1)
(1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1)
Since the weak order only requires that the last element of one endomorphism is larger then the last element of the other endomorphism and the product order requires that all elements are larger the product order is an extension of the weak order.

Sunday, August 11, 2013

Arithmetic decompositions of natural numbers

Every natural number can be additively partitioned so for example 3 can be decomposed to 1+1+1 or 1+2 and every number can be multiplicatively partitioned so for example 4 can be decomposed into 2*2. Arithmetic decompositions combine both additive and multiplicative partitioning:
0,1,(+ 1 1), 2,  (+ 1 1 1), (+ 1 2), 3, 
(* (+ 1 1) (+ 1 1)), (* 2 (+ 1 1)), (* 2 2), 
(+ 1 1 1 1), (+ 1 1 2), (+ 2 2), (+ 1 3), 4, 
(+ 1 (* (+ 1 1) (+ 1 1)), (+ 1 (* 2 (+ 1 1))), 
(+ 1 (* 2 2)), (+ 1 1 1 1 1), (+ 1 1 1 2), 
(+ 1 2 2), (+ 1 1 3), (+ 2 3), 5
I'm not familiar with any integer sequence that enumerates the arithmetic decompositions nor any applications of their definition, however, I think it is interesting to consider how they might fit into a generalized decomposition system.

Sunday, August 4, 2013

String rewriting systems

We can describe rewriting systems on finite alphabets which include finitely presented monoids as a special case. The rewriting rules on words generated by a single letter can be described by an iteration type such as the iteration type of order 4:
(f 0 0 0 0) = (f)
(f 0 0 0 0 0) = (f 0)
One possible partial ordering on words of a finite alphabet is the shortlex ordering which is something we may make use of to canonize words under the rewriting system. We can describe groups generated by two involutions by the dihedral group D_n:
(f 0 1 0 1) = (f 1 0)
(f 0 0 1 1 0 0) = (f 0 1 0)
Groups generated by involutions form their own class that includes the symmetric group S_n the dihedral groups of order D_n products of them and various other groups.