pith. sign in

arxiv: 2605.14086 · v1 · pith:43G77UWRnew · submitted 2026-05-13 · 🧮 math.LO · math.CT

What can Topology tell us about Logical Complexity?

Pith reviewed 2026-05-15 02:17 UTC · model grok-4.3

classification 🧮 math.LO math.CT
keywords ordercomplexitymathrmsomearxivauthorscombinatorialcomputable
0
0 comments X

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.

The Effective Topos is a mathematical setting where objects behave like computable sets and functions. Inside it, the Lawvere-Tierney order compares these objects by a kind of logical complexity. The authors previously showed that this order matches a version of the Katětov order made into a game that allows repeated Fubini-style iterations. Placing both notions inside the same topological framework makes different kinds of complexity from logic and combinatorics appear to follow the same rules. The note explores these links informally and flags some new results that will appear later.

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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

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)
  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)
  1. 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.
  2. 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

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are introduced or quantified in the abstract; the note relies on background notions from effective topos theory and filter orders already present in the cited literature.

pith-pipeline@v0.9.0 · 5558 in / 999 out tokens · 45514 ms · 2026-05-15T02:17:25.368934+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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

145 extracted references · 145 canonical work pages

  1. [1]

    Orderings of ultrafilters , year =

    Andreas Blass , date-added =. Orderings of ultrafilters , year =

  2. [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 =

  3. [3]

    Takayuki Kihara and Ming Ng , date-added =. The

  4. [4]

    Filip. On. 2013 , bdsk-url-1 =. doi:10.1016/j.topol.2013.08.007 , journal =

  5. [5]

    A UNIFIED APPROACH TO

    Filip. A UNIFIED APPROACH TO. 2024 , bdsk-url-1 =. doi:10.1017/jsl.2024.8 , journal =

  6. [6]

    Ideals and filters on countable sets , year =

    David Meza Alc\'. Ideals and filters on countable sets , year =

  7. [7]

    The Game-Theoretic

    Takayuki Kihara and Ming Ng , note =. The Game-Theoretic

  8. [8]

    Loops, Inverse Limits and non-determinism , year =

    Vasco Brattka , date-added =. Loops, Inverse Limits and non-determinism , year =

  9. [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 =

  10. [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. [11]

    Geometric morphisms of realizability toposes , volume =

    Johnstone, Peter , fjournal =. Geometric morphisms of realizability toposes , volume =. Theory Appl. Categ. , mrclass =

  12. [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 =

  13. [13]

    Arrow algebras , volume =

    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. [14]

    Seely, Robert A. G. , doi =. Hyperdoctrines, natural deduction and the. Z. Math. Logik Grundlag. Math. , mrclass =. 1983 , bdsk-url-1 =

  15. [15]

    and Shelah, S

    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. [16]

    Talayco, Daniel E. , doi =. Applications of cohomology to set theory. Ann. Pure Appl. Logic , mrclass =. 1996 , bdsk-url-1 =

  17. [17]

    Model theory and applications , volume =

    Ehud Hrushovski , chapter =. Model theory and applications , volume =

  18. [18]

    Talayco, Daniel E. , doi =. Applications of cohomology to set theory. Ann. Pure Appl. Logic , mrclass =. 1995 , bdsk-url-1 =

  19. [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 =

  20. [20]

    Minimal models of

    Moerdijk, Ieke and Palmgren, Erik , doi =. Minimal models of. J. Symbolic Logic , mrclass =. 1997 , bdsk-url-1 =

  21. [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. [22]

    Sketches for arithmetic universes , url =

    Vickers, Steven , doi =. Sketches for arithmetic universes , url =. J. Log. Anal. , mrclass =. 2019 , bdsk-url-1 =

  23. [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 =

  24. [24]

    Pitts, Andrew M. , doi =. Tripos theory in retrospect , url =. Math. Structures Comput. Sci. , mrclass =. 2002 , bdsk-url-1 =

  25. [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. [26]

    Ming Ng , date-added =. Logical

  27. [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. [28]

    and Shelah, S

    Malliaris, M. and Shelah, S. , doi =. Cofinality spectrum problems: the axiomatic approach , url =. Topology Appl. , mrclass =. 2016 , bdsk-url-1 =

  29. [29]

    and Shelah, S

    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 =

  30. [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 =

  31. [31]

    Effective Correspondents to Cardinal Characteristics in

    Nicholas Andrew Rupprecht , date-added =. Effective Correspondents to Cardinal Characteristics in

  32. [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 =

  33. [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. [34]

    Ultrafilters and the

    Cancino, Jonathan and Guzm\'an, Osvaldo and Hru. Ultrafilters and the. Zb. Rad. (Beogr.) , mrclass =

  35. [35]

    Kat etov order between

    Filip\'ow, Rafa. Kat etov order between. Arch. Math. Logic , mrclass =. 2024 , bdsk-url-1 =. doi:10.1007/s00153-024-00924-7 , fjournal =

  36. [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. [37]

    Kat etov order,

    Hru. Kat etov order,. Rend. Istit. Mat. Univ. Trieste , mrclass =

  38. [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 =

  39. [39]

    , edition =

    Shelah, S. , edition =. Classification Theory: and the number of nonisomorphic models , volume =

  40. [40]

    A new class of

    Natasha Dobrinen and Stevo Todor. A new class of. Trans. Amer. Math. Soc. , number =

  41. [41]

    Ultrafilters and small sets , year =

    Jana Fla. Ultrafilters and small sets , year =

  42. [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. [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. [44]

    An introduction to inductive definitions , volume =

    Aczel, Peter , booktitle =. An introduction to inductive definitions , volume =

  45. [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. [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. [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. [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. [49]

    The Realizability Approach to Computable Analysis and Topology , year =

    Bauer, Andrej , date-added =. The Realizability Approach to Computable Analysis and Topology , year =

  50. [50]

    Instance reducibility and

    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. [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. [52]

    , date-added =

    Beeson, Michael J. , date-added =. Foundations of Constructive Mathematics , url =. 1985 , bdsk-url-1 =. doi:10.1007/978-3-642-68952-9 , isbn =

  53. [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. [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. [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. [56]

    Kleene degrees of ultrafilters , url =

    Blass, Andreas , booktitle =. Kleene degrees of ultrafilters , url =. 1985 , bdsk-url-1 =. doi:10.1007/BFb0076213 , isbn =

  57. [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. [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. [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. [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. [61]

    Combinatorial properties of

    J\". Combinatorial properties of. 2025 , bdsk-url-1 =. doi:10.4153/S0008414X25101879 , journal =

  62. [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. [63]

    Forcing indestructibility of

    Brendle, J\"org and Yatabe, Shunsuke , doi =. Forcing indestructibility of. Ann. Pure Appl. Logic , mrclass =. 2005 , bdsk-url-1 =

  64. [64]

    Theories, Sites, Toposes: Relating and studying mathematical theories through topos-theoretic `bridges' , year =

    Caramello, Olivia , isbn =. Theories, Sites, Toposes: Relating and studying mathematical theories through topos-theoretic `bridges' , year =

  65. [65]

    On the Isbell problem , year =

    Jonathan Cancino-Manr\'. On the Isbell problem , year =

  66. [66]

    2024 , bdsk-url-1 =

    Game-theoretic variants of cardinal invariants , url =. 2024 , bdsk-url-1 =. arXiv , author =:2308.12136 , primaryclass =

  67. [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. [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. [69]

    On the structure of

    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. [70]

    and Hirschfeldt, Denis R

    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. [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. [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 =

  73. [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. [74]

    , date-added =

    Johnstone, Peter T. , date-added =. Sketches of an

  75. [75]

    Tukey order among

    He, Jialiang and Hru. Tukey order among. J. Symb. Log. , mrclass =. 2021 , bdsk-url-1 =. doi:10.1017/jsl.2021.30 , fjournal =

  76. [76]

    Fremlin, D. H. , date-added =. Measure Theory

  77. [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. [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. [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. [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 =

Showing first 80 references.