Introduction

Order pervades mathematics and the sciences. Often, a reader’s intuitive notion of order is all that is necessary for understanding a particular invocation of the notion of order. However, a deeper examination of order reveals a rich taxonomy over the types of orderings that can arise and leads to powerful theorems with applications in mathematics, computer science, the natural sciences, and the social sciences.

The following are examples of orders that one might encounter in life:

• In a work place, employees may have a rank that determines which other employees they have authority over. IT workers report to the IT manager, marketers report to the marketing manager, managers report to the CEO, etc.

• In a grocery store, someone planning to buy corn flake cereal may consider the ordering on the prices of various brands of shredded wheat to decide which to purchase.

• At lunchtime, someone with a craving for burritos may order the nearby burrito restaurants by their distance from her workplace. She may also order these burrito joints by quality, and consider both orderings in her decision.

Now that we’ve seen some concrete examples of order, we can begin working toward a rigorous mathematical definition. In each of the above examples, we have some underlying set of objects that we are comparing: employees, corn flake brands, and burrito restaurants, respectively. We also have an ordering, which is a binary relation determining whether or not one object is “less than” another. This suggests that order esentially a pair of a set and some binary relation defined on it. Is this all we need to capture the notion of order?

Here are a few examples of binary relations which may or may not be orderings. Do they agree with your intuitive notion of ordering?

• 1.) The relation which includes all pairs of people \((a,b)\) such that \(a\) and \(b\) are friends.

• 2.) The relation of pairs of people \((a,b)\) such that \(a\) is a genetic descendant of \(b\).

• 3.) The relation on days of the week which contains the exactly pairs \((a,b)\) such that a directly precedes b: \(\{ (Monday, Tuesday), (Tuesday, Wednesday), ... \}\)

It turns out that only item 2 agrees with the mathematical definition of ordering. Intuitively, item 1 is not an ordering because of its symmetry: a friendship between two people does not distinguish one friend as being “less than” the other (not a healthy friendship, at least). Friendship is actually an instance of another important class of binary relations called the equivalence relations. Item 3 is not an ordering because it lacks transitivity: Monday directly precedes Tuesday and Tuesday directly precedes Wednesday, but Monday does not directly precede Wednesday.

Posets

We’re now ready to provide a formal, mathematical definition, for a class of objects called posets (a contraction of partially ordered set), which captures the idea of ordering.

--

Definition: Poset

A poset is a pair \(\langle P, \leq \rangle\) of a set \(P\) and a binary relation \(\leq\) on \(P\) such that for all \(p,q,r \in P\), the following properties are satisfied:

• Reflexivity: \(p \leq p\)

• Transitivity: \(p \leq q\) and \(q \leq r\) implies \(p \leq r\)

• Anti-Symmetry: \(p \leq q\) and \(q \leq p\) implies \(p = q\)

\(P\) is referred to as the poset’s underlying set and \(\leq\) is referred to as its order relation.

--

The above definition may strike some readers as more general than expected. Indeed, in both mathematics and conversational English, when someone states that a set of objects is ordered, they often mean that it is totally ordered. A total order is a poset for which any two elements of \(a\) and \(b\) of the underlying set are comparable; that is, \(a \leq b\) or \(b \leq a\). But our definition of a poset allows the possibility that two elements are incomparable. Recall our example of employees in a work place. In our reports-to relation, both an IT manager and a marketing manager report to the CEO; however, it would not make sense for an IT manager to report to a marketing manager or vice versa. The marketing and IT managers are thus incomparable. We write \(a \parallel b\) to state that two poset elements \(a\) and \(b\) are incomparable.

Another important distinction must be made. Partial orders as we have described them are not strict orders. From any poset \(\langle P, \leq \rangle\), we can derive an strict order relation \(<), which includes exactly those pairs of \(\leq\) relating two elements of \(P\) that are distinct. It should be noted that, while strict orders are transitive and vacuously anti-symmetric, they are not partial orders because they are not reflexive. In everyday situations, strict orders seem to be more useful, but in mathematics non-strict orderings are of more use, and so non-strictness is built into the definition of poset.