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.