Saturday, December 28, 2013

Degree of a transseries

I believe that the construction of surreal numbers and transseries should be done through a process of extensions going in order from natural numbers, to integers, to rationals, to reals, and then to real polynomials. In keeping with the fact that these number systems are extensions of one another we can compute the integer part of a real number or the standard part of a real number.

An analogous notion is computing the degree of a transseries. The way I think we should go about doing this is to compute the standard part of $\frac{ln(f(x))}{ln(x)}$. Since transseries are closed under logs and division this remains a transseries for any transseries so we can still compute its standard part.

If we plug in a constant we get $\frac{ln(c)}{ln(x)}$ which goes to zero for any constant. if we plug in $ln(x)$ we get $\frac{ln(ln(x))}{ln(x)}$ which also goes to zero, If we plug in the square root we get $\frac{ln(\sqrt{x})}{ln(x)}$ which goes to 1/2, if we plug in quadratics we get a degree of two, if we plug in quintics we get a degree of three, and if we go on to plug in exponentials we get a degree of infinity. It is necessary to use the infinity to deal with exponential degrees just as it is necessary to use infinity to deal with transfinite values when computing the standard part.

The next phase to build our transseries system is to make use of exponential and logarithmic values. With exponentials we get growth rates greater then any polynomial degree and with logarithms we get growth rates that are so small they are not distinguishable in the degrees system. In essence exponentials are of infinite degree and logarithms are of infinitesimal degree.

Thursday, December 26, 2013

Asymptotic analysis of combinatorial species

Given a collection of classes of entities we can arrange those entities in terms of generality in order to get an ontology. In particular this can be applied to mathematical structures over a set:

Well it is certainly the case that there is no set number of structures we can apply to a set there is a set number of structures in all the other classes described in the above ontology. The number of families of sets over a set is $2^{2^n}$. The number of N-ary relations over a set is $2^{n^k}$ which in the case of unary relations is $2^n$, in the case of binary relations is $2^{n^2}$, and in the case of ternary relations is $2^{n^3}$.

Some species although different from other species have the same growth rates as them. Coreflexive relations have a growth rate of $2^n$ like unary relations because both of them involve picking out subsets of a set. This leads to a natural bijection between unary relations and coreflexive binary relations based upon membership so for example the unary relation $\{(1), (2), (3)\}$ might go to the binary relation $\{(1, \; 1), (2, \; 2), (3, \; 3)\}$.

We can get the growth rates for a variety of other classes of structures. For reflexive relations we get $2^{n^2 -n}$, for symmetric relations we get $2^{\frac{n^2}{2}+\frac{n}{2}}$, for independency relations we get $2^{\frac{n^2}{2} - \frac{n}{2}}$, for antisymmetric relations we get $2^n 3^{\frac{n^2}{2}+\frac{n}{2}}$, for asymmetric relations we get just $3^{\frac{n^2}{2}+\frac{n}{2}}$, for functions we get $(n+1)^n$, and for binary operations we get $(n+1)^{2^{n}}$.

Each of these growth rates can be expressed as transseries, for example, $(n+1)^{2^{n}}$ can be expressed as $e^{\log(x+1)e^{\log(2)x}}$. The ontological order is a suborder of the asymptotic order on the collection of species as every subspecies of some other species has a smaller growth rate then its parent species.

Thursday, December 19, 2013

The role of light in perception

One of the most important sources of perception of the real the world is light. Light includes radio waves, microwaves, infrared light, ultraviolet rays, x rays, and gamma rays in addition to the visible light that is most familiar to humans. These other sources of light are essential to the astronomical perception of physical entities across the universe.

Through light we can get images and videos of the environment. With these perceptual stimuli we can begin to create spatiotemporal models of the environment. With the process of perceptual recognition we can give semantic meaning to stimuli by relating them to categories.

Thursday, December 12, 2013

Perceptual recognition

Given a set of observations of a partially observable system and a set of categories of parts of the partially observable system it is useful for us to be able to recognize rather or not parts of the environment belong to one of our categories. There are two types of perceptual recognition: non-localized recognition and localized recognition.

The process of non-localized recognition simply compares our observations to the definition of our category in order to make a determination. Localized recognition on the other hand attempts to locate entities within our model of the external environment.

An example of localized recognition is that we given some observations of a star such as its spectra we can determine that said star is a sun-like star. On the other hand with localized recognition we can determine that said star is the sun. Localized recognition generally requires information about the location of objects in the environment relative to one another.

Friday, December 6, 2013

Perception action cycle

An agent receives inputs from its environment in the form of perceptions and it outputs things to its environment in the form of actions. Perceptions and actions are combined together in the perception action cycle. The perception action cycle is an inherently causal process as actions precede perceptions which may themselves be preceded by previous actions.

In stochastic systems it is especially important for agents to be able to perform causal reasoning so that they can determine what the most probable effects of their actions will be. The predicted outcomes of an action can be integrated into an agent's plans so that an agent can be prepared to deal with all contingencies.

Wednesday, December 4, 2013

Algebraic ontology

I have created an ontology that contains all the most common structured collections used in mathematics including sets, lists, relations, binary relations, partial orders, lattices, distributive lattices, functions, ternary relations, monoids, groups, semirings, rings, fields, residuated lattices, bilattices, etc.

I intend to actively work on improving this ontology so that I can provide a formalization of the most important elements of algebra for my reasoning engine.

Wednesday, November 27, 2013

Cognitive ontology based upon observability

Given a system an intelligent agent can either completely observe the current state of the system or it can only only observe certain parts of the system. Based upon this idea we can categorize cognition in terms of observability as described by the Hasse diagram below:

The category of reasoning includes all cognitive processes that only involve the mind of the agent and not the external world. One fundamental reasoning process is categorization which can be used for example to produce an ontology of abstract structures such as lists, sets, relations, and numbers. Numeric reasoning can involve not just the set of real numbers but surreal numbers as well.

A fundamental part of abstract reasoning is optimization which is the process of finding an optimal item amongst a set of possibilities based upon some criterion such as in linear programming. This also applies to planning problems in games in which the agent must find the best course of action from the current state to achieve a certain goal.

