Search

We show that the category of countable Borel equivalence relations (CBERs) is dually equivalent to the category of countable $\mathcal{L}_{\omega_1\omega}$ theories which admit a one-sorted interpretation of a particular theory we call $\mathcal{T}_\mathsf{LN} \sqcup \mathcal{T}_\mathsf{sep}$ that witnesses embeddability into $2^\mathbb{N}$ and the Lusin--Novikov uniformization theorem. This allows problems about Borel combinatorial structures on CBERs to be translated into syntactic definability problems in $\mathcal{L}_{\omega_1\omega}$, modulo the extra structure provided by $\mathcal{T}_\mathsf{LN} \sqcup \mathcal{T}_\mathsf{sep}$, thereby formalizing a folklore intuition in locally countable Borel combinatorics. We illustrate this with a catalogue of the precise interpretability relations between several standard classes of structures commonly used in Borel combinatorics, such as Feldman--Moore $\omega$-colorings and the Slaman--Steel marker lemma. We also generalize this correspondence to locally countable Borel groupoids and theories interpreting $\mathcal{T}_\mathsf{LN}$, which admit a characterization analogous to that of Hjorth--Kechris for essentially countable isomorphism relations., Comment: 55 pages

We study the lattice of all Borel clones on $2 = \{0,1\}$: classes of Borel functions $f : 2^n \to 2$, $n \le \omega$, which are closed under composition and include all projections. This is a natural extension to countable arities of Post's 1941 classification of all clones of finitary Boolean functions. Every Borel clone restricts to a finitary clone, yielding a "projection" from the lattice of all Borel clones to Post's lattice. It is well-known that each finitary clone of affine mod 2 functions admits a unique extension to a Borel clone. We show that over each finitary clone containing either both $\wedge, \vee$, or the 2-out-of-3 median operation, there lie at least 2 but only finitely many Borel clones. Over the remaining clones in Post's lattice, we give only a partial classification of the Borel extensions, and present some evidence that the full structure may be quite complicated., Comment: 58 pages, 14 figures

Crater detection can provide valuable information for humans to explore the topography and understand the history of extraterrestrial planets. Due to the significantly varying scenario distributions, existing detection models trained on known labelled crater datasets are hardly effective when applied to new unlabelled planets. To address this issue, we propose a two-stage adaptive network (TAN) for semi-supervised cross-domain crater detection. Our network is built on the YOLOv5 detector, where a series of strategies are employed to enhance its cross-domain generalisation ability. In the first stage, we propose an attention-based scale-adaptive fusion (ASAF) strategy to handle objects with significant scale variances. Furthermore, we propose a smoothing hard example mining (SHEM) loss function to address the issue of overfitting on hard examples. In the second stage, we propose a sort-based pseudo-labelling fine-tuning (SPF) strategy for semi-supervised learning to mitigate the distributional differences between source and target domains. For both stages, we employ weak or strong image augmentation to suit different cross-domain tasks. Experimental results on benchmark datasets demonstrate that the proposed network can enhance domain adaptation ability for crater detection under varying scenario distributions.

An \'etale structure over a topological space $X$ is a continuous family of structures (in some first-order language) indexed over $X$. We give an exposition of this fundamental concept from sheaf theory and its relevance to countable model theory and invariant descriptive set theory. We show that many classical aspects of spaces of countable models can be naturally framed and generalized in the context of \'etale structures, including the Lopez-Escobar theorem on invariant Borel sets, an omitting types theorem, and various characterizations of Scott rank. We also present and prove the countable version of the Joyal-Tierney representation theorem, which states that the isomorphism groupoid of an \'etale structure determines its theory up to bi-interpretability; and we explain how special cases of this theorem recover several recent results in the literature on groupoids of models and functors between them., Comment: 41 pages

We prove several results showing that every locally finite Borel graph whose large-scale geometry is "tree-like" induces a treeable equivalence relation. In particular, our hypotheses hold if each component of the original graph either has bounded tree-width or is quasi-isometric to a tree, answering a question of Tucker-Drob. In the latter case, we moreover show that there exists a Borel quasi-isometry to a Borel forest, under the additional assumption of (componentwise) bounded degree. We also extend these results on quasi-treeings to Borel proper metric spaces. In fact, our most general result shows treeability of countable Borel equivalence relations equipped with an abstract wallspace structure on each class obeying some local finiteness conditions, which we call a proper walling. The proof is based on the Stone duality between proper wallings and median graphs, i.e., CAT(0) cube complexes. Finally, we strengthen the conclusion of treeability in these results to hyperfiniteness in the case where the original graph has one (selected) end per component, generalizing the same result for trees due to Dougherty--Jackson--Kechris., Comment: 42 pages; added section 6.B on one selected end

