CHAPTER 14 Ordered Sets and Lattices
14.1Introduction
Order and precedence relationships appear in many different places in mathematics and computer science.
This chapter makes these notions precise. We also define a lattice, which is a special kind of an ordered set.14.2Ordered Sets
SupposeRis a relation on a setSsatisfying the following three properties:[O 1 ] (Reflexive) For anya∈S, we haveaRa.[O 2 ] (Antisymmetric) IfaRbandbRa, thena=b.[O 3 ] (Transitive) IfaRbandbRc, thenaRc.ThenRis called apartial orderor, simply anorderrelation, andRis said to define apartial orderingofS. The
setSwith the partial order is called apartially ordered setor, simply, anordered setorposet. We write(S, R)
when we want to specify the relationR.
The most familiar order relation, called theusual order, is the relation≤(read “less than or equal”) on the
positive integersNor, more generally, on any subset of the real numbersR. For this reason, a partial order relation
is usually denoted by; and
ab
is read “aprecedesb.” In this case we also write:
a≺bmeansabanda=b; read “astrictly precedesb.”
bameansab; read “bsucceedsa.”
b.ameansa≺b; read “bstrictly succeedsa.”
/,≺/,/, and.are self-explanatory.
When there is no ambiguity, the symbols≤,<,>, and≥are frequently used instead of,≺,., and,
respectively.337Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.