Often times we cannot simply search the entire game tree which means that we need to use reinforcement learning instead to arrive at the optimal solution to the problem. Unlike with logical deduction the reinforcement learning process only produces approximate results. Another learning process is clustering which allows the agent to create new categories rather then simply working with the established ones.

All of these abstract reasoning processes are fundamentally divorced from the problems of incomplete and inconsistent information that arise from perception. It may be the case that incomplete information is a fundamental property of agents in the physical world as agents can only ever perceive things in their past light cone. Perception include vision, hearing, smell, taste, and touch among other senses. Intelligent agents should be able to learn from all these different sorts of perceptual signals.

Sunday, November 24, 2013

Basic cognitive ontology

A basic ontology of cognitive processes is presented in the hasse diagram below. This defines cognition in terms of perception, optimization, learning, and categorization.

I have been saying for a while now that perceptual learning is fundamental to cognition and I have written about this so it shouldn't be too surprising that perception and learning are both listed above. What is perhaps more interesting is that I now list categorization as a core cognitive process.

After creating so many ontologies like this one it is my contention that the categorization and characterization of entities plays a fundamental role in cognition. Simply having a vast ontology like the one provided by Cyc is not enough however as an intelligent agent should also be able to form new categories on the fly using clustering.

In a way essentially every cognitive process can be described as optimization, learning for example can be described as finding an optimal model that fits an experiential data set. Optimization and learning are deeply connected through the process of reinforcement learning which teaches an intelligent agent to perform optimally in its environment. Optimization and learning are so closely tied to one another it is questionable rather they should even be described as separate processes.

Wednesday, November 20, 2013

Mereology and causality

The basis of the ontological category of concretia is spacetime. We perceive the parts of spacetime (events) and relate those to one another through cause and effect relations (causality). In this ontology spacetime is itself an event: it is the largest possible event.

In this ontology causality relations do not occur between the atoms of causal set theory but rather between parts of spacetime which may be composed of such atoms. This implies that we are actually comparing different subsets of a partial order to one another.

Precedence occurs when all the elements of one part of spacetime cause another part. Causual independence occurs when the light cone associated with one of the events doesn't intersect the other events spatiotemporal presence. On possible example is that everything that happens in a given year on Earth is causually independent of everything that happens in a given year on Alpha Centauri as there is 4.367 light years of separation between us.

Monday, November 18, 2013

Causual set theory

Just as mereology partially orders physical structures based upon parthood causality partially orders physical processes based upon precedence. Both mereology and causality should play a fundamental role in any ontology dealing with physical objects. The Standard Upper Merged Ontology (SUMO) seems well suited enough to deal with both sorts of reasoning as it explicitly distinguishes between physical objects and physical processes in its ontology.

Causal reasoning plays a fundamental role in AI as any intelligent agent should be able to perform causal recognition by taking an effect and then determining what its causes may be and prediction by taking a cause and then determining what its effects may be. In either case probabilistic methods may play a role in the reasoning process as a system may use the frequencies of certain effects produced by a cause in order to help predict what the effect will be.

One interesting theory is that of causal sets which unifies quantum gravity and relativity by positing that the physical universe is fundamentally structured by causality. Time dilation indicates that we cannot place an absolute total ordering on events so the only way to effectively understand time is with a causal partial order like the one provided by causal set theory.

Sunday, November 10, 2013

On the ontological nature of incidence structures

Lets consider the following functional dependencies structure #{(#{} #{}) (#{0} #{0}) (#{0} #{1}) (#{1} #{0}) (#{1} #{1}) (#{0 1} #{0 1}) (#{0 1} #{0}) (#{0 1} #{1}) (#{0 1} #{}) (#{0} #{}) (#{1} #{})}. Should this structure be classified as a set, a relation over a set, or a relation over the power set of a set? Depending upon how this structure is classified it could have a size of 2, 4, or 11.

My recently line of thinking is that the underlying set of an incidence structure should be metadata and most ontological questions will be answered by asking about the overlying set itself which means that this set would still qualify as a transitive binary relation regardless of what it is defined over. I am not sure that this is the right approach but this seems to make sense for now.

For non-incidence structures like measure spaces, metric spaces, and rings there is no need to deal with the problem of different underlying sets. With this approach I believe I am on track to classifying most mathematical structures though I haven't exactly worked out exactly how to classify state spaces yet.

Saturday, November 9, 2013

Closure of binary relations

The three main classes of binary relations that exhibit closure operations are reflexive, transitive, and symmetric classes. From the intersection of these classes we get some other classes of relations that exhbit closure operations:

Preorder: reflexive and transitive
Dependency relation: reflexive and symmetric
Equivalence relation: reflexive, symmetric, and transitive

Another class of relation that exhibits a closure operation is the set of complete relations. Its corresponding closure operation is complete closure.

Thursday, October 31, 2013

Cognitive architecture

Memory should be partitioned according to perception in the cognitive architecture. Sensory memory includes sensory stimulus that is completely unprocessed, short term memory includes sensory stimulus well it is being processed, and empirical memory includes sensory stimulus that has already been processed. Conceptual memory contains logical ideas that are independent of perception and other conceptual generalizations.
  • Sensory Memory
  • Short Term Memory
  • Empirical Memory
  • Conceptual Memory
The organization of conceptual memory should be based upon an ontology of concepts. This ontology should include all mathematical concepts such as numbers, lists, and relations as well as concepts whose instances are described in empirical memory.

Wednesday, October 30, 2013

CHREST cognitive architecture

In my previous discussion on reasoning and perception I came to the conclusion that cognitive architectures should not be characterized by the distinction between perception and action as in ACT-R. One of the cognitive architectures that properly recognizes the central role of perception is CHREST.

CHREST perception facilities are organized into short term memory (STM) and long term memory (LTM). Recognition is used to relate elements in the STM to elements in the LTM. It is my contention that empirical knowledge should form a special category of the LTM which is far more dependent upon the changing interpretations of sensory perceptions then logical statements.