We prove that the category of continuous lattices and meet- and directed join-preserving maps is dually equivalent, via the hom functor to $[0,1]$, to the category of complete Archimedean meet-semilattices equipped with a finite meet-preserving action of the monoid of continuous monotone maps of $[0,1]$ fixing $1$. We also prove an analogous duality for completely distributive lattices. Moreover, we prove that these are essentially the only well-behaved "sound classes of joins $\Phi$, dual to a class of meets" for which "$\Phi$-continuous lattice" and "$\Phi$-algebraic lattice" are different notions, thus for which a $2$-valued duality does not suffice., Comment: 16 pages; revisions from refereeing

We prove the a.e. nonamenability of locally finite quasi-pmp Borel graphs whose every component admits at least three nonvanishing ends with respect to the underlying Radon--Nikodym cocycle. We witness their nonamenability by constructing Borel subforests with at least three nonvanishing ends per component, and then applying Tserunyan and Tucker-Drob's recent characterization of amenability for acyclic quasi-pmp Borel graphs. Our main technique is a weighted cycle-cutting algorithm, which yields a weight-maximal spanning forest. We also introduce a random version of this forest, which generalizes the Free Minimal Spanning Forest, to capture nonunimodularity in the context of percolation theory., Comment: 33 pages, 3 figures. More statements, context, and open questions have been added. Minor mistakes have been corrected and the overall presentation has been improved

We extend the Becker--Kechris topological realization and change-of-topology theorems for Polish group actions in several directions. For Polish group actions, we prove a single result that implies the original Becker--Kechris theorems, as well as Sami's and Hjorth's sharpenings adapted levelwise to the Borel hierarchy; automatic continuity of Borel actions via homeomorphisms; and the equivalence of "potentially open" versus "orbitwise open" Borel sets. We also characterize "potentially open" $n$-ary relations, thus yielding a topological realization theorem for invariant Borel first-order structures. We then generalize to groupoid actions, and prove a result subsuming Lupini's Becker--Kechris-type theorems for open Polish groupoids, newly adapted to the Borel hierarchy, as well as topological realizations of actions on fiberwise topological bundles and bundles of first-order structures. Our proof method is new even in the classical case of Polish groups, and is based entirely on formal algebraic properties of category quantifiers; in particular, we make no use of either metrizability or the strong Choquet game. Consequently, our proofs work equally well in the non-Hausdorff context, for open quasi-Polish groupoids, and more generally in the point-free context, for open localic groupoids., Comment: 59 pages; revisions from refereeing

We explain how Johnstone's 1989 proof of the closed subgroup theorem for localic groups can be viewed as a point-free version of Pettis's theorem for Baire topological groups. We then use it to derive localic versions of the open mapping theorem and automatic continuity of Borel homomorphisms, as well as the non-existence of binary coproducts of complete Boolean algebras., Comment: 12 pages

We show that in a category with pullbacks, arbitrary sifted colimits may be constructed as filtered colimits of reflexive coequalizers. This implies that "lex sifted colimits", in the sense of Garner--Lack, decompose as Barr-exactness plus filtered colimits commuting with finite limits. We also prove generalizations of these results for $\kappa$-small sifted and filtered colimits, and their interaction with $\lambda$-small limits in place of finite ones, generalizing Garner's characterization of algebraic exactness in the sense of Ad\'amek--Lawvere--Rosick\'y. Along the way, we prove a general result on classes of colimits, showing that the $\kappa$-small restriction of a saturated class of colimits is still "closed under iteration"., Comment: 15 pages; expanded Section 6 to discuss algebraic exactness; reorganized Section 4

We use first-principles simulation and virtual crystal approximation to reveal the unique double band inversion and topological phase transition in Ge1-xSnx alloys. Wavefunction parity, spatial charge distribution and surface state spectrum analyses suggest that the band inversion in Ge1-xSnx is relayed by its first valence band. As the system evolves from Ge to {\alpha}-Sn, its conduction band moves down, and inverts with the first and the second valence bands consecutively. The first band inversion makes the system nontrivial, while the second one does not change the topological invariant of the system. Both the band inversions yield surface modes spanning the individual inverted gaps, but only the surface mode in the upper gap associates with the nontrivial nature of tensile-strained {\alpha}-Sn., Comment: 5 pages, 6 figures

