Multiset theoretic definition of the ordered pair

It is well known in set theory that the ordered pair can be represented by set systems like {{a}} or {{a} {a b}}. Either of these set systems can be combined to form the multisets {a} and {a a b}. This leads to the multiset theoretic definition of the ordered pair. This puts the element with the highest multiplicity first before the second element with less multiplicity. This is necessary so that the multiset corresponds to a set system so {a} corresponds to {{a}} and {a a b} coresponds to {{a} {a b}.

One immediate consequence of this fact is that all binary relations can be represented as sets of multisets. Well it is clear that graphs and preorders, both of which can be considered to be types of binary relations, can be represented as set systems, there are certain other binary relations that cannot be represented as set systems well all binary relations can be. The multiset theoretic definition of binary relations corresponds then to the set of combinational multisets of a set of kuratowski pairs which is a set of sets of sets.

Set theory in a multiset theoretic context

Set theory is the basic foundation of mathematics, but we can consider certain aspects of set theory from a multiset theoretic perspective. Sets can be considered to be special types of multisets and set systems can be considered to be special types of multiset partitions. In order to get the multiset corresponding to a set system, you can get the combinational multiset of the set system by combining each set counting multiplicity. The multiplicity of each element in this multiset is the degree of the element in the set system.

• Sets : multisets with repetitiveness zero
• Set systems : distinct multiset partitions with distinct parts

Set systems come in different forms based upon the multisets that they partition. General set systems have various different combinational multisets that come in various degrees of repetitiveness. If the combinational repetitiveness of the set system is zero, then the set system is a set partition. If the combinational repetitiveness is one, then it is pseudoindependent. Well general systems partition multisets, set partitions partition sets. As the set systems with the smallest combinational repetitiveness, set partitions will play a fundamental role in our ontology.

• Set partitions: set systems whose combinational multisets are also sets
• Pseudoindependent families : set systems whose combinational multisets have max repetitiveness one

The isomorphism types of set partitions are equivalent to the signatures of multisets, as multisets are essentially sets that have a set partition associated with them. The set partition associated with a multiset tells which elements are repetitions of one another, well for a set this is simply trivial. This demonstrates why set partitions and multisets must be two of the most basic elements of the ontology. With this realized, there are two types of partial orders that are immediately realised on set partitions and set systems in general:

• Degree reduction ordering
• Refinement and coarsification ordering

The importance of the degree reducing ordering of set systems was already described as it demonstrates the simplification of set systems, and the operation of taking the combinational multiset is monotone with respect to the degree reduction ordering. This makes multisets a fundamental part of set theory. The refinement and coarsification ordering determines the degree to which a set system is partitioned, rather then the element it is partitioning. The refinement ordering on set partitions is especially important as it describes the extent to which a set is partitioned. Multisets can also be coarsified, for example, given a set system which has the finest partition we can get the multiset of cardinalities of that set system which can coarsify the collection to some extent based upon cardinality equality. This demonstrates the relation between multisets and set partitions.

Multiset repetitiveness

Once we accept that our pure set theory must be enriched with multisets which can be produced from any set system by combining sets counting multiplicity, then it is interesting to consider how sets fit into the picture of multiset theory. Given any multiset we can get the distance from that multiset to a set under the multiset ordering, which is essentially the repetitiveness of the multiset.

(defn repetitiveness
  [coll]

  (- (count (multiset coll))
     (count (set coll))))

This means that sets are essentially repetitiveness zero multisets. More interesting though is the concept of near-sets which are multisets which have no more then a distance of one from a set. So the most set like multisets are sets themselves, then near sets, then near near sets, and so on. As you can see, there is a hierarchy of different degrees of setness in multiset theory.

Degree reductions

Sets can be simplified by taking subsets of them. Set systems on the other hand can be simplified not only by taking subsets of them, but also by taking subsets of their members. Taking a subset of a member necessarily reduces the degree of some union member of the set system, which is the number of times it is included in different sets of the set system. So taking subsets of members are degree reductions. I will demonstrate this without the nullfree degree reductions, which don't use the empty set. Set partitions are pairwise disjoint so their degree reductions form a boolean algebra. The size of this boolean algebra is determined by the order of the set system rather then its cardinality.



In my brief survey of the smallest set systems, I described the fact that the set theoretic definition of the ordered pair, the kuratowski pair, is in fact the simplest type of set system that isn't pairwise disjoint. It is therefore, also the simplest type of set system whose degree reductions do not form a boolean algebra. In fact, its degree reductions don't even form a lattice, as can clearly by the weak ordering below. The set systems #{#{0}, #{1}} and #{#{0 1}} both have the same degree signature and share the same reductions without a common reduction between them.



To demonstrate further, the degree reductions of the power set like set system with degree signature 2,2 is displayed below. This in some sense, the next simplest type of set system after the kuratowski pair. It also forms a weak ordering, but with a clearly greater height.



Another small set system, the kuratowski pair unioned with a pairwise disjoint member produces a different degree reductions partial order. This order is also not a lattice, just like the kuratowski pair order, nor is it a weak order. Instead, it is the product order of the weak order of the kuratowski pair with a size two total order. As the boolean algebra is a product order of total orders, it follows that all the orderings so far have been product orders of weak orders. The degree reductions order is a product order of the degree reductions of each of the intersection connected components of the partial order, so pairwise disjoint set systems form boolean algebras.



The next set system with cardinality sum four with a slightly larger degree reductions partial order comes from the order three chain seen below. This set system #{#{0} #{0 1 2}} has two kuratowski pairs as immediate degree reductions and two set partitions, determined by reducing degree one elements or degree two elements. Reducing the degree two elements produces set partitions and reducing degree one elements produces kuratowski pairs. As kuratwoski pairs are weak orders and not lattices, this order isn't a lattice either. Only the set partitions form boolean algebras.



This demonstrates what I am talking about when referring to degree reductions, so that it is clear what this concept means. Now there are two types of simplifications of set systems: subsets of the set system and degree reductions taken from subsets of the members of the set system. These two orderings are the main things that have determined by thoughts on pure set theory.

Cardinalities

When studying elementary set theory, the most basic thing that one reasons about sets is their cardinality. A set can only be a subset of another if its cardinality is less then its cardinality. In other words, the cardinality forms a monotone function on partially ordered sets, the sets partially ordered by a boolean algebra, and the cardinalities totally ordered.

Sets -> Cardinalities

Degree multisets and signatures

Given a set system we can form a multiset from that set system, by combining all of its elements counting multiplicity so for example #{#{0} #{0 1}} can be combined to get the multiset {0 0 1}. The degree of some union member of the set system is the number of sets it belongs in, so this is fully determined by the combinational multiset. The operation of taking the multiset associated a set system is a monotone function associated with the degree reductions order rather then the subset reductions order. The distributive lattice of multisets can then be mapped by a monotone function again to the set of signatures ordered by the Young's lattice.

Set systems -> Multisets -> Signatures

All these foundational concepts emerge directly from pure set theory, without the need for any additional structures. As all the introduced concepts like cardinalities, multisets, and multiset signatures all form distributive lattices, they can be represented as sets with their lattice operations left in tact so we don't really leave the domain of pure set theory.

Representing graphs and preorders as set systems

In the fundamentals of combinatorics I previously described the fact that preorders and graphs are the most fundamental objects of study in combinatorics. Further, I described how interrelated graph theory and order theory are. Graphs such as the comparability graph can be formed from any preorder, and the adjacency containment preorder can be formed from any graph. For trivially perfect graphs, which are the comparability graphs of trees, these preorders fully determine the graphs. The selection of preorders and graphs as fundamental was not random, but rather it was determined by the fact both structures can be represented by set systems. They are among the simplest set systems that can be formed by rank.

One of the reasons to privilege set systems among all other structures is that set systems can be used to describe the classified substructures of any structure. This means that graphs can be fully determined by certain substructures of a structure like the cliques of a graph, or the chains of a partial order which determines the inclusion comparability graph of the order. Likewise, preorders can be formed by certain classified substructures, such as the numerous cases of sets of substructures determined by a closure operation generated by its singleton elements. As set systems are the basic way of describing substructures, graphs and preorders as special cases of them are fundamental concepts.

Graphs:

Independency families
Independency families are nullfree subsingleton free rank two families. In other words all of their sets are either size one or two and the size one sets are not subsets of the size two sets, which means that all the size one or singleton sets are isolated. This means that they are sperner families, as no set is contained in one another.

#{#{0 1} #{0 2} #{1 2} #{2 3}}
#{#{0 1} #{0 2} #{1 2} #{1 3} #{2 3}}

Dependency families
Dependency families are nullfree subsingleton closed rank two families. In other words, they are subnonnull closed set systems, as all the subsets of any set other then the empty set are included in the set. This makes them the rank two counterpart to the independency families. Dependency families are fully determined by their incidence order, which makes them an ideal means of representing graphs. Dependency families form a strongly unique extrema part width two height two partial order under inclusion. The maximal cliques of a cluster graph form a set partition.

#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{2 3}}
#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{1 3} #{2 3}}

Maximal cliques families
Maximal clique families are another sperner family representation of graphs, which means that the ordering properties of the set system tell us nothing here as well. The difference from independency families is that the maximal clique families are not necessarily rank two. Instead, they are of conjunctive rank two, in the sense that they are a rank two set system.

#{#{0 1 2} #{2 3}}
#{#{0 1 2} #{1 2 3}}

Clique families
The clique families are another set system that are of conjunctive rank two, which essentially means that the goal clauses of conjunctive form of the set system are not a size greater then two. All representations of graphs are in some sense rank two, because they are fundamentally generated by pairs of elements. Like the clique families, these are ordered set systems, except that they form a meet semilattice rather then a strongly unique extrema order, making them more lattice like. In fact, these are the total join representations of a atomistic meet semilattice.

#{#{} #{0} {1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{0 1 2} #{2 3}}
#{#{} #{0} #{1} #{2} #{3} #{0 1} #{0 2} 
  #{1 2} #{1 3} #{2 3} #{0 1 2} #{1 2 3}}

Preorders

Preorder containment families
Given any preordering relation we can form the principal ideals of the preorder, by the input sets of the elements of the preorder. This fully preserves the specialization order of the preorder through the inclusion order of the set system, which makes this an ideal representation for preorders. A partial order with some property is represented by an order containment family with the same property. As a result, when thinking of preorders I tend to think of preorder containment families as the canonical representation of them.

#{#{0} #{0 1} #{0 2} #{0 1 2 3}}
#{#{0} #{1} #{0 1 2} #{0 1 3}}
#{#{0 1} #{2 3} #{0 1 2 3 4 5}}
#{#{0 1} #{0 1 2 3} #{0 1 2 3 4 5}}

Alexandrov topologies
Alexandrov topologies are topologies that are both union closed and intersection closed. In other words, they are null extrema closed families. It is known that these families are represented entirely by their specialization preorders. In fact, all finite topologies are Alexandrov topologies, which can be represented by their preorders. An Alexandrov topology can be formed from a preorder by taking all lower sets of the preorder, rather then simply the principal ideals. The corresponding preorder containment family can be produced by the join irreducible member sets of the topology or the singleton closures. These families are conjunctive rank two as well except they are logically generated by definite clauses rather then goal clauses.

#{#{} #{0} #{0 1} #{0 2} #{0 1 2} #{0 1 2 3}}
#{#{} #{0} #{1} #{0 1} #{1 2} #{0 1 2}}
#{#{} #{0} #{1} #{0 1} #{0 1 2} #{0 1 3} #{0 1 2 3}}
#{#{} #{0 1} #{0 1 2 3} #{0 1 2 3 4 5}}

Set systems of small size

In the most general sense, the size of any entity is the number of parts that it has. The parts of any entity in metaphysics rather it is an abstract object like a collection or a number or a concrete entity like a physical object is determined by a partial ordering relation. For general sets, it is rather obvious that the size of a set is the number of elements it has which is the cardinality. This is rather trivial, and it doesn't require further consideration. When considering set systems, not only does the set system have parts so does its members. So a better way of determining the size of a set system is the cardinality sum, which is the sum of all the cardinalities of members in the set system. Size is monotone with respect to complexity.

Set systems of size one or less:

All the set systems of size one or less are trivial like {} and {{0}}. It doesn't matter for the purposes of this classification to consider rather or not the set systems contain the empty set.

Set systems of size two:

All the set systems of size two are pairwise disjoint so we can consider the two set partitions of two elements which are {{0} {1}} and {{0, 1}}.

Set systems of size three:

Signature 1,1,1
There are three set partitions of a set of three elements. These are the set partition {{0}, {1}, {2}}, the set partition {{0}, {1,2}} and the set partition {{0, 1, 2}}. It should be clear that all the set partitions are determined up to isomorphism by their cardinality multisets.

Signature 1,2
The next set system on three elements is {{0},{0,1}} which is the first ordered set system and the simplest set system that is not pairwise disjoint. This is why it is chosen to be the set theoretic definition of the ordered pair. Extending from the theory of set systems and continuing to the theory of sets of sets of sets, one arrives at the theory of sets of kuratowski pairs, also known as binary relations, which forms one of the most basic concepts of pure set theory.

Set systems of size four:

Signature 1,1,1,1
There are five set partitions of four elements:
{{0},{1},{2},{3}}
{{0},{1},{2,3}}
{{0,1},{2,3}}
{{0},{1,2,3}}
{{0,1,2,3}}.

Signature 1,1,2
There are three types of set systems with degree signature 1,1,2. These set systems are pseudo-independent because they are nearly pairwise disjoint as seen by their degree signature. Each degree signature whose multiplicities are consecutive starting with one, are associated with a single chain partition which in the case of this set system looks like {{0},{0,1,2}}. This is a chain because it is totally ordered under inclusion, and it is laminar because all chains are laminar.

Another laminar set system with this degree signature is {{0},{1},{1,2}} which is the unique non-order connected laminar set system with this degree signature. This is equal to a kuratowski pair unioned with a disjoint singleton set. As a result its connectivity cardinality multiset is {1,3}.

The set system {{0,1},{1,2}} is the simplest non-laminar set system. In the same manner that the kuratowski pair represents the simplest set system which isn't pairwise disjoint, this set system represents the simplest set system which isn't laminar. The complementary clique family to the laminar family is the set of all anti-disjoint sperner families, so this is the simplest non-disjoint sperner family. Anti-disjoint sperner families are not order connectivity preserving, because they are intersection connected but not inclusion connected.

Signature 2,2
The power set like set system {{0},{1},{0,1}} is the only set system with its degree signature, as its the maximal degree signature of order two. It is a laminar set system, which corresponds to the join representations of a height two upper tree of order three.

Set systems of size five:

Signature 1,1,1,1
There are seven set partitions of five elements:
{{0} {1} {2} {3} {4}}
{{0} {1} {2} {3 4}}
{{0} {1} {2 3 4}}
{{0} {1 2} {3 4}}
{{0} {1 2 3 4}}
{{0 1} {2 3 4}}
{{0 1 2 3 4}}

Signature 1,1,1,2
Set systems of this degree signature are pseudo-independent because they are nearly pairwise disjoint as removing a single element makes them set partitions. As a result, all of the laminar set systems of this sort are going to be height two interval ordered subsingleton-free multichain families. To begin with there is the chain partition {{0},{0,1,2,3}} constructing by adding a subsingleton to the four element set.

Then we can consider the case of adding a subsingleton to the three element which gets us {{0},{1},{1,2,3}} which also is not order connected as before. There has 1,4 connectivity signature.

Then we can consider the cases where we add a subsingleton to a two element set. This results in {{0},{1},{2},{2,3}} which has 1,1,3 connectivity signature and {{0,1},{2},{2,3}} which has 2,3 connectivity signature. These are both set systems based upon adding a subsingleton to pair but they are distinguished by their connectivity signatures. These can also be obtained by unioning a disjoint set system with a kuratowski pair.

The two non-laminar set systems with these degree signature are the maximal cliques of the paw and the co-paw. The paw cliques family {{0,1,2},{2,3}} is uniquely dependent well the co-paw cliques family {{0,1},{1,2},{3}} is not uniquely dependent. As the co-paws family is triangle free all its cliques are trivial and it could also be considered an independency family.

Signature 1,2,2
There are four types of set systems with signature 1,2,2. To begin with there is the chain partition, which is always associated with a degree signature of this sort which is {{0 1} {0 1 2}}. As a chain, this naturally corresponds to a total preorder under the operation of taking principal ideals.

Then there is the upper tree order containment family {{0},{1},{0,1,2}}. This corresponds to the principal ideals on the height two upper tree of size three, rather then the join representations discussed previously because even though 2 is join irreducible it is an element of this set system.

The set system {{0} {1} {2} {1 2}} corresponds to the join representations of an upper tree as well as a singleton set added to it. It is like the set system on 2,2 with a singleton added to it because it is not uniquely connected.

The set systems described so far have been laminar. There are two types of set systems with this size and this order which are non-laminar and they are based upon adding singleton elements to the previously-described non-laminar path independency family. The one with this degree signature is {{0,1},{1,2} {2}} which is based upon adding a loop at one of the endpoints of the path independency family rather than in its center.

Signature 1,1,3
There is only one set system with this degree signature and it is the star {{1},{0,1},{1,2}} which has a common member of all of its sets. This is the order containment family on the height two lower tree with three elements. Although this is order connectivity preserving, it is also not laminar because laminar set systems tend to be upper trees under their inclusion ordering. It is based upon adding a loop to the center of the non-laminar path independency family described previously.

Set systems of size six:

Signature 1,1,1,1,1,1
There are eleven set partitions of size elements.
{{0},{1},{2},{3},{4},{5}}
{{0},{1},{2},{3},{4,5}}
{{0},{1},{2,3},{4,5}}
{{0,1},{2,3},{4,5}}
{{0},{1},{2},{3,4,5}}
{{0},{1,2},{3,4,5}}
{{0,1,2},{3,4,5}}
{{0},{1},{2,3,4,5}}
{{0,1},{2,3,4,5}}
{{0},{1,2,3,4,5}}
{{0,1,2,3,4,5}}

Signature 1,1,1,1,2
In order to classify all set systems of this degree signature we will begin with the uniquely dependent set systems. The only laminar uniquely depedent family is the chain family corresponding to this signature which is {{0},{0,1,2,3,4}}.

There are also two uniquely dependent families which are maximal clique families of certain graphs. The maximal cliques of the butterfly {{0,1,2},{2,3,4}} is the first maximal cliques family of this sort and the other is the maximal cliques of the (4,1) lollipop graph {{0,1,2,3},{3,4}}.

Among the non uniquely dependent ones we have the chain plus one element {{0},{1},{1,2,3,4}} which is a laminar family for a multichain preorder.

Then we have the paw plus one element {{0,1},{1,2,3},{4}} which is effectively a maximal cliques family with a singleton set corresponding to an isolated vertex.

The path can be connected to two types of partitions yielding {{0,1},{1,2},{3},{4}} and {{0,1},{1,2},{3,4}} the later of which is a uniform set system.

The 3-chain can also be connected to two types of partitions yielding {{0,1},{2},{2,3,4}} and its refinement {{0},{1},{2},{2,3,4}}.

Then finally there are three types of set partitions that can be added to a kuratowski pair {{0,1,2},{3},{3,4}} its partial refinement {{0},{1,2},{3},{3,4}} and its total refinement {{0},{1},{2},{3},{3,4}}. All of these set systems are laminar.

Signature 1,1,2,2
There are two types of rank four laminar families with this signature the chain {{0,1},{0,1,2,3}} and the lower tree {{0},{1},{0,1,2,3}}.

The maximal cliques of the diamond graph are {{0,1,2},{2,3,4}} which are two sets that intersect at two common points which have each have a degree of two.

The paw graph has two types of peripheral vertices which can have loops added to them to in their maximal cliques family to get two different types of set system {{0,1},{1,2,3},{0}} and {{0,1},{1,2,3},{3}}.

Then the maximal cliques on the path graph of four elements {{0,1},{1,2},{2,3}} also has this signature and it is rank two.

There are two types of laminar families with a singleton added to them {{0},{1},{2},{1,2,3}} and {{0},{1,2},{1,2,3}}. Both of these have connectivity type 1,5.

Then there is the non-laminar family with a singleton added to it {{0},{1,2},{2,3},{3}} which has this signature and connectivity type 1,5.

Finally we can consider the two types of set systems with a 2+2 component and the two other types of disjoint components added to them which are {{0},{1},{2},{3},{2,3}} and {{0,1},{2},{3},{2,3}}. Both of these set systems are laminar like the other types with larger connected components described previously.

Signature 2,2,2
As this a regular degree signature, all set systems of this signature will be regular families. To begin with, there are two laminar families with this signature both of which have rank three, which means they have a triangle. The first is {{0,1,2},{0},{1},{2}} and the second is {{0,1,2},{0},{1,2}}.

The path graph has two peripheral vertices and one central vertices which has a higher degree then the periphery ones. In order to regularize them, we can add loops to the peripheral vertices to get the set system {{0,1},{1,2},{0},{2}} which corresponds to the path independency family with subsingletons added to its endpoints.

Finally there is the triangle independency family {{0,1},{0,2},{1,2}} which is the simplest independency family which is not a maximal cliques family. Actually this corresponds to the two section of the clique {0,1,2}.

Signature 1,1,1,3
The only laminar set system with this degree signature is the order containment family of the height two lower forest constructed by adding a single element to the size three lower tree {{0},{1},{1,2},{1,3}}.

The triangle free independency family {{0,1},{0,2},{0,3}} corresponds to the non-trivial edges of the star graph on four elements. It is also a uniform set system because each set has the same cardinality.

Adding a singleton set to the center of the maximal cliques set system of the paw gets the set system {{1},{0,1},{1,2,3}} which has this degree signature. It is neither a laminar family or a maximal cliques family.

Signature 1,2,3
The chain progression partition corresponding to this degree signature {{0},{0,1},{0,1,2}} is the unique progression family type on three elements.

Well the chain partition is naturally associated with this degree signature, another set system with this degree signature is the join representations of the four element fence partial order {{0},{1},{0,1},{1,2}} which is also an uneven path graph with a loop at one center vertex and one endpoint vertex and one periphery vertex. Both of these set systems are laminar.

Young's lattice

There are many different lattices, so it is important to know which ones are important and why. This is especially true of integer partitions where are there many different types of orderings. The importance of the Young's lattice is that it describes the ordering of the signatures of multisets, for example, for one number to divide another, its prime signature must precede the other number's in the Young's lattice. A multiset can only be included in another if its signature is in the Young's lattice.



The signatures play a similar role in multiset theory to cardinal numbers in set theory, as they describe the ordering properties of multisets. The multiset ordering forms a distributive lattice. The amazing thing is that the Young's lattice forms a distributive lattice as well. As a distributive lattice, the signatures of the Young's lattice are sets of multisets of maximum order two whose two atoms are the types of partitions conjugate to one another.

Foundational distributive lattices

An unordered collection can be either a set or a multiset. Unordered collections are the foundational core of mathematics, as well as the basis of all ontologies. All unordered collections form distributive lattices. Sets and multisets also have an isomorphism types associated with them, for the sets it is the cardinal numbers, and for multisets it is the multiplicities signatures. In order for a set to be included in another its cardinality must be less then the cardinality of the other set. In order for a multiset to be included in another its signature must be less then the signature of the other multiset.

• Sets : cardinal numbers
• Multisets : multiplicities signature

The cardinals form a total order which means they are also distributive. The multiplicities signatures are partially ordered by the Young's lattice, which also forms a distributive lattice. Both the cardinals and the multiplicities signatures can therefore be included among the set of distributive lattice ordered structures. As a consequence of this, the Young's lattice is one of the most fundamental distributive lattices in lattice theory. I will talk about the Young's lattice in more detail next.