\chapter{Priority and coherent stabilization}
\label{pri:chapter}
\section{Restraints and blocks}
Let \(\alpha\) be admissible. A requirement in an \(\alpha\)-recursive construction controls a portion of a growing oracle. An action may enumerate an ordinal into the oracle and at the same time protect an \(\alpha\)-finite set of negative answers. An injury occurs when an action of higher priority conflicts with a protected answer. The injury discards the affected computation and may create a need for a new witness. The relevant question is whether all the earlier injuries fit in one history in \(L_\alpha\).
For example, to construct incomparable enumerably presented oracles \(A,B\), assign an unbounded supply of distinct witnesses to each proposed reduction. Suppose a stage witnesses that a procedure using \(B\) gives answer \(0\) on a chosen witness \(x\). An action puts \(x\) into \(A\) and restrains changes in the queried negative part of \(B\). Positive answers to queries about \(B\) survive because the enumeration is increasing. If the restraint survives, the reduction fails at \(x\). If the reduction is total and correct, some such action must eventually occur once the higher restraints have settled. An unchanged witness outside \(A\) would otherwise get a convergent answer \(0\) with a genuine use. This is the diagonal argument behind the classical method. The eventual success of a particular priority scheme depends on which histories the ground model can collect.
At an admissible ordinal, the work of Sacks and Simpson proves incomparability even for the weak version of reducibility. The \(\alpha\)-finite injury method bounds the uses of predecessor requirements by working below suitable internal cardinals. Other cases require projecting the list of requirements down to a shorter list on which the stabilization argument can be run. Shore's method puts requirements with the same side of the construction into blocks and orders the blocks by a definable cofinal sequence. Its benefit is that requirements in a block need not injure one another. The proofs use specific connections among projecta, definable cofinalities, and bounded enumerations \cite[VIII.1--3]{Sacks}\cite{ShoreUniform,ChongFriedman}.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Latex, x=1cm,y=1cm,font=\small]
\draw[->] (0,0)--(10.6,0) node[right]{stage};
\draw[thick,blue!70!black] (0.5,0.75)--(3.2,0.75);
\draw[thick,blue!70!black] (3.7,0.75)--(6.0,0.75);
\draw[thick,blue!70!black,->] (6.65,0.75)--(9.95,0.75);
\draw[thick,orange!75!black] (1.0,1.6)--(3.2,1.6);
\draw[thick,orange!75!black,->] (3.7,1.6)--(9.95,1.6);
\draw[dashed] (3.4,-.22)--(3.4,1.86);
\draw[dashed] (6.25,-.22)--(6.25,1.04);
\node[anchor=west] at (0.55,1.95) {earlier block};
\node[anchor=west] at (0.55,1.10) {later block};
\node[below] at (3.4,-.05) {injury};
\node[below] at (6.25,-.05) {new restraint};
\node[anchor=south] at (8.25,.77) {stable tail};
\end{tikzpicture}
\caption{A block history records injuries as well as the restraint that survives. Uniform stabilization of a prefix asks for one tail on which every restraint in that prefix has settled.}
\label{pri:injury-figure}
\end{figure}
\begin{definition}
An \(\alpha\)-recursive approximation \(a(s,i)\) to an ordinal function \(a_\infty\) on \(\gamma\leq\alpha\) is \emph{tame} if for every \(\delta<\gamma\) there is \(b<\alpha\) such that \(a(s,i)=a_\infty(i)\) for all \(s\geq b\) and \(i<\delta\).
\end{definition}
Sacks's tame \(\Sigma_2\) maps admit approximations of this kind. The \(\Sigma_1\) projectum is the least \(\rho\leq\alpha\) into which \(\alpha\) admits a \(\Sigma_1\)-definable injection, with set parameters allowed. A tame \(\Sigma_2\) projectum instead measures the minimal indexing length of a tame map onto the height. The two constraints are different. A shorter list of codes may have an approximation which keeps changing arbitrarily late on one proper prefix. Admissible collection gives a convenient sufficient condition.
\begin{lemma}[Collecting final-action bounds]
\label{pri:collect}
Let \(d\in L_\alpha\), and suppose \(a(s,i)\) is defined for \(s<\alpha\), \(i\in d\). If a total \(\Sigma_1(L_\alpha)\) graph \(b:d\to\alpha\) has the property that \(a(s,i)\) is constant for \(s\geq b(i)\), then there is a common stabilization stage for \(d\).
\end{lemma}
\begin{proof}
Apply \(\Sigma_1\) Collection to witnesses for the graph. The range of \(b\) is a set in \(L_\alpha\), and its supremum is an ordinal of \(L_\alpha\). Use that supremum as the common stage.
\end{proof}
The \(\Sigma_1\) hypothesis is on a bound with its witnesses. A proof of eventual constancy for each coordinate does not supply those witnesses automatically. For \(\alpha=\omega\), the approximation \(a(s,i)=1\) for \(i<s\) and \(0\) otherwise stabilizes uniformly on every finite prefix. No stage is constant on the entire domain. The same distinction applies at transfinite stages, with the ground notion of boundedness in place of numerical finiteness.
\section{Stabilization in a slice}
Let \(\mathcal X\) be an \(\infty\)-topos and \(U\in\mathcal X\). Let \(S\) be a nonempty ordinal of stages and \(I\) a small partially ordered set of observation windows. The order \(i\leq j\) means that \(i\) is a restriction of \(j\). A \emph{history} in this section is a diagram
\[
H:N(I^{\mathrm{op}})\times N(S)\longrightarrow\mathcal X_{/U}.
\]
Here \(N\) denotes the nerve. The \(S\)-arrows advance a record. The \(I^{\mathrm{op}}\)-arrows discard its observations outside a smaller window. A new stage may discard failed choices even if the underlying oracle grows. For actual construction records these arrows must be supplied with the corresponding coherence data. A sequence of estimates that offers only objects at each stage does not yet define such a history. In particular the following result applies after one has built a coherent record of the operations and cancellations.
Call \(i\) eventually stable if every transition on some tail \(S_{\geq b_i}\) is an equivalence in the slice. Write \(H_\infty(i)=\operatorname{colim}_{s\in S}H(i,s)\). The colimit here is semantic. It need not be formed inside \(L_\alpha\).
\begin{proposition}[Coherent eventual objects]
\label{pri:eventual}
If \(i\) is eventually stable, every structural map \(H(i,s)\to H_\infty(i)\) with \(s\geq b_i\) is an equivalence. If \(J\subseteq I\) is a subposet with one bound \(b\) for all its windows, then the comparison
\[
H(-,b)|_{J^{\mathrm{op}}}
\longrightarrow H_\infty|_{J^{\mathrm{op}}}
\]
is an equivalence of diagrams. These assertions are preserved by pullback along any \(V\to U\).
\end{proposition}
\begin{proof}
Every tail is cofinal. It has a first object \(b_i\), so the transition maps give a natural transformation from the constant diagram at \(H(i,b_i)\) to the tail. This is a pointwise equivalence by the stabilization hypothesis. The indexing nerve is contractible, so the colimit of that constant diagram is \(H(i,b_i)\). This proves the assertion at \(b_i\), and the same argument applies starting at a later \(s\). With a common bound \(b\), the structural comparison is natural on \(J^{\mathrm{op}}\) and equivalences of diagrams are pointwise. Finally, pullback on slices has both adjoints and hence preserves the colimits computing \(H_\infty\).
\end{proof}
The square in Figure~\ref{pri:window-square} records a coherence condition in the history. For two stable windows, take a stage later than both bounds to read the restriction map between the eventual objects. Proposition~\ref{pri:eventual} shows that this reading is compatible with all subsequent stages. It also identifies the reading for any subdiagram that has a common bound. This allows the restrictions to retain nontrivial automorphisms of the stable witnesses.
\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=2.4em,row sep=2.6em]
H(j,s) \arrow[r] \arrow[d,"\mathrm{res}"']&
H(j,t) \arrow[r] \arrow[d,"\mathrm{res}"']&
H_\infty(j) \arrow[d,"\mathrm{res}"]\\
H(i,s) \arrow[r]&
H(i,t) \arrow[r]&
H_\infty(i)
\end{tikzcd}
\caption{Advancing a record and restricting a window commute with the coherence of the history. The horizontal maps are equivalences once the corresponding row has stabilized.}
\label{pri:window-square}
\end{figure}
\begin{theorem}[Descent of a specified bound]
\label{pri:descent}
Let \(v:V\to U\) be an effective epimorphism and \(b\in S\). If every transition of \(v^*H(i,-)\) beyond \(b\) is an equivalence for each \(i\in J\), then \(b\) is a common bound for \(H\) on \(J\). For a covering family, separate bounds suffice if they are bounded by a single stage.
\end{theorem}
\begin{proof}
For each transition use conservativity of pullback along \(v\). Indeed, slice descent along the Čech nerve of \(v\) identifies a morphism over \(U\) by its compatible pullbacks. If its pullback to \(V\) is an equivalence, then so are its pullbacks in every degree of the Čech nerve. An equivalence in that limit of slices is detected componentwise. For a covering family, pull back first along its coproduct and use the common stage.
\end{proof}
Local existence of a stabilization stage may fail to give a global one. In spaces, take \(U=\mathbb N\) discrete and \(S=\omega\). At stage \(s\) let the fiber over \(n\) be \(B\mathbb Z\) when \(n\leq s\), and a point otherwise. At the first change use the basepoint inclusion. There is a bound over each component. There is no single bound over \(U\), because the transition where the \(n\)-th circle appears changes the fundamental group of that fiber. The eventual family still exists and its pullbacks satisfy Proposition~\ref{pri:eventual}.
\section{Observing infinitely many windows}
Consider the natural comparison
\[
\operatorname{colim}_{s\in S}\lim_{i\in I^{\mathrm{op}}}H(i,s)
\longrightarrow
\lim_{i\in I^{\mathrm{op}}}\operatorname{colim}_{s\in S}H(i,s).
\]
If there is a common stabilization stage on \(I\), both sides are computed by the stage diagram at that bound. Stable behavior at individual windows is weaker, even if every proper initial segment of windows has a bound.
\begin{example}[Direct sum and product of loop groups]
\label{pri:sumproduct}
Work in spaces and put \(S=I=\omega\). Let \(H(i,s)=(B\mathbb Z)^{\min(i,s)}\). Restriction forgets final coordinates. Advancement appends basepoints. The two operations commute and define a history. At fixed \(i\) the eventual value is \((B\mathbb Z)^i\). At fixed \(s\) the inverse limit over windows is \((B\mathbb Z)^s\). The comparison therefore induces on fundamental groups the inclusion
\[
\bigoplus_{n<\omega}\mathbb Z
\longrightarrow \prod_{n<\omega}\mathbb Z .
\]
In computing the left group one uses that loops, and homotopies of loops, in a filtered colimit of spaces are represented at finite stages. On the right, loops in the product are products of loops. The all-ones element is absent from the image. These histories are tame on every finite initial window, yet a compatible family of loop classes can require unboundedly many stages.
\end{example}
The distinction explains the role of a bounded family of requirements in an ordinal construction. A finite or adequately bounded collection of windows can be audited from a single stage. The inverse limit of all the eventual windows counts coherent observables regardless of whether a single admissible stage presented them. The effectivity conditions in the classical priority proof address the former operation.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:VIII]{[Worked solutions]}}}
\begin{exercise}
\label{ex:VIII.1}
Give a priority rule for two conflicting finite signed restraints and analyze what happens if the same requirement has the right to discard its own witness repeatedly. Specify an extra condition on the rule that bounds its own actions when all higher restraints have stabilized.
\end{exercise}
\begin{exercise}
\label{ex:VIII.2}
For a countable successor-stage construction with finite predecessors, assume each new injury is charged to a distinct higher-priority action. Bound the number of actions at each requirement when every requirement acts at most once in each interval separated by injuries, including the initial and final intervals. A requirement with no injuries may act at most once. State which part of the argument changes if the predecessor list is infinite.
\end{exercise}
\begin{exercise}
\label{ex:VIII.3}
Replace the ordinal \(S\) in Proposition~\ref{pri:eventual} by a small directed poset. Formulate a cofinal-cone hypothesis giving a common representative for the eventual diagram on a given finite family of windows.
\end{exercise}
\begin{exercise}
\label{ex:VIII.4}
Let \(G\) act nontrivially on a finite set \(E\). Regard this action as a family over \(BG\). Construct a history over \(BG\) with stable fiber \(E\) and describe the distinction between a stable family and a stable section.
\end{exercise}
\begin{exercise}
\label{ex:VIII.5}
Modify Example~\ref{pri:sumproduct} to put the obstruction in \(\pi_k\) for each fixed \(k\geq 2\). Determine the comparison on all homotopy groups.
\end{exercise}
\begin{exercise}
\label{ex:VIII.6}
Give a criterion in terms of cofinality of \(S\) and cardinality of \(I\) that turns separate bounds into a common bound. Prove the corresponding sufficiency for a covering family in Theorem~\ref{pri:descent}.
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