A Study of the Theory of Partially Ordered Multi-Sets

A Study of the Theory of Partially Ordered Multi-Sets

Chapter One

Aim and Objectives of the Study

The aim of this research is to study the theory of partially ordered structures and develop an ordered multiset structure with the intent of extending existing notions and results particularly on certain combinatorial parameters studied for sets, to multisets.

In order to achieve this aim, our main objectives are to:

1. Develop a partially ordered multiset structure that admits hierarchy between the points of a multiset and establish properties satisfied by this
2. Construct substructures of the ordered multiset and investigate their
3. Extend combinatorial parameters of linear extensions, realizers, and dimension to multisets using the structure constructed in i
4. Extend results on these parameters from the set theoretical context to multisets and obtain some new results that are peculiar to ordered
5. Investigate algorithms for constructing linear extensions of a partially ordered set and develop a heuristic algorithm for generating multiset linear extensions to be implemented on a partially ordered multiset

CHAPTER TWO

LITERATURE REVIEW

Partially Ordered Sets and Combinatorial Theory

The theory of ordered sets lies at the confluence of several branches of Mathematics which includes in particular, set theory, lattice theory, combinatorial theory and some aspects of modern operational research. Over the last thirty years, researchers have made considerable efforts towards developing the theory of ordered sets. Partially ordered sets can be said to have their origin in the work of George Boole (1854), An investigation of the laws of thought, while developing an axiomatic theory of propositional logic. In 1883, George Cantor, founder of set theory, envisaged that every set could be well ordered. This well ordering principle for which Cantor could not provide a proof, remained at the heart of the theory of ordinal and cardinal numbers. In 1904, Ernst Zermelo using the axiom of choice, provided a proof of the well ordering theorem.

In 1930, Szpilrajn established a fundamental result in ordered set theory: Every ordering on a set can be extended to a linear ordering. He proved that any order on an ordered set P has at least one linear extension. He also proved a stronger result:  Let  be an order on P and let  be  elements of P such that ||  i.e.,  and  are  incomparable,  then  there  exist  two  linear  extensions of such that and .

Building on Szpilrajn’s results, Dushnik and Miller (1941) showed that every partial order is the intersection of a collection of linear orders. They also defined the dimension of an ordered set P as the minimum cardinality of a realizer of P. Their results showed that there exist partially ordered sets of arbitrarily large dimensions.

Dilworth (1950) established that in a finite ordered set P, the minimum number of chains whose set union is P equals the maximum number of pairwise incomparable elements of P. This classical theorem of Dilworth has played a significant role in motivating research in ordered set theory. Like a number of other results in combinatorics, Dilworth’s theorem is equivalent to Hall’s Marriage theorem, Konig-Egervary theorem, Menger’s theorem and the maxflow-mincut theorem for network flows. Dilworth’s theorem has been extended and modified through deep and detailed investigations by a number of researchers.

Hiraguchi (1951) used Dilworth’s theorem to prove that the dimension of an order never exceeds its width. This results showed that if P is a poset on     points with           , then              ⌊     ⌋.  An analogue of Dilworth’s theorem in the infinite setting was presented by Perles (1963). However, the theorem does not extend so simply to ordered sets with infinite width. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be different from each other. In particular, for every infinite cardinal number there is an infinite ordered set with width whose partition into  the  fewest  chains  has  chains (Harzheim, 2005).

Hansson (1968), proved an analogue of Szpilrajn’s theorem for ordering extensions of quasi orderings.

In 1971, Mirsky inspired by Dilworth’s theorem, proved that for every partially ordered set, the height also equals the minimum number of antichains into which the set may be partitioned. For sets of order dimension 2, the two theorems coincide but for more general partial orders the theorems differ. Dilworth’s theorem and Mirsky’s theorem are also related through the theory of perfect graphs. Mirsky’s theorem states that comparability graphs are perfect. Analogously, Dilworth’s theorem states that every complement graph of a comparability graph is perfect. The perfect graph theorem of Lovasz (1972) states that the complements of perfect graphs are always perfect, and can be used to deduce Dilworth’s theorem from Mirsky’s theorem and vice versa (Golumbic 1980).

Fishburn (1973) showed that every quasi-ordering has an ordering extension. While Hansson’s proof proceeds directly without making use of Szpilrajn’s extension theorem, Fishburn’s proof utilizes Szpilrajn’s results (Hansson, 1968).

Dynamic programming has been successfully used in the past to solve a large class of  precedence constrained sequencing problems. The main limitations of this method has been the amount of storage required, which is directly related to the number of ideals in the precedence structure. Knuth (1973) presented a fast algorithm for computing linear extensions (or topological sorts) of an ordered set together with its implementation.

