• DocumentCode
    2176585
  • Title

    Bases for chain-complete posets

  • Author

    Markowsky, George ; Rosen, Barry K.

  • fYear
    1975
  • fDate
    13-15 Oct. 1975
  • Firstpage
    34
  • Lastpage
    47
  • Abstract
    Given partially ordered sets (posets) P and Q, it is often useful to construct maps g:P→Q which are chain-continuous: least upper bounds (supremums) of nonempty linearly ordered subsets are preserved. Chaincontinuity 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 f:B→Q has a unique chain-continuous extension g:P→Q. Two characterizations of the chain-complete posets which 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. Finally, we consider extension bases which can be recursively listed and derive a recently established theorem as a corollary.
  • Keywords
    Application software; Computer applications; Computer science; Lattices; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1975., 16th Annual Symposium on
  • Conference_Location
    USA
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/SFCS.1975.7
  • Filename
    4567856