Independent scholarship · Open accessThe monthly digest

Original LaTeX source

Higher Categorical Recursion Theory

\chapter{Forcing and sheaves of witnesses}
\label{forc:chapter}

\section{Three orders on information}

A rank bound makes analytic truth accessible to a stage-by-stage analysis. Chapter IV of Sacks applies this idea to measure, Cohen forcing, and perfect forcing. In each case a smaller condition supplies more information, but the admissible restrictions differ. A Cohen condition is a binary cylinder \([s]\), refined by extending the finite string \(s\). A measure condition is a Borel set of positive measure, ordered by inclusion modulo null sets. A perfect condition is a nonempty perfect closed subspace of Cantor space, refined by taking a perfect subspace. In the effective theory the last conditions carry hyperarithmetic codes. The three choices give different basis and degree theorems. For instance the measure theorem gives a hyperarithmetic member of a positive-measure lightface \(\Pi^1_1\) set, while the effective perfect forcing theorem gives minimal hyperdegrees \cite[IV.2 and IV.5]{Sacks}.

For category, a set is meager if it is contained in a countable union of nowhere dense sets. A null set has measure zero for the usual product probability on Cantor space. Even for Borel sets these notions differ. For each \(m\) choose, inside every basic cylinder, a smaller cylinder so that the sum of the measures of the chosen cylinders is less than \(2^{-m}\). Their union \(O_m\) is open and dense. The intersection \(\bigcap_m O_m\) is dense and null. Its complement is meager and conull. The choice of forcing decides which assertion of existence these sets can witness.

Let \(P\) be a nonempty set of conditions, ordered so that \(q\leq p\) means \(q\) is stronger. The lower sets form a topology on \(P\). Write \(B=\operatorname{RO}(P)\) for the complete Boolean algebra of regular opens \(U=\operatorname{int}\overline{U}\), and set
\[
 e(p)=\operatorname{int}\overline{\{q:q\leq p\}} .
\]
The image is dense in \(B\setminus\{0\}\). Indeed any nonempty regular open contains some \(p\) and then contains \(e(p)\). Two conditions are compatible precisely when their regular opens have nonempty intersection. For the nontrivial implication, if \(r\) belongs to both regular opens, extend \(r\) first below \(p\) and then below the second condition. Such refinements exist by the definition of regularization in the lower topology. A downward closed sieve \(S\) below \(p\) covers in the dense topology precisely when
\[
 \bigvee_{q\in S}e(q)=e(p).
\]
For if \(S\) is dense below \(p\), its union of lower opens has the same regularization as the lower open of \(p\). If some refinement \(r\le p\) has no further refinement in \(S\), the nonzero open \(e(r)\) is disjoint from the join. This argument also explains how a dense basis of conditions presents the same local truth values as the Boolean algebra.

\section{What a Boolean truth value retains}

Regard a complete Boolean algebra \(B\) as a site with covers \(b=\bigvee_i b_i\). Let \(\mathcal X_B=\operatorname{Shv}(B;\mathcal S)\) be its \(\infty\)-topos of sheaves of spaces. Denote by \(h_b\) the representable subterminal sheaf for \(b\). Its support is \(b\). In fact a subterminal sheaf is determined by the ideal of objects over which it has a section. The ideal is downward closed and closed under arbitrary joins by descent. It is therefore principal, so \(\operatorname{Sub}(1)\cong B\). For a sheaf \(W\) let \(\|W\|\in B\) denote the support of \(W\to 1\). Then
\[
 \|W\|=\bigvee\{b:W(b)\text{ is nonempty}\}.
\]
The formula asserts local existence. The space \(W(b)\) may retain the group of automorphisms of a witness and the homotopies between its identifications. Those data do not enter the join.

\begin{lemma}
\label{forc:partitions}
Every cover of \(b\in B\) has a disjoint refinement whose join is \(b\). If \(b=\bigvee_i c_i\) is disjoint, evaluation at \(b\) satisfies
\[
 W(b)\simeq \prod_i W(c_i).
\]
Thus \(b\leq\|W\|\) implies that \(W(b)\) is nonempty.
\end{lemma}
\begin{proof}
Well-order the covering family and replace its \(i\)-th member \(b_i\) by
\(c_i=b_i\wedge\neg\bigvee_{j<i}b_j\). Omitting zero terms gives a disjoint family with the same join, by induction on the ordering. In the sheaf topos, \(\coprod_i h_{c_i}\to h_b\) is an effective epimorphism by the cover condition. It is a monomorphism because the summands are subterminal and pairwise disjoint, and coproducts are disjoint and universal. It is consequently an equivalence. Mapping this equivalence into \(W\) gives the product formula, illustrated in Figure~\ref{forc:fig-partition}. If \(b\leq\|W\|\), intersect a cover by opens carrying sections with \(b\), take a disjoint refinement, and choose the local sections. The product formula amalgamates them.
\end{proof}