A fundamental aspect of CHREST is the idea of a chunk which is a maximal familiar substructure of a given sensory stimulus. CHREST uses an advanced system of attention management to determine what elements of the environment should be perceived. Many of the elements of CHREST were defined by the earlier cognitive architecture EPAM.

Tuesday, October 29, 2013

Methods of solving mathematical problems

The simplex algorithm is a fairly effective method of solving linear programming problems though there are many linear programming problems for which an inexact solution with optimal utility is desirable. For problems in which we cannot produce exact solutions we need to use heuristics to get a best approximation of the optimal solution.

Metaheuristics can be used to produce solutions to mathematical problems under conditions of limited computational capacity. Hill climbing is a metaheuristic that can be used to find local optima by iteratively improving an arbitrary solution to a problem but it is not guaranteed to produce a global optima.

The hill climbing metaheuristic can be used for example to optimize a solution to the traveling salesman problem by first finding a basic feasible solution and then switching the order in which certain nodes are visited as long as that switch improves the solution. There are various other metaheuristics such as tabu search that can be used to solve mathematical optimization problems.

Friday, October 25, 2013

Some types of mathematical problems

Analytic optimization
Analytic optimization problems are defined by the optimization of a function over a set of real vectors to the set of real numbers $\mathbb{R}^n \to \mathbb{R}$. The most generally applicable type of analytic optimization is linear programming so it is worth starting out with that and then continuing on to describe the nonlinear cases afterwards.

Linear programming:
Real linear programming problems can be solved using the simplex method, however, most integer programming problems don't have exact solutions so they require the use of heuristics. A variety of combinatorial problems including TSP, covering problems, and boolean satisfiability can be solved using integer linear programming.

Nonlinear programming:
Given some general multivariable real function we can use the combination of partial derivatives and equation solving to solve unconstrained optimization problems. Otherwise, there are special kinds of nonlinear programming such as fractional programming and quadratic programming that have their own sorts of solutions.

Goal oriented optimization:
In general goal based problems include a discrete temporal model and a predicate that determines rather or not the current state is the goal state. In planning problems the problem is generally to find the shortest sequence of moves to reach the goal state and in turn selection problems the problem is to find a move that maximizes the frequency of wins and minimizes the frequency of loses in the game tree.

Planning problems:
The purpose of planning problems is to find a sequence of moves to achieve the goal state that is optimal with respect to some ordering condition such as the size of the sequences. Planning problems include shortest path problems such as the problem of finding the shortest path in a maze and combination puzzles such as the 15-puzzle and the Rubik's cube puzzle.

Turn selection problems:
In any combinatorial game such as chess, checkers, go, connect four, or tictactoe players select moves each turn out of the set of valid moves based upon rather or not their move is going to achieve the end goal taking into account all possible future moves.

Tuesday, October 22, 2013

Perception and reasoning

After thinking about the different branches of AI I now feel that the most important basic distinction to make is between perception and reasoning. This is similar to the distinction between empiricism and rationalism in epistemology.

An intelligent agent that isn't dealing with an unknown environment such as one that is playing a game such as go, chess, checkers, or tictactoe in which there is no fog of war has no need for perception as we know it. Likewise intelligent agents that are solving logical puzzles such as sudoku only need to use their reasoning.

When an intelligent agent needs to understand the real world it ends up producing an empirical knowledge base which includes facts such as that Einstein once lived from 1879 to 1955 and patterns in the spacetime environment such as Newton's universal law of gravitation. Every single object in the empirical knowledge base is uncertain to some probability and dependent on the current point in time.

One of the fundamental things about the reasoning / perception distinction is that the aforementioned empirical knowledge base can be defined as a removable part. An agent capable of intelligent reasoning should be able to learn everything about the world from scratch based upon its learning and reasoning capabilities alone.

Likewise, an intelligent agent that know nothing about the real world could still play chess intelligently or produce logical solutions to sudoku. The reasoning component in general is very much mathematical / logical in nature as it focuses on mental objects that may have no physical instantiation.

One possible alternative to the reasoning / perception distinction is the declarative / procedural distinction, however, I don't think this is really valuable because there is no way we can really remove a procedural component from an AI as the techniques of optimization and decision theory are too fundamentally intertwined with the rest of the agent's reasoning capabilities to really be removable.

Sunday, October 20, 2013

Problems intelligent agents must confront

An intelligent agent that percieves its environment and acts upon it to maximize its own utility must confront at least three significant problems:
  • limited actions: an agent with limited actions must use decision theory to determine which action is the best one to take in this situation.
  • limited perception: an agent with limited perception must create models of its environment based upon the evidence obtained by its observations.
  • limited time: an agent with limited time must give attention to certain issues, plan, and predict the future.
To give an example of how this limitations might relate to games, logic puzzles like sudoko are purely in the realm of mathematical logic so they do not fall into any of these categories of limitations. Games like chess and go have limited actions as you need to select which move you think is the best each turn as do games in which the outcomes of actions are uncertain.

When it comes to limitations on perception and time, turn based games with fog of war have limited perception, real time games with revealed maps have limited time, and real time games with fog of war have limited perception and limited time.

The primary purpose of the scientific method is to deal with limited perception. With the scientific method we create models of the outside universe and we use perceptual evidence to determine which models of the universe are the most accurate.

the major object of perception of the physical universe is light which is dealt with by computer vision. Other senses include sound, touch, taste and temperature. Evidence obtained from such sense can be used as evidence to evaluate the accuracy of models of the physical universe.

The area of limited time is related to limited action through the notion of planning in which agents create plans of actions that they intend to perform over time and limited time is related to the area of limited perception through prediction as agents can create predictive models that determine what will happen in the future.

Friday, October 18, 2013

FRIL

The FRIL language (Fuzzy Relation Inference Language) combines logic programming with uncertainity. FRIL combines support for classical logic with support for fuzzy logic and probability unified by mass assingments. FRIL has a list based syntax so in a way it is a dialect of Lisp:
(less-than
  (1 2)
  (2 3)
  (3 4))
FRIL supports both discrete and continuous fuzzy sets each with their own syntactic representations. The extension of classical logic with fuzzy sets makes FRIL a much more general and powerful language then Prolog.

Thursday, October 17, 2013

Extensions to classical logic

An intelligent reasoning system must be able to effectively handle information that is uncertain, imprecise, and vague. This implies that an intelligent reasoning system should have a much richer system of logic then the boolean algebraic logic which is used to define mathematics.

Extensions to the classical logic system including fuzzy logic which has degrees of belief, paraconsistent logic which has both belief and doubt, and probablistic logic which uses probability distributions. A reasoning system which uses such advanced logics may play a significant role in the construction of an AI.

Monday, October 14, 2013

Mathematical logic and order theory

An inescapable conclusion of the study of order theory is that mathematical logic is deeply intertwined with the study of partial ordering relations. We can form partial orders called concept hierarchies corresponding to the logical inclusion of predicates and we can represent elements of partial orders that form distributive lattices including well orders as sets or predicates. This naturally leads to the definition of Von Neumann ordinals in a well order for example. A description of the relation between mathematical logic and order theory is forthcoming.

Thursday, October 10, 2013

Complete lattice extensions

The natural numbers with infinity can be described as a complete lattice which can be extended by the integers with positive and negative infinity which can in turn be extended by the complete lattice of real numbers.

Given a real number such as 27/5 we can get an interval approximation for this number through the integers sublattice of (5,6). Likewise for a negative real number such as -5/4 we can get an approximation of (-2,-1). Since the sublattice of natural numbers doesn't contain any negative numbers the only approximation we can get there is (> 0).

Given the trivial lattice containing just the number zero we can get approximations of (< 0), (> 0), and equal to zero which are essentially just the sign of the number. Given the complete lattice of real numbers we can always get a standard part which doesn't even need to be expressed as an interval because the real numbers form a dense complete total order.

The surreal number $27/5+\frac{1}{\omega}$ has a standard part of 5, an integer part of (5,6) as described earlier, and a sign of (< 0). The infinite surreal numbers $\omega$ and $\sqrt{\omega}$ both have a standard part of (< Infinity). Complete lattice extensions can be used to construct ever more advanced total ordered number systems.

Thursday, October 3, 2013

Continuous iteration of exponentation

The continuous iteration of the exponentiation operation may hold the key to extending transseries to deal with larger and larger growth rates. We can iterate the exponentation operation to integer arguments for example $exp^2(x) = exp(exp(x))$, $exp^{-1}(x) = log(x)$, and $exp^{-2}(x) = log(log(x))$ so the key to continuous iteration are the fractional iterates of exponentiation such as the half-iterate.

These fractional iterates of exponentiation apparently can be described by the natural tetration operation $tet$ and its inverse function in a similar manner to how we can describe general iterates of multiplication using $exp$ and its inverse function $ln$. As a result of this it may be the case that we should extend transseries with the $tet$ function in order to implement iterates of $exp$ and larger growth rates.

Monday, September 30, 2013

Veblen hierachy of ordinal numbers

We already know that a wide variety of ordinal numbers be expressed in cantor norm formal such as 0,1,2,3,4, $\omega$, $\omega+1$, $\omega^2+2\omega+1$, $\omega^\omega$, and $\omega^{2\omega^3+1}+2\omega^5+3\omega^2+2$.

We can use the generalized veblen function of one argument to express these same ordinals so we get $\phi(1)$, $\phi(1)+1$, $\phi(2)+2\phi(1)+1$, $\phi(\phi(1))$, $\phi(2\phi(3)+1)+2\phi(5)+3\phi(2)+2$. The first ordinal that cannot be expressed as such a number in Cantor normal form is $\epsilon_0$ which equals $\phi(0,1)$.

The first ordinal which cannot be expressed through addition and the veblen function of two arguments is the Fefermann-Schutte ordinal which is equal $\phi(0,0,1)$. A considerable amount of countable ordinal numbers can be expressed by the generalized veblen function.

Saturday, September 28, 2013

Mathematical ions

The most common numbers used in mathematics have an ordering relation <= associated with them for example the natural numbers appear in the order 0,1,2,3,4,... the integers appear in the unbounded order ...,-2,-1,0,1,2,... the rational numbers are are densely ordered variant of the integers and the reals are the dedekind completion of the rational numbers.

The ordinal numbers are the order types of well orders and therefore they include the natural numbers 0,1,2,3,4,... mentioned before as well as infinite numbers such as $\omega$, $2\omega$, $\omega^2$ and $\omega^\omega$. The surreal numbers are a large ordered field that include the natural numbers, the integers, the rational numbers, the real numbers, the transfinite ordinals, infinitesimals, and much more.

It is my contention that numbers should be related to ordering and not just arithmetic so the so called "complex numbers" belong to the class of ions which includes binarions, quaternions, octonions, and sedenions rather then the class of numbers. Numbers should be related to ordering which implies that the class of surreal numbers is the single class of numbers to rule them all. In conclusion every number is a surreal number.

Friday, September 20, 2013

Incidence structures as height two orders

