Order theory

Introduction

Order per­vades math­e­mat­ics and the sci­ences. Often, a reader’s in­tu­itive no­tion of or­der is all that is nec­es­sary for un­der­stand­ing a par­tic­u­lar in­vo­ca­tion of the no­tion of or­der. How­ever, a deeper ex­am­i­na­tion of or­der re­veals a rich tax­on­omy over the types of or­der­ings that can arise and leads to pow­er­ful the­o­rems with ap­pli­ca­tions in math­e­mat­ics, com­puter sci­ence, the nat­u­ral sci­ences, and the so­cial sci­ences.

The fol­low­ing are ex­am­ples of or­ders that one might en­counter in life:

  • In a work place, em­ploy­ees may have a rank that de­ter­mines which other em­ploy­ees they have au­thor­ity over. IT work­ers re­port to the IT man­ager, mar­keters re­port to the mar­ket­ing man­ager, man­agers re­port to the CEO, etc.

  • In a gro­cery store, some­one plan­ning to buy corn flake ce­real may con­sider the or­der­ing on the prices of var­i­ous brands of shred­ded wheat to de­cide which to pur­chase.

  • At lunchtime, some­one with a crav­ing for bur­ri­tos may or­der the nearby bur­rito restau­rants by their dis­tance from her work­place. She may also or­der these bur­rito joints by qual­ity, and con­sider both or­der­ings in her de­ci­sion.

Now that we’ve seen some con­crete ex­am­ples of or­der, we can be­gin work­ing to­ward a rigor­ous math­e­mat­i­cal defi­ni­tion. In each of the above ex­am­ples, we have some un­der­ly­ing set of ob­jects that we are com­par­ing: em­ploy­ees, corn flake brands, and bur­rito restau­rants, re­spec­tively. We also have an or­der­ing, which is a bi­nary re­la­tion de­ter­min­ing whether or not one ob­ject is “less than” an­other. This sug­gests that or­der es­en­tially a pair of a set and some bi­nary re­la­tion defined on it. Is this all we need to cap­ture the no­tion of or­der?

Here are a few ex­am­ples of bi­nary re­la­tions which may or may not be or­der­ings. Do they agree with your in­tu­itive no­tion of or­der­ing?

  • 1.) The re­la­tion which in­cludes all pairs of peo­ple \((a,b)\) such that \(a\) and \(b\) are friends.

  • 2.) The re­la­tion of pairs of peo­ple \((a,b)\) such that \(a\) is a ge­netic de­scen­dant of \(b\).

  • 3.) The re­la­tion on days of the week which con­tains the ex­actly pairs \((a,b)\) such that a di­rectly pre­cedes b: \(\{ (Monday, Tuesday), (Tuesday, Wednesday), ... \}\)

It turns out that only item 2 agrees with the math­e­mat­i­cal defi­ni­tion of or­der­ing. In­tu­itively, item 1 is not an or­der­ing be­cause of its sym­me­try: a friend­ship be­tween two peo­ple does not dis­t­in­guish one friend as be­ing “less than” the other (not a healthy friend­ship, at least). Friend­ship is ac­tu­ally an in­stance of an­other im­por­tant class of bi­nary re­la­tions called the equiv­alence re­la­tions. Item 3 is not an or­der­ing be­cause it lacks tran­si­tivity: Mon­day di­rectly pre­cedes Tues­day and Tues­day di­rectly pre­cedes Wed­nes­day, but Mon­day does not di­rectly pre­cede Wed­nes­day.

Posets

We’re now ready to provide a for­mal, math­e­mat­i­cal defi­ni­tion, for a class of ob­jects called posets (a con­trac­tion of par­tially or­dered set), which cap­tures the idea of or­der­ing.

--

Defi­ni­tion: Poset

A poset is a pair \(\langle P, \leq \rangle\) of a set \(P\) and a bi­nary re­la­tion \(\leq\) on \(P\) such that for all \(p,q,r \in P\), the fol­low­ing prop­er­ties are satis­fied:

  • Reflex­ivity: \(p \leq p\)

  • Tran­si­tivity: \(p \leq q\) and \(q \leq r\) im­plies \(p \leq r\)

  • Anti-Sym­me­try: \(p \leq q\) and \(q \leq p\) im­plies \(p = q\)

\(P\) is referred to as the poset’s un­der­ly­ing set and \(\leq\) is referred to as its or­der re­la­tion.

--

The above defi­ni­tion may strike some read­ers as more gen­eral than ex­pected. In­deed, in both math­e­mat­ics and con­ver­sa­tional English, when some­one states that a set of ob­jects is or­dered, they of­ten mean that it is to­tally or­dered. A to­tal or­der is a poset for which any two el­e­ments of \(a\) and \(b\) of the un­der­ly­ing set are com­pa­rable; that is, \(a \leq b\) or \(b \leq a\). But our defi­ni­tion of a poset al­lows the pos­si­bil­ity that two el­e­ments are in­com­pa­rable. Re­call our ex­am­ple of em­ploy­ees in a work place. In our re­ports-to re­la­tion, both an IT man­ager and a mar­ket­ing man­ager re­port to the CEO; how­ever, it would not make sense for an IT man­ager to re­port to a mar­ket­ing man­ager or vice versa. The mar­ket­ing and IT man­agers are thus in­com­pa­rable. We write \(a \parallel b\) to state that two poset el­e­ments \(a\) and \(b\) are in­com­pa­rable.

Another im­por­tant dis­tinc­tion must be made. Par­tial or­ders as we have de­scribed them are not strict or­ders. From any poset \(\langle P, \leq \rangle\), we can de­rive an strict or­der re­la­tion \(<), which in­cludes ex­actly those pairs of \(\leq\) re­lat­ing two el­e­ments of \(P\) that are dis­tinct. It should be noted that, while strict or­ders are tran­si­tive and vac­u­ously anti-sym­met­ric, they are not par­tial or­ders be­cause they are not re­flex­ive. In ev­ery­day situ­a­tions, strict or­ders seem to be more use­ful, but in math­e­mat­ics non-strict or­der­ings are of more use, and so non-strict­ness is built into the defi­ni­tion of poset.

Children:

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.