ora-0021
1.9 Horns, composition, and quasi-categories
The \(i\)-th horn \(\Lambda _i^n\subset \Delta ^n\) contains every face except the \(i\)-th. A filler extends a map \(\Lambda _i^n\to X\) to \(\Delta ^n\to X\).
For \(n=2\), the inner horn \(\Lambda _1^2\) contains
but omits the composite edge \(x_0\to x_2\). A filler supplies the missing composite together with its compositional witness.
Following Section 1.1 of Riehl and Verity [ 2022 ] , we use quasi-categories as our concrete model of \(\infty \)-categories.
A quasi-category is a simplicial set \(X\) in which every inner horn can be filled. Explicitly, for every \(n\geq 2\), every \(0{\lt}i{\lt}n\), and every simplicial map \(u:\Lambda _i^n\to X\), there is an extension \(\bar u:\Delta ^n\to X\) satisfying
The filler is required to exist, but it need not be unique.
The nerve of an ordinary category has unique inner horn fillers. It fills all horns precisely when the category is a groupoid. A general quasi-category allows spaces of coherent compositions without requiring decisions to be reversible.
Rubik’s Cube gives a concrete world in which outer-horn filling is natural. Let \(X\) be the set of legal cube configurations and let \(G\) be the group generated by the legal face turns. The associated action groupoid
has configurations as objects and a morphism \((g,x):x\to g\mathbin {\cdot }x\) for each move sequence \(g\). Its inverse is \((g^{-1},g\mathbin {\cdot }x)\). Consequently, the nerve \(N(G\ltimes X)\) is a Kan complex: inner horns are filled by composing move sequences, while outer horns are filled by reversing moves to recover a missing side of a compositional history.
Sokoban has a sharply different geometry. Its objects may again be taken to be legal board configurations and its morphisms to be executable action sequences. Local walking moves are often reversible, but a push need not be. If a crate is pushed into a non-goal corner, no legal action sequence can “unpush” it. The resulting decision category still has composites, so its ordinary nerve has unique inner-horn fillers, but it is not a groupoid and some outer horns have no fillers.
The contrast is structural rather than merely a difference in difficulty. A Rubik’s Cube learner can seek a latent group action, generators, inverses, and relations. A Sokoban learner must also represent irreversible reachability and detect actions that destroy future possibilities. Thus horn filling turns reversibility into a property of the learned compositional world rather than an informal attribute attached to particular actions.
The classical algebraic counterpart of this contrast is the Krohn–Rhodes prime decomposition theorem [ Krohn and Rhodes , 1965 ] . It represents a finite-state machine by a cascade of permutation components, whose dynamics are group-like and reversible, and reset components, whose dynamics discard information. Chapter 5 returns to the theorem as a possible learning principle: discover a compact hierarchy of reversible and irreversible generators instead of reconstructing a flat global state space.
11. Inner horns ask whether observed local steps compose coherently. Outer horns ask whether a missing step can be recovered by solving backward. Rubik’s Cube generally permits both; Sokoban need not. ↩
Convention. Unless another model is explicitly declared, the term \(\infty \)-category in this book means a quasi-category. Thus its higher composition is encoded by compatible inner-horn fillers rather than by strictly unique composites.
The term Kan appears in two related but distinct constructions. A Kan extension universally extends a diagram. A Kan horn-filling condition belongs to simplicial homotopy theory. UODL uses both, but one does not imply the other.