Wednesday, December 31, 2014

Structural specialization

There are a variety of cases in which it makes sense to preorder a set based upon the elements that it contains. One example is that with the set representation of a multiset the elements of the set include special multiple elements which are dependent upon previous multiples. Also algebraic structures like graphs have a specialization preorder associated with them in which edge elements are dependent upon the vertices that they contain. Multigraphs are a combination of these two notions as they can have multiples of edges which are dependent upon previous multiples of edges which are then dependent upon vertices.

A standard specialization relation can be provided that combines all these different notions of structures on sets into a single unified relation. This combined specialization relation will allow for all elements of distributive lattices to be treated like sets, multisets, and algebraic structures to be treated in a uniform way. This will then improve the handling of multisets and related structures like multigraphs so that they can be treated as a first class object in the algebra system.

Tuesday, December 16, 2014

Multiset systems

One of the critical problems of set theory is how to represent sequences as sets. Well Kuratowski solved the problem for sequences of size two through the set theoretic definition of the ordered pair there is no obvious solution to the problem of representing sequences of arbitrary size as set systems because sequences may contain repeated elements. I have thought about this problem so much in terms of set systems that I did not consider the possibility of using a multiset system instead.

In order to represent any sequence all we need to do is use a multiset system containing the multiset of elements up to a point in the sequence for each point in the sequence. This solution is so simple I am surprised I did not hear about this before. It is probably because multisets are far too often pushed aside for sets but no more. From now on I am going to make full use of multisets when I think about mathematics.

Wednesday, November 26, 2014

Disjoint union closed families

The disjoint union closed families are precisely those families for which it is the case that the union of any two disjoint sets in the family is contained within the family. The disjoint union closed families generalize both the union closed families which are both disjoint union closed and nondisjoint union closed and the symmetric difference closed families. The symmetric difference of any two disjoint sets is their union so symmetric difference closed families are disjoint union closed.

Besides the union closed families and the symmetric difference closed families the antidisjoint families are disjoint union closed. The antidisjoint families are precisely those families of sets whose every pair of sets is not disjoint. These include the nullfree chain families which also happen to have the property that they are union closed as they are chain families as well as the antidisjoint sperner families which are antidisjoint families that also contain no comparable pairs.

Monday, November 24, 2014

Nondisjoint union closed families

A family of sets is nondisjoint union closed if for all pairs of sets in the family whenever those sets have a nonempty intersection then their union is contained in the family. Such families of sets are order connectivity preserving because each dependent component of the family is upper bounded by its union and it is therefore connected.

The laminar families are of course nondisjoint union closed because the only nondisjoint pairs of sets that appear in a laminar family are chains. This means that independent families which never contain nondisjoint pairs and laminar multichain families are nondisjoint union closed.

The union closed families are of course also nondisjoint union closed as they are both disjoint union closed and nondisjoint union closed at the same time. The connectivity complexes are precisely those families of sets that are subunique closed as well as nondisjoint union closed. The connectivity complexes describe the connected sets of a structure which are nondisjoint union closed because if two nondisjoint sets are connected then so is their union.

Sunday, November 16, 2014

Order connectivity preserving families

The order connectivity preserving families are precisely those families whose comparable connected components and dependent connected components are equal. This implies that order connectivity preserving families generalize preorder containment families and irreducible containment families which are two of the major ways of converting partial orders into set systems. Here are some examples of such order connectivity preserving families:
#{#{0 1} #{2 3}}
#{#{} #{0} #{1} #{0 1}}
#{#{0} #{0 1} #{0 2} #{0 1 2 3}}
An example of a family of sets that is not order connectivity preserving is #{#{0 1} #{1 2}}. The two sets #{0 1} a #{1 2} are dependent despite being incomparable so this is not an order connectivity preserving family. Well it is possible to have a family of sets with such intersecting elements that is order connectivity preserving such as #{#{0 1} #{1 2} #{0 1 2}} considering that all uniquely order connected families preserve order connectivity it is only the laminar families which forbid dependent incomparable sets that are order connectivity preserving for all their subsets. All order connectivity preserving multichain families are laminar as is the case with multichain containment families.

Friday, October 31, 2014

Laminar families

