sec-crossword-limit

9.15 Running example: crossword solving as universal completion

A crossword puzzle gives a finite, visible instance of decentralized online decision making. Assign one agent to every across or down clue. Agent \(\alpha \) observes its clue text, the declared answer length \(m_\alpha \), and whatever crossing letters have currently been revealed. Its action space is not an untyped vocabulary but a length-indexed candidate object

\[ C_\alpha \subseteq \Sigma ^{m_\alpha }, \]

where \(\Sigma \) is the alphabet. The grid supplies the information and compatibility architecture independently of any particular solving algorithm.

Let \(E\) be the set of crossing cells. If crossing \(e\) joins clue \(\alpha \) at position \(p(\alpha ,e)\) to clue \(\beta \) at position \(p(\beta ,e)\), evaluation at that position gives maps

\[ \rho _{\alpha e}:C_\alpha \longrightarrow \Sigma , \qquad \rho _{\beta e}:C_\beta \longrightarrow \Sigma . \]

The compatible answer pairs at this one crossing form the pullback

\[ C_\alpha \times _{\Sigma }C_\beta . \]

To assemble all crossings at once, form the clue–crossing incidence category \(\mathbb X\). Its objects are the clues and crossing cells, and it has one arrow \(\alpha \to e\) for each incidence. Define the crossword diagram \(D:\mathbb X\to \mathbf{Set}\) by

\[ D(\alpha )=C_\alpha , \qquad D(e)=\Sigma , \qquad D(\alpha \to e)=\rho _{\alpha e}. \]

Definition 9.23 Crossword solution object

The crossword solution object is the limit

\begin{equation} \mathsf{Sol}(D)=\lim _{\mathbb X}D. \end{equation}

9.11

Equivalently,

\[ \mathsf{Sol}(D) \cong \left\{ (w_\alpha )_\alpha \in \prod _\alpha C_\alpha \ \middle |\ \begin{array}{l} \rho _{\alpha e}(w_\alpha )=\rho _{\beta e}(w_\beta ),\\[-2pt] \text{for every crossing }e=\alpha \cap \beta \end{array} \right\} . \]

Proposition 9.24 Universal property of crossword completion

For every set \(Z\) equipped with a compatible family of maps \(Z\to C_\alpha \) and \(Z\to \Sigma \) forming a cone over \(D\), there is a unique map \(Z\to \mathsf{Sol}(D)\) through which the entire family factors. Consequently, the points of \(\mathsf{Sol}(D)\) are exactly the globally consistent crossword fillings.

Proof ▼

This is the defining universal property of the limit in 9.11. In \(\mathbf{Set}\), a point of the limit selects one word from every \(C_\alpha \), while commutativity of its cone forces the two selected words incident at each crossing to have the same projected letter. Conversely, every such compatible selection determines a unique point of the limit.

The proposition identifies the universal part of solving. It does not assert that \(\mathsf{Sol}(D)\) is inhabited or has only one point. Nonempty local candidate sets, and even nonempty pullbacks at every crossing considered separately, need not produce a nonempty global limit because the locally compatible pairs may make incompatible choices elsewhere. An empty limit is a global contradiction; several points encode unresolved ambiguity; a singleton is a uniquely completed puzzle relative to the registered candidates.

This is also an exact UDL decomposition. A left stage interprets clue evidence and generates or enlarges the candidate objects \(C_\alpha \). The right stage is the limit, equivalently the right Kan extension along the terminal functor \(\mathbb X\to \mathbf1\), which retains only globally compatible families:

\[ \text{local clue evidence} \xrightarrow {\ \operatorname {Lan}\ } \text{typed candidate words} \xrightarrow {\ \operatorname {Ran}_{\mathbb X\to \mathbf1}=\lim _{\mathbb X}\ } \mathsf{Sol}(D). \]

The universal construction determines the object of feasible global decisions, not which feasible point an agent should prefer.

To make that final choice, attach a semantic score \(s_\alpha :C_\alpha \to V\) to each clue and declare an aggregation and an observer. In the familiar numerical realization one might select

\[ \operatorname *{argmax}_{(w_\alpha )_\alpha \in \mathsf{Sol}(D)} \sum _\alpha s_\alpha (w_\alpha ). \]

The limit supplies consistency; the scoring observer ranks its points. Neither operation substitutes for the other.

The Witsenhausen interpretation is equally direct. The agents share the team objective of completing one grid, but have different information fields

\[ \mathcal I_\alpha =\{ \text{clue }\alpha ,\ m_\alpha , \text{currently revealed crossing letters}\} . \]

The clue-intersection graph replaces a single global clock. Propagating a proposed letter changes the information available to neighboring agents, and reciprocal across–down dependencies can create cycles. The natural protocol is therefore asynchronous or nonsequential. If commitments affect downstream observations without transmitting the evidence that produced them, the information pattern can also exhibit Witsenhausen’s nonclassical feature.

Online revelation produces a changing diagram \(D_t\): definitions are recalled, candidate words are removed or reweighted, and crossing letters become fixed. Candidate restriction typically points from later to earlier sets, matching the inverse variance of the online Kan quotients in 9.7. A failed commitment can make \(\mathsf{Sol}(D_t)\) empty; repairing it requires revising a declaration or an earlier answer rather than estimating a better point inside the empty object.

Finally, the example separates tangent change from structural repair. Perturbing semantic scores while the grid, candidate supports, and crossing maps remain fixed belongs to one infinitesimal stratum. Adding a candidate, deleting a word, or changing the incidence diagram crosses a discrete boundary and is not represented by an ordinary tangent vector. With enriched candidate objects, a homotopy limit can retain alternative senses and the witnesses by which local interpretations cohere. Crossword solving will therefore serve throughout the book as a running test of four distinct operations: local generation, global consistency, observer-based selection, and repair under progressive revelation.

The crossword running example separates exact compatibility from selection and repair. A crossing is a pullback; the whole grid is the limit of the clue–crossing incidence diagram. An observer ranks points only after consistency, while an empty limit sends the solver back to the… — Figure 9.1 The crossword running example separates exact compatibility from selection and repair. A crossing is a pullback; the whole grid is the limit of the clue–crossing incidence diagram. An observer ranks points only after consistency, while an empty limit sends the solver back to the declaration.