<p><a href="http://www.math.utu.fi/icalp04/godel2004.html" rel="nofollow noreferrer">The 2004 Gödel Prize</a> was shared between the papers:</p>
<ul>
<li><em>The Topological Structure of Asynchronous Computation</em>.<br />
By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923</li>
<li><em>Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge</em>.<br />
By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483.</li>
</ul>
<p>Quotes from <a href="http://www.math.utu.fi/icalp04/godel2004.html" rel="nofollow noreferrer">the 2004 Gödel Prize:</a></p>
<blockquote>
<p>The two papers offer one of the most important breakthroughs in the theory of distributed computing.</p>
<p>The discovery of the <strong>topological nature of distributed computing</strong> provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.</p>
</blockquote>
<hr />
<p>Related post: <a href="https://cstheory.stackexchange.com/q/2898/12739">Applications of topology to computer science</a></p>

CC BY-SA 3.0
2015-05-24T18:38:23.067Z
Although these are certainly *great* applications of topology in TCS, they are really applications of "combinatorial/algebraic topology" rather than what I *think* the OP meant by "general topology" (which is more in the point-theoretic / set-theoretic / logical arena).
Joshua Grochow
CC BY-SA 3.0
2015-05-24T02:34:02.457Z
2015-05-24T02:34:02.457Z
2020-06-17T09:38:08.363Z
hengxin
<p>Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been characterized using topology. </p>

<p>Defining Liveness <a href="http://www.sciencedirect.com/science/article/pii/0020019085900560" rel="nofollow" title="Defining Liveness Alpern and Schneider">Alpern and Schneider</a></p>

<p>Safety and Liveness in Branching time <a href="http://dl.acm.org/citation.cfm?id=871868" rel="nofollow" title="Safety an liveness in Branching Time">Manolios et. al.</a></p>

CC BY-SA 3.0
2015-05-23T12:24:45.257Z
2016-02-25T13:29:21.087Z
2016-02-25T13:29:21.087Z
Mitesh J
<p>One major application of topology in semantics is the topological approach to computability. </p>

<p>The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it doesn't terminate (since you can never be certain you have not waited long enough to see it terminate). This corresponds to equipping the two point set {HALT, LOOP} with the Sierpinski topology, where $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ are the open sets. So then we can basically get pretty far equating "open set" with "computable property". One surprise of this approach to traditional topologists is the central role that non-Hausdorff spaces play. This is because you can basically make the following identifications</p>

<p>$$
\begin{matrix}
\mathbf{Computability} &amp; \mathbf{Topology}\\
\mbox{Type} &amp; \mbox{Space} \\
\mbox{Computable function} &amp; \mbox{Continuous function} \\
\mbox{Decidable set} &amp; \mbox{Clopen set} \\
\mbox{Semi-decidable set} &amp; \mbox{Open set} \\
\mbox{Set with semidecidable complement} &amp; \mbox{Closed set} \\
\mbox{Set with decidable equality} &amp; \mbox{Discrete space} \\
\mbox{Set with semidecidable equality} &amp; \mbox{Hausdorff space} \\
\mbox{Exhaustively searchable set} &amp; \mbox{Compact space} \\
\end{matrix}
$$</p>

<p>Two good surveys of these ideas are MB Smyth's <em>Topology</em> in the <em>Handbook of Logic in Computer Science</em> and Martin Escardo's <a href="http://www.cs.bham.ac.uk/~mhe/papers/entcs87.pdf" rel="nofollow"><em>Synthetic topology of data types and classical spaces</em></a>.</p>

<p>Topological methods also play an important role in the semantics of concurrency, but I know much less about that. </p>

CC BY-SA 3.0
2015-05-01T21:35:18.417Z
Thank you for your enlightening answer! I will have a look.
user135172
CC BY-SA 3.0
2015-05-24T03:03:09.703Z
Is it possible to seek a finer topology for polynomial hierarchy alone?
Turbo
CC BY-SA 3.0
2015-05-25T03:54:15.230Z
A fascinating application of these ideas can be found in the series of posts "Seemingly impossible functional programs" - http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ , http://math.andrej.com/2014/05/08/seemingly-impossible-proofs/
jkff
CC BY-SA 3.0
2015-06-01T06:12:52.217Z
Can you give us a little more here? I find this answer very difficult to comprehend. For example, assume for a contradiction that the semi-decidable subsets of $\mathbb{N}$ form a topology, as you appear to be claiming. Then it follows that **since** for every natural number $k \in \mathbb{N}$, the singleton set $\{k\} \subseteq \mathbb{N}$ is semi-decidable, **hence** arbitrary unions of singleton subsets of $\mathbb{N}$ are semi-decidable. Ergo every subset of $\mathbb{N}$ is semi-decidable, a contradiction.
goblin GONE
CC BY-SA 3.0
2015-04-30T11:30:38.630Z
2016-07-26T17:45:53.780Z
2016-07-26T17:45:53.780Z
Neel Krishnaswami
<p>I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.</p>

<p>Are there any applications for these subjects in computer science?
I have looked a bit, and found a lot of applications (of course) for finite graph theory, finite topology, low dimensional topology, geometric topology etc.</p>

<p>However, I am looking for applications of the infinite objects of these subjects, i.e. infinite trees (<a href="https://en.wikipedia.org/wiki/Aronszajn_tree">Aronszajn trees</a> for example), infinite topology etc.</p>