The laminar families are precisely those families of sets in which each pair of sets is either comparable or independent. It is therefore implied that the laminar families include both chain families which are precisely those families in which each pair of sets is comparable and independent families which are precisely those families in which ear pair of sets is independent. Here are some such laminar families:
#{#{0 1 2} #{3 4 5}}
#{#{0} #{0 1} #{2} #{2 3}}
#{#{0} #{0 1} #{0 1 2} #{0 1 2 3}}
By definition the intersection of any pair of incomparable sets in a laminar family is the empty set so nullfree laminar families are intersection free. Laminar multichain families which generalize both chain families and independent sperner families are union free in addition to intersection free so they are all examples of extrema free laminar families.

Neighbourhood related families

Given a family of sets and a point in the union of the family of sets the neighbourhood of sets around that point is the family of all sets that contain that point as a member. Given the collection of the neighbourhoods of a given family of sets there are two set systems that we can form from the neighbourhoods using union and intersection.

By taking the intersection of each of the neighbourhoods of the family of sets we can get a preorder containment family and by taking the union of each of the neighbourhoods of the family of sets we can get a adjacencies family. Both of these families are nullfree and the preorder containment family is also union free. The adjacencies family is also subunique free as it is subsingleton free in addition to nullfree.

Tuesday, September 30, 2014

Managing complexity

Complexity is interpreted in a variety of ways. With mereology systems that have more parts tend to be more complex then ones that do not. Within information theory the notion of complexity is determined by Kolmogorov complexity. In computer science there is a notion of complexity called computational complexity which is related to the growth rate of the computation time with respect to argument size.

Information theory

Information theory studies the ways in which we can encode information. This includes the study of the lossless compression of information. Information theory is related to thermodynamics by Landauer's principle which is always related to reversible computing.

Saturday, August 30, 2014

Height two orders and convex families

Given a partially ordered set the convex sets of the partial order form an atomistic convex geometry and the height two partial orders form a subclass closed family. These two families correspond to one another as the minimal family that generates a convex family under the convex closure operation is always going to be a height two partial order. Consider the following height two family:
#{#{0} #{1} #{2} #{3} #{0 1 2} #{1 2 3}}
The convex closure of the above height two family is a family which contains all of the elements of the height two family plus those elements that are necessary to make the family convex:
#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} 
  #{1 2} #{1 3} #{2 3} #{0 1 2} #{0 1 3}}
Certain partial orders can be both height two and convex. These include the dependency families which are the subsingleton closed nullfree rank two families. The dependency families correspond to the simple graphs in graph theory and they can also be produced from any atomistic height two order in which no element has more then two predecessors.

Sunday, August 24, 2014

Independent sets of Moore families

Lets suppose that we have a family of sets that forms a Moore family.
#{#{} #{0} #{1} #{2} #{0 1 2}}
Then the independent sets of that Moore family are precisely those sets that form power sets when intersected with all the sets of the Moore family. Here are the independent sets of the above Moore family:
#{#{} #{0} #{1} #{2}}
If a given Moore family is a family of flats formed from a matroid then the independent sets of that family can be used to reproduce the matroid. If the Moore family is instead an Alexandrov family then the independent sets are the cliques of the complement of the comparability relation of the specialization preorder. This means that the independent sets of an Alexandrov family form a clique complex.

Saturday, May 31, 2014

Monogenic semigroups

The monogenic semigroups are semigroups that are generated by a single element. All semigroups that are generated by at least two elements must contain distinct maximal proper subsemigroups corresponding to those elements. This means that all semigroups that contain only a single maximal proper subsemigroup are necessarily monogenic. Nonetheless, not all monogenic semigroups contain only one maximal proper subsemigroup.

The monogenic semigroups that contain only one maximal proper subsemigroup are called primary monogenic semigroups. Non-primary monogenic semigroups include cyclic groups that are of non-prime power orders. The prime power cyclic groups are called primary cyclic groups and hence they are primary monogenic semigroups. The primary monogenic semigroups can be used to generate the elements of any semigroup.

Friday, May 30, 2014

Perfect graphs

Amongst the set of all graphs the perfect graphs are particularly interesting. Perfect graphs subsume both comparability graphs and co-comparability graphs so they can describe both the comparability and the incomparability conditions of partial ordering relations. As the the perfect graphs exclude odd holes and odd anti-holes they are far easier to describe using partial orders themselves.

