A Logical Interpretation of Some Bits of Topology

Edit: These ideas are also discussed here and here (thanks to Qiaochu Yuan: I found out about those links by him linking back to this post).

Although topology is usually motivated as a study of spatial structures, you can interpret topological spaces as being a particular type of logic, and give a purely logical, non-spatial interpretation to a number of bits of topology.

This seems like one of those facts that was obvious to everyone else already, but I’ll write a quick blog post about it anyway.

As you’re probably aware, a set S of natural numbers is called semi-decidable if there is a computer program which, given any n\in\mathbb{N}, will eventually terminate and return “Yes” if n\in S. If n\notin S, the program is not required to ever return and you may never learn whether or not n\in S.

There are many such “semi-decidable” propositions P unrelated to natural numbers which intuitively have the same property: i.e., there is some test you can perform such that, if P is true, you will eventually find out, but if it’s false, you may never learn that fact. For example, consider the proposition P that you are (strictly) taller than 6 feet. To test P, you could measure your height with ever-finer rulers. If your height h is actually strictly greater than 6 feet, you will eventually find out when you use a ruler with granularity finer than h-6 to measure your height. On the other hand if P is false and you are unfortunate enough that h is exactly 6, you will never learn whether or not P is true no matter how fine a ruler you use.

Semi-Decidable Logic

Let’s come up with a logic for such semi-decidable propositions. We’ll keep it a propositional logic to keep things simple. First off, notice that we shouldn’t allow negation: if P is semi-decidable, it’s not necessarily the case that \neg P is. On the other hand, we can allow conjunction: if P and Q are semi-decidable, then you can test P\wedge Q by testing P and Q separately and stopping if and when both the tests for P and Q stop.

Furthermore, we can allow arbitrary disjunctions: given \{P_i\}, we can test \bigvee \{P_i\} by running all the tests in parallel and stopping when any of them stop. Note that even given that we can arbitrarily many tests at the same time, it still doesn’t follow that arbitrary conjunctions of semi-decidable propositions are semi-decidable: if the first one terminates after 1 minute, the second after 2, etc., we’ll never be able to stop the test of the conjunction even though all tests terminate eventually.

Implication is a bit tricky: P\rightarrow Q isn’t necessarily semi-decidable for the same reason that \neg P isn’t, but we still want to reason about the case where P implies Q. Therefore, we’ll allow the formation of the statement P\vdash Q with the meaning that P implies Q, but only at the “top level”, i.e., you can’t nest this connective.

Finally, both \top and \bot are semi-decidable.

Now we need rules to tell us when a set of statements implies another statement. First off, there are some boring structural rules that I’ll omit (e.g., P\vdash Q and Q\vdash R imply P\vdash R and so on).

There are rules that give the two connectives their meaning:

  • For any P and Q, P\wedge Q\vdash P and P\wedge Q\vdash Q hold.
  • For any P, Q, and R, the statements R\vdash P and R\vdash Q together imply R\vdash P\wedge Q.
  • For any P and \{Q_i\}, P\vdash \bigvee \left(\{P\}\cup\{Q_i\}\right) holds.
  • For any P and \{Q_i\mid i\in \mathcal{I}\}, the set of statements \{Q_i \vdash P\mid i\in\mathcal{I}\} implies the statement \bigvee \{Q_i\}\vdash P.

Finally, there’s a distributivity rule:

  • For any P and \{Q_i\mid i\in\mathcal{I}\} the statements P\wedge \bigvee \{Q_i\} and \bigvee \{P\wedge Q_i\mid i\in\mathcal{I}\} are equivalent (each implies the other).

Topology

As you’ve probably guessed, there is a close connection between semi-decidable logics and topological spaces. In fact, given a topological space, you can form a semi-decidable logic by making a propositional symbol P_U for each open set U. You can then interpret all propositional formulas as open sets by interpreting \bigvee as union and \wedge as intersection. Finally, take as a set of axioms the set of all statements P\vdash Q where the open set corresponding to P is a subset of the open set corresponding to Q. This set is closed under the inference rules given.

You can also start with a semi-decidable logic and generate a topology; this is a form of Stone duality.  In general, if you start with a topological space, translate to a semi-decidable logic, then translate back, you might not get your original space back.  However, you will if the space you start with is sufficiently nice (e.g., Hausdorff).