Maximum antichains also called maximum Sperner families, named after Sperner who first characterized them, in the case where P is a finite Boolean lattice. Sperner showed that the maximum size of an antichain containing n elements is

(⌊      ⌋).

Freese (1974) showed that under the natural ordering, the maximal sized antichains of an ordered set form a distributive lattice, a theorem attributed to Dilworth on the decomposition of partially ordered sets.

₦3,000.00 – DOWNLOAD CHAPTERS 1-5 PROCEED TO DOWNLOAD Added to cart

 

CHAPTER THREE

FUNDAMENTALS OF ORDERED SETS, MULTISETS AND MULTISET ORDERINGS

In this chapter, fundamental concepts and results on classical ordered sets are presented. These structures are extensively studied in the research monograph (Trotter, 1992) and survey article (Trotter, 1995) (see also Harzheim, 2005 and Harju, 2006). Basic notions and notations of multisets and multiset orderings as presented in Blizard (1989), Singh et al. (2007), Singh and Isah (2016), Tella et al., (2014A) are explicated.

Notions and Notations of Partially Ordered Sets

Order theory captures the intuition of ranking that arise from instances where each element in a set can be compared to any other element and cases where some elements of a given set are incomparable. Essentially, in order to develop an ordered structure, the notion of relation plays a fundamental role. A binary relation R on a set is comprehended as .

A relation R is called:

1. A quasi-order (or pre order) if it is reflexive and transitive
2. A partial order if it is reflexive, transitive and antisymmetric

• Alinear order (or total order), if it is a partial order and for any two elements  , either .

Definition 

For two relations and , their composition is the relation  defined as follows:

{        |                                    }

Definition 

A partially ordered set (we use the now standard term poset henceforth) is a pair             where  is a set, and   is a reflexive, antisymmetric, and transitive binary relation on   . The set    is    called the ground set and is called a partial order.

CHAPTER FOUR

PARTIALLY ORDERED MULTISETS

In this chapter, a new ordered multiset structure                      is developed. Substructures of     the ordered multiset are also constructed. We consider generalization of known results that hold for ordered sets and obtain some properties that are peculiar to ordered multisets. In particular, by employing set-based partitioning, the width and height of a partially ordered multiset are characterized.

The Ordering

In this section, we introduce the ordering         on a mset         and present properties         satisfied by the ordered structure  , which we call a partially ordered multiset. Here, the   ordering induced by the underlying base set plays a vital role in defining hierarchies between the points of .

CHAPTER FIVE

COMBINATORICS OF PARTIALLY ORDERED MULTISETS

Notions of combinatorics of ordered multisets are investigated in this chapter. The classical extension theorem for ordered sets is generalized. Also, an algorithm for generating mset linear extensions of ordered multisets is constructed and implemented on a partially ordered multiset. Finally, some characterizations for the dimension of an ordered multiset are presented.

CHAPTER SIX

SUMMARY, CONCLUSIONS AND RECOMMENDATIONS

 Summary

The theory of partially ordered structures was studied in this work. A new partially ordered multiset structure was constructed exploiting the ordering induced by the underlying generic set. Substructures of the ordered multiset were also constructed with some new results. New concepts were defined particularly in the area of combinatorics of ordered structures. Consequently, some new results were obtained on the defined ordered multiset structure.

Fundamentals of ordered sets, which included, operations on partially ordered sets and their properties, were presented. Existing orderings on multisets were also explicated. Some classical theorems of ordered sets were investigated and these were extended to ordered multisets. Various formulations of partially ordered multisets were also described.

The proposed  ordered  multiset structure     was used to extend results on ordered sets to  ordered multisets. Substructures of the partially ordered multiset were formulated and investigated via the defined suborder. In particular, Dilworth’s decomposition theorem for partially ordered sets and its dual were extended to partially ordered multisets under restricted conditions.

By using a partially ordered base set, the concepts of linear extensions, realizers and dimension were extended to ordered multisets. Significantly, the classical extension theorem for ordered sets was extended to ordered multisets, this formed the basis for establishing some new results on the ordered multiset structure. Among other results, it was shown that any partial mset order can be sorted into an mset linear order while maintaining all preexisting relations. Consequently, an algorithm for generating mset linear extensions of partially ordered multisets was constructed and implemented. It was also shown that the concept of realizers is well-defined on the new ordered multiset structure. Finally, some characterizations for the dimension of an ordered multiset were obtained on the ordered multiset structure.

Conclusions

Not very surprisingly, multisets are found quite apt to represent partial orders. The new ordered multiset structure constructed via the ordering induced by the underlying generic set was suitable for extending concepts and properties, particularly in the area of combinatorics, that hold on the classical ordered sets to multisets. New results were obtained through generalization of known results that hold for ordered sets to multisets, some properties that are peculiar to ordered multisets were also established.

Contributions to knowledge

