A Classroom Note on Topological Ordering

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.