What can Topology tell us about Logical Complexity?
Pith reviewed 2026-05-15 02:17 UTC · model grok-4.3
The pith
A computable variant of the gamified Katětov order on filters is isomorphic to the Lawvere-Tierney order, linking combinatorial complexity measures to computability in topos theory.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
a computable variant of the gamified Katětov order is isomorphic to the original ≤_LT-order
Load-bearing premise
That the gamified Katětov order, closed under well-founded iterations of Fubini powers, precisely captures the combinatorial complexity shifts already present in the Lawvere-Tierney order.
read the original abstract
In the 1980s, category theorists introduced the Lawvere-Tierney $(\leq_{\mathrm{LT}})$ order in the Effective Topos, known to effectively embed the Turing degrees. Understanding its structure is a longstanding open problem in the area. In particular, there was an informal sense that the $\leq_{\mathrm{LT}}$-order reflects certain shifts in combinatorial complexity, but a precise characterisation remained elusive for some time. Recent work by the authors has substantially clarified the picture. In arXiv:2602.08138, the authors introduced a game-theoretic (''gamified'') version of the Kat\v{e}tov order on filters over $\omega$ -- essentially, this is the usual Kat\v{e}tov order now closed under well-founded iterations of Fubini powers. The first major theorem of the paper was to show that a computable variant of the gamified Kat\v{e}tov order is isomorphic to the original $\leq_{\mathrm{LT}}$-order. This was a surprising discovery, and opens up many challenging questions regarding the interplay between combinatorial and computable complexity, which informed the rest of the paper's investigations. This note gives an informal survey of some of these interactions explored in arXiv:2602.08138, and announces some forthcoming results. The guiding perspective is that different notions of complexity arising in different areas of logic can be seen to be controlled by the same mechanism -- once placed in the right topological framework.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This informal survey note discusses interactions between combinatorial and computable complexity, centered on the authors' prior result (arXiv:2602.08138) that a computable variant of the gamified Katětov order—filters over ω closed under well-founded iterations of Fubini powers—is isomorphic to the Lawvere-Tierney order ≤_LT in the effective topos (which effectively embeds the Turing degrees). It frames different notions of logical complexity as controlled by the same topological mechanism and announces forthcoming results.
Significance. If the asserted isomorphism holds, the note would supply a concrete combinatorial characterization of the structure of ≤_LT, linking shifts in complexity to game positions and winning strategies in a way that could resolve aspects of the longstanding open problem on the order's structure and bridge computability theory with category-theoretic topology.
major comments (1)
- The central claim—that the computable gamified Katětov order is isomorphic to ≤_LT—is stated in the abstract and introduction but supplies neither an explicit isomorphism (mapping game positions/strategies to subobject classifiers or topology shifts) nor a verification that the computable restriction and well-founded Fubini iteration closure preserve the effective embedding of Turing degrees; this correspondence is load-bearing for the survey's guiding perspective yet remains unstated in the manuscript.
minor comments (2)
- The manuscript employs informal phrasing such as 'surprising discovery' and 'opens up many challenging questions'; these could be replaced with more precise statements for a formal note.
- The title is broad; consider adding a subtitle referencing the effective topos and the gamified Katětov order to better reflect the specific content.
Axiom & Free-Parameter Ledger
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Gamified Katětov order ... closed under well-founded iterations of Fubini powers
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Orderings of ultrafilters , year =
Andreas Blass , date-added =. Orderings of ultrafilters , year =
-
[2]
Partial orders on the types in N , url =
Rudin, Mary Ellen , doi =. Partial orders on the types in N , url =. Transactions of the American Mathematical Society , language =. 1971 , bdsk-url-1 =
work page 1971
-
[3]
Takayuki Kihara and Ming Ng , date-added =. The
-
[4]
Filip. On. 2013 , bdsk-url-1 =. doi:10.1016/j.topol.2013.08.007 , journal =
-
[5]
Filip. A UNIFIED APPROACH TO. 2024 , bdsk-url-1 =. doi:10.1017/jsl.2024.8 , journal =
-
[6]
Ideals and filters on countable sets , year =
David Meza Alc\'. Ideals and filters on countable sets , year =
- [7]
-
[8]
Loops, Inverse Limits and non-determinism , year =
Vasco Brattka , date-added =. Loops, Inverse Limits and non-determinism , year =
-
[9]
Sheaf toposes for realizability , url =
Awodey, Steven and Bauer, Andrej , doi =. Sheaf toposes for realizability , url =. Arch. Math. Logic , mrclass =. 2008 , bdsk-url-1 =
work page 2008
-
[10]
More on geometric morphisms between realizability toposes , volume =
Faber, Eric and van Oosten, Jaap , fjournal =. More on geometric morphisms between realizability toposes , volume =. Theory Appl. Categ. , mrclass =
-
[11]
Geometric morphisms of realizability toposes , volume =
Johnstone, Peter , fjournal =. Geometric morphisms of realizability toposes , volume =. Theory Appl. Categ. , mrclass =
-
[12]
Implicative algebras: a new foundation for realizability and forcing , url =
Miquel, Alexandre , doi =. Implicative algebras: a new foundation for realizability and forcing , url =. Math. Structures Comput. Sci. , mrclass =. 2020 , bdsk-url-1 =
work page 2020
-
[13]
Benno van den Berg and Marcus Bri\". Arrow algebras , volume =. Annals of Pure and Applied Logic , number =. 2026 , bdsk-url-1 =. doi:https://doi.org/10.1016/j.apal.2025.103664 , issn =
-
[14]
Seely, Robert A. G. , doi =. Hyperdoctrines, natural deduction and the. Z. Math. Logik Grundlag. Math. , mrclass =. 1983 , bdsk-url-1 =
work page 1983
-
[15]
Malliaris, M. and Shelah, S. , booktitle =. Open problems on ultrafilters and some connections to the continuum , url =. 2017 , bdsk-url-1 =. doi:10.1090/conm/690 , isbn =
-
[16]
Talayco, Daniel E. , doi =. Applications of cohomology to set theory. Ann. Pure Appl. Logic , mrclass =. 1996 , bdsk-url-1 =
work page 1996
-
[17]
Model theory and applications , volume =
Ehud Hrushovski , chapter =. Model theory and applications , volume =
-
[18]
Talayco, Daniel E. , doi =. Applications of cohomology to set theory. Ann. Pure Appl. Logic , mrclass =. 1995 , bdsk-url-1 =
work page 1995
-
[19]
Cohomology detects failures of the axiom of choice , url =
Blass, Andreas , doi =. Cohomology detects failures of the axiom of choice , url =. Trans. Amer. Math. Soc. , mrclass =. 1983 , bdsk-url-1 =
work page 1983
-
[20]
Moerdijk, Ieke and Palmgren, Erik , doi =. Minimal models of. J. Symbolic Logic , mrclass =. 1997 , bdsk-url-1 =
work page 1997
-
[21]
Arithmetic universes and classifying toposes , volume =
Vickers, Steven , fjournal =. Arithmetic universes and classifying toposes , volume =. Cah. Topol. G\'eom. Diff\'er. Cat\'eg. , mrclass =
-
[22]
Sketches for arithmetic universes , url =
Vickers, Steven , doi =. Sketches for arithmetic universes , url =. J. Log. Anal. , mrclass =. 2019 , bdsk-url-1 =
work page 2019
-
[23]
Hyland, J. M. E. and Johnstone, P. T. and Pitts, A. M. , doi =. Tripos theory , url =. Math. Proc. Cambridge Philos. Soc. , mrclass =. 1980 , bdsk-url-1 =
work page 1980
-
[24]
Pitts, Andrew M. , doi =. Tripos theory in retrospect , url =. Math. Structures Comput. Sci. , mrclass =. 2002 , bdsk-url-1 =
work page 2002
-
[25]
Sheaves in Geometry and Logic: A first introduction to topos theory , year =
Mac Lane, Saunders and Moerdijk, Ieke , isbn =. Sheaves in Geometry and Logic: A first introduction to topos theory , year =
-
[26]
Ming Ng , date-added =. Logical
-
[27]
Moss & Chris Steinsvold (2007 ): T opology and Epistemic Logic
Vickers, Steven , booktitle =. Locales and toposes as spaces , url =. 2007 , bdsk-url-1 =. doi:10.1007/978-1-4020-5587-4\_8 , isbn =
-
[28]
Malliaris, M. and Shelah, S. , doi =. Cofinality spectrum problems: the axiomatic approach , url =. Topology Appl. , mrclass =. 2016 , bdsk-url-1 =
work page 2016
-
[29]
Malliaris, M. and Shelah, S. , doi =. Cofinality spectrum theorems in model theory, set theory, and general topology , url =. J. Amer. Math. Soc. , mrclass =. 2016 , bdsk-url-1 =
work page 2016
-
[30]
Cardinal invariants, non-lowness classes, and
Greenberg, Noam and Kuyper, Rutger and Turetsky, Dan , doi =. Cardinal invariants, non-lowness classes, and. Computability , mrclass =. 2019 , bdsk-url-1 =
work page 2019
-
[31]
Effective Correspondents to Cardinal Characteristics in
Nicholas Andrew Rupprecht , date-added =. Effective Correspondents to Cardinal Characteristics in
-
[32]
Cardinal coefficients associated to certain orders on ideals , url =
Borodulin-Nadzieja, Piotr and Farkas, Barnab\'as , doi =. Cardinal coefficients associated to certain orders on ideals , url =. Arch. Math. Logic , mrclass =. 2012 , bdsk-url-1 =
work page 2012
-
[33]
Cardinal invariants of analytic
Hern\'andez-Hern\'andez, Fernando and Hru. Cardinal invariants of analytic. Canad. J. Math. , mrclass =. 2007 , bdsk-url-1 =. doi:10.4153/CJM-2007-024-8 , fjournal =
-
[34]
Cancino, Jonathan and Guzm\'an, Osvaldo and Hru. Ultrafilters and the. Zb. Rad. (Beogr.) , mrclass =
-
[35]
Filip\'ow, Rafa. Kat etov order between. Arch. Math. Logic , mrclass =. 2024 , bdsk-url-1 =. doi:10.1007/s00153-024-00924-7 , fjournal =
-
[36]
The category dichotomy for ideals , url =
Dow, Alan and Figueroa-Sierra, Ra\'ul and Guzm\'an, Osvaldo and Hru. The category dichotomy for ideals , url =. Ann. Pure Appl. Logic , mrclass =. 2026 , bdsk-url-1 =. doi:10.1016/j.apal.2025.103717 , fjournal =
- [37]
-
[38]
Model theory and machine learning , url =
Chase, Hunter and Freitag, James , doi =. Model theory and machine learning , url =. Bull. Symb. Log. , mrclass =. 2019 , bdsk-url-1 =
work page 2019
-
[39]
Shelah, S. , edition =. Classification Theory: and the number of nonisomorphic models , volume =
-
[40]
Natasha Dobrinen and Stevo Todor. A new class of. Trans. Amer. Math. Soc. , number =
- [41]
-
[42]
An Arithmetical Hierarchy of the Law of Excluded Middle and Related Principles , year =
Akama, Yohji and Berardi, Stefano and Hayashi, Susumu and Kohlenbach, Ulrich , booktitle =. An Arithmetical Hierarchy of the Law of Excluded Middle and Related Principles , year =
-
[43]
Limit computability and ultrafilters , url =
Andrews, Uri and Cai, Mingzhong and Diamondstone, David and Schweber, Noah , date-added =. Limit computability and ultrafilters , url =. Computability , mrclass =. 2023 , bdsk-url-1 =. doi:10.3233/com-170176 , fjournal =
-
[44]
An introduction to inductive definitions , volume =
Aczel, Peter , booktitle =. An introduction to inductive definitions , volume =
-
[45]
Comodule representations of second-order functionals , url =
Ahman, Danel and Bauer, Andrej , date-added =. Comodule representations of second-order functionals , url =. J. Log. Algebr. Methods Program. , mrclass =. 2025 , bdsk-url-1 =. doi:10.1016/j.jlamp.2025.101071 , fjournal =
-
[46]
Fixed points of functors , url =
Ad\'. Fixed points of functors , url =. J. Log. Algebr. Methods Program. , mrclass =. 2018 , bdsk-url-1 =. doi:10.1016/j.jlamp.2017.11.003 , fjournal =
-
[47]
A comparison of various analytic choice principles , url =
Angl\`es d'Auriac, Paul-Elliot and Kihara, Takayuki , date-added =. A comparison of various analytic choice principles , url =. J. Symb. Log. , mrclass =. 2021 , bdsk-url-1 =. doi:10.1017/jsl.2021.37 , fjournal =
-
[48]
Ultrasheaves and double negation , url =
Awodey, Steve and Eliasson, Jonas , date-added =. Ultrasheaves and double negation , url =. Notre Dame J. Formal Logic , mrclass =. 2004 , bdsk-url-1 =. doi:10.1305/ndjfl/1099238447 , fjournal =
-
[49]
The Realizability Approach to Computable Analysis and Topology , year =
Bauer, Andrej , date-added =. The Realizability Approach to Computable Analysis and Topology , year =
-
[50]
Bauer, Andrej , date-added =. Instance reducibility and. Log. Methods Comput. Sci. , mrclass =. 2022 , bdsk-url-1 =. doi:10.46298/lmcs-18(3:20)2022 , fjournal =
-
[51]
Closed choice and a uniform low basis theorem , url =
Brattka, Vasco and de Brecht, Matthew and Pauly, Arno , date-added =. Closed choice and a uniform low basis theorem , url =. Ann. Pure Appl. Logic , mrclass =. 2012 , bdsk-url-1 =. doi:10.1016/j.apal.2011.12.020 , fjournal =
-
[52]
Beeson, Michael J. , date-added =. Foundations of Constructive Mathematics , url =. 1985 , bdsk-url-1 =. doi:10.1007/978-3-642-68952-9 , isbn =
-
[53]
Effective choice and boundedness principles in computable analysis , url =
Brattka, Vasco and Gherardi, Guido , date-added =. Effective choice and boundedness principles in computable analysis , url =. Bull. Symbolic Logic , mrclass =. 2011 , bdsk-url-1 =. doi:10.2178/bsl/1294186663 , fjournal =
-
[54]
Probabilistic computability and choice , url =
Brattka, Vasco and Gherardi, Guido and H\"olzl, Rupert , date-added =. Probabilistic computability and choice , url =. Inform. and Comput. , mrclass =. 2015 , bdsk-url-1 =. doi:10.1016/j.ic.2015.03.005 , fjournal =
-
[55]
Weihrauch complexity in computable analysis , url =
Brattka, Vasco and Gherardi, Guido and Pauly, Arno , booktitle =. Weihrauch complexity in computable analysis , url =. [2021] 2021 , bdsk-url-1 =. doi:10.1007/978-3-030-59234-9\_11 , isbn =
-
[56]
Kleene degrees of ultrafilters , url =
Blass, Andreas , booktitle =. Kleene degrees of ultrafilters , url =. 1985 , bdsk-url-1 =. doi:10.1007/BFb0076213 , isbn =
-
[57]
Two closed categories of filters , url =
Blass, Andreas , date-added =. Two closed categories of filters , url =. Fund. Math. , mrclass =. 1977 , bdsk-url-1 =. doi:10.4064/fm-94-2-129-143 , fjournal =
-
[58]
A model without ultrafilters , volume =
Blass, Andreas , fjournal =. A model without ultrafilters , volume =. Bull. Acad. Polon. Sci. S\'er. Sci. Math. Astronom. Phys. , mrclass =
-
[59]
and Pauly, Arno , date-added =
Brattka, Vasco and Le Roux, St\'ephane and Miller, Joseph S. and Pauly, Arno , date-added =. Connected choice and the. J. Math. Log. , mrclass =. 2019 , bdsk-url-1 =. doi:10.1142/S0219061319500041 , fjournal =
-
[60]
4, 1–36, doi:10.23638/LMCS-14(4:4)2018
Vasco Brattka and Arno Pauly , bibsource =. On the algebraic structure of. 2018 , bdsk-url-1 =. doi:10.23638/LMCS-14(4:4)2018 , journal =
-
[61]
J\". Combinatorial properties of. 2025 , bdsk-url-1 =. doi:10.4153/S0008414X25101879 , journal =
-
[62]
An analogy between cardinal characteristics and highness properties of oracles , year =
Brendle, J\"org and Brooke-Taylor, Andrew and Ng, Keng Meng and Nies, Andr\'e , booktitle =. An analogy between cardinal characteristics and highness properties of oracles , year =
-
[63]
Brendle, J\"org and Yatabe, Shunsuke , doi =. Forcing indestructibility of. Ann. Pure Appl. Logic , mrclass =. 2005 , bdsk-url-1 =
work page 2005
-
[64]
Caramello, Olivia , isbn =. Theories, Sites, Toposes: Relating and studying mathematical theories through topos-theoretic `bridges' , year =
- [65]
-
[66]
Game-theoretic variants of cardinal invariants , url =. 2024 , bdsk-url-1 =. arXiv , author =:2308.12136 , primaryclass =
-
[67]
Recursion Theory: Computational aspects of definability , url =
Chong, Chi Tat and Yu, Liang , date-added =. Recursion Theory: Computational aspects of definability , url =. 2015 , bdsk-url-1 =. doi:10.1515/9783110275643 , isbn =
-
[68]
On uniform relationships between combinatorial problems , url =
Dorais, Fran. On uniform relationships between combinatorial problems , url =. Trans. Amer. Math. Soc. , mrclass =. 2016 , bdsk-url-1 =. doi:10.1090/tran/6465 , fjournal =
-
[69]
Das, Pratulananda and Filip\'ow, Rafa. On the structure of. Ann. Pure Appl. Logic , mrclass =. 2021 , bdsk-url-1 =. doi:10.1016/j.apal.2021.102976 , fjournal =
-
[70]
Dzhafarov, Damir D. and Hirschfeldt, Denis R. and Reitzes, Sarah , date-added =. Reduction games, provability and compactness , url =. J. Math. Log. , mrclass =. 2022 , bdsk-url-1 =. doi:10.1142/S021906132250009X , fjournal =
-
[71]
Continuous and other finitely generated canonical cofinal maps on ultrafilters , url =
Dobrinen, Natasha , date-added =. Continuous and other finitely generated canonical cofinal maps on ultrafilters , url =. Fund. Math. , mrclass =. 2020 , bdsk-url-1 =. doi:10.4064/fm691-6-2019 , fjournal =
-
[72]
Tukey types of ultrafilters , url =
Dobrinen, Natasha and Todorcevic, Stevo , date-added =. Tukey types of ultrafilters , url =. Illinois J. Math. , mrclass =. 2011 , bdsk-url-1 =
work page 2011
-
[73]
Ultrapowers as sheaves on a category of ultrafilters , url =
Eliasson, Jonas , date-added =. Ultrapowers as sheaves on a category of ultrafilters , url =. Arch. Math. Logic , mrclass =. 2004 , bdsk-url-1 =. doi:10.1007/s00153-004-0228-0 , fjournal =
- [74]
-
[75]
He, Jialiang and Hru. Tukey order among. J. Symb. Log. , mrclass =. 2021 , bdsk-url-1 =. doi:10.1017/jsl.2021.30 , fjournal =
-
[76]
Fremlin, D. H. , date-added =. Measure Theory
-
[77]
Prenex normal form theorems in semi-classical arithmetic , url =
Fujiwara, Makoto and Kurahashi, Taishi , date-added =. Prenex normal form theorems in semi-classical arithmetic , url =. J. Symb. Log. , mrclass =. 2021 , bdsk-url-1 =. doi:10.1017/jsl.2021.47 , fjournal =
-
[78]
Refining the arithmetical hierarchy of classical principles , url =
Fujiwara, Makoto and Kurahashi, Taishi , date-added =. Refining the arithmetical hierarchy of classical principles , url =. MLQ Math. Log. Q. , mrclass =. 2022 , bdsk-url-1 =. doi:10.1002/malq.202000077 , fjournal =
-
[79]
Ultrafilters, finite coproducts and locally connected classifying toposes , url =
Garner, Richard , date-added =. Ultrafilters, finite coproducts and locally connected classifying toposes , url =. Ann. Pure Appl. Logic , mrclass =. 2020 , bdsk-url-1 =. doi:10.1016/j.apal.2020.102831 , fjournal =
-
[80]
Some structural aspects of the
Guzm\'an-Gonz\'alez, Osvaldo and Meza-Alc\'antara, David , date-added =. Some structural aspects of the. Order , mrclass =. 2016 , bdsk-url-1 =. doi:10.1007/s11083-015-9358-8 , fjournal =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.