The trivially perfect graphs and the co trivially perfect graphs are perfect graphs that are of particular interest to us. They can both be described entirely using preorders produced by the immediate reachability conditions on the graphs. Equivalence graphs are trivially perfect and their complements the complete partite graphs are co trivially perfect.

The threshold graphs are both trivially perfect and co trivially perfect. The threshold equivalence graphs form a Moore family of graphs with their own closure operation defined by split completion. Both empty graphs and complete graphs belong to the class of threshold equivalence graphs.

Wednesday, April 30, 2014

Embedding partial orders in complete lattices

Given a partially ordered set we can always embed that partial order within a complete lattice through Dedekind completion so that partial order becomes a suborder of a complete lattice. For finite unique extrema partial orders this simply means adding bounds to the partial order to make it into a lattice. Otherwise there may need to be elements placed between others such as in the case of the [2 2] weak order.

If we represent partial orders as set systems then the process of embedding the partial order within a complete lattice is equivalent to the process of embedding the set system within a Moore family. We can always acquire such a set system by taking the Moore completion of the family of sets.

The general applicability of lattice theory to problems of order theory through the process of embedding partial orders in complete lattices makes me think that lattice theory should play a fundamental role in our understanding of order theory. With an understanding of complete lattices we can better understand partial orders in general.

Tuesday, April 29, 2014

Representing order elements as sets

Given a partially ordered set we can always represent the elements of that partially ordered set as sets of join irreducible elements even if that set is not a distributive lattice. Consider for example the antichain on two elements #{(0 0) (1 1)} which is not a lattice. This antichain can be represented as the set #{#{0} #{1}}. Likewise larger antichains such as #{#{0} #{1} #{2}} can be represented as set systems.

The set systems that correspond to lattices are Moore families which means that they are intersection closed and they have a closure operation. The union of elements of the Moore family is equal to the closure of their union. Non-distributive lattices such as #{#{} #{0} #{1} #{2} #{0 1 2}} and #{#{} #{0} #{1} #{1 2} #{0 1 2}} can also be represented as set systems which demonstrates the applicability of this representation to non-distributive lattices.

The ability to represent any elements of partial orders as sets makes me think that it makes sense to use sets to represent essentially every mathematical entity. Even entities which aren't typically considered to be sets like numbers and booleans can always be described as singleton sets such that they have a cardinality of one. It is worthwhile nonetheless, to consider the different sets involved within a set system so for example a structured set might have a set corresponding to the underlying set and another set corresponding to the frame of the structure. With this there are different notions of sets in the structure but all the while the structure is still a set of some sort.

Monday, March 31, 2014

Logical foundations of mathematics

The object of mathematics in general is to reason under conditions of certainty. This involves the consideration of logical propositions with truth values such as true and false. With truth values such as true and false we can form predicates that return such truth values and an ontology of such predicates.

With predicates such as sets we can describe every object encountered in mathematics. And with an ontology we can get a clear picture of all these different types of objects. Then we can use logic and our ontology to reason about mathematical objects. By combining certain mathematical knowledge with logical models of uncertainty domains we can use logic to describe all declarative knowledge.

Wednesday, March 26, 2014

Logical models of uncertain domains

Well the set theory and logical predicate calculus provide a good foundation for understanding certain abstract domains we need to extend our logic to be able to deal with uncertainty. Given a system with unknown characteristics then we can create a model of that domain. Models classify uncertain domains by allowing us to apply predicates. Here are two of the simplest kinds of models:
  • Simple models: the simplest possible model of an uncertain domain is a set of values the domain may take. Applying a predicate to such a model yields true if the predicate is a subclass of the set of values of model, false it if it is independent of the set, and unknown otherwise.
  • Probabilistic models: a more advanced type of model is one in which applications of a predicate return probability values. Probabilities should be higher the more general a predicate is so that the probability that an object is an entity is always one.
Given any system with uncertain characteristics we can create a logical model of the system. If our agent is embodied within some environment then it can create a world model of the entire environment including it. If that environment is our physical reality then a world model containing all physical entities and their mereological and causal properties can be produced. In this way logic can be used to organize all declarative knowledge about real or imagined entities.

Sunday, February 23, 2014

Logical organization of declarative knowledge

