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

• @299, did you in­tend to make this a blog page (owned by you) as op­posed to a wiki page (owned by com­mu­nity)?

Also, it’s par­ented to Math playpen, but should prob­a­bly be par­ented to Math­e­mat­ics or a subtopic of math.

• I in­tended this to be a wiki page. My plan is to grad­u­ally de­velop it into a full fledged tu­to­rial on or­der the­ory (which might take awhile). I see that you have in­vited me to the math­e­mat­ics do­main. Do I need to join this do­main some­how?

• Sounds good!

The in­vite text is a bit un­clear. You don’t need to do any­thing; you already have the per­mis­sions to cre­ate/​edit pages in math do­main.

• After an­other ses­sion of us­ing Ar­bital, I have a few ques­tions and com­ments.

1.) Is there any mechanism for cita­tions? There prob­a­bly should be. A lot of what I have writ­ten about or­der the­ory so far is in­spired by Davey and Priestly’s In­tro­duc­tion to Lat­tices and Order. I don’t think it’s re­al­is­tic for some­one to pull an en­tire tu­to­rial on a math­e­mat­i­cal topic di­rectly out of their brain.

2.) I love the hover-over defi­ni­tion dis­play. It’s very con­ve­nient for look­ing up defi­ni­tions with­out hav­ing to tran­si­tion to other pages.

3.) It seems that it would be use­ful to be able em­bed ar­bital pages in­side of other ar­bital pages. Here’s the mo­ti­va­tion. Let’s say that I have a defi­ni­tion of poset, much like the one in this or­der the­ory tu­to­rial, but in its own page. It’s con­ve­nient to have short defi­ni­tion pages (like this one) for use with hover-over. How­ever, in this or­der the­ory tu­to­rial I don’t want to re­place the defi­ni­tion of poset with a link, be­cause it’s an im­por­tant part of or­der the­ory and there may be other text on this page that refers to it. Yet we still want to give the defi­ni­tion of poset its own page. Right now, it seems that the best way to do this in­volves re­dun­dancy: have two poset defi­ni­tions, one em­bed­ded in the tu­to­rial, and the other on its own page, in­clud­ing es­sen­tially the same con­tent. This re­dun­dancy does not seem ideal. This fea­ture sounds like it would be a night­mare to im­ple­ment, but it would be re­ally use­ful.

1. Not yet. You can just do foot­notes like “[1]” or make them links, like [1\](https://​​ar­bital.com)

2. Great!

3. Noted! We ac­tu­ally had a fea­ture like it some time ago and are plan­ning to bring it back be­fore long. It’s not clear what shape it’ll take, but some­thing like it is definitely nec­es­sary.

• The ed­i­tor kept au­to­mat­i­cally scrol­ling to top when I was try­ing to edit this page in Fire­fox just now.

• Hmm, can’t re­pro­duce. You were on the /​edit/​ page?

• I can’t re­pro­duce it ei­ther. Maybe it had some­thing to do with the USB key­board that I was us­ing.

• About the cita­tions: what I ac­tu­ally meant was that I want to have a bibliog­ra­phy, so that I can give due credit to any sources that I used to help write this tu­to­rial. I don’t want to add a bunch of su­per­scripts into this doc­u­ment.

• Ah… May be just put them at the bot­tom of the page. You an also wrap it in the %%co­ment%% syn­tax, so it’ll be visi­ble only to au­thors.