nLab
partial order

Contents

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 SS, a partial order on SS is a (binary) relation \leq with the following properties: * reflexivity: xxx \leq x always; * transitivity: if xyzx \leq y \leq z, then xzx \leq z; * antisymmetry: if xyxx \leq y \leq x, then x=yx = y.

A poset is a set equipped with a partial order.

As a preorder with antisymmetry

A poset is precisely a proset satisfying the extra condition that xyxx \leq y \leq x implies that x=yx = y.

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,yx, y, there is at most one morphism from xx to yy

  • if there is a morphism from xx to yy and a morphism from yy to xx (which by the above implies that xx and yy are isomorphic), then x=yx = y.

This says that a poset is a (0,1)-category or equivalently a thin category.

Equivalently, we may define a poset to be a skeletal thin category, or equivalently 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 xyx \le y and yxy \le x imply x=yx = 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 ff from a poset SS to a poset TT is a function from SS to TT (seen as structured sets) that preserves \leq:

xyf(x)f(y). x \leq y \;\Rightarrow\; f(x) \leq f(y) .

Equivalently, it is a functor from SS to TT (seen as certain categories).

In this way, posets form a category Pos.

Intervals

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

[x,y]={rC|xry}.[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 as a poset in its own right.) More generally, it is bounded above if it is has a top element and bounded below if it has a bottom element.

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][x,y] is a finite set is called locally finite or a causet.

A poset with a bounding countable subset is called σ\sigma-bounded. That is, the poset is σ\sigma-bounded above if there exists a sequence (x n) n=1 N(x_n)_{n=1}^{N} (where NN is a natural number or infinity) such that for every yy in the poset there is an x mx_m with yx my \leq x_m. (The poset is σ\sigma-bounded below if we have x myx_m \leq y instead.) Note that every bounded poset is σ\sigma-bounded, but not conversely. Note that some authorities require N=N = \infty; this makes a difference only for the empty poset (we say it is σ\sigma-bounded, they say it is not).

In higher category theory

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

Properties

Locales from posets – Alexandroff topology

Definition

For PP a poset, write Up(P)Up(P) for the topological space whose underlying set is the underlying set of PP and whose open subsets are the upward closed subsets of PP: those subsets UPU \subset P with the property that

((xU)and(xy))(yU). ((x \in U) and (x \leq y)) \Rightarrow (y \in U) \,.

This is called the Alexandroff topology on PP.

Proposition

This construction naturally extends to a full and faithful functor.

Up:Up : Poset \to Top \to Locale.

Proposition

For PP a poset, there is a natural equivalence

Sh(Up(P))[P,Set] Sh(Up(P)) \simeq [P,Set]

between the category of sheaves on the locale Up(P)Up(P) and the category of copresheaves on PP.

For more see Alexandroff topology.

Cauchy completion

Every poset is a Cauchy complete category. Posets are the Cauchy completions of prosets. (Rosolini)

References

Cauchy completion of prosets and posets is discussed in

  • G. Rosolini, A note on Cauchy completeness for preorders (pdf)

Here are some references on directed homotopy theory:

  • 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)

Revised on July 9, 2013 19:58:52 by Urs Schreiber (131.174.40.17)