\begin{figure}[htbp]
\centering
\begin{tikzcd}[column sep=3em,row sep=2.7em]
\displaystyle\coprod_i h_{c_i}
  \arrow[r,"\simeq"]
  \arrow[d,"\bigsqcup_i w_i"'] &
h_b \arrow[dl,dashed,"w"] \\
W &
\end{tikzcd}
\caption{On a disjoint Boolean partition, a system of local witness maps glues to a witness over the entire condition. The equivalence retains the whole mapping space.}
\label{forc:fig-partition}
\end{figure}


\begin{proposition}
\label{forc:boolean-arity}
In \(\mathcal X_B\), all base changes of \(\Pi_p\) preserve effective epimorphisms if and only if \(p\) is \(0\)-truncated.
\end{proposition}
\begin{proof}
First let \(Z\to h_b\) be a set-valued sheaf over a representable. Every local section \(h_c\to Z\) is a monomorphism. These subterminals cover \(Z\). The lattice \(\operatorname{Sub}(Z)\) is Boolean. For a subobject \(Q\), the pullback along each section \(z:h_c\to Z\) is \(h_d\hookrightarrow h_c\) for some \(d\leq c\). Split \(c\) into \(d\) and \(c\wedge\neg d\). On the second part the section has image disjoint from \(Q\), while on the first it factors through \(Q\). The sections jointly cover \(Z\), so \(Q\) and its pseudocomplement cover \(Z\). Applying the disjoint-refinement argument of Lemma~\ref{forc:partitions} in \(\operatorname{Sub}(Z)\) writes \(Z\) as a coproduct of subterminals.

Suppose \(p:C\to A\) is \(0\)-truncated. To test lifting for its dependent product, take a representable \(h_b\to A\) and a section of the target dependent product over \(h_b\). By adjunction that section is a map out of \(C\times_A h_b\). This arity is a set-valued sheaf over \(h_b\), so it decomposes as above. Each summand lifts through the given effective epimorphism by Lemma~\ref{forc:partitions} applied to its pullback. Their coproduct is a lift. Representables test effective epimorphisms because they generate sheaves under colimits. The argument applies after arbitrary base change.

Conversely assume preservation after every base change. For \(h_b\to A\) take \(Z=C\times_A h_b\), and cover \(Z\) by a coproduct \(Y\) of representables, using its local sections. The dependent product of \(Y\to Z\) is then effective epimorphic over \(h_b\), so it has a section over \(h_b\) by Lemma~\ref{forc:partitions}. This gives a section of \(Y\to Z\). A retract of a \(0\)-truncated object is \(0\)-truncated, so \(Z\) is \(0\)-truncated. Testing on the representables covering \(A\) yields the claim.
\end{proof}

For example let \(b=c\vee d\) be a nontrivial disjoint partition. In \(\mathcal X_B/h_b\) let a witness be locally an object of the classifying spaces \(B C_2\) over \(c\) and \(B C_3\) over \(d\). More precisely take the coproduct of the constant sheaf of value \(B C_2\) in the slice over \(c\) and of value \(B C_3\) over \(d\). Its support is \(b\). Under restriction of the witness family to nonzero Boolean pieces of either region, the corresponding finite groups act by automorphisms of the trivial witness. The two actions are distinguishable in the slice. Every nonzero subregion of \(c\) still has a nonidentity automorphism of order two on the trivial witness. Over \(d\), a witness is locally isomorphic to the trivial witness with automorphism group \(C_3\). Thus an automorphism of order dividing two is locally the identity and hence the identity by descent. The Boolean truth value discards the variation of the groups.

For truth at a generic, there is an important restriction on the families of joins used. Let \(M\) be a transitive ground model with a Boolean algebra which it regards as complete. An \(M\)-generic filter \(G\) on its nonzero conditions meets every dense set of conditions in \(M\). For a family \((b_i)\in M\),
\[
 \bigvee_i b_i\in G\quad\Longleftrightarrow\quad
 b_i\in G\text{ for some }i .
\]
Indeed the conditions below some \(b_i\), together with those below \(\neg\bigvee_i b_i\), form a dense set in \(M\). The equivalence proves the existential step of the truth lemma for formulas whose ranked name families belong to \(M\). The Boolean and atomic steps then use the ultrafilter property and atomic evaluation. A ground generic filter need not preserve joins from arbitrary families outside the ground model. This truth test is about Boolean values of propositions. It makes no assertion about evaluating higher witness types, or about hyperdescent on arbitrary hypercovers.

\section{A bound from the chain condition}

The following result gives a categorical form of one part of the rank argument. Call \(B\) \(\kappa\)-cc if every pairwise disjoint family of nonzero elements has cardinality less than the infinite cardinal \(\kappa\). Let \((W_\alpha)_{\alpha<\lambda}\) be a chain of sheaves of possible witnesses as the rank bound grows, where \(\lambda\) is a limit ordinal. Its Boolean support values are increasing. This is the situation obtained from a filtered name family as in Proposition~\ref{ind:filtered-image}.

\begin{theorem}
\label{forc:cc-bound}
Suppose \(B\) is \(\kappa\)-cc and \(\operatorname{cf}(\lambda)\geq\kappa\). If \(\bigvee_{\alpha<\lambda}\|W_\alpha\|\geq b\), there is a single \(\beta<\lambda\) for which \(W_\beta(b)\) is nonempty.
\end{theorem}
\begin{proof}
The elements \(b\wedge\|W_\alpha\|\) cover \(b\). Refine the cover to a disjoint partition \((c_i)\) by Lemma~\ref{forc:partitions}. Discard zero parts and choose \(\alpha_i<\lambda\) such that \(c_i\leq\|W_{\alpha_i}\|\). There are fewer than \(\kappa\) such stages. Their supremum is below \(\lambda\). Take \(\beta\) to be that supremum. By monotonicity every part satisfies \(c_i\leq\|W_\beta\|\), so their join \(b\) does too. The same lemma supplies the section at stage \(\beta\).
\end{proof}

The Cohen algebra has a countable dense basis of cylinders. Distinct disjoint nonzero elements must then contain distinct cylinders, so the algebra is \(\aleph_1\)-cc. In the measure algebra disjoint positive elements with measure at least \(1/n\) can occur at most \(n\) times, proving the same chain condition. The Church--Kleene ordinal has external cofinality \(\omega\). The theorem therefore does not supply the effective bound Sacks obtains for names below that ordinal. For a concrete failure at a countable limit, the cylinders \([0^i1]\) for \(i<\omega\) have join one in the Cohen algebra. Their union omits just the all-zero sequence. No finite initial portion has join one. The same example works in the measure algebra.

For perfect forcing in its full set-theoretic version, the perfect sets obtained by fixing all even coordinates to \(x\), for \(x\in 2^{\mathbb N}\), form a disjoint family of conditions. Their corresponding elements of \(B\) are disjoint and nonzero. Choose \(\omega_1\) of them, denoted \(d_\xi\), and let \(c\) be the complement of their join. The elements
\[
 b_\alpha=c\vee\bigvee_{\xi<\alpha}d_\xi
 \qquad(\alpha<\omega_1)
\]
have join one, and none equals one. Taking \(W_\alpha=h_{b_\alpha}\) shows that the stated uniform bound can fail at uncountable cofinality if the chain condition fails. This example concerns full perfect forcing. The countable collection of all hyperarithmetically coded trees is a different forcing presentation.

\section{Fusion and effective separation}

A perfect condition retains several incompatible alternatives. Fusion preserves them at successive depths, which explains why the usual decreasing-sequence construction for Cohen forcing does not suffice. The following version isolates the coding geometry from the required effective choices.

\begin{proposition}
\label{forc:continuous-fusion}
Let \(F:P\to 2^{\mathbb N}\) be continuous with \(P\) a nonempty perfect closed subset of Cantor space. There is a perfect closed \(Q\subseteq P\) on which \(F\) is constant or a topological embedding.
\end{proposition}
\begin{proof}
If \(F\) is constant on some nonempty relatively clopen subset of \(P\), take that subset. It remains perfect. Otherwise every nonempty relative clopen set has two points with different images. For each node of a full binary tree choose two disjoint nonempty relatively clopen subsets of its current clopen set, of diameters at most \(2^{-n}\) at level \(n\). Choose them near such a pair of points so that their images are contained in distinct cylinders. Continuity supplies these neighborhoods. Figure~\ref{forc:fig-fusion} shows two levels of the resulting refinement. At a given level the images of any two pieces are in disjoint sets, since this property was imposed where their branches first split. The intersection of the decreasing finite unions of pieces is compact. Along each branch compactness and the diameter bounds give one point, and distinct branches give distinct points. The branch map is continuous by the same bounds, so it is a homeomorphism onto a perfect set \(Q\). Distinct points have different images. The restriction is a continuous injection from a compact space to a Hausdorff space and is therefore an embedding.
\end{proof}

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[every node/.style={font=\small},>=Latex,x=1.2cm,y=1.01cm]
\node (r) at (0,0) {\(P\)};
\node (l) at (-1.55,-1) {\(P_0\)};
\node (b) at (1.55,-1) {\(P_1\)};
\node (ll) at (-2.25,-2) {\(P_{00}\)};
\node (lr) at (-.85,-2) {\(P_{01}\)};
\node (bl) at (.85,-2) {\(P_{10}\)};
\node (br) at (2.25,-2) {\(P_{11}\)};
\draw[thick,blue!66!black,->] (l) -- (r);
\draw[thick,orange!72!black,->] (b) -- (r);
\draw[thick,blue!66!black,->] (ll) -- (l);
\draw[thick,blue!66!black,->] (lr) -- (l);
\draw[thick,orange!72!black,->] (bl) -- (b);
\draw[thick,orange!72!black,->] (br) -- (b);
\end{tikzpicture}
\caption{Fusion keeps both children of each selected piece. Distinct image cylinders at a split remain distinct under every later refinement.}
\label{forc:fig-fusion}
\end{figure}

The corresponding lemma in Sacks deals with ranked formulas along hyperarithmetic perfect conditions. In the injective alternative one must also make recovery of the branch effective from its output and a fixed auxiliary code. The geometric proof does not control the complexity of the chosen clopen sets. Passing to a Boolean completion discards the rank of a Borel code. For instance a nonempty closed null set has value zero in the measure algebra regardless of how its code was obtained. Forcing can organize proofs of effective separation, but the proof has to work with the coded conditions and their bounds to retain that conclusion.


\section{A bound on the complexity of a separator}

There is a separation result in which the witness to be retained is itself a code. Fix a recursive ordinal \(\xi>0\). If two disjoint lightface analytic sets in Baire space can be separated by a \(\Pi^0_\xi\) set, Louveau's theorem gives a separator in the same Borel class with a hyperarithmetic Borel code \cite[Ch.~IV, \S6]{Sacks}. Taking a set and its complement as the analytic pair gives the corresponding assertion for a hyperarithmetic set of Borel class \(\Pi^0_\xi\). The theorem keeps the Borel class of the separator, in addition to making the separator effective. For instance a hyperarithmetic \(G_\delta\) set admits a hyperarithmetic sequence of effective Borel codes for open sets whose intersection is that set, with hyperarithmetic parameters allowed.

The forcing proof uses nonempty analytic sets as conditions and tracks the real witnesses in their tree presentations. The sets used as conditions need not be closed. To pass from a decreasing sequence of such conditions to a point in all of them, the proof must arrange finite approximations to compatible witnesses as well as to the point. The assertion that a point belongs to the intersection is an existential projection of this combined limiting relation. Forming the dependent product of chosen witness presentations before taking its image is the slice-theoretic version of retaining the simultaneous data. Neither the existence of that product nor the stability of its image under pullback proves the effective bound on the Borel code. That bound is the additional conclusion of the classical forcing argument.\index{Louveau separation theorem}

\section[Exercises]{Exercises\enspace{\normalfont\normalsize\hyperref[solutions:V]{[Worked solutions]}}}

\begin{exercise}
\label{ex:V.1}
For two conditions \(p,q\) in a poset, prove that \(e(p)\leq e(q)\) exactly when every extension of \(p\) is compatible with \(q\). Use the criterion to describe the quotient that precedes regular-open completion.
\end{exercise}

\begin{exercise}
\label{ex:V.2}
Let \(B\) be complete and atomless. Show that it has no completely prime filter in the full external universe. Explain how a generic filter over a countable ground model can nonetheless preserve every join specified by a family in that model.
\end{exercise}

\begin{exercise}
\label{ex:V.3}
For the real line with its ordinary topology, exhibit a cover which has no disjoint open refinement. Relate this obstruction to the witness family of Example~\ref{ind:countable-failure}.
\end{exercise}

\begin{exercise}
\label{ex:V.4}
Prove the converse of the chain-condition argument in this form. If \(B\) fails \(\kappa\)-cc and \(\kappa\) is regular, construct a chain of subterminal sheaves indexed by \(\kappa\) whose join is terminal and no member is terminal.
\end{exercise}

\begin{exercise}
\label{ex:V.5}
Let \(P\) be obtained by fixing the even coordinates of a binary sequence. Compare the value of the corresponding closed-set assertion in the Cohen, measure, and full perfect forcing algebras. Explain why a positive answer for a perfect condition requires a condition comparison, using the refinement order on perfect conditions.
\end{exercise}

\begin{exercise}
\label{ex:V.6}
Replace the binary output in Proposition~\ref{forc:continuous-fusion} by a continuous map to a Hausdorff space with a countable separating family of opens. Decide which parts of the construction carry over. State what further effective information would be required to implement branch recovery.
\end{exercise}

\begin{exercise}
\label{ex:V.7}
Given a disjoint Boolean partition, independently prescribe a connected groupoid as witness type over every part. Determine the space of sections after restricting to a subcondition which meets several parts. Find two examples with the same support and inequivalent section spaces.
\end{exercise}

End of manuscript · Back to top ↑