Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T12:29:40.875Z Has data issue: false hasContentIssue false

Which Ordered Sets have a Complete Linear Extension?

Published online by Cambridge University Press:  20 November 2018

Maurice Pouzet
Affiliation:
Université de Lyon I, Villeurbanne, France
Ivan Rival
Affiliation:
University of Calgary, Calgary, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

It is a well known and useful fact [4] that every (partially) ordered set P has a linear extension L (that is, a totally ordered set (chain) on the same underlying set as P and satisfying a ≦ b in L whenever a ≦ b in P). It is just as well known that an ordered set P can be embedded in an ordered set P′ which, in turn, has a complete linear extension L′ (that is, a linear extension in which every subset has both a supremum and an infimum); just take L′ to be the “completion by cuts” of L. However, an arbitrary ordered set P need not, itself, have a complete linear extension (for example, if P is the chain of integers or, for that matter, if P is any noncomplete chain). It is natural to ask which ordered sets have a complete linear extension?

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1981