The following results are the main contributions of this thesis:

1. Constructing  an  ordered  multiset  structure        ,  and  proving  its  following properties:
   1. is a pmset.

1. The intersection of two pomsets is also a

• An mset in is partially ordered if and only if its root set is a sub poset of . where     is the class of finite msets defined over a set    , and     is a poset    with ground set .

1. A pointis maximal in if and only if is maximal in the root
2. If is linearly ordered then maximal and maximum  (resp.  minimal  and  minimum) points
3. Formulating substructures of and explicating the following properties;
4. Every well-ordered pomset is an mset
5. A maximal mset chain necessarily contains its upper

• If is a collection of all maximal mset chains in a pomset , and is an mset containing all upper bounds of the elements of . Then any two distinct points in   are incomparable.

1. A necessary and sufficient condition forto have a maximum of one element for any  . Where   are mset chains and mset antichains in the pomset ,
2. Dilworth’sdecomposition theorem and its dual were extended to ordered msets
3. by characterizing the width and height of the pomset exploiting set-based partitioning, into minimum number of mset chains and antichains, respectively.
4. The extension theorem was generalized through the followingresults:
5. A pomset   is  an mset extension of   if and only if  the poset   is  an    extension of    , where    and    are defined over    and    , respectively, such that and Q have a common ground
6. For any pair of points                    with                    incomparable in      ,   there exists a pomset extending such that .
7. Every finite pomset has an m set linear
8. A heuristic algorithm (Algorithm M-LIN (1)) and an exact algorithm (Algorithm M-LIN (2)) for generating mset linear extensions were constructed and evaluated on a randomly generated ordered multiset
9. The following results on mset realizers and dimension were established on the defined ordered multiset structure:
   1. A partial mset order is the intersection of its set of

1. The size of an mset realizer is bounded by the size of the realizer of its base set i.e., | |  |  |, where  and  are realizers for the pomset  and the poset  , respectively.
2. For any  ,    , where      and      denote the dimensions of and , respectively.

1. , if and.
2. The dimension of the pomset is
3. Dimension of is at most the width of.

 Recommendations

Partially ordered multisets help in understanding the semantics of parallel programs and are found suitable to model runs of concurrent systems. In view of numerous and diverse practical applications of ordered multisets, there is a growing need to develop a wider class of ordered multiset structures, for researchers to investigate and adopt the structure that is most suitable to model the application problem at hand. With further investigations, our defined ordered structures can be extended to compare multisets in the class of finite multisets defined over a set . Also, the structure proposed in section 4.5 needs further vindication as it promises to be useful in modelling complex application problems.

References

• Aceto, L. (1991). Full abstraction for series-parallel pomsets. Edited by S. Abramsky and T. S. Maibaum. Lecture Notes in Computer Science. Springer-Verlag Berlin, 493: 1-25.
• Bachmair, L., Dershowitz, N., & Hsiang, J. (1986). Orderings for equational proofs, in: Proc. IEEE Symp. on Logic in Computer Science, Cambridge, MA, 346-357.
• Baclawski, K. (1981), Rings with lexicographic straightening law. Adv. In Math., 39: 185-213. Baeten, J. C. M., & Weijland, W. P. (1990). Process Algebra. Cambridge University Press, Cambridge.
• Behrendt, G. (1988). Maximal antichains in partially ordered sets. ARS Combinatoria, 25C: 149- 157.
• Ben-Amram, A., & Codish, M. (2008). A SAT-based approach to size change termination with global ranking functions. 14^th Intl. Conference on tools and algorithms for construction and analysis of systems (TACAS), LNCS, Springer Verlag.
• Bertet, K., Gustedt, J., & Morvan, M. (2003). Weak-order extensions of an order. Theoretical Computer Science, 304: 249-268.
• Bianco, L., Dell’Olmo, P., & Giordani, S. (1997). An optimal algorithm to find the jump  number of partially ordered sets. Computational Optimization and Applications, 8(2): 197-210.
• Blizard, W. (1989). Multiset theory. Notre Dame Journal of Formal Logic, 30: 36-66.
• Blizard, W. (1990). Negative membership. Notre Dame Journal of Formal Logic, 31: 346-368. Bouchitte, V., & Habib, M. (1987). NP-Completeness properties about linear extensions. Order, 4: 143-154.
• Bouchitte, V., Habib, M., & Jegou, R. (1985). On the greedy dimension of a partial order. Order, 1: 219-224.
• Brandt, J. (1982). Cycles of partitions. Proc. American Mathematical Society, 85: 483-486. Brightwell, G., & Winkler, P. (1991). Counting linear extensions. Order, 8(3): 225-242.

₦3,000.00 – DOWNLOAD CHAPTERS 1-5 PROCEED TO DOWNLOAD Added to cart