Mathematical logic provides the foundation for the organization of all declarative knowledge stored by an intelligent agent. By creating an ontology we can organize our knowledge base in terms of the logical classification of entities. The main categories in a logical ontology of mathematical entities are ordered collections, unordered collections, algebraic structures, and elements of algebraic structures. Relations are specified as unordered collections of ordered collections and algebraic structures are specified as a system of relations over a underlying set.

Well Von Neumann ordinals can be specified as unordered collections numbers including naturals, integers, rationals, reals, surreals, complex numbers, numbers, surcomplex numbers, quaternions, octonions, among others can be specified as elements of algebraic structures. In this way the four categories of the upper ontology described previously are sufficiently powerful to classify most mathematical entities.

The only limitation of this approach to classification is that partially observable systems cannot be described as mathematical structures in the traditional sense. Nonetheless, it is my contention that we can represent the set of states a partially observable system may take and reason about them using logic. We can enrich the system with a mereology and then form a logical ontology of parts of the system.

Well it is certainly true that logic provides an ideal foundation for the formalization of all declarative knowledge this doesn't mean that we don't need more then this for general intelligence such as a system of procedural knowledge for approximate optimization, a module system for loading domain specific knowledge such as interaction, and an advanced learning system for acquiring new knowledge and transforming modules.

Tuesday, February 18, 2014

Classification of partially observable systems

Our logical ontology provides us with the means to classify abstract fully observable systems such as combinatorial games. This approach places mathematical entities into an advanced ontology that includes lists, sets, relations, and algebraic structures among others. Partially observable systems such as spacetime provide us with the conundrum of determining how to classify and identify entities based upon uncertain and limited perceptual information on the external environment.

It is my contention that the methods of mathematical logic should be extended to deal with partially observable systems by providing the means to classify entities based upon a limited set of observations about them. Given a partially observable system the process of classification involves taking the environment and classifying it as an entity and then receiving additional information and using that to further specify the class of our environment.

Given our observations we deduce that physical reality is composed of galaxies, star systems, planets, molecules, atoms, subatomic particles, and various other classes of concrete entities. All of these different concrete entities are parts of the universe in the logical mereology. The universe is the top level entity in the mereology and all other instances of concrete entities are parts of it.

Friday, February 14, 2014

Signatures of algebraic structures

Algebraic structures have signatures associated with them. These signatures specify the set of relations defined over the underlying set of the algebraic structure. Here are a few signatures:
  • Semiring: (S + *)
  • Ordered group: (S <= +)
  • Ordered ring: (S <= + *)
  • Ordered differential composition ring: (S <= + * c d)
The internal relations of algebraic structures are used to define mathematical objects such as numbers and games. Games are algebraic structures with a binary relation move between positions and a unary relation winning that tells rather or not a given position is winning or not.

Tuesday, February 4, 2014

Subalgebras and reducts

Given an algebraic structure with a variety of symbols such as addition and multiplication associated with it we can take subalgebras of the structure and reducts of the structure. Subalgebras are produced by taking a subset of the underlying set of the structure. Reducts are produced by taking a subset of the set of symbols associated with the structure.

For example an additive group (S,+) may be a reduct of a field (S,+,*) and an ordered group (S,<=,+) both of which are reducts of an ordered field (S,<=,+,*). A subreduct of a structure is a substructure of the algebraic structure that is both a subalgebra and a reduct because it uses a subset of the underlying set and a subset of the set of symbols used by the structure. The ring of integers is a subreduct of the ordered field of rational numbers.

Saturday, February 1, 2014

Algebraic structures and symbols

When I first constructed my system for dealing with algebraic structures I only provide support for structures with a pair of operations like rings and fields which were numbered so there were no symbols involved.
  • <= comparison
  • + addition
  • * multiplication
  • c composition
  • d differentiation
  • m metric
  • w weight
The first five of the above symbols are used for ordered differential composition rings like those of transseries. The second two describing metric and weighting functions subsume what was previously provided by the weighted hypergraphs system. Vector spaces will also be provided with the scalar multiplication operation being denoted by the symbol s for now.

Sunday, January 12, 2014

Weighted hypergraphs

