Simplex Category

definition example

The simplex category $\Delta$ has one object $[n]:=\{0<1<\cdots <n\}$ for each $n\in \mathbb{N}$, and its morphisms $[m]\to [n]$ are the monotone maps ($i\le j\Rightarrow f(i)\le f(j)$). It is the Skeleton of $\mathbf{FLin}$, the category of finite nonempty linear orders and monotone maps: every finite nonempty linear order is isomorphic to exactly one $[n]$, so the inclusion $\Delta \hookrightarrow \mathbf{FLin}$ is an Equivalence of Categories (CTfS Exercise 4.3.4.4) — just as the category of the sets $\underline{n}$ is equivalent to $\mathbf{Fin}$.

Sources: CTfS Exercise 4.1.1.8 (counting monotone maps), Exercise 4.3.4.4 ($\mathbf{FLin}\simeq \Delta$), Example 4.6.1.6 (simplicial sets), §4.6.3 ($\Delta \subseteq \mathbf{FLin}$ full), Exercise 4.5.2.9 (iterated cones); §2.7.4.3 (simplicial complexes).

Counting morphisms

A monotone map $[m]\to [n]$ is a non-decreasing sequence $f(0)\le \cdots \le f(m)$ of $m+1$ values in $\{0,\dots ,n\}$ — a multiset of size $m+1$ drawn from $n+1$ values — so

$$|\Delta ([m],[n])|=(\genfrac{}{}{0ex}{}{m+n+1}{m+1}).$$

In CTfS Exercise 4.1.1.8: $|\mathrm{Hom}([0],[3])|=4$ (pick a point), $|\mathrm{Hom}([3],[0])|=1$ ($[0]$ is terminal), $|\mathrm{Hom}([2],[3])|=\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, and $|\mathrm{Hom}([1],[n])|=\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)$.

Faces and degeneracies

Every monotone map factors uniquely as a surjection followed by an injection, and these are generated by

• coface maps $d^i:[n-1]\to [n]$, the injection that skips $i$ — including a face of an $(n-1)$-simplex into an $n$-simplex;
• codegeneracy maps $s^i:[n+1]\to [n]$, the surjection that hits $i$ twice — collapsing a simplex.

They satisfy the cosimplicial identities (e.g. $d^j{d}^i=d^i{d}^{j-1}$ for $i<j$), which give a presentation of $\Delta$.

Simplicial sets

A simplicial set is a Presheaf $X:{\Delta }^{\mathrm{op}}\to \mathbf{Set}$ — a C-Set on the schema ${\Delta }^{\mathrm{op}}$ (Opposite Category). $X_n:=X([n])$ is the set of $n$-simplices, and $X(d^i):X_n\to X_{n-1}$ takes the $i$-th face. Truncating at $n\le 1$ and forgetting degeneracies leaves the Graph schema $E\rightrightarrows V$: a simplicial set is a “higher-dimensional graph”. Unlike simplicial complexes, simplicial sets have “excellent formal properties” (CTfS Example 4.6.1.6): they form a Topos with all limits and colimits. The representable $\Delta (-,[n])$ is the standard $n$-simplex ${\Delta }^n$, and by the Yoneda Lemma its maps into $X$ are exactly $X_n$. The nerve of a category $\mathcal{C}$ has as $n$-simplices the composable strings $c_0\to c_1\to \cdots \to c_n$, and embeds $\mathbf{Cat}$ fully faithfully in simplicial sets.

The objects $[n]$ appear elsewhere too: $[n]$ is the $(n+1)$-fold iterated cone on the empty category (CTfS Exercise 4.5.2.9), and $[1]$ is the Walking Arrow.

JuliaLeanHaskell

Docs: Graphs

using Catlab
# monotone maps [m] → [n] between the linear orders {0<…<m}, {0<…<n}  (CTfS Exercise 4.1.1.8)
monotone_maps(m, n) = [f for f in Iterators.product(fill(0:n, m + 1)...) if issorted(collect(f))]
length(monotone_maps(0, 3)), length(monotone_maps(3, 0)), length(monotone_maps(2, 3))   # (4, 1, 20)
binomial(3 + 2 + 1, 2 + 1)                                                            # 20 = C(m+n+1, m+1)
# coface d^i : [n-1] → [n] skips i; codegeneracy s^i : [n+1] → [n] repeats i
d(i) = j -> j < i ? j : j + 1
s(i) = j -> j <= i ? j : j - 1
all((d(2) ∘ d(0))(j) == (d(0) ∘ d(1))(j) for j in 0:1)   # a cosimplicial identity: d²d⁰ = d⁰d¹
# the boundary of the 2-simplex as a symmetric graph (its 1-skeleton): an empty triangle
∂Δ2 = cycle_graph(SymmetricGraph, 3)
nv(∂Δ2), ne(∂Δ2) ÷ 2                                                                  # (3, 3)

import Mathlib
open CategoryTheory
#check SimplexCategory                 -- objects [n], morphisms monotone maps Fin (m+1) →o Fin (n+1)
#check @SimplexCategory.δ              -- coface maps
#check @SimplexCategory.σ              -- codegeneracy maps
#check @SimplexCategory.δ_comp_δ       -- a cosimplicial identity
#check SSet                            -- simplicial sets: SimplexCategoryᵒᵖ ⥤ Type
#check @nerve                          -- the nerve of a category

import Data.List (sort)
 
-- a morphism [m] → [n] as its list of values [f 0, …, f m] (non-decreasing)
monotone :: Int -> Int -> [[Int]]
monotone m n = filter (\f -> f == sort f) (sequence (replicate (m + 1) [0..n]))
 
compose :: [Int] -> [Int] -> [Int]      -- (g . f) as lists: apply g's table to f's values
compose g f = map (g !!) f
 
-- map length [monotone 0 3, monotone 3 0, monotone 2 3] == [4, 1, 20]