\chapter{Recursive trees and their path spaces}
\label{tree:chapter}
\section{From arithmetical tests to trees}
\index{recursive tree}\index{analytical hierarchy}A tree on \(\omega\) is a set of finite strings closed under initial
segments. A path is a function \(x:\omega\to\omega\) all of whose finite
restrictions are in the tree. Use a fixed recursive coding of finite
strings. A family \(T_m\) is recursive when one program decides whether
a string belongs to \(T_m\), with \(m\) as an additional numerical
input. Write \([T_m]\) for the set of paths. The usual analytical classes
below are lightface unless a real parameter is displayed.
\begin{theorem}[Tree normal form]
\label{tree:normal}
A predicate \(A(m)\) is \(\Sigma^1_1\) iff there is a recursive family
of trees \(T_m\) with \(A(m)\) equivalent to \([T_m]\ne\varnothing\).
\end{theorem}
\begin{proof}
Write \(A(m)\) as \(\exists x\,\theta(m,x)\) with \(\theta\) arithmetical.
Put the number quantifiers in prenex form. A function of the earlier
universally quantified numbers can serve as a witness for each
existential number quantifier. Combine the finitely many new functions
and \(x\) into one real \(z\). The result is
\(\exists z\,\forall k\,R(m,z,k)\), where the test of \(R\) halts after
finitely many questions to \(z\). Put a string \(s\) in \(T_m\) when
none of the first \(|s|\) tests has rejected after \(|s|\) steps with
partial oracle \(s\). Suspend any test that asks for a value outside
\(s\). A rejection persists under extension. A failed total test is
eventually seen along the corresponding sequence of prefixes. Thus
paths are precisely the witnesses passing all tests. Conversely the
condition \(x\upharpoonright n\in T_m\) is recursive in \(m\) and the
prefix, so the existence of a path has the required formula.
\end{proof}
For a real input \(y\), the test can consult finite prefixes of \(y\)
and of the witness. This gives a recursive tree of pairs \((s,t)\) of
equal length. The set of pairs of reals passing the test is effectively
closed in Baire space squared, and the desired predicate is its
projection on the first coordinate. See \cite[Chs.~I--II]{Sacks}
and \cite{MosDescriptive}. Figure~\ref{tree:descending} shows why a test
for arbitrarily long finite instances cannot replace the path
quantifier on Baire space.
\begin{figure}[!ht]
\centering
\begin{tikzpicture}[
dot/.style={draw,rounded corners=2pt,inner sep=3pt,font=\small},
edge/.style={-{Latex[length=1.5mm]},thin},
every node/.style={font=\small}]
\node[dot] (r) at (0,0) {\(\langle\rangle\)};
\node[dot] (n0) at (-3,-0.9) {\(\langle0\rangle\)};
\node[dot] (n1) at (-1,-0.9) {\(\langle1\rangle\)};
\node[dot] (n2) at (1.5,-0.9) {\(\langle2\rangle\)};
\node (more) at (3,-0.9) {\(\cdots\)};
\node[dot] (n10) at (-1,-1.8) {\(\langle1,0\rangle\)};
\node[dot] (n20) at (.6,-1.8) {\(\langle2,0\rangle\)};
\node[dot] (n21) at (2.55,-1.8) {\(\langle2,1\rangle\)};
\node[dot] (n210) at (2.55,-2.7) {\(\langle2,1,0\rangle\)};
\foreach \source/\target in {r/n0,r/n1,r/n2,r/more,n1/n10,n2/n20,n2/n21,n21/n210}
{\draw[edge] (\source) -- (\target);}
\node at (-.95,-2.65) {\(\operatorname{rank}(\langle n\rangle)=n\)};
\end{tikzpicture}
\caption{The tree of strictly decreasing strings. Its root has rank
\(\omega\), but each choice of first coordinate bounds the length of
the remaining string.}
\label{tree:descending}
\end{figure}
\section{Path witnesses over a variable base}
\index{path object}\index{propositional truncation}In an \(\infty\)-topos \(\mathcal X\), fix \(U\) and a tower
\[
T_0 \longleftarrow T_1 \longleftarrow T_2 \longleftarrow \cdots
\]
in \(\mathcal X_{/U}\). A tree coded by subobjects of the finite
strings has such a tower. General towers also allow homotopy types as
the levels. Set \(W(T)=\lim_{n}T_n\) in the slice. A section \(V\to W(T)\)
over \(U\) is a coherent path parametrized by \(V\to U\). Thus the
tower expresses compatibility, including the coherence of the
restrictions when the levels are higher types. Let
\(\mathrm{Path}(T)=\tau_{\leq -1}^{U}W(T)\), regarded as a subobject of
\(U\). The expression \(\tau_{\leq -1}^{U}\) means relative
propositional truncation, or equivalently the image factor of
\(W(T)\to U\).
\begin{proposition}[Reindexing paths]
\label{tree:reindex}
For \(f:V\to U\) there are canonical equivalences
\[
f^*W(T)\simeq W(f^*T),\qquad
f^*\mathrm{Path}(T)\simeq \mathrm{Path}(f^*T).
\]
In spaces, if \(U\) and all levels of \(T\) are discrete, these
constructions give the ordinary family of path sets and its support.
\end{proposition}
\begin{proof}
Pullback in an \(\infty\)-topos has a left adjoint, so it preserves the
limit. Relative \((-1)\)-truncation is preserved by pullback. One can
also check the second claim using the image factorization as an
effective epimorphism followed by a monomorphism, both stable under
pullback. In spaces, limits of discrete spaces are discrete and the
\((-1)\)-truncation of a discrete space is nonempty iff the underlying
set is nonempty. Apply this calculation at every point.
\end{proof}
In the case of a subobject \(R\hookrightarrow U\times B\), this is the
base-change formula for the projection predicate
\(\exists_{U\times B\to U}R\), illustrated in
Figure~\ref{tree:basechange}. For Theorem~\ref{tree:normal} the subobject
\(R\) is the path relation and \(B=\omega^\omega\), taken discretely in
spaces. The object \(R\) can be retained after the existential
projection has been computed.
\begin{figure}[!ht]
\centering
\begin{tikzcd}[row sep=large,column sep=large]
R\times_U V \arrow[r]\arrow[d,two heads] & R\arrow[d,two heads]\\
\mathrm{im}(R\to U)\times_U V \arrow[r]\arrow[d,hook]
& \mathrm{im}(R\to U)\arrow[d,hook]\\
V \arrow[r,"f"']& U
\end{tikzcd}
\caption{The two squares are pullbacks. Reindexing carries both the
witness object and the proposition that witnesses exist.}
\label{tree:basechange}
\end{figure}
\begin{example}[Path transport around a circle]
\label{tree:circle}
Take \(\mathcal X=\mathcal S\), the \(\infty\)-category of spaces, and
let \(U=S^1\). Put \(T_0=U\) and \(T_n=\widetilde U\) for \(n\geq1\),
where \(\widetilde U\to U\) is the two-sheeted covering of the circle.
Let the first parent map be the covering and every subsequent map
be the identity. The fiber tree at any point consists of a root and
two rays. Its path object over \(U\) is the covering itself. Its image
is all of \(U\), whereas a section of the covering would split the
homomorphism \(\mathbb Z\xrightarrow{\times2}\mathbb Z\) induced on
fundamental groups. A circuit around the base exchanges the paths.
The same tower construction with the Hopf fibration
\(S^3\to S^2\) in place of the two-sheeted covering has connected path
fibers of type \(S^1\). Its image is all of \(S^2\), but it has no
section because \(\pi_2(S^3)=0\) and \(\pi_2(S^2)=\mathbb Z\).
Here a pointwise path choice fails to extend coherently even though
all the pointwise path spaces are connected.
\end{example}
The ordinary normal form singles out recursive codes in addition to
forming a limit and a projection. An arbitrary internal tower need
not have such a code. A realizability interpretation supplies its own
effective presentations, for example via the Kleene application
operation in assemblies. Tracking an arrow there is extra data even
when its underlying set map has already been specified \cite{Hyland}.
The comparison in Proposition~\ref{tree:reindex} concerns the
specified discrete trees and their truth values.
\section{Accessibility as a dependent polynomial}
\index{accessibility}\index{dependent polynomial}Let \(S\to U\) be an object of vertices and let \(D\) be an object of
edges. Write \(d:D\to S\) for the child and \(p:D\to S\) for the parent.
On \(\mathcal X_{/S}\) use the functor \(P=\Pi_p d^*\), with \(\Pi_p\)
the dependent product. In internal language \(P(X)_s\) is the type of
assignments of an \(X\)-witness to every child of \(s\). This is a
dependent polynomial with one constructor for each parent.
\begin{theorem}[Accessibility object]
\label{tree:access}
If \(P\) preserves \(\lambda\)-filtered colimits for a regular infinite
cardinal \(\lambda\), its initial algebra is the family obtained from
the empty family by \(\lambda\) stages of \(P\), taking colimits at
limit stages. The family is subterminal over \(S\) and is preserved by
change of base in \(U\).
\end{theorem}
\begin{proof}
The chain of length \(\lambda\) is \(\lambda\)-filtered, and its
successor stages are cofinal. Applying \(P\) to its colimit therefore
gives the same colimit. This is the initial algebra. Indeed, for any
algebra, the compatible maps from the chain into its carrier are forced
at the empty stage and at successors by the algebra operation, and at
limits by the colimit universal property. The chain construction with
this compatibility gives a contractible space of algebra maps. The
empty family and \(P\) preserve the subterminal condition, and
filtered colimits preserve it by exactness. Finally, pullback preserves
the colimits in the chain and commutes with dependent products by
Beck--Chevalley. The pulled-back chain stabilizes at the same stage and
gives the initial algebra there.
\end{proof}
In a presentable \(\infty\)-topos one can choose a sufficiently large
\(\lambda\), using accessibility of the adjoints between the
presentable slices \cite{Lurie}. The formula is the accessibility
instance of the construction of dependent well-founded trees. Compare
\cite{GambinoHyland}. For sets it says that a vertex is accessible
once every child is accessible. With dependent choice, a
nonaccessible vertex has an infinite path, since a nonaccessible
child can be chosen repeatedly. The converse holds by induction on an
accessibility derivation, by passing to the tail of any proposed path.
This converse works internally as well.
\begin{example}[No internal path, but no accessibility at the origin]
\label{tree:opens}
In the topos of sheaves on \(\mathbb R\), take a global root and let
level \(n\geq1\) be the open
\(U_n=(-1/n,1/n)\), with inclusions as the parent maps. Regard the same
objects as discrete sheaves of spaces. The limit of this tower of
subterminal objects is the interior of their intersection, hence
empty. At every stage of the accessibility construction, the
subobject of accessible vertices in each level excludes the origin.
For successors, every neighbourhood of zero at that level contains
zero in the next level, where accessibility has failed at the
preceding stage. Limits are unions of open subobjects. Thus the root
has no accessibility witness near zero even though the path predicate
is everywhere false. Away from zero one can use a neighbourhood
disjoint from some \(U_n\) and prove accessibility by finitely many
predecessor steps. The stalk at zero provides a further calculation.
Each level has a one-point stalk there, whereas the path object has
empty stalk. The stalk functor fails to preserve this countable limit.
Reindexing in Proposition~\ref{tree:reindex} is pullback in a fixed
topos and preserves all limits in the slices.
\end{example}
\section{Effective rank bounds}
\index{effective boundedness}\index{Kleene--Brouwer order}\index{separation theorem}Adjoin a root to an empty tree whenever necessary. A well-founded
tree in sets has a rank defined by the supremum of
\(\operatorname{rank}(t)+1\) over its immediate children \(t\). A
recursive well-founded tree has rank below \(\omega_1^{\mathrm{CK}}\).
Its Kleene--Brouwer order, with extensions first and larger distinct
coordinates later, is a recursive well-order. An infinite descending
sequence in that order would yield a path by eventually stabilizing
the coordinates one at a time. An order type of this order bounds the
tree rank.
\begin{theorem}[A bound for a family]
\label{tree:bounded}
Let \(D\subseteq\omega\) be \(\Sigma^1_1\), and let \(T_m\) be uniformly
recursive and well founded for \(m\in D\). One recursive ordinal
strictly bounds their root ranks for \(m\in D\).
\end{theorem}
\begin{proof}
Choose witness trees \(S_m\) for \(D\). Form a recursive tree whose
first coordinate chooses \(m\) and whose subsequent coordinates give
strings of equal length in \(S_m\) and \(T_m\). This tree is well
founded. A path would witness both \(m\in D\) and a path through
\(T_m\). If \(m\in D\), pairing each string of \(T_m\) with the
corresponding prefix of one path through \(S_m\) embeds \(T_m\) above
the first coordinate \(m\). The root rank of the combined tree
strictly bounds the rank in question.
\end{proof}
For separation, let \(A,B\subseteq\omega\) be disjoint \(\Sigma^1_1\)
sets, and choose witness trees \(T_m\) for \(B\). By
Theorem~\ref{tree:bounded} choose a recursive well-order of length
\(\beta+1\) with \(\beta\) greater than the ranks of the \(T_m\) for
\(m\in A\). At a successor stage prune the vertices with no child in
the preceding tree. At a limit take the intersection. A real coding
the entire pruning hierarchy of one \(T_m\) is given by an
arithmetical condition in the recursive well-order. Such a code
exists and is unique by transfinite recursion. Thus both assertion
and denial of root removal at stage \(\beta\) have a \(\Sigma^1_1\)
description, using the same hierarchy. The root has been removed for
\(m\in A\), and it survives for \(m\in B\), as the vertices of a path
survive every stage. Removal at \(\beta\) gives a \(\Delta^1_1\)
separator. This proof separates the effective contribution, the
recursive code for a common bound, from the semantic contribution,
transfinite pruning on the indicated presentation.
\section{Basis elements and uniformization}
Gandy's basis theorem gives an element \(x\) of any nonempty lightface \(\Sigma^1_1\) class in \(\omega^\omega\) with \(\omega_1^x=\omega_1^{\mathrm{CK}}\). Its relative form uses the join of \(x\) with the oracle in the presentation. This conclusion gives an ordinal bound on recursive well-orders in that parameter. The selected point need not be hyperarithmetic. A recursive tree can have a path and contain no hyperarithmetic path. The source of the basis theorem is a refinement of \(\Sigma^1_1\) conditions controlling each proposed relative well-order, using rank boundedness to control the successful comparisons \cite[Ch.~III]{Sacks}. The point satisfying the simultaneous constraints comes from an additional genericity argument on the analytic conditions.\index{Gandy basis theorem}
There is a simpler argument in the special case of a unique point. If \(A\) is a lightface \(\Sigma^1_1\) singleton \(\{a\}\), the two predicates
\[
\exists x\,(x\in A\ \wedge\ x(n)=k),\qquad
\exists x\,(x\in A\ \wedge\ x(n)\ne k)
\]
are both \(\Sigma^1_1\) and are disjoint complements. Thus the graph of \(a\) is \(\Delta^1_1\). Carrying out the argument uniformly for a recursively parameterized family of such singletons gives a single \(\Delta^1_1\) graph. A lightface \(\Pi^1_1\) singleton gives instead a \(\Delta^1_2\) graph by the same test with one more existential real quantifier. The effective coanalytic uniformization theorem supplies \(\Pi^1_1\) singletons in sections of a lightface \(\Pi^1_1\) relation on recursive Polish spaces, through a uniformizing subrelation \cite[Ch.~III]{Sacks}\cite{MosDescriptive}. Its selection is a statement about pointclasses on the chosen effective spaces.\index{coanalytic uniformization}
In the slice of spaces, uniqueness has a stronger homotopical form. If a witness map has contractible homotopy fibers, it is an equivalence, and its section has a contractible space of choices. If each fiber instead has exactly one component, the relative \(0\)-truncation has this uniqueness. The Hopf example above has this latter property without a section of the witness map. Transport therefore distinguishes two ways of interpreting a unique output. One is uniqueness of the equivalence class of the witness. The other is contractibility of the full witness type. The projection formulas carry either assertion under base change, once its appropriate witness object has been specified.
\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:II]{[Worked solutions]}}}
\begin{exercise}
\label{ex:II.1}
Make the timed-prefix test in Theorem~\ref{tree:normal} primitive
recursive by explicitly coding a bounded machine run. Include both a
real parameter and a numerical parameter in the test.
\end{exercise}
\begin{exercise}
\label{ex:II.2}
Replace the two-sheeted covering in Example~\ref{tree:circle} by a
finite local system over \(BG\) for a discrete group \(G\).
Characterize existence of a section of \(W(T)\) in terms of the action.
Compute the path support when the action set is empty.
\end{exercise}
\begin{exercise}
\label{ex:II.3}
Take two trees over \(U\) and put the fiber product of their levels at
every depth. Relate its path object to the two path objects. Compare
the path support of the product with the intersection of the two
supports.
\end{exercise}
\begin{exercise}
\label{ex:II.4}
Give the accessibility stages for the tree in
Figure~\ref{tree:descending}. Compare the stage of the root with the
stage of a root having one child of rank \(n\) for every positive even
number \(n\).
\end{exercise}
\begin{exercise}
\label{ex:II.5}
In a metric space, take a nonempty closed nowhere-dense set \(K\)
and put \(U_n=\{x:d(x,K)<1/n\}\). Use these levels in
Example~\ref{tree:opens}. Determine the root's path support and
accessibility support.
\end{exercise}
\begin{exercise}
\label{ex:II.6}
Relativize Theorem~\ref{tree:bounded} to a fixed real \(z\). Identify
which tree presentations, ranks, and pruning codes now depend on \(z\).
\end{exercise}
\begin{exercise}
\label{ex:II.7}
Produce a recursive well-founded tree of root rank
\(\omega+1\) such that exactly one child of the root has rank
at least \(\omega\). Construct a second example of rank
\(\omega\cdot2\) in which no child has that rank.
\end{exercise}
\begin{exercise}
\label{ex:II.8}
Given a uniformly \(\Sigma^1_1\) relation \(R(n,x)\) with at most one \(x\) in each fiber, determine the complexity of its domain. Under what hypothesis on that domain does the argument for singletons give a \(\Delta^1_1\) graph of the numerical values of its partial selector?
\end{exercise}
Original LaTeX source
Higher Categorical Recursion Theory
End of manuscript · Back to top ↑