What is Topology?
Of all the branches of mathematics I have studied, Topology was the one with the biggest mismatch between what I expected, and how it actually was. Eventually I reached Algebraic Topology, and that is all about the things you expect: Mobius strips, Klein bottles, pairs of pants, knots and handlebodies. But the subject starts with the machinery of Point Set Topology, and in particular with a set of axioms that can seem highly unmotivated. So I’m going to describe Topology in a way that is completely different from what you’ll find in any Topology textbook I know, but which does draw on published ideas in Computer Science. Nonetheless, I am describing standard off-the-shelf point set topology, just dressing it with different intuitions.
Suppose I have some set X and a (possibly infinite) collection of machines. To each machine M is associated a subset of X, U. The idea is that given an element x of X, you can use the machine M to test to see if x is an element of U. The catch is that the machine can only reply “yes”, and that you don’t know how long to wait for the answer, only that if the answer is “yes”, the machine will eventually, after a finite time, give you an answer. If x isn’t in U, the machine sits there forever, neither saying “yes” nor “no”. We’ll call a set V “observable” if for every x in V, we can use a machine, or some combination of machines, to show (in a finite time of course) that x is in V. So all of the U’s associated to machines M are observable.
Now suppose we have two machines, M and N, associated with sets U and V respectively. We input x to both machines. If x is in U intersection V then eventually both machines will reply “yes”. We don’t know how long to wait, but we know it’ll be a finite wait. Similarly, if x is in U union V we known that one machine or the other will eventually say “yes”. So U intersection V and U union V are both observable.
Now suppose we have a (possibly infinite) collection of observable sets Ui. Let U be the union of all the Ui. Given any element x of U, it must be a member of one of the Ui. But every Ui is observable, so there is some combination of machines that can prove that x is in Ui. And hence we can show that x is in U. So unions of infinite collections of observable sets are observable.
(Note that in the previous paragraph I didn’t say you had to have an algorithm for saying which Ui you should use, given x. I’m just saying that some Ui must exist. This means I’m not talking about semidecidability. But observability is similar to semidecidability.)
So what are the machines that I’m talking about? Let’s leave that undecided. We can use the above observations to make a definition:
Given a set X, a system of observables is a set of subsets of X, called observable sets, with the properties
So let me fill in with an example. Suppose we have some devices for measuring signed lengths (or, say, x-coordinates in some frame of reference). These lengths take value in the real line, R. If the device measures a length within its observable set it eventually says “yes”, otherwise it hangs until you press reset. Suppose x is in a device’s observable set. Then some mechanism eventually leads to a “yes” response. But if the device is based on reasonable physical principles, it must be possible to tweak x by a tiny amount and still trigger the same mechanism, otherwise the device would, in some sense, be infinitely discriminating around x. So if x is in an observable set U, then the interval [x-e,x+e] must also be in U for some, possibly very small, e. So let’s define a system of observables on the real line by saying U is observable if for every x in it, there is some e such that [x-e,x+e] is in the set. Intuitively, these are sets that are “fuzzy round the edges”. That’s a reasonable property of a real world measuring device.
Suppose we can augment our devices by applying transformations to a value x before applying the machine. For example, if the machine works optically you could imagine applying a magnifying lens to it to improve its accuracy. For a 10x lens, say, we’d apply the function x -> 10x to our point, and then apply a machine M to see if 10x lies in U. More generally, if our transforming function is f, then applying that to x converts our machine into a machine that tests whether x is an element of the set
f-1(U) = {y | f(y) in U}
If f is the product of a physical process, it’s reasonable to expect f to be continuous at all of its arguments. So what does f-1(U) look like for continuous f? Well, by definition, f is continuous at x if for all d there is an e such that |x-x’|<e means |f(x)-f(x’)|<d. So if x is in f-1(U), then f(x) has a small interval around it in U (because by stipulation, U is observable) and so x has a small interval around it in f-1(U) (by continuity of f). In other words, the continuous functions are precisely those functions for which f-1(U) is observable for all observable U, ie. the functions that don't let us observe the unobservable.
So...I’ve talked about observability, and machines, and ways to pre-process the input to these machines. What does any of this have to do with topology? Well, it simply *is* topology. Not a generalisation, or a special case. What I have described is precisely the subject matter of topology. The only difference is that a “system of observables” is normally called a topology and an “observable” set is normally called an open set. And given a topology on a set A, and a topology on a set B, topologists define continuity by saying that f:A->B is continuous if f-1 maps open sets to open sets.
What I’ve tried to do in a few paragraphs is motivate the usual axioms of topology. Usually they are presented as a fait accompli which is justified after the fact by geometrical intuitions. I hope I’ve given a way to look at these axioms that makes them seem natural a priori and that spans both geometrical and computational ideas.
Anyway, now we’re armed with the notion of a topology, I can get back to considering functions from () to ()...
Suppose I have some set X and a (possibly infinite) collection of machines. To each machine M is associated a subset of X, U. The idea is that given an element x of X, you can use the machine M to test to see if x is an element of U. The catch is that the machine can only reply “yes”, and that you don’t know how long to wait for the answer, only that if the answer is “yes”, the machine will eventually, after a finite time, give you an answer. If x isn’t in U, the machine sits there forever, neither saying “yes” nor “no”. We’ll call a set V “observable” if for every x in V, we can use a machine, or some combination of machines, to show (in a finite time of course) that x is in V. So all of the U’s associated to machines M are observable.
Now suppose we have two machines, M and N, associated with sets U and V respectively. We input x to both machines. If x is in U intersection V then eventually both machines will reply “yes”. We don’t know how long to wait, but we know it’ll be a finite wait. Similarly, if x is in U union V we known that one machine or the other will eventually say “yes”. So U intersection V and U union V are both observable.
Now suppose we have a (possibly infinite) collection of observable sets Ui. Let U be the union of all the Ui. Given any element x of U, it must be a member of one of the Ui. But every Ui is observable, so there is some combination of machines that can prove that x is in Ui. And hence we can show that x is in U. So unions of infinite collections of observable sets are observable.
(Note that in the previous paragraph I didn’t say you had to have an algorithm for saying which Ui you should use, given x. I’m just saying that some Ui must exist. This means I’m not talking about semidecidability. But observability is similar to semidecidability.)
So what are the machines that I’m talking about? Let’s leave that undecided. We can use the above observations to make a definition:
Given a set X, a system of observables is a set of subsets of X, called observable sets, with the properties
- X and the empty set are observable
- arbitrary unions of observable sets are observable
- finite intersections of observable sets are observable
So let me fill in with an example. Suppose we have some devices for measuring signed lengths (or, say, x-coordinates in some frame of reference). These lengths take value in the real line, R. If the device measures a length within its observable set it eventually says “yes”, otherwise it hangs until you press reset. Suppose x is in a device’s observable set. Then some mechanism eventually leads to a “yes” response. But if the device is based on reasonable physical principles, it must be possible to tweak x by a tiny amount and still trigger the same mechanism, otherwise the device would, in some sense, be infinitely discriminating around x. So if x is in an observable set U, then the interval [x-e,x+e] must also be in U for some, possibly very small, e. So let’s define a system of observables on the real line by saying U is observable if for every x in it, there is some e such that [x-e,x+e] is in the set. Intuitively, these are sets that are “fuzzy round the edges”. That’s a reasonable property of a real world measuring device.
Suppose we can augment our devices by applying transformations to a value x before applying the machine. For example, if the machine works optically you could imagine applying a magnifying lens to it to improve its accuracy. For a 10x lens, say, we’d apply the function x -> 10x to our point, and then apply a machine M to see if 10x lies in U. More generally, if our transforming function is f, then applying that to x converts our machine into a machine that tests whether x is an element of the set
If f is the product of a physical process, it’s reasonable to expect f to be continuous at all of its arguments. So what does f-1(U) look like for continuous f? Well, by definition, f is continuous at x if for all d there is an e such that |x-x’|<e means |f(x)-f(x’)|<d. So if x is in f-1(U), then f(x) has a small interval around it in U (because by stipulation, U is observable) and so x has a small interval around it in f-1(U) (by continuity of f). In other words, the continuous functions are precisely those functions for which f-1(U) is observable for all observable U, ie. the functions that don't let us observe the unobservable.
So...I’ve talked about observability, and machines, and ways to pre-process the input to these machines. What does any of this have to do with topology? Well, it simply *is* topology. Not a generalisation, or a special case. What I have described is precisely the subject matter of topology. The only difference is that a “system of observables” is normally called a topology and an “observable” set is normally called an open set. And given a topology on a set A, and a topology on a set B, topologists define continuity by saying that f:A->B is continuous if f-1 maps open sets to open sets.
What I’ve tried to do in a few paragraphs is motivate the usual axioms of topology. Usually they are presented as a fait accompli which is justified after the fact by geometrical intuitions. I hope I’ve given a way to look at these axioms that makes them seem natural a priori and that spans both geometrical and computational ideas.
Anyway, now we’re armed with the notion of a topology, I can get back to considering functions from () to ()...
posted by sigfpe at Saturday, February 23, 2008
12 Comments:
It seems your arbitrary unions are in fact countable unions. Is that just to keep the exposition simple, or is this computability-theoretic analogy not exact?
No, I mean arbitrary unions. As I (briefly) mentioned, I'm not assuming there is an algorithm to determine which set in an arbitrary union to use, just that there is one. This means that the analogy with computability isn't exact. Escardo discusses this subject here: http://www.cs.bham.ac.uk/~mhe/papers/entcs87.pdf where he finds a way to make the analogy exact. But I'm interested in going the other way, seeing if there are useful intuitions about general topology that can be gained from thinking about the computer science angle.
"But every Ui is observable, so there is some combination of machines that can prove x in Ui"
That sounds an awful like the compactness theorem I know from logic. Because of the name of that theorem, I suspect first order logic forms a topology where the open sets are the sets of satisfiable sentences.
Thanks for this intro. Topology is a big area of math that I've seen very little of.
Luke,
One statement of the compactness theorem is precisely that the set of all valuations in propositional calculus forms a compact space when endowed with the right topology. But I haven't defined compactness in this post.
For completeness: A cover of a topological space is a (possibly infinite) set of open spaces whose union is the entire space. A subcover is a subset of these sets whose union is still the entire space. A compact space is one where every cover has a finite subcover. That has a nice interpretation in terms of what I call observability but this box really is too small.
Good stuff! I would only add a short paragraph to explain that the intersection of an infinite collection of observable sets does not have to be observable.
Hi Dan,
On your website you have a page comparing various x86 compilers and you say "Tell me how to get an assembly listing out of the free evaluation of this compiler and I'll test my code."
referring to the Digital Mars compiler. The compiler switch you are looking for is -cod.
Sorry to post this here but I couldn't find your e-mail address anywhere.
It is interesting that the notion
of a topology involves two iterations
of the powerset: a set of subsets closed under ... .
There is another approach to topology,
sometimes called formal topology where
you start with neighbourhoods which
have an inclusion relation, and a
"covering" relation between neighbourhoods
and families or sets of neighbourhoods.
If these have the right properties, one
can define the notion of point
(using coinduction).
To find out about formal topology,
start at http://www.math.unipd.it/~sambin/.
The cover relation in formal topology
is a "higher order" relation, as it is
between a neighbourhood and a subset of
the neighbourhoods. So the whole
structure involves two iterations
of powerset.
Steven Vicker's textbook Topology via logic treats topology in a somewhat similar manner: not identical since he doesn't try to justify observability in terms of physical computation, but he does try to ground the intuitions of topology in terms of observability.
You have given a good account of the "orthodox" definition in general topology, but motivated by computational observability, roughly as it was done in theoretical computer science in the (1970s? and) 1980s. However, Punya is quite right to query the meaning of the "arbitrary" unions and suggest that maybe they ought to be countable, because there is plainly a serious mis-match here between set theory and computation.
There is certainly a tradition in pure mathematics of restricting attention to countable unions. This is found in particular in probability and measure theory, because the unions correspond to sums of real numbers, which only exist when at most countably many of them are non-zero. For a similar reason, "cozero" sets in functional analysis (ie the subspaces on which real-valued functions take nonzero values) also form such a system. The definitions are prefixed with the Greek letter sigma (σ), though this seems a bizarre choice. More abstractly, a number of people in South Africa, in particular, study sigma-frames, ie lattices with countable joins over which finite meets distribute.
However, countability is the wrong idea. It is really just a mutilated form of set theory, which naturally generates and deals with larger "cardinalities". If you believe in set theory, you should accept these as part of the system. On the other hand, the mathematical objects that matter are already either countable or countably based, so this mutilation doesn't actually change very much.
Countability completely misses the point of computation. We should be talking about recursive enumerability (RE) instead. The set of non-terminating programs is countable in the classical sense but not RE. What sense does it make to make a parallel observation composed of parts that only qualify for inclusion if some other observation fails to be made?
There is another mathematical tradition that objects to the arbitrary unions because they are impredicative, ie the thing being defined lies amongst the data for the definition. I'm not going to try to explain this point of view in any detail, because, being a categorist, I am rather keen on universal properties, which are inherently impredicative. I shall just point out how arbitrary unions lead to a solution of the halting problem: given any program P, consider the union (in the sense of this blog) of all programs Q for which P&Q fails (ie P and Q do not both terminate); this gives the negation of P, ie a program that terminates iff P doesn't.
Recursive enumerability and/or predicativity are such fundamental ideas that they should really be built into the foundations, not bolted on afterwards. In other words, we want a type theory for all of our investigations that takes account of them from the start.
In the case of predicativity, this is what Per Martin-Löf's type theory does. Along with it come Peter Aczel's CZF (constructive Zermelo-Fraenkel set theory), and Formal Topology, on which there are a number of authors, most notably Giovanni Sambin, although I am not sure that they sing from quite the same hymn-sheet. Algebraic Set Theory (originally by André Joyal and Ieke Moerdijk, but now led by Steve Awodey) is a different tradition, but talks about similar ideas, and I hope to see some convergence in the next few years. In Formal Topology, there are no "arbitrary" open sets or unions thereof. Instead there are "basic" open sets that may perhaps be generated by some recursive process, along with rules for saying when certain families of them "cover" a finite intersection of others. This is entirely consistent with tradition in analysis, where open balls are used, rather than general open subsets. Recursive enumerability is somehow built in to the recursive nature of definitions in Martin-Löf type theory, although this relationship has not so far been laid out very clearly, so far as I am aware.
My theory, Abstract Stone Duality, is based on a different idea, but also ends up with recursive enumerability built in. Instead of regarding the system of open subsets as a set with the algebraic structure of meets and joins, it treats it as another space. The machinery for handling an algebraic theory and its models is provided by the categorical notion of monad, but please note that the category of algebras is the one called after Eilenberg and Moore, which is bigger than the Kleisli category that Eugenio Moggi used for his application of monads to computer science.
We can get a long way by "pretending" that the spaces have joins of chains, as in domain theory, without actually asserting this as an axiom. Finite meets and joins, along with the monadic structure and the Phoa principle that I mentioned in my
previous posting, already recover a lot of the basic results about general topology. The next thing to add is the natural numbers object N, along with general recursion and N-indexed union. Then we already have a theory of general topology with recursively enumerable unions instead of arbitrary ones, and in particular the lattice of RE sets provides the topology on N itself. When we add an axiom for joins of chains, we get a complete theory of computably based locally compact spaces.
Charles,
Hey thanks! I found a few pages of his book online here: http://books.google.com/books?id=9Hh_EoxeiV8C He is using 'affirmable' exactly how I'm using 'observable', including the comment on the top of page 9 about arbitrary unions.
This is the best motivation for the axioms of topology that I've ever seen, and the only one that's ever satisfied me! I've been searching for a motivation for a week or two, but I realize now that I was looking in the wrong places: geometry and analysis.
The more I learn about topology, the more misleading the common description of topology as "rubber sheet geometry" seems to be. Perhaps topologists ought to start using the slogan, "Topology is the study of affirmable sets"!
I run into this post by accident, and I found this outline of the basic (formal) topology ideas very interesting. I currently study a biological system that seems to be implementing very similar algorithms (as strange as it sounds). The work is submitted but not published yet, and I will probably post it online soon. I could send a link to it if you are interested.
Post a Comment
<< Home