tag:blogger.com,1999:blog-86778555106746729462017-11-29T04:37:45.776-08:00Lisp AIjhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.comBlogger227125tag:blogger.com,1999:blog-8677855510674672946.post-85770343631962228952017-08-24T22:09:00.000-07:002017-08-24T22:09:02.058-07:00Geodetic graphsGeodetic graphs have the particular property that each pair of points has a unique shortest path between them, or geodesic. Trees are a special case of geodetic graphs in which each pair of points has a unique path in general between them. Block graphs are sometimes called clique trees, they include trees and also happen to be the chordal geodetic graphs.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-56052052114160438422017-04-03T01:44:00.001-07:002017-04-03T03:01:02.912-07:00Partition logicThe logic of set partitions is a fundamental part of the analysis of ordering relations. The set partitions necessarily form a lattice which has certain properties corresponding to its join and meet operations. At the same time, the elements themselves form a Moore family depending upon which direction you intend to take the ordering. The Moore family then necessarily comes with a corresponding closure operation.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-86973928549166975592017-01-01T18:53:00.001-08:002017-03-29T06:05:05.027-07:002016 year in reviewThe methods of propositional logic can be applied to situations that arise from boolean algebra. Boolean formulas are applicable to any boolean algebra structure rather it is booleans themselves or sets, classes, and other predicate like structures. Set theoretic operations like union, intersection, difference, and symmetric difference can be expressed in terms of boolean formulas. These set theoretic operations are not unlike the logical connectives defined by these same boolean formulas. <br /><br />At the same time, a wide variety of constraint satisfaction problems like sudoku can be expressed in terms of boolean formulas. Boolean formulas defined by clauses that have no more then two elements are equivalent to implication graphs. Backtracking search methods can be used to solve constraint satisfaction problems like sudoku and implications can be used to narrow down the search space for any partial candidate solution in the backtracking search. <br /><br />The exact solutions to constraint satisfaction problems can therefore be deduced. In the vast majority of cases exact constraint satisfaction methods are not applicable and we need to use heuristics and statistics instead to get approximate solutions to optimization problems.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-91821513344474518002016-12-16T21:12:00.002-08:002016-12-16T21:12:52.285-08:00Boolean algebra equationsBoolean algebra equations can be built from meet, join, and complementation based upon the distributive law and the fact that complementation is an involution. These boolean algebra formulas can be put into conjuctive normal form or disjunctive normal form based upon which lattice operation is going to be at the highest level of nesting. These boolean algebra equations are applicable to any boolean algebra rather it is truth values or entire sets. Propositional logic formulas then can be defined based upon the principles of boolean algebra.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-19076398071697041902016-09-24T23:11:00.001-07:002016-09-24T23:11:08.687-07:00Propositional logic formulasPropositional logic deals with the truth values of propositions and how they are related through logical connectives. In general propositional logic formulas can be represented using conjunctive normal form or disjunctive normal form. These propositional logic formulas have a wide variety of general applications. In particular, numerous constraint satisfaction problems can be described as boolean satisfiability problems in propositional logic. Constraint satisfaction is a vital area of interest in propositional logic.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-15487855266858347482016-06-30T23:22:00.001-07:002016-06-30T23:22:20.077-07:00Families of kuratowski pairsFamilies of kuratowski pairs which are set systems that define a pair between two elements fully characterize correspondences between sets. It is by using families of kuratowski pairs that we can deal with questions of relation algebra. Each family of kuratowski pairs necessarily has rank at most two because each kuratowski pair has a maximum cardinality of two. This means that these are rank limited set systems.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-54434887406112223172016-06-15T22:19:00.001-07:002016-06-15T22:20:19.533-07:00The rank of set systemsGiven a set of sets then the rank of that set system is the maximum cardinality of the sets it contains as members. We can determine certain characteristics of a set system based upon their rank. Set systems of rank at most one are rank complete which means they are like a set which may or may not contain the empty set. Set systems of rank at most two include as a particular case set systems that define comparability. This process can be extended further to determine properties of the rank of higher set systems. <br /><br />The rank property can also be used to understand sets of sets of sets. Given a sets of sets of sets then the rank is the maximum cardinality of a set of sets contained in the set of sets of sets. We can deduce that families of kuratowski pairs necessarily have a rank of at most two because the pairs never have more then two members. The families of kuratowski pairs effectively generalize correspondences between sets. Kuratowski pairs also have the property that their union has at most two elements so the rank of the set of unions is at most two which makes the ranking property even stronger for them.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-29882358536803304642016-05-25T01:11:00.002-07:002016-05-25T01:11:31.844-07:00Relation algebraWe can establish a theory of binary relations in terms of their ordering as well as composition and transposition. The composition of binary relations generalizes the notion of composition of functions. Functional binary relations merely have a functional dependency from their input argument to the output argument. The inverse functional binary relations are their transpose. One to one binary relations are both functional and inverse functional. The composition of one to one binary relations is a one to one binary relation. Symmetric binary relations are equal to their transposition. The involutions are symmetric as well as functional. These properties allow us to better understand binary relations in terms of composition and transposition.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-77523611971250437692016-03-12T22:14:00.002-08:002016-03-12T22:14:37.531-08:00Incidence order of graphsThe incidence order of a graph is a type of partial order that forbids three different partial orders [1 1 1], [2 2], and [3 1]. If these three partial orders are forbidden as suborders then the partial order may be embedded in the incidence order of a graph. This defines the suborder closure of the class of incidence orders of graphs. In order for a partial order to be an incidence order of a graph all of its non-minimal elements must also have exactly two parts. <br /><br />If this final condition is met then the join representations of the partial order correspond to a dependency family. There is a complementary condition produced by the transposition of the incidence order of a graph. Only those graphs which have locally at most two elements meet this suborder condition in their transposition. All graphs can be produced from the join representations of a partial order that meets these conditions.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-32139903957675873962016-01-02T10:15:00.001-08:002016-03-03T02:38:16.452-08:002015 year in reviewWithin the year 2015 it was realized that it can be useful to study pure set theory. By studying pure set theory we are also dealing with pure ontology. We are classifying sets entirely in terms of their own properties as sets. We can use set systems in order to define preorder containment families and alexandrov families which correspond to one another. We can also define dependency families in accordance with this process. Dependency families can be defined as the join representations of certain preorder containment families. Though we can deal with sets of sets as a particular case we can also deal with sets of sets of sets. These allows us to deal with structures which we could not effectively define simply with sets of sets. In this way we are still dealing with pure ontology as we are defining sets entirely in terms of sets. As we create a pure ontology dealing with sets and classes defined entirely in terms of themselves we can later extend this ontology to deal with particulars but in the end the pure ontology is the foundation of this.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-17036399517767553212015-08-31T04:12:00.001-07:002015-09-25T13:02:54.284-07:00Threshold graphs and interval ordersThreshold graphs like interval orders have the property that each element is determined by some vertex invariant in all substructures. In threshold graphs all elements are determined by degree. In interval orders all elements are determined entirely by their interval representations. Both of these properties are maintained in forbidden substructures of each of these structures. Weak orders are the special class of interval orders whose elements are determined in terms of degrees. Threshold orders are interval orders with threshold comparability.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-34732961139952196522015-05-30T20:59:00.001-07:002015-09-25T12:47:45.655-07:00Weakly chordal graphsThe weakly chordal graphs are a subclass of the perfect graphs that exclude all holes and antiholes. The weakly chordal graphs are an important class of graphs in order theory. Well the class of weakly chordal graphs does not include all comparability graphs or all cocomparability graphs it does include all permutation graphs which are the graphs that are both comparability and cocomparability. This means it also includes the cographs which also happen to be permutation graphs. <br /><br />The chordal graphs as well as their complements the cochordal graphs are weakly chordal. The trivially perfect graphs are precisely those graphs that are both chordal and cographs. The cotrivially perfect graphs are precisely those graphs that are both cochordal and cographs. The trivially perfect graphs and the cotrivially perfect graphs can both be expressed entirely in terms of preorders. Only weakly chordal graphs can be described entirely in terms of preorders in this sense.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-55019398098493894342015-04-30T22:32:00.002-07:002015-09-25T12:32:20.100-07:00Comparisons between setsWe can produce certain comparisons between sets such as based upon the intersection size. This is what leads to the classes of independent, linear, and antidisjoint families of sets. The independent families have no intersection between elements. Linear families have no intersection larger then one. And the antidisjoint families are complementary to the independent families in the sense that no elements lack intersection. Pairs of sets can only either be comparable or incomparable which is what leads to chain families and sperner families. In chain families each pair of sets is comparable. In sperner families each pair of sets is incomparable. Laminar families are produced by the union of independence and comparability as each element is either comparable or it has empty intersection. In uniform families each element has the same size. Each of these comparisons between sets corresponds to a clique family. The dependence condition of antidisjoint families produces line graphs and the comparability condition produces comparability graphs and cocomparability graphs of subclass containment orders.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-47263768948461256072015-03-30T19:49:00.001-07:002015-09-25T12:24:03.100-07:00Forbidden subfamiliesGiven a set theory we can classify families of sets based upon forbidden subfamilies. As with most classes determined by forbidden substructures the classification of families based upon forbidden subfamilies is characterized based upon the size of the largest forbidden subfamily. If the largest forbidden subfamily is of size one then the class is going to be a power set of some family often determined by cardinality. If the largest forbidden subfamily is of size two then the class is going to be a clique family because it is generated by the dependencies between pairs of elements. Another issue is the smallest forbidden subfamily. All families with size greater then the forbidden size will be accepted automatically. The two issues of the largest and smallest size of a forbidden substructure help to determine nature of subclass closed families.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-56105428049056987342015-03-28T19:41:00.001-07:002015-04-25T03:32:21.926-07:00Algebraic set theoryThe theory of sets can be described by a boolean algebra equipped with a singleton function which converts between any atom in the boolean algebra into its corresponding member value. Sets can then be described within this algebraic structure entirely in terms of the join operation of the boolean algebra and the singleton function. This allows us to describe sets entirely in terms of algebraic set theory. <br /><br />The only element in a boolean algebra which does not contain any atoms is the lower bound element of the boolean algebra. By using this lower bound element, the join operation of the boolean algebra, and the singleton function we can produce elements of the pure elements of the algebra. These pure elements correspond to the pure sets which we generally encounter in set theory. Some algebras of sets are limited to only pure elements and others are not.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-38013682035168974782015-02-28T22:01:00.001-08:002015-04-25T02:44:34.847-07:00Atoms of a latticeGiven a distributive lattice then we can determine that the atoms of that lattice are those elements that cover the lower bound of that lattice. In other words they are the singleton elements of that lattice. For example in the case of the lattice of sets under inclusion the atoms of that lattice are the singleton sets. The atoms of a lattice play an interesting role in the description of that lattice. <br /><br />In the case of the lattice of sets we find that any given entity can be converted to a singleton set containing only that entity and likewise any singleton set containing only a single entity can be converted into back into that entity. This means that the function to convert entities into singleton sets is a one to one correspondence. This singleton function is not described by the order on the sets so it is outside of the underlying order theory. A lattice ordered structure can be extended with such a singleton function to be produced a more advanced structure of this sort.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-8207479051975794552015-01-01T19:28:00.001-08:002015-04-25T02:18:39.211-07:002014 year in reviewWithin the year 2014 I maintained my focus on order theory and then I began to examine set systems which are equivalent to suborders of a boolean algebra. Being a suborder each set system is partially ordered and each partial order can be embedded into a boolean algebra often in a variety of ways. In particular, given a partial order we can convert that partial order into the set system by taking the set of all sets of elements of principal ideals of that partial order. We can also convert that partial order into a distributive lattice by taking the set of lower sets though that does not preserve order. In this way the theory of set systems subsumes the theory of partial orders. Everything we can say about partial orders can also be expressed in terms of set systems. As a result of this fact, set systems became a primary concern of mine in the past year. <br /><br />Through my exploration of set systems as suborders of boolean algebras I later came to consider suborders of other distributive lattices. In particular, we can consider suborders of distributive lattices that are defined by multiset inclusion. In this way we can examine the idea of multiset systems in addition to set systems. An interesting facet of the theory of multiset systems is that we can convert any ordered collection into a multiset system regardless of cardinality just as we can convert any ordered collection into a set system using the kuratowski pair. After considering the theory of suborders of distributive lattices like these we can generalize and then consider the theory of suborders of a partial order in general. <br /><br />As the notion of set systems as suborders of a boolean algebra has been explored my ontology has continued to expand as these notions have been explored. As a result an ontology of set systems including a wide variety of classes of set systems has been produced including classes of set systems which are defined entirely by their order characteristics. In this way the ontology has expanded to deal with sets as well as sets whose members are all sets. These are distinguished from objects which are not ontologically classified as sets and sets which contain elements that are not classified as sets. As an ontology deals with sets and classes itself it is sensible that one of the most basic things to be classified in an ontology are such sets and classes. This is the approach that I am now taking to ontology engineering.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-88710973269960492902014-12-31T19:50:00.001-08:002015-01-01T00:54:55.218-08:00Structural specializationThere 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. <br /><br />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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-89321699575695526032014-12-16T20:31:00.002-08:002014-12-16T20:40:04.390-08:00Multiset systemsOne 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. <br /><br />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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-21056667270913424972014-11-26T21:59:00.001-08:002014-12-02T16:31:18.780-08:00Disjoint union closed familiesThe 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. <br /><br />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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-7940871715232430142014-11-24T23:27:00.001-08:002014-12-02T16:16:07.456-08:00Nondisjoint union closed familiesA 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. <br /><br />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. <br /><br />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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-59333218987496480562014-11-16T23:25:00.001-08:002014-11-16T23:57:57.514-08:00Order connectivity preserving familiesThe 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: <pre class="brush:clojure"><br />#{#{0 1} #{2 3}}<br />#{#{} #{0} #{1} #{0 1}}<br />#{#{0} #{0 1} #{0 2} #{0 1 2 3}}<br /></pre> 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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-62372984815061170802014-10-31T01:20:00.001-07:002014-11-16T23:57:14.346-08:00Laminar familiesThe 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: <pre class="brush:clojure"><br />#{#{0 1 2} #{3 4 5}}<br />#{#{0} #{0 1} #{2} #{2 3}}<br />#{#{0} #{0 1} #{0 1 2} #{0 1 2 3}}<br /></pre> 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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-77145777327890903682014-10-31T01:19:00.001-07:002015-09-25T12:35:47.409-07:00Neighbourhood related familiesGiven 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. <br /><br />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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0tag:blogger.com,1999:blog-8677855510674672946.post-76492004892813450672014-09-30T23:28:00.001-07:002015-04-25T01:45:09.748-07:00Managing complexityComplexity 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.jhunihttp://www.blogger.com/profile/05342856856194792634noreply@blogger.com0