nLab direction

Redirected from "directed set".
Contents

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

Contents

Idea and terminology

A direction on a set SS is a preorder on SS 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,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:

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

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.

Last revised on November 6, 2017 at 10:43:59. See the history of this page for a list of all contributions to it.