We systematically develop analogs of basic concepts from classical descriptive set theory in the context of pointless topology. Our starting point is to take the elements of the free complete Boolean algebra generated by the frame $\mathcal{O}(X)$ of opens to be the "$\infty$-Borel sets" in a locale $X$. We show that several known results in locale theory may be interpreted in this framework as direct analogs of classical descriptive set-theoretic facts, including e.g., the Lusin separation, Lusin-Suslin, and Baire category theorems for locales; we also prove several extensions of these results. We give a detailed analysis of various notions of image, and prove that a continuous map need not have an $\infty$-Borel image. We introduce the category of "analytic $\infty$-Borel locales" as the regular completion under images of the unary site of locales and $\infty$-Borel maps, and prove analogs of several classical results about analytic sets, such as a boundedness theorem for well-founded analytic relations. We also consider the "positive $\infty$-Borel sets" of a locale, formed from opens without using $\neg$. We in fact work throughout with $\kappa$-copresented $\kappa$-locales and $\kappa$-Borel sets for arbitrary regular $\omega_1 \le \kappa \le \infty$, thereby incorporating the classical context as the special case $\kappa = \omega_1$. The basis for the aforementioned localic results is a detailed study of various known and new methods for presenting $\kappa$-frames, $\kappa$-Boolean algebras, etc. In particular, we introduce a new type of "two-sided posite" for presenting $(\kappa, \kappa)$-frames $A$ (i.e., both $A$ and $A^{op}$ are $\kappa$-frames), and use this to prove a general $\kappa$-ary interpolation theorem for $(\kappa, \kappa)$-frames, which dualizes to the aforementioned separation theorems., Comment: 121 pages

We prove that the category $\mathsf{SBor}$ of standard Borel spaces is the (bi-)initial object in the 2-category of countably complete Boolean (countably) extensive categories. This means that $\mathsf{SBor}$ is the universal category admitting some familiar algebraic operations of countable arity (e.g., countable products, unions) obeying some simple compatibility conditions (e.g., products distribute over disjoint unions). More generally, for any infinite regular cardinal $\kappa$, the dual of the category $\kappa\mathsf{Bool}_\kappa$ of $\kappa$-presented $\kappa$-complete Boolean algebras is (bi-)initial in the 2-category of $\kappa$-complete Boolean ($\kappa$-)extensive categories., Comment: 28 pages; revisions from refereeing

We prove that every open $\sigma$-locally Polish groupoid $G$ is Borel equivalent to the groupoid of models on the Urysohn sphere $\mathbb{U}$ of an $\mathcal{L}_{\omega_1\omega}$-sentence in continuous logic. In particular, the orbit equivalence relations of such groupoids are up to Borel bireducibility precisely those of Polish group actions, answering a question of Lupini. Analogously, every non-Archimedean (i.e., every unit morphism has a neighborhood basis of open subgroupoids) open quasi-Polish groupoid is Borel equivalent to the groupoid of models on $\mathbb{N}$ of an $\mathcal{L}_{\omega_1\omega}$-sentence in discrete logic. The proof in fact gives a topological representation of $G$ as the groupoid of isomorphisms between a "continuously varying" family of structures over the space of objects of $G$, constructed via a topological Yoneda-like lemma of Moerdijk for localic groupoids and its metric analog. Other ingredients in our proof include the Lopez-Escobar theorem for continuous logic, a uniformization result for full Borel functors between open quasi-Polish groupoids, a uniform Borel version of Kat\v{e}tov's construction of $\mathbb{U}$, groupoid versions of the Pettis and Birkhoff--Kakutani theorems, and a development of the theory of non-Hausdorff topometric spaces and their quotients., Comment: 70 pages

An analog of Nadel's effective bound for the continuous Scott rank of metric structures, developed by Ben Yaacov, Doucha, Nies, and Tsankov, will be established: Let $\mathscr{L}$ be a language of continuous logic with code $\hat{\mathscr{L}}$. Let $\Omega$ be a weak modulus of uniform continuity with code $\hat{\Omega}$. Let $\mathcal{D}$ be a countable $\mathscr{L}$-pre-structure. Let $\bar{\mathcal{D}}$ denote the completion structure of $\mathcal{D}$. Then $\mathrm{SR}_\Omega(\bar{D}) \leq \omega_1^{\hat{\mathscr{L}}\oplus\hat{\Omega}\oplus\mathcal{D}}$, the Church-Kleene ordinal relative to $\hat{\mathscr{L}}\oplus\hat{\Omega}\oplus\mathcal{D}$.

