A direction on a set SS is a preorder on SS in which any (finite) set of elements has a common upper bound. A directed set is a set equipped with a direction.

Directedness is an asymmetric condition. Sometimes a direction as defined here is called upward-directed; a preorder whose opposite is upward-directed is called downward-directed. Another term for downward-directed is codirected.

A diagram in a category whose domain is a directed set (regarded as a thin category) is called a directed diagram, and dually.


Finitely directed set


A finitely upward-directed set (which is the default notion) is a set with a preorder \leq such that:

  1. there exists an element (so the set is inhabited); and

  2. given elements x,yx, y, there exists an element zz such that xzx \leq z and yzy \leq z.

It follows that, given any finite set x 1,,x nx_1, \dots, x_n of elements, there exists an element zz such that x izx_i \leq z for all ii.

(For constructive purposes, one should interpret ‘finite set’ above as a finitely indexed set, as shown.)

Equivalently, this says:


A directed set is a proset which is a filtered category: a filtered (0,1)-category.


More generally, if κ\kappa is a cardinal number, then a κ\kappa-directed set is equipped with a preorder \leq such that, given any index set AA with A<κ|A| \lt \kappa and function ix ii \mapsto x_i from AA, there exists an element zz such that x izx_i \leq z for all ii. Then a finitely directed set is the same as an 0\aleph_0-directed set. An infinitely directed set allows any index set AA whatsoever, but this reduces to the statement that the proset has a top element.


Directions on the real line are quite interesting; there's a textbook (probably LIMITS: A New Approach to Real Analysis) that does ordinary calculus rigorously from scratch using directions, and there's a paper (which I can't find now) generalising interval arithmetic to arithmetic on directions.

As a partially ordered set is a special kind of category, so a (finitely) directed set is such a category in which all finite diagrams admit a cocone. If the category actually has finite coproducts (equivalently, all finite colimits), then it has all joins and so is a join-semilattice. (In particular, every join-semilattice is a directed set.)

Directed sets are heavily used in point-set topology and analysis, where they serve as index sets for nets (aka Moore–Smith sequences). In this application, it is important that a direction need not be a partial order, since a net need not preserve the preorder in any way but by default still preserves equality. (But in principle, one could force a directed set to be a poset by allowing a net to be a multi-valued function; this has practical consequences for the meaning of sequence in the absence of countable choice.)

Joins over directed index sets are directed joins; colimits over directed index sets are directed colimits. These play an important role in the theory of locally presentable and accessible categories; see also filtered category.

Revised on June 19, 2012 19:37:25 by Mike Shulman (