Bases for Chain-Complete Posets
Various authors (especially Scott, Egli, and Constable) have introduced concepts of "basis" for various classes of partially ordered sets (posets). This paper studies a basis concept directly analogous to the concept of a basis for a vector space. The new basis concept includes that of Egli and Constable as a special case, and one of their theorems is a corollary of our results. This paper also summarizes some previously reported but little known results of wide utility. For example, if every linearly ordered subset (chain) in a poset has a least upper bound (supremum), so does every directed subset.
Given posets P and Q, it is often useful to construct maps g:P → Q that are chain-continuous: supremurns of nonempty chains are preserved. Chain-continuity is analogous to topological continuity and is generally much more difficult to verify than isotonicity: the preservation of the order relation. This paper introduces the concept of an extension basis: a subset B of P such that any isotone ƒ B→Q has a unique chain-continuous extension g:P→Q. Two characterizations of the chain-complete posets that have extension bases are obtained. These results are then applied to the problem of constructing an extension basis for the poset [P → Q] of chain-continuous maps from P to Q, given extension bases for P and Q. This is not always possible, but it becomes possible when a mild (and independently motivated) restriction is imposed on either P or Q. A lattice structure is not needed.
G. Markowsky and B. K. Rosen, "Bases for Chain-Complete Posets," IBM Journal of Research and Development, vol. 20, no. 2, pp. 138-147, Institute of Electrical and Electronics Engineers (IEEE), Mar 1976.
The definitive version is available at http://dx.doi.org/10.1147/rd.202.0138
Keywords and Phrases
Computer Metatheory; Posets; Automata Theory
International Standard Serial Number (ISSN)
Article - Journal
© 1976 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.