JavaScript is disabled for your browser. Some features of this site may not work without it.

## A Classroom Note on Topological Ordering

#####
**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

#####
**Subject**

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