# Order theory

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

Children:

- Partially ordered set
A set endowed with a relation that is reflexive, transitive, and antisymmetric.

- Join and meet
- Lattice (Order Theory)
A poset that is closed under binary joins and meets.

- Totally ordered set
A set where all the elements can be compared as greater than or less than.

- Monotone function
An order-preserving map between posets.

- Complete lattice
A poset that is closed under arbitrary joins and meets.

Parents:

- Mathematics
Mathematics is the study of numbers and other ideal objects that can be described by axioms.

@299, did you intend to make this a blog page (owned by you) as opposed to a wiki page (owned by community)?

Also, it’s parented to Math playpen, but should probably be parented to Mathematics or a subtopic of math.

I intended this to be a wiki page. My plan is to gradually develop it into a full fledged tutorial on order theory (which might take awhile). I see that you have invited me to the mathematics domain. Do I need to

jointhis domain somehow?Sounds good!

The invite text is a bit unclear. You don’t need to do anything; you already have the permissions to create/edit pages in math domain.

After another session of using Arbital, I have a few questions and comments.

1.) Is there any mechanism for citations? There probably should be. A lot of what I have written about order theory so far is inspired by Davey and Priestly’s Introduction to Lattices and Order. I don’t think it’s realistic for someone to pull an entire tutorial on a mathematical topic directly out of their brain.

2.) I love the hover-over definition display. It’s very convenient for looking up definitions without having to transition to other pages.

3.) It seems that it would be useful to be able embed arbital pages inside of other arbital pages. Here’s the motivation. Let’s say that I have a definition of poset, much like the one in this order theory tutorial, but in its own page. It’s convenient to have short definition pages (like this one) for use with hover-over. However, in this order theory tutorial I don’t want to replace the definition of poset with a link, because it’s an important part of order theory and there may be other text on this page that refers to it. Yet we still want to give the definition of poset its own page. Right now, it seems that the best way to do this involves redundancy: have two poset definitions, one embedded in the tutorial, and the other on its own page, including essentially the same content. This redundancy does not seem ideal. This feature sounds like it would be a nightmare to implement, but it would be really useful.

Not yet. You can just do footnotes like “[1]” or make them links, like [1\](https://arbital.com)

Great!

Noted! We actually had a feature like it some time ago and are planning to bring it back before long. It’s not clear what shape it’ll take, but something like it is definitely necessary.

The editor kept automatically scrolling to top when I was trying to edit this page in Firefox just now.

Hmm, can’t reproduce. You were on the /edit/ page?

I can’t reproduce it either. Maybe it had something to do with the USB keyboard that I was using.

About the citations: what I actually meant was that I want to have a bibliography, so that I can give due credit to any sources that I used to help write this tutorial. I don’t want to add a bunch of superscripts into this document.

Ah… May be just put them at the bottom of the page. You an also wrap it in the %%coment%% syntax, so it’ll be visible only to authors.