Quasi-Polish spaces were introduced by de Brecht as a possibly non-Hausdorff generalization of Polish spaces sharing many of their descriptive set-theoretic properties. We give a self-contained exposition of the basic theory of quasi-Polish spaces, based on their "logical" characterization as $\mathbf{\Pi}^0_2$ subspaces of countable powers of Sierpinski space, with several new proofs emphasizing this point of view as well as making more extensive use of Baire category techniques., Comment: 20 pages; simplified proof of game characterization; various minor fixes

We show that the uniform measure-theoretic ergodic decomposition of a countable Borel equivalence relation $(X, E)$ may be realized as the topological ergodic decomposition of a continuous action of a countable group $\Gamma \curvearrowright X$ generating $E$. We then apply this to the study of the cardinal algebra $\mathcal K(E)$ of equidecomposition types of Borel sets with respect to a compressible countable Borel equivalence relation $(X, E)$. We also make some general observations regarding quotient topologies on topological ergodic decompositions, with an application to weak equivalence of measure-preserving actions., Comment: 31 pages; revisions from refereeing

We prove a strong conceptual completeness theorem (in the sense of Makkai) for the infinitary logic $\mathcal L_{\omega_1\omega}$: every countable $\mathcal L_{\omega_1\omega}$-theory can be canonically recovered from its standard Borel groupoid of countable models, up to a suitable syntactical notion of equivalence. This implies that given two theories $(\mathcal L, \mathcal T)$ and $(\mathcal L', \mathcal T')$ (in possibly different languages $\mathcal L, \mathcal L'$), every Borel functor $\mathsf{Mod}(\mathcal L', \mathcal T') \to \mathsf{Mod}(\mathcal L, \mathcal T)$ between the respective groupoids of countable models is Borel naturally isomorphic to the functor induced by some $\mathcal L'_{\omega_1\omega}$-interpretation of $\mathcal T$ in $\mathcal T'$. This generalizes a recent result of Harrison-Trainor, Miller, and Montalb\'an in the case where $\mathcal T, \mathcal T'$ each have a single countable model up to isomorphism., Comment: 49 pages; minor revisions

We show that every countable Borel equivalence relation structurable by $n$-dimensional contractible simplicial complexes embeds into one which is structurable by such complexes with the further property that each vertex belongs to at most $M_n := 2^{n-1}(n^2+3n+2)-2$ edges; this generalizes a result of Jackson-Kechris-Louveau in the case $n = 1$. The proof is based on that of a classical result of Whitehead on countable CW-complexes., Comment: 12 pages; minor revisions

A category has the amalgamation property (AP) if every pushout diagram has a cocone, and the joint embedding property (JEP) if every finite coproduct diagram has a cocone. We show that for a finitely generated category $\mathbf I$, the following are equivalent: (i) every $\mathbf I$-shaped diagram in a category with the AP and the JEP has a cocone; (ii) every $\mathbf I$-shaped diagram in the category of sets and injections has a cocone; (iii) a certain canonically defined category $\mathcal{L}(\mathbf{I})$ of "paths" in $\mathbf I$ has only idempotent endomorphisms. When $\mathbf I$ is a finite poset, these are further equivalent to: (iv) every upward-closed subset of $\mathbf I$ is simply-connected; (v) $\mathbf I$ can be built inductively via some simple rules. Our proof also shows that these conditions are decidable for finite $\mathbf I$., Comment: 14 pages

For a class $\mathcal K$ of countable relational structures, a countable Borel equivalence relation $E$ is said to be $\mathcal K$-structurable if there is a Borel way to put a structure in $\mathcal K$ on each $E$-equivalence class. We study in this paper the global structure of the classes of $\mathcal K$-structurable equivalence relations for various $\mathcal K$. We show that $\mathcal K$-structurability interacts well with several kinds of Borel homomorphisms and reductions commonly used in the classification of countable Borel equivalence relations. We consider the poset of classes of $\mathcal K$-structurable equivalence relations for various $\mathcal K$, under inclusion, and show that it is a distributive lattice; this implies that the Borel reducibility preordering among countable Borel equivalence relations contains a large sublattice. Finally, we consider the effect on $\mathcal K$-structurability of various model-theoretic properties of $\mathcal K$. In particular, we characterize the $\mathcal K$ such that every $\mathcal K$-structurable equivalence relation is smooth, answering a question of Marks., Comment: 77 pages; answered Remark 5.28 (Problem 9.2)