Orders

Why

We can arrange the natural numbers from left to right. We want to speak of arranging the elements of any set from left to right, in some order. Can we so order subsets?

Definition

A relation $R$ in a set $A$ is antisymmetric if, for every $a$ and $b$ in $A$, $(a, b) \in R$ and $(b, a) \in R$ implies that $a = b$. A partial order is a reflexive, transitive, and antisymmetric relation.

If I have three objects $a$, $b$, and $c$, and I arrange them in that “order” from left to right, I can always say whether one of the objects is “to the left of” another. In contrast, we use the word “partial” above to indicate that two elements need not be comparable. For example, consider the equality relation on $\set{a, b, c}$. This is really “no order” at all and $A$ is “totally unordered”, but it is (by our definition) a partial order.

A partial order $T$ on $A$ is total (or linear, simple) if, for each $a$ and $b$ in $A$, $(a, b) \in T$ or $(a, b) \in T$. Although total orders are familiar (see Natural Order), experience shows it to be expedient to generalize order to mean partial order.

Example: set inclusion

A natural motivation for and first example of a partial order is the relation of set inclusion on the set of subsets of some set (sometimes called the inclusion partial order).

For example, if $A = \set{a, b}$, then $\powerset{A}$ consists of the four elements $\varnothing$, $\set{a}$, $\set{b}$ and $\set{a,b}$. Recall that $\subset$ is reflexive and transitive (see Set Inclusion). However not all subsets are comparable. For example, neither $\set{a} \subset \set{b}$ nor $\set{b} \subset \set{a}$. So $\subset$ is not a total order on $A$. Exercise: Show that $\subset$ is total if and only if $A$ is empty or a singleton.

Ordered sets

A partially ordered set (or poset) is an ordered pair whose first coordinate is a set and whose second coordinate is a partial order in the first coordinate. Similarly with a totally ordered set (or simply ordered set, linearly ordered set), whose second coordinate is total. Preferring one word to three, we call such a set a chain.

Given an order $R$ on $A$, we can recover $A$ as $\dom R$. So the ordered pair formalism is redundant, albeit standard. It is common, however, to speak primarily of the set we are ordering, prior to the order. By “let $X$ be a partially ordered set” we always mean “let $X$ be the domain of a partial order”.

Notation

Let $A$ be a set. We tend to denote a partial order on $A$ by $\preceq$. So then, we denote a partially ordered set by $(A, \preceq)$.

As usual (see Relations), we write $a \preceq b$ to mean $(a, b) \in A$. Alternatively, we write $b \succeq a$ to mean $a \preceq b$. In other words, $\succeq$ is the inverse relation (see Converse Relations) of $\preceq$. We call such order-involving statements (e.g., $a \preceq b$) comparisons.

Maximal and minimal elements

Suppose $(P, \preceq)$ is a partially ordered set. Given $A \subset P$, an element $a$ is maximal in $A$ (with resepct to $\preceq$) if $b \preceq a$ for all $b \in A$. Similarly, $a \in A$ is minimial in $A$ (with respect to $\preceq$) if $a \preceq b$ for every $b \in A$.