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.