<p>Any ideas?</p>

<p>Thank you!!</p>

CC BY-SA 3.0
2015-04-30T22:25:35.543Z
see also [Application of set theory subjects as ordinals, forcing, generic filters in software engineering](http://cs.stackexchange.com/questions/40903/application-of-set-theory-subjects-as-ordinals-forcing-generic-filters-in-soft) cs.se
vzn
CC BY-SA 3.0
2015-05-01T20:50:45.253Z
In addition to Neel's great answer, you might also be interested in computable ordinals, which play an interesting role in computability theory: http://en.wikipedia.org/wiki/Recursive_ordinal
Joshua Grochow
<set-theory><topology><topological-graph-theory>
Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?
user135172
# Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

(Asked by: username_0 on 2015-04-30)

I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.

Are there any applications for these subjects in computer science?
I have looked a bit, and found a lot of applications (of course) for finite graph theory, finite topology, low dimensional topology, geometric topology etc.

However, I am looking for applications of the infinite objects of these subjects, i.e. infinite trees ([Aronszajn trees](https://en.wikipedia.org/wiki/Aronszajn_tree) for example), infinite topology etc.

Any ideas?

Thank you!!

**Tags:** set-theory, topology, topological-graph-theory

> **Comments:**
> **username_1**: see also [Application of set theory subjects as ordinals, forcing, generic filters in software engineering](http://cs.stackexchange.com/questions/40903/application-of-set-theory-subjects-as-ordinals-forcing-generic-filters-in-soft) cs.se  
> **username_2**: In addition to Neel's great answer, you might also be interested in computable ordinals, which play an interesting role in computability theory: http://en.wikipedia.org/wiki/Recursive_ordinal  

---

## 3 answers

### Answer by username_5 on 2015-04-30. Score: 21 | Accepted answer

One major application of topology in semantics is the topological approach to computability.

The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it doesn't terminate (since you can never be certain you have not waited long enough to see it terminate). This corresponds to equipping the two point set {HALT, LOOP} with the Sierpinski topology, where $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ are the open sets. So then we can basically get pretty far equating "open set" with "computable property". One surprise of this approach to traditional topologists is the central role that non-Hausdorff spaces play. This is because you can basically make the following identifications

$$
\begin{matrix}
\mathbf{Computability} & \mathbf{Topology}\\
\mbox{Type} & \mbox{Space} \\
\mbox{Computable function} & \mbox{Continuous function} \\
\mbox{Decidable set} & \mbox{Clopen set} \\
\mbox{Semi-decidable set} & \mbox{Open set} \\
\mbox{Set with semidecidable complement} & \mbox{Closed set} \\
\mbox{Set with decidable equality} & \mbox{Discrete space} \\
\mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\
\mbox{Exhaustively searchable set} & \mbox{Compact space} \\
\end{matrix}
$$

Two good surveys of these ideas are MB Smyth's *Topology* in the *Handbook of Logic in Computer Science* and Martin Escardo's [*Synthetic topology of data types and classical spaces*](http://www.cs.bham.ac.uk/~mhe/papers/entcs87.pdf).

Topological methods also play an important role in the semantics of concurrency, but I know much less about that.

> **Comments:**
> **username_0**: Thank you for your enlightening answer! I will have a look.  
> **username_6**: Is it possible to seek a finer topology for polynomial hierarchy alone?  
> **username_7**: A fascinating application of these ideas can be found in the series of posts "Seemingly impossible functional programs" - http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ , http://math.andrej.com/2014/05/08/seemingly-impossible-proofs/  
> **username_8**: Can you give us a little more here? I find this answer very difficult to comprehend. For example, assume for a contradiction that the semi-decidable subsets of $\mathbb{N}$ form a topology, as you appear to be claiming. Then it follows that **since** for every natural number $k \in \mathbb{N}$, the singleton set $\{k\} \subseteq \mathbb{N}$ is semi-decidable, **hence** arbitrary unions of singleton subsets of $\mathbb{N}$ are semi-decidable. Ergo every subset of $\mathbb{N}$ is semi-decidable, a contradiction.  

---

### Answer by username_3 on 2015-05-24. Score: 4

[The 2004 Gödel Prize](http://www.math.utu.fi/icalp04/godel2004.html) was shared between the papers:

* *The Topological Structure of Asynchronous Computation*.  
  By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923
* *Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge*.  
  By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483.

Quotes from [the 2004 Gödel Prize:](http://www.math.utu.fi/icalp04/godel2004.html)

> The two papers offer one of the most important breakthroughs in the theory of distributed computing.
>
> The discovery of the **topological nature of distributed computing** provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.

---

Related post: [Applications of topology to computer science](https://cstheory.stackexchange.com/q/2898/12739)

> **Comments:**
> **username_2**: Although these are certainly *great* applications of topology in TCS, they are really applications of "combinatorial/algebraic topology" rather than what I *think* the OP meant by "general topology" (which is more in the point-theoretic / set-theoretic / logical arena).  

---

### Answer by username_4 on 2015-05-23. Score: 4

Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been characterized using topology.

Defining Liveness [Alpern and Schneider](http://www.sciencedirect.com/science/article/pii/0020019085900560 "Defining Liveness Alpern and Schneider")

Safety and Liveness in Branching time [Manolios et. al.](http://dl.acm.org/citation.cfm?id=871868 "Safety an liveness in Branching Time")


---

