nLab direction

This entry is about the concept in order theory. For the concept in analytic geometry see at direction of a vector.

Idea and terminology

A direction on a set $S$ is a preorder on $S$ in which any finite subset has an upper bound. A directed set is a set equipped with a direction. A directed poset is a directed set whose preorder is a partial order (so directed proset might be a better term than directed set). Note that many authors by directed set mean directed poset.

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 or codirected.

A subset of a poset (or proset) which is a directed set (when regarded as a poset in its own right) is a directed subset, and dually. More generally, a diagram in a category whose domain is a directed set (when regarded as a thin category) is called a directed diagram, and dually.

Definitions

Finitely directed set

Definition

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, y$, there exists an element $z$ such that $x \leq z$ and $y \leq z$.

It follows that, given any finite set $x_1, \dots, x_n$ of elements, there exists an element $z$ such that $x_i \leq z$ for all $i$.

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

Equivalently, this says:

Definition

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

In analogy with the definition there, we can provide an unbiased definition that is also commonly used in the literature:

Definition

A directed set is a proset in which every finite subset has an upper bound.

Higher cardinality

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 $A$ with $|A| \lt \kappa$ and function $i \mapsto x_i$ from $A$, there exists an element $z$ such that $x_i \leq z$ for all $i$. Then a finitely directed set is the same as an $\aleph_0$-directed set. An infinitely directed set allows any index set $A$ whatsoever, but this reduces to the statement that the proset has a top element.

Remarks

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.