That Logic Blog

April 18, 2005

Discretely Causal

Physicists have long considered spacetime to consist of a smooth real manifold equipped with a fancy sort of metric. One condition on a spacetime that physicists such as Roger Penrose favour as being "physically reasonable" is global hyperbolicity. What this condition essentially means is that some sort of "global" time coordinate exists. In particular, it makes sense to speak about causality.

Rafael Sorkin initiated the study of causal sets. A causal set is a partially ordered set that is locally finite. That is each set of the form {x : a <= x <= b} is finite:
Spacetime and Causal Sets, Rafael Sorkin.

What is intriguing is that we now have a discrete object, namely a causal set, which in some way encodes information about spacetime. Researchers have extended this in a few different ways. In one direction, one may wonder what a causal set looks like to an observer based at one point of the set:

The internal description of a causal set: What the universe looks like from the inside
. Fontini Markapoulou.

The basic thrust of the above paper is that whenever you are at some point in a causal set, you know what events have happened in the past. Then, as you shift around the causal set, the set of events that are in your past changes. Markapoulou characterises this with some simple category theory that is explained very nicely in her paper.

For those familiar with branching temporal logics, such as CTL*, there isn't much new here. Most developments of branching temporal logics assume that the past is linear and that the future is branching. That is, when you stand at a moment in time, there is only one possible history, but many possible futures. An exception is one of the logics in the following paper, which augments CTL(*) with a branching past operator:

Once and for all, Kupferman, O.; Pnueli, A (you or your institution needs an IEEE Explore account to view this paper).

Now, a natural concern is whether the notion of a causal set is intrinsically artificial. That is, given a causal set, is it possible to reconstruct a continuous spacetime? The following paper answers this in the affirmative:

A domain of spacetime intervals in general relativity
. Keye Martin and Prakash Panangaden

Martin and Panangaden do something very cool in this paper. Given a spacetime M, and a point x in M, let F(x) be all the points that are in the future of x and reachable by a timelike curve starting at x. Define a partial order on m by x <= y iff y is in F(x). Then, given a countable dense subset of points of some spacetime, together with the "causality relation" (which I have defined via F), we can reconstruct the entire spacetime, topology and all!Super cool! The techniques are based on domain theory, which was introduced by Scott in order to give a semantics to the lambda calculus. What the above paper shows is that techniques developed in theoretical computer science are applicable to something seemingly unrelated: general relativity. One point to note is that they drop the local finiteness condition on the "causal sets". This is because they work with continuous posets (well, bicontinuous posets actually), where one has a sort of interpolation condition on the order, which negates the possibility of local finiteness.

So, what is the global hyperbolicity condition anyway? If we have some spacetime M, then for each p and q in M, let I(p,q) be all the events in M that are in the "causal future" p as well as the "causal past of q". The "Alexandroff topology" (or rather, one topology with that name..) is obtained by taking as a basis all of the sets I(p,q) for p,q in M. We say that M is strongly causal if its Alexandroff topology is Hausdorff, which amounts to saying that its Alexandroff topology is the same as the manifold topology. The spacetime M is globally hyperbolic if it is strongly causal and for all a,b in M, the intersection of up(a) and down(b) is compact in the manifold topology on M. Here, up(a) are all those elements "above" a in the partial order and similarly for down(b).

Along the way, they show that every globally hyperbolic spacetime can be realised as a bicontinuous poset, where the order is the one I defined above. Moreover, the interval topology on the poset is the same as the original manifold topology.

Martin and Panangaden give a very convincing argument for swapping the "local finiteness" condition for a "bicontinuity" condition in the description of a causal set, though they remain diplomatic and don't go so far as to say this. Anyway, it's a pretty cool application of some ideas originally developed for "logic in computer science", so you should check it out!


Anonymous Anonymous said...

Interesting post.

