Saturday, 1 July 2006

gn.general topology - Is there good evidence that topological spaces are the correct way to study the general theory of continuity?

Geometry and "theory of distance" are not the only motivation for general topology. Another motivation comes from information processing and computation.



Briefly, let us consider the notion of "observable subset" where by "observable" we mean "can be confirmed by a (finite-time) computation". More precisely, a subset $S subseteq X$ of a datatype $X$ is computationally observable if there exists a program $p$ such that




for all $x in X$, $p(x)$ terminates if, and only if $x in S$.




Note the assymetry between an observable subset and its complement. You can think of the fact that $p(x)$ terminates as giving you half a bit of information.



We make the following basic observations:



  1. The empty subset is observable by a program which never terminates.

  2. The whole set is observable by a program which always terminates.

  3. If $S$ and $T$ are observable by $p$ and $q$, respectively, then $S cap T$ is observable by the program $p; q$ (execute $p$, wait for it to finish then execute $q$).

  4. If $(S_n)$ is a sequence of subsets observable by a (computable) sequence $p_n$ of programs, then $bigcup_n S_n$ is observable by the program which runs $p_0, p_1, p_2, ldots$ in parallel by dovetailing and finishes as soon as one of them does.

If we replace "observable" by "open" and generalize to arbitrary unions instead of just countable computable ones, we get the usual definition of topology.



You should convince yourself that it is unreasonable to expect that a countable intersection of observable subsets is observable: if it were, we could solve the Halting problem.



The topological spaces which arise in theoretical computer science from the point of view that "open = computationally observable" are typically not Hausdorff, let alone metrizable. They are however very nice spaces with lots of good properties.



You asked about continuity. Under the view I described we can show that computable maps are continuous in a very natural way: if $f : X to Y$ is computable and $S subseteq Y$ is observable by $p$ then $f^{-1}(S)$ is observable by $q(x) = p(f(x))$.



To summarize




"Observable sets are open, computable maps are continuous."




So yes, the usual definition of continuous maps as one whose inverse image preserves open sets is right. The definition of topology, however, could be discussed a bit further. There is something fishy about going from computable countable unions to general ones just like that.

No comments:

Post a Comment