Bisimulation theory and Quillen model categories (an extended abstract)

J.M. Egger

July 16, 2007

1 Overview

Given a class of objects and a notion of “an equivalence of objects”, a categorist naturally looks for a more general notion of arrow, such that the invertible arrows correspond to equivalences. This is the project which we pursue, with respect to automata and bisimulations.

By automata, we do not necessarily mean labelled transition systems (ltss). What we are really interested in are the presheaf models for bisimulation [Joyal-Nielsen-Winskel]

(also [Kurz-Rosicky?]).

What makes this project interesting is that bisimulations are not maps of automata, in the obvious sense, but rather a certain kind of span: a span of open maps.

Our idea is that one should formally invert the bisimulations in the category of all spans to obtain an “optimal” category whose objects are automata and whose invertible arrows are bisimulations. The fact that open maps form half of a weak factorisation system suggests that there might be a Quillen model structure (qms) at play—which might make the situation easier to handle.

2 General abstract nonsense

Let K denote a category with pullbacks and (L, R) a weak factorisation system (wfs) on K. [Intuitively, we think of K as a category of automata, and R as the class of open maps.]

Note that we shall use span(K) to denote the category whose arrows are isomorphism classes of spans, because (for the time being) I don't want to have to worry about

bicategorical things, and because restricting to relations would require a second
factorisation system on K.

Definition We consider the following three classes of maps in span(K):

1. C is the class of spans of the form \xymatrix{x & r \ar[l]_{α} \ar[r]^{λ} & y} with λ ∈ L; 2. W is the class of spans of the form \xymatrix{x & r \ar[l]_{ρ_{0}} \ar[r]^{ρ_{1}} & y} with ρ_{0}, ρ_{1} ∈ R;

3. F is the class of spans of the form \xymatrix{x & r \ar[l]_{λ} \ar[r]^{β} & y} with λ ∈ L;

Lemma

If L is stable under pullbacks in K, then (C, W ∩ F) and (C ∩ W, F) form wfss on span(K).

Proof We shall treat the case (C, W ∩ F) only, as the case (C ∩ W, F) follows symmetrically.

Factorisation is easy: given a span \xymatrix{x & r \ar[l]_{α} \ar[r]^{β} & y}, let \xymatrix{r \ar[r]^{λ} & s \ar[r]^{ρ} & y} denote an (or, the functorially specified) (L, R)-factorisation of β; then

[figure: r; α; λ; s; ρ; x; s; y]

is a (C, W ∩ F)-factorisation of \xymatrix{x & r \ar[l]_{α} \ar[r]^{β} & y}.

Lifting is not much harder, except that it involves some largeish diagrams which I haven't gotten around to TEXing yet. This is where the pullback hypothesis is used.

   Retracts had better work out or I'm a fool!  q.e.d.

There’s still one thing missing for (C, W, F) to define a qms on span(K).

Lemma W satisfies two-out-of-three if and only if R does.

Proof

Consider spans of the form [figure: x; x; ρ; y] and [figure: x; y; ρ; y] , as appropriate. q.e.d.

Note that if R satisfies two-out-of-three, then (L, R, K) forms an essentially degenerate qms—by which I mean that the homotopy relation, when restricted to fibrant and cofibrant objects, is trivial—i.e., in this case, the homotopy category is equivalent to the full subcategory of cofibrant objects. [Let us call the latter simply L-objects, to avoid possible confusion between the qmss on K and span(K).]

In the case where (L, R) is a unique factorisation system, the cofibrant replacement functor defines a coreflection of K into the full subcategory determined by the L-objects. (this has been studied by Borceux and Janelidze), but, in general, it seems not to.

One final issue to be dealt with is the existence of finite products and coproducts in span(K): I presume that the following is well known and therefore omit proof.

Lemma If K is lextensive, then span(K) has finite products and coproducts.

Putting the three lemmata together we obtain:

Theorem

If K is lextensive, L is stable under pullback, and R satisfies two-out-of-three, then span(K) equipped with (C, W, F) is a Quillen model category.

Now fortunately or unfortunately, depending on one’s point of view, (C, W, F) is essentially degenerate, in the sense defined above.

Clearly, an object of span(K) is fibrant if and only if it is an L-object; dually it is cofibrant if and only if it is an L-object. Now the two-out-of-three axiom for R implies that any Rarrow between L-objects is iso. Extensivity—i.e., the universal property of coproduct—does the rest of the damage.

Theorem

Ho(span(K)) is equivalent to span(Ho(K)) (where the latter is calculated with respect to the essentially degenerate qms on K described above).