5
$\begingroup$

In the book "topology via logic" by Steven Vickers, topology is introduced for computer scientists, with the idea that topology captures the idea of approximate information.

I am somewhat confused by the explanation. In particular, I'm confused by how it relates to sigma-algebra's, which are also a way to express approximate information. In the case of sigma-algebra's, we can think of each set in the sigma-algebra as the sigma as a "signal" that we may receive, and the elements of that set as the "possible worlds" in which we would receive that signal. The sigma algebra then denotes the fact that we don't know in which exact world we are, but we know what subset of possible worlds we are. The axiom of closure under complementation follows intuitively from this: If we don't get the signal that we're in subset of worlds $A$ then we must be in $A^c$.

What is the rationale behind using topology instead of sigma-algebra's for capturing approximate information in computer science?

In particular, how are the differences between topology and sigma-algebra's imply for how they are used as frameworks for talking about approximate information?

  • closure under complementation in sigma-algebra's but not in topology

  • closure under countable unions in sigma-algebra but arbitrary unions in topology.

  • closure under countable intersections in sigma-algebra but finite intersections in topology.

$\endgroup$
3
  • $\begingroup$ The rationale could depend on how "the idea that topology captures the idea of approximate information." is phrased by the author. It can be useful to quote the relevant portion of the book or summarize it if it is too lengthy. $\endgroup$
    – Discrete lizard
    Feb 13 '19 at 11:49
  • $\begingroup$ @Discretelizard, this feels to me like the type of thing that someone who is familiar with this application of topology wouldn't need the particular information of how this particular author formalizes it. $\endgroup$
    – user56834
    Feb 13 '19 at 11:50
  • $\begingroup$ I'm not talking about the formalization, I'm talking about the motivation for the connection between approximation and topology. It could very well be the case that from some point of view, the difference between topology and sigma-algebra is irrelevant in modelling approximate information and the author merely used it to provide a motivation to do topology. $\endgroup$
    – Discrete lizard
    Feb 13 '19 at 11:58
4
$\begingroup$

What sort of structure we get depends on what we are trying to model. Your starting assumptions may well lead to $\sigma$-algebras, but in computer science we have a certain understanding of "approximate information" which is naturally captured by topology.

Consider the following pieces of information:

  • no information
  • it is raining
  • it is not raining

Clearly, "no information" approximates both "it is raining" and "it is not raining". If we think of "it is raining" as an observation that can be made, then the following assymetry is cruicial: having the information "it is not raining" is not equivalent to not having the information "it is raining". That is, if you don't receive some piece of information saying that $P$ holds, then you simply don't know. It is faulty to presume that you know $\lnot P$. This is the root cause of why the $\sigma$-algebra law of complementation is not valid in this context.

Now, to motivate closure under arbitrary unions and finite intersections (but not under arbitrary intersection), we need to take a slightly different point of view. Let us say that we want verifiable information, i.e., we say that we "have information $A$" if we can reasonably verify that $A$ holds.

  1. To verify a binary conjunction $A \land B$, we verify both $A$ and $B$.
  2. To verify an arbitrary disjunction $\bigvee_i A_i$ it is sufficient to verify a single $A_j$.

However:

  1. To verify an infinite conjunction $\bigwedge_i A_i$ we would have to verify all $A_i$'s, and this may not be doable algorithmically (or in a physically realistic manner).

  2. Just because we know how to verify $A$ does not mean that we also know how to verify $\lnot A$.

Example: to verify that a given machine $T$ halts it suffices to run the machine and wait until it stops. At this point we have verified that $T$ stops. (It is irrelevant what would have happened if $T$ did not stop!) But how could we verify that $T$ does not stop? It's not in general verifiable whether $T$ stops.

Another example: "$x > 0$" is a verifiable property of computable reals, but "$x \leq 0$" is not. (Recall that $x \in \mathbb{R}$ is computable if there is an algorithm which, for any given $n \in \mathbb{N}$ gives an interval $[a_n,b_n]$ with rational endpoints such that $a_n < x < b_n$ and $b_n - a_n < 2^{-n}$.) The verification algorithm works as follows: given an algorithm for computing $x$, find $n \in \mathbb{N}$ such that $0 < a_n$. If $x > 0$ then this algorithm will terminate after a finite time, thereby confirm that $x > 0$. If $x \leq 0$ then the algorithm will run forever, but that is OK because we only need to confirm $x > 0$, we are not trying to deny $x > 0$ in case it does not hold. In contrast, we cannot confirm $x \leq 0$ because there is no algorithm which takes as input $x \in \mathbb{R}$ and terminates if, and only if, $x \leq 0$.

$\endgroup$
2
$\begingroup$

I don't consider myself knowledgable enough about logic to provide a complete answer myself, but I think the following two posts (1 from math.stackexchange, one from mathoverflow) contain some information that may help you understand the topology part of your question better:

  1. Dan Piponi's answer here gives a good explanation about how topologies can represent approximate information
  2. This post which was written later summarizes the first post + has some additional information about the information-interpretation of topologies

Unfortunately I'm not familiar with corresponding explanations for Sigma Algebras, even though I think your question is quite natural and agree that both objects are somewhat similar.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.