Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Classroom Note on Topological Ordering

A Classroom Note on Topological Ordering

File(s)
80-429.ps (110.81 KB)
80-429.pdf (358.09 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6269
Collections
Computer Science Technical Reports
Author
Cammack, L.
Cooper, C.
Abstract

A partially ordered set (poset) is a pair (S,R) where S is a nonempty set and R is a reflexive, antisymmetric, transitive relation on S. (Equivalently, a pair (S,R') where R' is an irreflexive, transitive relation on S.) Unless otherwise stated the second definition will be the one used in this discussion. (S,R) is a chain if R is a total order on S, that is, given any pair a, b in S, either (a,b) or (b,a) is in R. The notion of embedding a poset in a complete lattice is a well known lattice theoretic result. [ see Foulis(1)] In this sequel we consider a special case of that result; namely, the embedding of a poset in a chain. Although the proof in the finite case suggests an intuitively obvious constructive algorithm [see Kahn(2)] it was only recently that an optimal' solution was discovered which can be implemented in linear time. [see Knuth(3)]. The proof in the infinite case first appeared in print in a paper by Szpilrajn. [see Szpilrajn(4)]. In this presentation the proof in the infinite case is a reasonably clean' and straightforward application of Zorn's lemma which can be readily understood by the average undergraduate.

Date Issued
1980-06
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-429
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance