There is a folklore correspondence between topology as semi-decidability amongst computer scientists, which is explained in places like:

  1. The monograph Synthetic Topology: of Data Types and Classical Spaces
  2. An answer by Andrej Bauer on reversing the order of quantifiers .

I recently also learnt that Coarse structures are a type of "dual" to topologies, in that they capture "global" behaviour versus "local" behvaiour that topologies capture. This viewpoint is explained in:

  • This answer on MathOverflow to the question "dualizing topology", which writes down the topology axioms using category theory and then dualizes the construction.
  • In general, the view appears to be held that Coarse Stuctures is the correct way to dualize a topology to study large-scale phenomena. My understanding is that it was used very effectively by Gromov to study hyperbolic groups by considering quasi-isometry.

So, it is natural to ask, "what is the computational equivalent of a coarse structure"? I was hoping the answer would be something like "co-induction" / "making progress", since topology seems to be about "deciding" things. However, I have no clue how to proceed with such a question. I'd love some insight into this.

  • 1
    $\begingroup$ @YCor, I think your edit changed the meaning of the title. Perhaps the SAT-style analogy notation is unfamiliar? The original title, I think, was not expressing general bafflement as the current one seems to do, but asking "What is to coarse structures as semi-decideability is to topology?" In case I am mistaken, I will leave it to @‌SiddharthBhat to revert. $\endgroup$ – LSpice Feb 13 at 0:57
  • $\begingroup$ @LSpice that was indeed the intention --- However, I was worried the title was too flippant / not well communicated. If the analogy notation is indeed well known, then I'd like to change it back! $\endgroup$ – Siddharth Bhat Feb 13 at 1:10
  • 1
    $\begingroup$ Indeed the initial colons were cryptic to me; the OP's new title looks good. $\endgroup$ – YCor Feb 13 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.