A Classroom Note on Topological Ordering
Loading...
No Access Until
Permanent Link(s)
Collections
Other Titles
Authors
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1980-06
Publisher
Cornell University
Keywords
computer science; technical report
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-429
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
technical report