The idea of a weighted hypergraph provides a suitable generalization of weighted graphs, metric spaces, and measure spaces. Predicates are provided for each of these classes of weighted hypergraphs in the system:
(metric-space? 
  (weighted-hypergraph. 
    #{0 1 2} 
    {#{0} 0, #{1} 0, #{2} 0, #{0 1} 1, #{0 2} 1, #{1 2} 1}))

(measure-space?
  (weighted-hypergraph.
    #{0 1}
    {#{} 0, #{0} 1/2, #{1} 1/2}, #{0 1} 1}))
Amongst the measure spaces there is a class of distributions whose weights all range from zero to one inclusive. Amongst the distributions there are special classes of distributions such as uniform distributions and degenerate distributions among others.

Saturday, January 11, 2014

Alexandrov topology

Given a preorder we can form a special kind of topology called an Alexandrov topology and given such a topology we can go back to the preorder so we have a bijection between the class of preorders and the class of Alexandrov topologies. Here is an example of Alexandrov topology formed by a partial order:
(= (alexandrov-topology (weak-order [#{0} #{1} #{2}]))
   (hypergraph.
     #{0 1 2}
     #{#{} #{2} #{1 2} #{0 1 2}}))
Using the specialization preorder function we can specify classes of Alexandrov topologies that correspond to classes of preorders in our ontology. Here are a few such classes of topologies:
(def partition-topology?
  (comp equivalence-relation? specialization-preorder))

(def discrete-topology?
  (comp antichain? specialization-preorder))

(def trivial-topology?
  (comp complete-relation? specialization-preorder))
Topology is based upon the inclusion order of sets provided by the ontology and the specialization preorder so I think that it is fair to say that topology is based upon order theory.

Friday, January 10, 2014

Partial orders and complementation

Given a bounded lattice we can form a symmetric binary relation of that relates elements to one another if they are complements of one another. Here are some examples of complementation relations produced from bounded lattices:
(= (complementation-relation (weak-order [#{0} #{1} #{2}]))
   #relation{
     :vertices #{0 1 2}
     :edges #{[0 2] [2 0]}})

(= (complementation-relation (weak-order [#{0} #{1 2} #{3}]))
   #relation{
     :vertices #{0 1 2 3}
     :edges #{[0 3] [1 2] [2 1] [3 0]}})
We know that complemented lattices are those bounded lattices that have functional complementation relations and uniquely complemented lattices are those bounded lattices that have complementation relations that are involutions.
(= (complemented-lattice? order)
   (unary-operation? (complementation-relation order)))
(= (uniquely-complemented-lattice? order)
   (involution? (complementation-relation order)))
It is worth noting that the complementation relation itself can be partially ordered by the complementary pairs ordering function to get a partially ordered relation.

Thursday, January 9, 2014

Partial orders and betweenness

Given any partial order we can produce a ternary betweenness relation defined by the condition that b is between a and c if either a <= b <= c or c <= b <= a. Here is an example of a betweenness relation corresponding to a partial order relation:
(= (betweenness-relation (weak-order [#{0} #{1} #{2}]))
   #user.relation{
     :vertices #{0 1 2}
     :edges #{[2 1 0] [1 0 0] [2 2 1] [1 1 1] 
              [0 0 1] [1 2 2] [0 1 2] [2 1 1] 
              [2 2 2] [1 1 2] [0 0 2] [2 0 0] 
              [2 2 0] [1 1 0] [0 0 0] 
              [0 1 1] [0 2 2]})
Like with the ternary relations of infima and suprema the ternary relation of betweenness preserves the connectivity of the underlying partial order.
(= (connected-components order)
   (connected-components (betweenness-relation order)))
A convex set of a betweenness relation is a set that includes all elements between its members. Ordered geometry uses betweenness relations as part of its foundation as we can define the elements that are between any points in a geometric space.

Wednesday, January 8, 2014

Partial orders and extrema

Given any partial ordering relation we can form ternary extrema relations of suprema and infima based upon least upper bounds and greatest lower bounds. These extrema relations necessarily are idempotent, commutative, and have the generalized associative property. However, in general these ternary relations are not either magmas or even binary operations for that matter.
(false? 
  (binary-operation? 
    (infima-relation (weak-order [#{0 1} #{2 3}))))

(binary-operation? 
  (infima-relation (weak-order [#{0 1}]))))

(false? 
  (magma? 
    (infima-relation (weak-order [#{0 1}]))))
In order for the extrema relations of a partial order to be binary operations the partial order [2 2] must be forbidden as a suborder. Since lower and upper forests are defined as suborders of [2 2] they are examples of partial orders with unique extrema. If a commutative idempotent associative binary operation is a magma it is a semilattice so there is a clear correspondence between partial orders that are meet or join semilattices and extrema relations that are magmas. Another interesting property is that connectivity is maintained by the extrema relation:
(= (connected-components order)
   (connected-components (infima-relation order))
Zero elements and identity elements in extrema relations correspond to upper and lower bounds in the underlying partial order relation.

Tuesday, January 7, 2014

Ontology of modules

In order to facilitate the use of modules it may be useful to categorize the modules available the systems into an ontology. This ontology would be combined with an ontology of logical entities in order to form the core system of a modular intelligence. The system of logical entities in the core system is not our main interest in categorizing modules but rather our main interest is the system of modules that extend our core logic.

Therefore in addition to the category of logical components there should be categories for temporal and computational tasks such as state management and scheduling, perceptual learning tasks that involve reasoning under uncertainty, and for interaction with external entities such as through natural language processing.

An AI without modules dealing with interaction and social relations could be an excellent astronomer for example in that it could perceive the universe around it but it wouldn't have the ability to communicate those results to people who are still dependent upon natural languages. In order to do that the AI may have to load an interaction module.

Monday, January 6, 2014

Module dependencies

Modules may depend upon other modules for their use. The dependency relation should be a preorder as every module depends upon itself and if one module depends upon another which depends upon another that first module depends upon the last. Furthermore, if there are cyclic dependencies such that one component depends upon another component those components should be combined together to form a single module so dependencies should be antisymmetric and therefore a partial order.

Along with the dependencies order in the module system our core should also contain the generalization order of an ontology. The ontology may be used to categorize modules themselves based upon the things that they are dealing with like I/O, file systems, graphics, sound processing, etc. This demonstrates that an ontology can play a complementary role to the module system.

Saturday, January 4, 2014

Modular intelligence

I am designing a modular framework for artificial intelligence programming. The core system will contain the ontology and module system as well as information about preferences and goals. In this sense the core system will be mostly declarative as it will specify what the agent wants, what classes of entities exist, and what modules are out there and so it will be up to the module system to provide specific knowledge about how to do things.

The modules in the system will be uncertain and context dependent so they will be changing a lot over time. Machine learning algorithms like reinforcement learning and supervised learning should be used to help shape module space. A system with highly advanced machine learning capabilities such as a seed AI could radically transform module space.

Perhaps the most important component of the module space will be the perceptual cortex which will contain all the functionality related to perception and reasoning under uncertainty. An initial perceptual cortex could be built based upon OpenCV as it has many of the perceptual capabilities one could hope for. Another important class of modules are interaction modules which include modules dealing with user interfaces and language processing.

Wednesday, January 1, 2014

2013 year in review

This last year has had a considerably transformative effect on me. After seeing the considerable usefulness of orders to partitioning and decomposing entities into parts and places I decided to switch my primary focus to order theory. I made partial orders the core of my computer algebra system and I begun to explore the concepts of order theory in more detail.

By examining the ways in which enumerations could be combined I also stumbled upon ordinal numbers. I then realized that the number system should not be limited to finite numbers and instead it should be extended to include transfinite numbers like the ordinals. From there I stumbled upon the surreal numbers and transseries and I have been working on implementing them ever since.

My interest in order theory led me to consider the different classes of partial orders such as antichains, total orders, weak orders, interval orders, and series parallel orders and the fact that these are themselves ordered by inclusion. This led me to build an ontology of my own and to consider other ontologies that other people have constructed such as Dolce, Cyc, SUMO, and GFO.

Through my examination of these different ontologies I begun to consider fundamental questions of how an ontology should be constructed. One of my conclusions which is encouraged by the results of causal set theory is that the ontology of concrete entities should be an ontology of processes and events which may be related to one another causally.

After this I begun to consider how my reasoning engine and ontology could be extended to deal with more general AI applications. It is my conclusion that my logical core should be extended with modules to dealing with uncertainties such as procedural uncertainty and declarative uncertainty. The core of my AI framework should then be a combined ontology and module system.