nLab
transfinite composition

Contents

Idea

The axioms of a category ensure that every finite number of composable morphisms has a (unique) composite.

Transfinite composition is a means to talk about morphisms in a category that behave as if they were the result of composing infinitely many morphisms.

Definition

Transfinite composition is indexed by ordinals. For convenience we first recall the definition of these assuming excluded middle in the ambient set theory (for definitions not assuming this see at ordinal and pointers given there):

Definition

A partial order is a set SS equipped with a relation \leq such that for all elements a,b,cSa,b,c \in S

1) (reflexivity) aaa \leq a;

2) (transitivity) if aba \leq b and bcb \leq c then aca \leq c;

3) (antisymmetry) if a aba\leq b and ba\b \leq a then a=ba = b.

This we may and will equivalently think of as a category with objects the elements of SS and a unique morphism aba \to b precisely if aba\leq b. In particular an order-preserving function between partially ordered sets is equivalently a functor between their corresponding categories.

A bottom element \bot in a partial order is one such that a\bot \leq a for all a. A top element \top is one for wich aa \leq \top.

A partial order is a total order if in addition

4) (totality) either aba\leq b or bab \leq a.

A total order is a well order if in addition

5) (well-foundedness) every non-empty subset has a least element.

An ordinal is the equivalence class of a well-order.

The successor of an ordinal is the class of the well-order with a top element freely adjoined.

A limit ordinal is one that is not a successor.

Examples

The finite ordinals are labeled by nn \in \mathbb{N}, corresponding to the well-orders {012n1}\{0 \leq 1 \leq 2 \cdots \leq n-1\}. Here (n+1)(n+1) is the successor of nn. The first non-empty limit ordinal is ω=[(,)]\omega = [(\mathbb{N}, \leq)].

Definition

Let 𝒞\mathcal{C} be a category, and let IMor(𝒞)I \subset Mor(\mathcal{C}) be a class of its morphisms.

For α\alpha an ordinal (regarded as a category), an α\alpha-indexed transfinite sequence of elements in II is a diagram

X :α𝒞 X_\bullet \;\colon\; \alpha \longrightarrow \mathcal{C}

such that

  1. X X_\bullet takes all successor morphisms ββ+1\beta \stackrel{\leq}{\to} \beta + 1 in α\alpha to elements in II

    X β,β+1I X_{\beta,\beta + 1} \in I
  2. X X_\bullet is continuous in that for every nonzero limit ordinal β<α\beta \lt \alpha, X X_\bullet restricted to the full-subdiagram {γ|γβ}\{\gamma \;|\; \gamma \leq \beta\} is a colimiting cocone in 𝒞\mathcal{C} for X X_\bullet restricted to {γ|γ<β}\{\gamma \;|\; \gamma \lt \beta\}:

    X βlim γ<βX γ. X_\beta \simeq \underset{\longrightarrow}{\lim}_{\gamma \lt \beta} X_\gamma \,.

The corresponding transfinite composition is the induced morphism

X 0X αlimX X_0 \longrightarrow X_\alpha \coloneqq \underset{\longrightarrow}{\lim}X_\bullet

into the colimit of the diagram, schematically:

X 0 X 0,1 X 1 X 1,2 X 2 X α. \array{ X_0 &\stackrel{X_{0,1}}{\to}& X_1 &\stackrel{X_{1,2}}{\to}& X_2 &\to& \cdots \\ & \searrow & \downarrow & \swarrow & \cdots \\ && X_\alpha } \,.
Remark

For purposes of constructive mathematics, the continuity condition should be stated as follows:

  • For every ordinal β<α\beta \lt \alpha, X X_\bullet restricted to {γ|γβ}\{\gamma \;|\; \gamma \leq \beta\} is a colimiting cone in 𝒞\mathcal{C} for the disjoint union of {X 0}\{X_0\} and the restriction of X X_{\bullet} to {γ+1|γ<β}\{\gamma + 1 \;|\; \gamma \lt \beta\}.

This actually includes F(0)=XF(0) = X as a special case but says nothing when β\beta is a successor (so the successor clause is still required).

Applications

Transfinite composition plays a role in

References

For instance

Revised on April 11, 2016 09:57:11 by Urs Schreiber (131.220.198.60)