A note on computable étale spaces
Matthew de Brecht · 2026
Read A note on computable étale spaces by Matthew de Brecht (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27466.txt.
Introduction
In this note, de Brecht defines computable étale spaces over a topological space within the TTE framework. He shows they are equivalent to computable functions from the space to ODS, the effective category of overt-discrete spaces. For a computable category or groupoid, he establishes an equivalence between functors to ODS and étale spaces equipped with an action by that category. The note links étale spaces, which arise in topos theory through the sheaf-space equivalence, to computable functions and functors.
Catalog record
| CREATOR | Matthew de Brecht |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48385 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27466
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on computable étale spaces Matthew de Brecht Abstract An étale space over a topological space Y Y is defined as a local homeomorphism from a topological space X X into Y Y . They often come up in topos theory because of the equivalence between sheaves and étale spaces over a space. In this note, we define computable étale spaces over a computable topological space Y Y within the TTE framework of computable topology, and show they are naturally equivalent to computable functions from Y Y to 𝖮𝖣𝖲 {\mathsf{ODS}} , the effective quasi-Polish category of overt-discrete quasi-Polish spaces. More generally, if 𝒞 {\mathcal{C}} is a computable category (or groupoid), then there is an equivalence between computable functors from 𝒞 {\mathcal{C}} to 𝖮𝖣𝖲 {\mathsf{ODS}} , and computable étale spaces equipped with a computable action by 𝒞 {\mathcal{C}} . 1 Introduction We recommend [ 26 ] for an intuitive explanation of the connections between Grothendiek toposes and geometric logic. Briefly, frames (complete lattices satisfying a certain infinitary distributive law) correspond to the Lindenbaum-algebras of propositional geometric theories, and Grothendiek toposes in a sense correspond to the “Lindenbaum algebras” of predicate geometric theories. A famous result by Joyal and Tierney [ 15 ] shows that every Grothendiek topos is equivalent to the category of continuous actions of a localic groupoid. An analogous connection between \omega_{1} -pretoposes and \omega_{1} -coherent theories was established by R. Chen in [ 1 , 2 ] . An \omega_{1} -pretopos is a generalization of a Grothendiek topos where only countable coproducts are required to exist, rather than all small coproducts. Similarly, \omega_{1} -coherent logic is the restriction of geometric logic that requires infinitary disjunctions to be countable. R. Chen showed that the syntactic \omega_{1} -pretopos (the “Lindenbaum algebra”) of a countable \omega_{1} -coherent theory is equivalent to the category {\mathrm{\mathbb{Act}}}({\mathcal{C}}) of (countably based) continuous actions of a quasi-Polish groupoid {\mathcal{C}} . This can be viewed as a generalization (from propositional logic to predicate logic) of R. Heckmann’s spatiality result [ 12 ] , which implies the Lindenbaum algebra of a countable \omega_{1} -coherent propositional theory is isomorphic to the frame of opens of a quasi-Polish space. This note is a contribution towards effectivizing R. Chen’s result and other aspects of Grothendiek topos theory. We define computable étale spaces over a computable topological space Y within the TTE framework of computable topology [ 27 ] , and show they are equivalent to computable functions from Y to {\mathsf{ODS}} , the effective quasi-Polish category of overt discrete quasi-Polish spaces. More generally, we show that for any computable category {\mathcal{C}} there is a computability preserving equivalence between the category {\mathrm{\mathbb{Act}}}({\mathcal{C}}) of (countably based) étale spaces with continuous actions by {\mathcal{C}} , and the functor category {\mathsf{ODS}}^{\mathcal{C}} of (topologically) continuous functors from {\mathcal{C}} to {\mathsf{ODS}} . It follows that the syntactic \omega_{1} -pretopos of a countable \omega_{1} -coherent theory is equivalent to a functor category {\mathsf{ODS}}^{\mathcal{C}} for some quasi-Polish category {\mathcal{C}} . These syntactic \omega_{1} -pretoposes are analogous to classifying (Grothendiek) toposes of geometric theories, and the categorically equivalent functor categories {\mathsf{ODS}}^{\mathcal{C}} are suitable for computability theory because they are internal categories of {{\bf QCB}_{0}} . See [ 11 , 19 , 8 , 10 ] for related work applying computability theory to category theoretical structures. See also [ 16 ] for connections between Lawvere-Tierney topologies and computability theory. We mainly work with computable topological spaces 1 1 1 Readers uninterested in computability can interpret “computable topological space” as “countably based space”, and “computable function” as “continuous function”. , but will need {{\bf QCB}_{0}} -spaces [ 24 ] for functor categories. One could also generalize further to represented spaces [ 22 ] , which appears necessary to internalize some categories of interest [ 8 ] . We will also emphasize the constructions for quasi-Polish spaces, because they are exactly what is needed to establish the connections with \omega_{1} -coherent logic. By encoding quasi-Polish spaces as spaces of ideals and using the techniques of [ 20 ] , most of our results can be formalized within the subsytem \mathsf{ACA_{0}} of second order arithmetic (or even weaker systems). 2 Preliminaries 2.1 Computable topological spaces Let \prec be a transitive relation on {\mathbb{N}} . A subset I\subseteq{\mathbb{N}} is an ideal if and only if: 1. I\not=\emptyset , ( I is non-empty ) 2. (\forall a\in I)(\forall b\in{\mathbb{N}})\,(b\prec a\Rightarrow b\in I) , ( I is a lower set ) 3. (\forall a,b\in I)(\exists c\in I)\,(a\prec c\,\&\,b\prec c) . ( I is directed ) The collection {{\mathrm{\mathbf{I}}}(\prec)} of all ideals has the topology generated by basic open sets of the form [a]_{\prec}=\{I\in{{\mathrm{\mathbf{I}}}(\prec)}\mid a\in I\} . A topological space is quasi-Polish if it is homeomorphic to a space of the form {{\mathrm{\mathbf{I}}}(\prec)} for some transitive relation \prec on {\mathbb{N}} . A represented space is effectively quasi-Polish if it is computably isomorphic to a space of the form {{\mathrm{\mathbf{I}}}(\prec)} for some computably enumerable (c.e.) transitive relation \prec on {\mathbb{N}} . An effectively quasi-Polish space is computably overt if furthermore the corresponding relation \prec is such that E_{\prec}=\{a\in{\mathbb{N}}\mid[a]_{\prec}\not=\emptyset\} is c.e. A computably overt effective quasi-Polish space is called a computable quasi-Polish space . Quasi-Polish spaces were introduced in [ 6 ] , and the equivalent characterization in terms of spaces of ideals that we use here was first shown in [ 5 ] . Effective quasi-Polish spaces have been studied in [ 25 , 17 , 5 , 13 , 4 ] . An admissible representation [ 23 ] of {{\mathrm{\mathbf{I}}}(\prec)} represents each ideal by an enumeration of its elements. A function f\colon{{\mathrm{\mathbf{I}}}(\prec_{1})}\to{{\mathrm{\mathbf{I}}}(\prec_{2})} is computable iff there is a Type Two Turing Machine [ 27 ] which when given any enumeration of the elements of any I\in{{\mathrm{\mathbf{I}}}(\prec_{1})} outputs an enumeration of f(I)\in{{\mathrm{\mathbf{I}}}(\prec_{2})} . A c.e. open subset (or {\Sigma}^{0}_{1} -subset ) of {{\mathrm{\mathbf{I}}}(\prec)} is an open subset of the form \bigcup_{a\in S}[a]_{\prec} for some c.e. subset S\subseteq{\mathbb{N}} . A {\Pi}^{0}_{2} -subset is a subset of the form \{I\in{{\mathrm{\mathbf{I}}}(\prec)}\mid(\forall i\in{\mathbb{N}})[I\in U_{i}\Rightarrow I\in V_{i}]\} for some c.e. sequence (U_{i},V_{i})_{i\in{\mathbb{N}}} of c.e. open subsets of {{\mathrm{\mathbf{I}}}(\prec)} . Effective quasi-Polish spaces are closed under {\Pi}^{0}_{2} -subspaces (this is a well-known result, but see the proof of Theorem 3 in [ 7 ] for how to prove this in \mathsf{ACA_{0}} ). A pair (\prec,X) , where \prec is a c.e. transitive relation and X\subseteq{{\mathrm{\mathbf{I}}}(\prec)} , is called a computable topological space 2 2 2 See Section 4.2 of [ 7 ] for a proof that this definition is computably equivalent to the more common definition of a computable (or effective) topological space . . Computable functions, c.e. open subsets, and {\Pi}^{0}_{2} -subsets of computable topological spaces are defined by restricting the definition for effective quasi-Polish spaces to their subspaces. Computable topological spaces are countably based, and conversely every countably based space is homeomorphic to a computable topological space for some suitable \prec . 2.2 Computable categories A computable category is an internal category [ 14 ] in the category of computable topological spaces and computable functions. More concretely, a computable category is a tuple {\mathcal{C}}=({\mathcal{C}}_{\mathsf{Obj}},{\mathcal{C}}_{\mathsf{Mor}},{\sigma},{\tau},{\iota},\circ) consisting of the following data: • {\mathcal{C}}_{\mathsf{Obj}} (objects) and {\mathcal{C}}_{\mathsf{Mor}} (morphisms) are computable topological spaces. • {\sigma}\colon{\mathcal{C}}_{\mathsf{Mor}}\to{\mathcal{C}}_{\mathsf{Obj}} (source), {\tau}\colon{\mathcal{C}}_{\mathsf{Mor}}\to{\mathcal{C}}_{\mathsf{Obj}} (target), and {\iota}\colon{\mathcal{C}}_{\mathsf{Obj}}\to{\mathcal{C}}_{\mathsf{Mor}} (identity) are computable functions. • \circ:\subseteq{\mathcal{C}}_{\mathsf{Mor}}\times{\mathcal{C}}_{\mathsf{Mor}}\to{\mathcal{C}}_{\mathsf{Mor}}