nLab
partial order

Idea

A partial order on a set is a way of ordering its elements to say that some elements precede others, but allowing for the possibility that two elements may be incomparable without being the same. This is the fundamental notion in order theory.

Definitions

As a set with extra structure

A poset can be understood as a set with extra structure.

Given a set $S$, a partial order on $S$ is a (binary) relation $\le$ with the following properties:

• reflexivity: $x\le x$ always;
• transitivity: if $x\le y\le z$, then $x\le z$;
• antisymmetry: if $x\le y\le x$, then $x=y$.

A poset is a set equipped with a partial order.

As a category with extra properties

A poset can be understood as a category with extra property.

A poset is a category such that:

• for any pair of objects $x,y$, there is at most one morphism from $x$ to $y$
• if there is a morphism from $x$ to $y$ and a morphism from $y$ to $x$, then $x=y$.

Equivalently, we may define a poset to be a skeletal category enriched over the cartesian monoidal category of truth values.

When we do this, we are soon led to contemplate a slight generalization of partial orders: namely preorders. The reason is that the antisymmetry law, saying that $x\le y$ and $y\le x$ imply $x=y$, is evil in a certain sense. (On the other hand, it is not evil if taken as a definition of equality.)

Monotone functions

The morphisms of partially ordered sets are monotone functions; a monotone function $f$ from a poset $S$ to a poset $T$ is a function from $S$ to $T$ (seen as seen as structured sets) that preserves $\le$:

$$x\le y\Rightarrow f(x)\le f(y).$$x \leq y \;\Rightarrow\; f(x) \leq f(y) .

Equivalently, it is a functor from $S$ to $T$ (seen as certain categories).

In this way, posets form a category Pos.

Intervals

A (closed bounded) interval in a poset $C$ is a set of the form

$$[x,y]=\{r\in C\mid x\le r\le y\}.$$[x,y] = \{r\in C|x\le r\le y\}.

A poset is locally finite if every closed bounded interval is finite.

Kinds of posets

A poset with a top element and bottom element is called bounded. (But note that a subset of a poset may be bounded without being a bounded poset itself.)

A poset with all meets and joins is called a lattice; if it has only one or the other, it is still a semilattice.

A poset in which every finite set has an upper bound (but perhaps not a least upper bound, that is a join) is a directed set.

As remarked above, a poset in which each interval $[x,y]$ is a finite set is called locally finite or a causet.

In higher category theory

An poset can be understood as a (0,1)-category. This suggests an obvious vertical categorification of the notion of poset to that of n-poset.

References

• Marco Grandis, Directed homotopy theory, I. The fundamental category (arXiv)
• Tim Porter: Enriched categories and models for spaces of evolving states, Theoretical Computer Science, 405, (2008), pp. 88–100.
• Tim Porter, Enriched categories and models for spaces of dipaths. A discussion document and overview of some techniques (pdf)