The arrow of influence between theoretical computer science and theoretical physics is in fact two-way.
Penrose et al's ideas about time-paths in spacetime has had influence in concurrency theory, in particular the development of an algebraic topology of concurrent systems. See the work of the GETCO conferences (Geometric and Topological Methods in Concurrency), particularly the work of Eric Goubault, Martin Raussen and Lisbeth Fajstrup.

Posted by Peter

4:16 AM  
Anonymous Anonymous said...

As a PS:

Models with multiple pasts have a natural application in computer science (and elsewhere) -- to system diagnosis. If your printer breaks down, for example, there are multiple ways in which this breakdown state could have been reached, all of which paths are possible until some diagnosis is undertaken. Arguably, if the fault is serious, there is only one future path for the system following this state.


Posted by Peter

4:22 AM  
Anonymous Anonymous said...

Thanks for the comments, Peter. I'll have to check out Goubault et al's stuff some time. If I am not mistaken, there's a bunch of people down this end of the world working on similar things, though coming at it via higher dimensional category theory (which I know absolutely zilch about).

It seems to me that a logic with a branching past and linear future is not really different from one with a branching future and linear past. I agree, though, that a "branching both ways" logic is sensible in diagnosis/model checking of concurrent systems.  

Posted by Jon

8:52 AM  
Anonymous Anonymous said...

Yes, Jon, Higher-dimensional category theory is also one approach considered by the GETCO folks -- if you have multiple (computer) processes working simultaneously, then modeling the many ways in which they can interact leads one naturally to n-categories.

Are you aware of the conference held on n-cats in North America last summer? Details here . The papers may still be accessible on the site.

In addition, some of the recent theoretical work in interactive computation leads one also directly to n-cats: I am thinking of Samson Abramsky's work on game-theoretic semantics for interactive computation, and Robin Milner's theory of bigraphs, which aims (among much else) to be a theory of hyperlinks. As Abramsky has said, Turing's model of computation is actually very simplistic in comparison to the computing going on all around us (interactive, autonomous processes, working under multi-threaded, ever-on, operating systems), and so it is not surprising that such real-world complexity needs advanced pure math to model.


Posted by Peter

5:09 PM  
Anonymous Anonymous said...

Alright, Peter, you've sold me on learning about n-categories :) These seem like good places to start: 

Posted by Jon

2:07 PM  
Anonymous Anonymous said...

Yes, forgot to mention Tom Leinster's nice book.

If you like category theory, then n-category theory has to be n-times better! (Although that inference step does not work with, say, ice-creams.)

I do have one colleague who says it can all be done in enriched categories, but personnally I find the n-cat approach more intuitive.

Posted by Peter

5:14 PM  
Anonymous Anonymous said...

Hi Jon,

Its true from one perspective that local finiteness
seems ruled out by interpolation, but perhaps worth pointing out that something like local finiteness is also retained: instead of requiring [a,b] finite, it is taken to be *compact*.


Posted by Anonymous

3:41 AM  
Anonymous Carey R. Carlson said...

The application of causal sets to cosmology pertains to very large sets. The application to quantum theory is at the foundation level of the causal set hypothesis, and the most important results involve very small causal sets. For example, a causal set of three elements and three links-- a causal triangle-- is the simplest causal set in which a relative frequency is formed, and this serves physics as a relative energy comparison in accord with Plank's E=hf. With this development, each causal link is serving as a quantum of energy. Inspired by the definability of energy, I have modeled Bohr's formula by constructing the electron and its cloud formations as simple causal sets. Further developments yield the fine structure constant, the isolation of charge quanta, the electron "states" of quantum mechanics, and the structure of up/down quarks and the nucleus.
In regard to the continuum, there is no need for it, except to account for the global approximations represented by the differential equations of General Relativity. Physics is no different than economics in its use of the infinitesimal calculus. There are no infinitesimal economic transactions, in spite of the usefulness of calculus in working with supply-and-demand curves.
The findings in quantum theory fulfill the promise of the causal set hypothesis as the Theory of Everything. -- Carey

3:09 AM  

Post a Comment

<< Home