Incidence structures are defined by a set of elements and another set of edges over those elements such that each edge is dependent upon some subset of the set of elements. Every incidence structure can be expressed as an oriented set system with sets of edges grouped by their corresponding elements:
{#{1 2} #{4}, 
 #{0 1} #{3}}
Incidence structures may be represented as height two partial orders with an option to classify disconnected nodes as either empty nodes or empty edges. If we exclude empty edges as a possibility as we can also represent height two partial orders as incidence structures:



One advantage of such incidence structures is that they allow us to define mathematical substructures of a structured sets such as relations and hypergraphs as lower suborders of the height two partial order and they can likewise be used to describe all other parts of an incidence structure.

Thursday, September 19, 2013

Orders derived from group action

Each permutation group produces a partition of the power set of the underlying set of the group. By the definition of partitioned partial orderings this produces a partial ordering relation from the group action. The partial ordering of a disjoint union of permutation groups is the product order of the partial orderings of each of those permutation groups.

The symmetric group and the alternating group are both completely transitive so they produce a total ordering relation $T_n$. Permutation groups that are defined as the disjoint union of such completely transitive groups effectively produce a multiset inclusion lattice. The cyclic group $C_4$ produces the free distributive lattice of size 2:


The cyclic group $C_2$ is the smallest group that doesn't produce a complete lattice as its underlying partial order and it is the smallest group that isn't the product of transitive groups:


The cyclic group $C_5$ is an example of a transitive group whose partial ordering is also not a complete lattice:


As I already mentioned in my post on ranking elements of partial orders the size of an element of one of these partial orders is its height and the cardinality of one of these partial orders is the total height minus one.

Saturday, September 14, 2013

Ranking elements of distributive lattices

There is a correspondence between the number of join irreducibles contained in an element of a distributive lattice and its ordinal height minus one:
(= (dec (count [1 1 1 1]))
   (count #{#{} #{#{}} #{#{} #{#{}}}}))
The same principle applies to multisets which are elements of a distributive inclusion lattice:
(= (rank {:x 1, :y 2})
   (dec (count [1 2 2 1]))
   (count #{{:x 1} {:y 1} {:y 2}))
This implies that we can use the idea of join irreducible elements as a basis for structured multisets and canonical forms of structures. A canonical labeling of a structure is one over a set-theoretic natural number such as #{#{} #{#{}} #{#{} #{#{}}}} and a structured multiset is a structure over the join irreducibles of the multiset. The key is to implement an effective partial canonization technique so that we can properly determine the equality of such structures.

Friday, September 13, 2013

Ordered multisets

Partially ordered multisets are a generalization of sets, multisets, and lists so they provide a fairly general setting from which to describe mathematical collections. We can define series parallel collections that are closed under the fundamental operations of union and ordinal sum:
(= (ordinal-union {:x 1, :y 2} {:x 2, :y 1})
   {:x 3, :y 3})
(= (ordinal-sum [1 2 3] [4 5 6])
   [1 2 3 4 5 6])
The operation of union corresponds to the combination of multisets and the operation of the ordinal sum corresponds to the concatenation of lists. Things get really interesting once we combine these two operation together to get series parallel collections that cannot be classified as any of the familiar collection types.

Thursday, September 12, 2013

Partitions of a poset

Given a partitioned partial ordering relation we can produce a new partial order on the parts of the partition defined the condition that part one is less the part two if for every element of part one there exists some element of part two such that these two elements are less then one another in the underlying partial order.

We can use this notion of partitioned posets to partially order isomorphism types including cardinal numbers and the canonical labelings of relations. This allows us to maintain the use of partial orders even when we aren't dealing with structured sets which demonstrates how fundamental order theory really is.

Wednesday, September 11, 2013

Closure operators

A closure operator on a partially ordered set is an increasing, extensive, idempotent endofunction. Of particular interest to us are closure operators on the boolean algebra which can in fact be described by their set of fixed points which form an upper bounded meet subsemilattice of the boolean algebra.

A preorder can be produced from a closure operator on a boolean algebra by the inclusion order on the closure of singletons. Set systems that are entirely determined by their closure preorder are equivalent to Alexandrov topologies.

Besides the reachability closure on any binary relation we have the closure of upper sets, lower sets, convex sets, rank complete suborders, join subsemilattices, meet subsemilattices, sublattices, and complemented sublattices among others.

Monday, September 9, 2013

Boolean algebraic closure

Given a subset of a boolean algebra the closure of the subset under the operations of union, intersection, and complementation is equivalent to a partition of the boolean algebra.

Consider the set system #{#{0 1} #{2 3}} of #{0 1 2 3 4}. The boolean algebraic closure of this set system is defined by partition #{#{0 1} #{2 3} #{4}}. For the set system #{#{0 1} #{0 1 2}} of #{0 1 2 3 4} the resulting partition is #{#{0 1} #{2} #{3 4}}.

I believe this correspondence between boolean subalgebras and equivalence relations demonstrates the close connection between sets and equality. A fundamental aspect of the definition of a set is that a set must not contain elements that are equivalent to one another.

Thursday, September 5, 2013

Symmetries and functional dependiencies

We can combine the functional dependencies of a set of elements with a group of symmetries of the set in order to construct an advanced system of reasoning about relations. One immediate application of the combination of these two notions is that we can combine symmetry and dependency to find involutions amongst the elements.

The set of relations with certain functional dependencies and symmetries forms a meet subsemilattice of the set of all relations. This allows us to use the combination of symmetries and functional dependencies to reason logically about classes of relations such as functions, bijections, constants, symmetric relations, binary operators, cancellative operations, and commutative operations.

Sunday, September 1, 2013

Complementary pairs

Given a lattice we can find certain elements that are both independent and covering which are called complements of one another. If we order pairs of such elements we can get complementary pairs. Here is an example of an expression of the boolean algebra on three elements as complementary pairs:
[#{0 1 2} #{}]
[#{1 2} #{0}], [#{0 2} #{1}], [#{0 1} #{2}]
[#{2} #{0 1}], [#{1} #{0 2}], [#{0} #{1 2}]
[#{} #{0 1 2}]
By convention such complementary pairs are expressed such that sets in a boolean algebra are equivalent to height two weak orders or in other words total functions from the underlying set to the two valued total order. One of the the major reasons I am interested in exploring such complementary pairs is their applications to set partitions:
[#{#{0} #{1} #{2}} #{#{0 1 2}}]
[#{#{1} #{0 2}} #{#{0 1} #{2}}], 
[#{#{0} #{1 2}} #{#{0 1} #{2}}], 
[#{#{0 1} #{2}} #{#{1} #{0 2}}], 
[#{#{0} #{1 2}} #{#{1} #{0 2}}], 
[#{#{0 1} #{2}} #{#{0} #{1 2}}],
[#{#{1} #{0 2}} #{#{0} #{1 2}}]
[#{#{0 1 2}} #{#{0} #{1} #{2}}]
Such complementary pairs of set partitions are a generalization of place forms applicable to other means of decomposing structures. In the most general setting we simply consider set partitions that are covering by ignoring the independence property but such pairs of set partitions aren't necessarily decompositions so that makes them much less interesting to us.

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]
  
  (cond
   (= size 0) (list [])
   :else (mapcat
          (fn [i]
            (map
             (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)
(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 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.

Thursday, July 25, 2013

Algebraic preorders

Two of the most common algebraic structures, binary relations and monoids, have a preorder associated with them:
  • Monoids: reachability can be defined by $(x <= y) \implies \exists \; a,b: axb = y$
  • Binary relations: reachability can be defined by $x <= y$ if there exists some path from x to y
I believe that the applicability of order theory to such common structures is a solid justification for its foundational status.

Tuesday, July 23, 2013

Interval orders

We can represent a wide variety of partial orders as interval orders:
()
([0 0])
([0 0] [0 0])
([0 0] [1 1])
([0 0] [0 0] [0 0])
([0 0] [0 0] [1 1])
([0 0] [0 1] [1 1])
([0 0] [1 1] [1 1])
([0 0] [1 1] [2 2])
According to automorphism groups of forbidden posets by Gerhard Behrendt the class of automorphisms of finite interval orders is equal to that of finite weak orders which motivates our discussion of interval orders. The order 2+2 avoided by interval orders is the first partial order which has an automorphism group that isn't orbit symmetric.

Monday, July 22, 2013

Forbidden induced suborders

Several classes of partial orders can be described by their avoidance of a single induced suborder:
  • Antichains: [1 1]
  • Total orders: [2]
  • Weak orders: {1 1, [1 1] 1}
  • Upper/lower forests: [1 2] and [2 1]
  • Interval orders: {[1 1] 2}
  • Series-parallel partial orders: the zigzag poset
The semiorders can be described as the subset of the set of interval orders that avoid another order type in addition to the one the interval orders avoid.

Friday, July 19, 2013

Subsets of a poset

There are certain special subsets of a partially ordered set:
  • Directed Sets: these are subsets whose every pair of elements contains an upper or lower bound.
  • Centered Sets: these are subsets whose every finite subset of elements contain an upper or lower bound.
  • Upper/Lower Sets: subsets that contain all elements less then or greater then values that they contain. The lattice of these sets is a sufficient basis for representing distributive lattices.
  • Dedekind Cuts: subsets whose set of lower bounds of its set of upper bounds is equal to itself. The lattice of these is the dedekind completion.
The analysis of such subsets is important to our understanding of order theory.

Wednesday, July 17, 2013

Transseries

Transseries are a composable, differentiable totally ordered field whose values can be used to approximate rates of growth of real functions. Here are a few transseries listed in order: $x^{-2}$, $x^{-1}$, $log(x)$, $12$, $x^2 + 2x + 1$, sinh, cosh, $e^x$, $e^{e^x}$.

Transeries can also be used to solve homogeneous LODEs with constant coefficients and real roots which is why they include cosh, sinh, $e^x$, and all polynomial functions. Functions with growth rates less then polynomials like $log(x)$ and $x^{-1}$ and functions with growth rates that are greater then exponential like the double exponential $e^{e^x}$ do not fall into this category of functions.

The theory of transseries subsumes much of surreal analysis because transseries are simultaneously surreal numbers and transformations of themselves. The full extent of the applications of transseries has not yet been fully explored.

Tuesday, July 16, 2013

Elements of distributive lattices

Every element in a distributive lattice such as the total ordering on the natural numbers can be represented as a lower set of join irreducible elements. This approach allows us to represent all natural numbers as sets:
#{}
#{#{}}
#{#{} #{#{}}}
#{#{} #{#{}} #{#{} #{#{}}}}
This also can be used to represent all natural numbers as sets of prime powers with respect to the divisibility relation:
#{}
#{2}
#{3}
#{2 4}
#{5}
#{2 3 6}
#{7}
#{2 4 8}
We can also use this to effectively represent abstract simplical complexes as sets of lower sets of the set of lower sets of an antichain.

Thursday, July 11, 2013

On multiplicative lower sets

The set of all orders of elements of the symmetric group S_n forms a multiplicative lower set:
(#{0} 
 #{1} 
 #{2} 
 #{2 3} 
 #{3 4} 
 #{4 5 6} 
 #{4 5 6} 
 #{7 10 12} 
 #{7 8 10 12 15} 
 #{8 9 12 14 15 20})
The set of lower sets over the divisibility relation forms a distributive lattice with its own union and intersection operations.

Friday, July 5, 2013

Data dependencies

We can associate an input place and an output place with every operation in order to model data dependencies. Bernstein's condition describes when two operations are independent and can therefore be executed in parallel.

Thursday, June 13, 2013

Implementing the Tamari lattice

The catalan numbers enumerate several different structures in combinatorics including monotone paths, dyck words, and semiorders. A catalan lattice is a class of disjoint lattices each having a catalan number of elements. The tamari lattice is a catalan lattice that can be implemented by applying min/max to monotone paths.

Sunday, June 9, 2013

Ordinal numbers

Like all surreal numbers, ordinal numbers can be described by a transfinite sequence of terms that are ordered by order of magnitude. The predecessors of the ordinal number $\omega^\omega$ can all be described by a sequence of ordinal monomials $m \omega^n$ totally ordered by the value of the exponent $n$.

The predecessors of the ordinal number $\epsilon_0$ contain all the ordinal numbers that can be represented by exponential polynomials. Such ordinal numbers can be represented by sequences of ordinal numbers raised to the power of some other ordinal sequence such as $w^{w^2+2} + w^2 + 2$.

Friday, May 31, 2013

Ordering list elements with component intervals

Every list induces an equivalence relation of its indexes called the kernel of the list. Every finite totally ordered set has a component interval which includes the parts of a partition of the indexes of a list. Here is an example in which we compute the component intervals:
(= (component-intervals [3 0 1 0 1 2 3 4])
   [[1 3] [2 4] [5 5] [0 6] [7 7]]
Since the set of intervals of a partially ordered set is itself partially ordered we know that we can partially order those five intervals to get the following ordering relation:
(= (order-from-list [3 0 1 0 1 2 3 4 ])
   [[1 0 1 0 1]
    [0 1 1 0 1]
    [0 0 1 0 1]
    [0 0 0 1 1]
    [0 0 0 0 1]]
The order type of the above partial ordering relation is the rooted tree {{{} 2} 1, {} 1}. Producing all the different configurations of a list that satisfy an unbounded partial order is a far more complex task that once achieved can be used to compute all the different permutations of a list by their ordering.

Friday, May 24, 2013

Product orders

Let $\mathbb{N}_k$ represent an elementary total order with $k$ elements. Every divisibility relation is the product of total orders. The divisibility lattice of 24 is $\mathbb{N}_2 \times \mathbb{N}_4$.

The prime signature of a number describes the divisibility lattice of a number up to isomorphism by describing it as a product of total orders. The number of divisors of a number is the size of this ordering relation and the number of prime factors of a number counting repetition turns it into a graded lattice.

Wednesday, May 22, 2013

Ordering ordering relations

Every partial ordering relation falls between two weak orders: a child weak order and a parent weak order. These two weak orders form an order interval. Of course weak orders themselves have a trivial component interval since their child and parent intervals are both equal.

The divisibility relation on the natural numbers $(\mathbb{N},|)$ is a suborder of the weak ordering relation induced by the big omega function which outputs the number of prime factors of a number counting multiplicity.

The width of a partial ordering relation is the size of its largest child total order and topologically sorting produces the parent total orders of the partial order.

Saturday, May 18, 2013

Weakly ordering vertex targets

Given a strongly connected directed graph G we can produce a weak order of the vertices of G based upon their proximity to a vertex G:
(= (targets-list G 0)
   [#{0} #{1 2} #{3}])
We can represent the shape of a targets list by enumerating the sizes of each target set which provides a useful graph invariant. By examining the cubic graphs of size 8 we see that not all regular graphs are eccentricity regular and not all graphs that are both regular graphs and eccentricity regular are distance regular. We further see that not all distance regular graphs are isomorphic.

Friday, May 17, 2013

List forms

We can form bijections from a list of elements of some size to alternative representations for those lists. We can use this functionality to describe nesting structures to begin with:
(= (nesting '(def inc [x] (+ x 1)))
   '(0 1 [2] (3 4 5)))
We can use the catalan numbers to enumerate all binary bracketings of size n. Given such a nesting structure we can apply it back to a list:
(= ((nesting-function '((0 1) (2 3)) [10 20 30 40])
   '((10 20) (30 40)))
Matrices and grids use a special kind of nesting. Besides describing lists with nesting structures we can describe lists by associating indexes with keys in a hash.

Friday, May 10, 2013

Cyclic permutation groups

Iterating cycle structures:
We can begin by describing the effects of iteration on a cycle structure:
({1 6} {6 1} {3 2} {2 3} {3 2} {6 1})
Using this we can effectively determine the cycle structure of cyclic subgroups and cyclic supergroups of any given cyclic permutation group.

Cyclic permutation groups:
Given a permutation we can select a canonical generator for the permutation group generated by that permutation by selecting a permutation amongst the available iterates using the lexicographic ordering of permutations.

Sunday, May 5, 2013

Clique complexes

Every undirected graph induces an abstract simplical complex called the clique complex and every abstract simplical complex induces an undirected graph called the 1-skeleton of the complex so in this sense undirected graphs and abstract simplical complexes are isomorphic structures.

Sunday, April 14, 2013

Approximating irrational numbers using intervals

Every irrational number can be progressively approximated using rational intervals. Here is a sequence of intervals that approximate $\sqrt{2}$:
[-Infinity Infinity]
[0 2]
[4/3 5/3]
[11/8 10/7]
[24/17 27/19]
[65/46 58/41]
[140/99 157/111]
[379/268 338/239]
[816/577 915/647]
[2209/1562 1970/1393]
[4756/3363 5333/3771]
[12875/9104 11482/8119]
[27720/19601 31083/21979]
[75041/53062 66922/47321]
[161564/114243 181165/128103]
[437371/309268 390050/275807]
This sequence of intervals is produced by the continued fraction representation for $\sqrt{2}$ which is 1,2,2,2,2,2,2,... with an infinite sequence of twos.

Saturday, April 13, 2013

Interval analysis

The set of all rational intervals is countable. We can develop analysis in terms of this intervals firstly through interval arithmetic:
(= (add-intervals [1 2] [3 4]) [4 6])
(= (multiply-intervals [1 2] [3 4]) [3 8])
We can express any continuous real function as a function of intervals using its set of extrema. For example, the square of the interval [-2,2] is [0,4] and the square of the interval [2,3] is [4,9].

Monday, March 25, 2013

Establishing a weak order from a partial order

Here is the partial ordering relation of the power set algebra of a set of size two:
[[1 1 1 1]
 [0 1 0 1]
 [0 0 1 1]
 [0 0 0 1]]
From this partial order we can get a weak order of the vertices [#{0} #{1 2} #{3}] based upon the upper and lower bounds. The lower bound is #{0} and the upper bound is #{3}. This produces the following weak order:
[[1 1 1 1]
 [0 1 1 1]
 [0 1 1 1]
 [0 0 0 1]]
Only weak orders themselves are equivalent to their underlying weak ordering relation. Topological sorting is related to weak ordering.

Sunday, March 17, 2013

The big omega function

The big omega function (A001222) describes the number of prime divisors of a number counted with multiplicity: 0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2.

The numbers zero and one do not have any prime factors. The prime numbers (A000040) have one factor, the semiprimes (A001358) have two factors, and the k-almost primes have k factors.

The big omega function tells us about the maximum number of fields of a structure of some cardinality. In practice, many structures don't use the prime factorization so they have even fewer fields then they do factors.

The number of multiplicative partitions of a number n with k factors is in the interval from p(k) to B(k) where p is the number of of additive partitions of k and B is the number of equivalence relations of size k

Saturday, March 16, 2013

Differences between primes

The differences between consecutive prime numbers are 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12.

The only prime numbers that have an odd difference are the first two prime numbers two and three. Twin primes have a difference of two, cousin primes have a difference of four, and sexy primes have a difference of six.

Prime triplets have differences of either 2,4 or 4,2. Prime quadruplets have differences of 2,2,4 or 2,4,2 and prime quintuplets have differences of 2,4,2,4 or 4,2,4,2. Finally, prime sextuplets have differences 4,2,4,2,4. The twin primes conjecture states that the number of differences of 2 are infinite which is necessary for there to be an infinite number of these prime k-tuples.

Friday, March 15, 2013

Enumerating labeled binary relations

Labeled binary relations on a set of size $n$ can be enumerated using the following counting sequences:
  • All relations: $2^{n^2}$
  • Commutative relations: $2^{n^{\underline 2}}$
  • Endofunctions: $n^n$
  • Permutations: $n!$
  • Equivalence relations: $B_n$
  • Weak orders: A000670

Wednesday, March 13, 2013

Algebraic combinatorics

A set of transformations on a data structure forms a transformation monoid. Place forms are a special type of transformation monoid. Another important type of transformation monoid is a permutation group. The permutation groups arise in combinatorics as the automorphism groups of graphs and various other discrete data structures such as lists.

The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.

By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.

Sunday, March 10, 2013

Describing structures by transformations

The automorphism group of a data structure transformations of that data structure that do not have any effect on it. The automorphism group of a list is the set of operations that map indexes to other indexes with equal value. We can enumerate all the orbits of this automorphism group on its parent symmetric group in order to enumerate all distinct permutations of the list.

Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.

Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.

Saturday, March 9, 2013

The well ordering principle

The set of natural numbers $\mathbb{N}$ is well ordered which means that every subset of the natural numbers can be described by a monotone increasing enumeration. Consider for example the set of prime numbers:
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53)
We can convert any prime number back into a natural number $\mathbb{N}$. For example, 547 can be converted to 100. These enumerations are endofunctions $\mathbb{N} \to \mathbb{N}$ that are reversible but not surjective. With finite functions all reversible surjective operations are automorphisms. The square numbers are another enumeration of natural numbers:
(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)
The set of all subsets of $\mathbb{N}$ under set union and set intersection forms a boolean algebra with $\mathbb{N} - S$ as the complement operation. The differences between elements of this enumeration form an integer sequence. Consider the sum of the totient function:
(0 1 2 4 6 10 12 18 22 28 32 42 46 58 64 72)
The additive differences of the sum of totients is the eulers totient function itself. In this sense, these monotone enumerations are related to integer sequences in general. We can generalize integer sequences by describing sequences of rational numbers $\mathbb{N} \to \mathbb{Q}$, however, an important difference is that the set of rational numbers $\mathbb{Q}$ is not well ordered.

Friday, March 8, 2013

Finitely differentiable functions

Functions that have a differentiation iteration type with a finite size are solutions to a simple two element homogeneous LODE with constant coefficients. The solutions to a LODE can be described by a basis which in this case can be ordered by the total ordering of rational number sequences.

The function $x^2+2x+1$ would become [1,2,1,0] for the LODE $y''''=y'''$. If we set the default value of each field in this ordered basis this vector could be reduced to [1,2,1] which is equivalent to description of this function as a polynomial. The function $e^x$ is unaffected by differentiation so it would simply be [1] for $y'=y$.

The hyperbolic trigonometric functions $cosh(x)$ and $sinh(x)$ are involutions under differentiation so they would be represented by [1/2,1/2] and [1/2,-1/2]. The trigonometric functions $sin(x)$ and $cos(x)$ have order four so they would be represented as [0,0,1,0] and [0,0,0,1].

Sunday, March 3, 2013

Enumerating structure types

Structures associate places with types. If the types of the fields of a structure are enumerated then the entire structure can be enumerated. The following elements are generated by (structure {:x (enum 0 1), :y (enum 0 1)}):
{:x 0, :y 0}, {:x 0, :y 1}, {:x 1, :y 0}, {:x 1, :y 1} 
By using slot places we can enumerate other associative collections as structures. Here is {first (enum 0 1), second (enum 0 1)}
[0 0], [0 1], [1 0], [1 1]
Sets use the contains? place system so here is all subsets of #{false, true} using {(contains? false) bool, (contains? true) bool} where bool is (enum false true):
#{}, #{false}, #{true}, #{false true}
We can also associate places with structures within a structure to enumerate grids. In general, structures are essential because they combine both enumerations and places together into one.

Saturday, March 2, 2013

The linear continuum

Discrete mathematics is founded on the integers, directed graphs and other discrete structures. On the other hand, continuous mathematics is based upon continuous structures the simplest of which is the linear continuum. The unit interval [0,1] is a linear continuum whose every element can be represented by an infinite sequence of binary digits the positions of which are natural numbers.

The infinite subsets of the natural numbers numbers cannot be enumerated because attempting to determine the equality of infinite data structures leads to the halting problem. Without an enumeration these infinite subsets cannot be described by discrete mathematics and herein lies the fundamental distinction between discrete and continuous mathematics.

The probabilities of statements form a linear continuum [0,1]. Negation is defined by $1-x$, conjunction is defined by $xy$, and disjunction is defined by by $x+y-xy$. The values of zero and one are the absolute certainties used in deductive logic but that aren't used in probabilistic logic.

In order to convert [0,1] to another interval [a,b] with finite length we can use a linear polynomial $|b-a|x+a$. With infinite intervals we can use the reciprocal function and the logarithm function to achieve the same effect. A discrete partition of the linear continuum is equivalent to a discrete probability distribution.

Friday, March 1, 2013

Iteration types of differentiation

The differentiation operation is a transformation of differentiable functions and it has different iteration types for different differentiable functions:
  • Identity: $c_1e^x$
  • Idempotent: $c_1e^x + c_2$
  • Involution: $c_1e^x + c_2e^{-x}$
All functions of a certain iteration type come from solutions to first order linear ordinary differential equations such as $y'=y$, $y''=y$, and $y''=y'$. The partial ordering of iteration types helps us to understand these differential equations. In general, polynomials, exp, sin, cos, sinh, and cosh and other similar functions all produce a finite number of differentiations.

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.