What can Topology tell us about Logical Complexity?
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909041220911104 |
|---|---|
| author | Kihara, Takayuki Ng, Ming |
| author_facet | Kihara, Takayuki Ng, Ming |
| contents | 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ětov order on filters over $ω$ -- essentially, this is the usual Katě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ě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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_14086 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | What can Topology tell us about Logical Complexity? Kihara, Takayuki Ng, Ming Logic Category Theory 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ětov order on filters over $ω$ -- essentially, this is the usual Katě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ě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. |
| title | What can Topology tell us about Logical Complexity? |
| topic | Logic Category Theory |
| url | https://arxiv.org/abs/2605.14086 |