With that out of the way, let’s interpret some topological concepts in our new logical framework!

  • Topologically, a neighborhood is any set which contains a non-empty open set. Logically, these correspond to propositions that are possible to learn. In the height example, the proposition that your height h is in [5\text{ ft}, 6\text{ ft}] is a neighborhood since you might happen to learn it by learning some stronger fact, but you can’t run a semi-decidable test for exactly that proposition.  In contrast, the proposition that your height is exactly 6 ft is not even a neighborhood.
  • Topologically, an open covering \mathcal{O} is a set of open sets whose union covers the whole space.  Logically, this corresponds to a deterministic experiment. If you run the tests in parallel, you are guaranteed that eventually (at least) one of them will stop, since the sets cover the whole space.  In the height example, the open covering of all open intervals of diameter 1\text{ cm} corresponds to measuring your height to a granularity of 1\text{ cm}  and recording the results.
  • Topologically, an open covering \mathcal{O}_1 is a refinement of an open covering \mathcal{O}_2 if every element of \mathcal{O}_1 is a subset of some element of \mathcal{O}_2.  Logically, this corresponds to experiment {O}_1 being more informative than experiment \mathcal{O}_2.  Whatever answer you get from experiment \mathcal{O}_1, you will be able to answer the question asked by experiment \mathcal{O}_2.
  • Topologically, a space is compact if every open cover has a finite refinement.  Logically, this means that anything about the space that you could find out by any experiment at all is actually discoverable by an experiment that runs only finitely many tests and hence is (maybe) doable in real life.
  • Topologically, a space has Lebesgue covering dimension n if all open covers have a refinement with no n+2 of the open sets having non-empty intersection.  Logically, this corresponds to something like a bound on the amount of information you can get from one experiment.  The information you get from running an experiment is just the list of propositions (open sets) which you’ve learned are true.  The condition guarantees that that list will be no longer than n+1, bounding the information received from the experiment.  This makes spatial sense too: a measurement on \mathbb{R} in general yields less information than a single measurement on \mathbb{R}^2.

Actually, that last correspondence was the whole impetus for me writing this blog post: I never really understood the definition of Lebesgue covering dimension from a spatial perspective, but it makes perfect sense to me from a logical perspective.

Miscellaneous

Here are a few more random facts which may or may not be accurate and/or make sense.

Geometric Logic

I believe that “semi-decidable logic” as I presented it is in fact the propositional version of geometric logic. Geometric logic also has a higher-order form: just as the propositional form corresponds to topologies, I believe the full higher-order form corresponds to toposes.

Sheaves

I think you can extend this interpretation of topological spaces to an analogous one for sheaves. I believe it’s something like: a sheaf corresponds to a set of solutions to some problem that you learn more about as you learn more semi-decidable propositions. In particular, the gluing property corresponds to the fact that: if you can determine via an experiment which of P or Q holds, and you have a solution given P and a solution given Q that are compatible, then you have a solution: run the experiment, then use the solution of whichever of P or Q turns out to be true.

Making sense of this is left as an exercise to the reader.

Grothendieck Topologies

I said above that I’d address the assumption that you can run arbitrarily many tests at once. I believe that, among many other things, Grothendieck topologies remove this restriction.

Regular topologies have the sort-of-odd property that the open covering relation is completely determined by the partial ordering on open sets given by inclusion. Grothendieck topologies do away with this: in a Grothendieck topology, there is in addition to the partial order an assignment for every open set of which sets of open sets are deemed to define “open covers”. Grothendieck topologies also remove the restriction that the “partial order” on open sets is a partial order; it’s allowed to be a more general category.

About these ads

8 Comments

Filed under Uncategorized

8 responses to “A Logical Interpretation of Some Bits of Topology

  1. To push the interpretation a bit further: the boldface Borel hierarchy arises naturally when we ask: “What is the topological notion corresponding to logical quantifiers?”

  2. Pingback: Ninth Linkfest

  3. Pingback: Weekly Picks « Mathblogging.org — the Blog

  4. Peter Berry

    The book “Topology via Logic” by Stephen Vickers takes this approach. It’s how I learned topology as a computer scientist.

  5. Joe

    Hi Mike, want to have lunch tomorrow (Mon)?
    Sorry, I can’t find your email -Joe

  6. Joe

    Oh yeah, you might like the book by Van den Dries “o-minimal structures”.
    As far as I heard this is the theory is main source of applications of logic (more precisely model theory) in topology. The baby (and model) example is semi-algabraic sets which are subsets of R^n defined by equalities and inequaliites of polynomials. From a logic perspective the sets are definable in the language with the symbols
    < + = *

  7. Peter Enis

    I don’t believe that arbitrary disjunctions of semi-decidable predicates is semidecidable. Running countably many tests in parallel is infeasible because it requires an infinite program description incorporating programs for all predicates.

    Moreover, semi-decidable subsets of N cannot form a topology: {n} is a semi-decidable set for every positive integer n, hence we get the discrete topology and every set is semidecidable, which is false.

  8. A. Nonymous

    I think even though it is impossible to run in parallel, you could run countably many programs as follows:

    FOR N FROM 1 TO INFINITY: FOR M FROM 1 TO N: RUN ONE STEP OF PROGRAM M; HALT IF PROGRAM M IS FINISHED.

    Each program will then eventually execute an infinite number of steps.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s