## September 7, 2009

### Coalgebraic Modal Logic

#### Posted by David Corfield

Recently I’ve been looking into the coalgebra community’s take on modal logic, which in a phrase states simply that

The key idea is to start from a dual adjunction between the semantics and syntax of propositional theories, as explained on page 3 of Exemplaric Expressivity of Modal Logics. Typically this is a Stone-style duality between (Lindenbaum algebras of) propositions and spaces of models or valuations for a propositional theory.

Modalities are then introduced on the syntactic side in the shape of an endofunctor, where the new modal propositional theories are algebras for this functor. Meanwhile, on the semantic side, we have a endofunctor whose coalgebras provide the semantics for the modal propositional theories. If all goes well, we end up lifting the Stone adjunction to one between coalgebras on one side and algebras on the other. It would be handy at this point if I’d learned how to draw suitable diagrams. As I haven’t you can see what’s going on on page 2 of Coalgebras and Their Logics.

To relate all this to something perhaps familiar, when you introduce the necessity operator $\square$ into a propositional theory, semantically you start thinking about the accessibility of one world from another. So, $\square P$ (it is necessarily the case that $P$) holds in my world if $P$ holds in all worlds accessible from my world. This accessibility relation is thus a relation $R$ between worlds, or in other words a coalgebra for the powerset functor:

$R: X \to P(X).$

Properties of the modalities, such as $\square P \vdash \square \square P$, correspond to properties of the relation, here transitivity.

But there are many other modalities we might want to consider, as explained here:

One large class of logics is the vast and growing family of modal logics, which are characterised by having operators that qualify formulas as holding in a certain way, e.g. ‘necessarily’, ‘in the future’, ‘everywhere’, ‘probably’, ‘as everyone knows’, or ‘normally’. (p. 1)

All of these are needed to analyse typical statements:

In a seemingly simple piece of knowledge such as ‘Normally, the likelihood of road congestion is smaller on weekends’, one implicitly makes use of default logics (‘normally’), probabilistic reasoning (‘the likelihood’) and temporal knowledge (‘weekends’) under a quantitative regime (‘smaller’).

In the case of probabilistic modalities, we might want modal operators such as

it is at least $p \%$ probable that at the next step $\phi$.

On the semantic side of this operator, we will need to revist our old friend the Giry monad which sends a set to the set of subprobability distributions it supports. Coalgebras for this functor are Markov chains. The resulting logic is Probabilistic modal logic.

We can even consider the $\pi$-calculus as a modal logic:

we use the presheaf category $N$ of functors from finite sets (of channel names) with injective renamings to a certain category of domains (representing observable behaviour in the presence of recursion). (p. 5)

The endofunctor on the semantic side, i.e., on $N$ is

$Pi(X) = \mathcal{P}(X + N \times X^N + N \times (N \times X) + N \times \delta X).$

We read Pi as follows. The possible one-step behaviours of a process are non-deterministic (due to $\mathcal{P}$) and may be one of the following alternatives: A silent step (the $X$ component), an input of a name $(X^N)$ over a channel $(N)$, the output of a free name over a channel (due to $N \times N \times X$) or the allocation and sending of a fresh name (the $N \times \delta(X)$-part). (p. 5)

This results in a “new fully abstract, sound and complete modal logic for the $\pi$-calculus”. For more details see Pi-Calculus in Logical Form.

Perhaps we can now start to glimpse connections between two pieces of work out of Carnegie-Mellon that we have commented on before. On the one hand, there’s the syntax-semantics duality of first-order theories due to Forssell. Here the dualising object is no longer $2$ but rather the category $Set$. Just as $2$ can be taken as equipped with many structures, so with $Set$.

For example, $Set$ is a category with finite products, and an object in the category, $\mathcal{F} \mathcal{P}$, of such categories with finite product preserving functors. But it is also a category with all limits and colimits, and an object in the category, $\mathcal{G}$, of such categories with functors which preserve limits, filtered colimits, and regular epimorphisms. This allows for the following duality, as Forssell explains,

• Models = $Hom_{\mathcal{F} \mathcal{P}} (Algebraic theory, Set)$
• Algebraic theory = $Hom_{\mathcal{G}} (Models, Set)$.

He goes on to show the duality between Boolean coherent categories (corresponding to first-order theories) and topological groupoids (corresponding to their models). We might hope then for modalities acting on the first-order syntax and semantics to be functors (maybe 2-functors) of a certain kind on these Boolean coherent categories.

We can think of the transition systems between models or worlds of propositional theories as telling us which members of a set of worlds are close to one another. For any ordered pair can we move from the first to the second – Yes or No? Now with first-order theories we’re working in a category of worlds and we want to know for any objects not just whether we can get from one to another, but how.

The trivial choice of transition system for a set is where $a R b$ if and only if $a = b$. This corresponds to the coalgebra $\a \mapsto \{a\}$. The equivalent for categories is, I would guess, the Yoneda embedding as a 2-coalgebra. Here an object relates to another via the arrows in the category itself. But presumably there must be other transition systems to work with.

The second piece of Carnegie-Mellon work may give us a clue as to how to proceed. It’s Awodey and Kishida’s sheaf semantics for first order modal logic. Here we model first-order modal logic by a sheaf over a space of worlds. A fibre contains the individuals living in the world indexed by a point in the base space.

So the question is: can these sheaf models for a first-order modal theory be seen as (2)-coalgebras for some endofunctor on the category of models of the nonmodal first-order theory?

The thrust of the coalgebraic approach to modal propositional logic is summarised as:

First, the coalgebraic model is flexible. That is, it can incorporate many different types of behaviour and interaction, e.g. location awareness, mobility and quantitative uncertainty, to name but a few. Second, the coalgebraic model is compositional: both on the logical and the semantical level it allows us to combine computational features and reason about their interaction. Third, the coalgebraic model is uniform, i.e. all computational aspects of the model share the same meta-theory. This in particular leads to software tools that are easier to design, to maintain and to implement. Finally, the coalgebraic model is compatible in the sense that it subsumes nearly all existing formal notions of state based system as special cases. (p. 10)

It would fun to extend this to first-order theories. There must be quite a space of logics out there.

Posted at September 7, 2009 12:25 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2053

### Re: Coalgebraic Modal Logic

When I was learning about monads, the monad for monoids was a particularly helpful example, as was seeing how $\mathbb{Z}_2$ is an algebra of the monad. So, can you walk us through an example of coalgebras? Like, is there such a thing as a comonoid? If so, can you show how a particular comonoid (is there such a thing as co-$\mathbb{Z}_2$?) arises as a coalgebra of the comonad for comonoids?

Posted by: Mike Stay on September 10, 2009 7:52 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

A comonoid is just like a monoid except backwards. A comonoid in the monoidal category $X$ is an object $C$ with a comultiplication

$\Delta: C \to C \otimes C$

and counit

$\epsilon : C \to I$

satisfying coassociativitiy and left/right counit laws. Or, more tersely: A comonoid in the monoidal category $X$ is a monoid in the monoidal category $X^{op}$.

However, comonoids in $Set$ are very dull, and it’s a great exercise to work out what they are.

Nobody tell Mike the answer! If he gets stuck, he can find it buried in an old $n$-Café article featuring similar puzzles.

Jim Dolan made me solve this puzzle, and it made me stronger, so I feel good about inflicting it on everyone else.

Anyway, this is why nobody cares about comonoids in $Set$ (or any other category with finite products). But comonoids in $Vect$ are great.

I think David and other people can give you piles of comonads with a computer science or logic flavor to them. The example he already mentioned is very nice. Suppose we have a poset, which is a simple sort of category. Let’s think of the elements of this poset as ‘propositions’, with the order relation as ‘implication’. Then any comonad on a poset can be thought of as saying ‘is necessarily true”. The definition of comonad simply says:

“if it’s necessarily true that $P$, then it’s necessarily true that it’s necessarily true that $P$

and

“if it’s necessarily true that $P$, then $P$.”

The first is the comultiplication, the second is the counit. They automatically satisfy all the equations they need to, since in a poset all possible equations between morphisms are true.

Dually, “is possibly true” is a monad. And so modal logic has a lot to do with both comonads and monads.

Posted by: John Baez on September 10, 2009 9:01 PM | Permalink | Reply to this

### Epistemic Logic; Re: Coalgebraic Modal Logic

This is another way in which Epistemic Logic differs from plain vanilla Modal Logic. Because if Agent-A knows that P is true, formally K_A(P) it does not follow (depending on which axioms you accept) that Agent-A knows that Agent-A knows that P, formally K_A(K_A(P)). Once you have public announcements to all agents, there is the disturbing situation in which one can be forced to stop knowing P when told P.

Balbiani et al wrote: “One motivation to formalize the dynamics of knowledge is to characterize how truth or knowledge conditions can be realized by new information. From that perspective, it seems unfortunate that in public announcement logic a true formula may become false because it is announced.

Posted by: Jonathan Vos Post on September 10, 2009 9:53 PM | Permalink | Reply to this

### Paradox of the Knower, vs Fitch’s Paradox of Knowability; Re: Epistemic Logic; Re: Coalgebraic Modal Logic

The above-mentioned “Paradox of the Knower” should not be confused with Fitch’s Paradox of Knowability
First published Mon Oct 7, 2002; substantive revision Wed Jul 1, 2009
.

Posted by: Jonathan Vos Post on September 10, 2009 9:59 PM | Permalink | Reply to this

### not know that one knows; Re: Epistemic Logic; Re: Coalgebraic Modal Logic

In the actual human brain, as opposed to the more abstract axiomatic theories, it is clear that one can know something but not know that one knows it.

Memories Exist Even When Forgotten, Study Suggests

Posted by: Jonathan Vos Post on September 10, 2009 10:38 PM | Permalink | Reply to this

### Re: Epistemic Logic; Re: Coalgebraic Modal Logic

One of my pet projects has been to investigate this epistemic knowledge problem in a multi-agent system. You are trying to find out how the public announcement changes the knowledge of different agents’. There are coalgebraic models corresponding to Kripke frames $M = (F,\pi)$ where $F$ is a set $W$ (of possible worlds’) with a family of equivalence relations on it and $\pi$ is an interpretation’ for the atoms of the language. The equivalence relations correspond to the ability or lack of it to distinguish the worlds apart.

The famous case of the Muddy Children’ gives a nice example of updating the model of the situation following a public announcement. The Kripke frame is usually represented by a graph with edges (coloured by the labels of the agents) corresponding to the equivalence relations (world $w$ and world $x$ are linked by an edge labelled $a$ if agent $a$ can not tell the situations / worlds $w$ and $x$ apart from $a$s available knowledge. Public announcements update the graph.

A very nice problem is to give an adequate (and convincing) description of that update process. (That the Kripke frame is a $n$-fold groupoid is a nice viewpoint that I always hoped would become useful but I do not know how to do it!)

The coalgebraic model here is a multiple one. There are as many cooperations as there are agents, so this is a more complex situation than David’s. It does give a nice semi-realistic use for Epistemic Modal Logics and Coalgebraic ideas.

There is a dual algebraic model using Boolean algebras with operators. I will describe that if someone is interested. (Perhaps the nLab needs some stuff on this!!!)

Posted by: Tim Porter on September 11, 2009 8:17 AM | Permalink | Reply to this

### Re: Epistemic Logic; Re: Coalgebraic Modal Logic

There are as many cooperations as there are agents, so this is a more complex situation than David’s.

It may be more complex than the example I gave, but coalgebra can easily cope with your situation. We just have

$F: X \to P(X)^A,$

or equivalently

$F: X \to P(X \times A),$

where $A$ is the set of agents.

This is just a labelled transition system, a kind of state transition system.

Posted by: David Corfield on September 11, 2009 12:51 PM | Permalink | Reply to this

### Re: Epistemic Logic; Re: Coalgebraic Modal Logic

Good point

Posted by: Tim Porter on September 11, 2009 1:29 PM | Permalink | Reply to this

### Re: Epistemic Logic; Re: Coalgebraic Modal Logic

I was unable to continue this yesterday, so let me give a bit more precision to my ideas. I was trying to describe a multiagent system and as David pointed out you can do that coalgebraically if the number of agents is fixed ($A$ is the set of agent labels).

I was discussing this with Bill Teahan in Bangor and he asked what would model the more realistic agent based systems where an agent may spawn’ a new agent who goes off to report back, seeking knowledge’ in the network (say where certain information resources are held, certain programs are available, say in grid computing models, and so on). The set of agents $A$ thus changes in time.

A similar situation occurs if the agents are sensors communicating measurements back about conditions, say, on the sea bed. Here an agent has limited broadcast power so can only communicate with nearby others. Conditions on the sea bed can be quite extreme, they can change so that sensors may become disabled and go out of action, so again the network changes in time. Can one build network structure into the logic, and can the logic change with change of structure in the network.

(This has distant links to questions TQFTs and AQFTS I think, with creation and destruction of states.)

If there are $n$ agents then the logic will be something like the $S5_n$ epistemic logic, and the relational models will be sets with $n$-equivalence relations on them. Now add in some new agents and eliminate others. How will the logic and its category of coalgebras react?

I got some basic results on this some years ago but could not refine my ideas enough so as to develop things further. Any thoughts???

Posted by: Tim Porter on September 12, 2009 7:59 AM | Permalink | Reply to this

### Re: Epistemic Logic; Re: Coalgebraic Modal Logic

This is more stuff to add to my list of things I wish I understood.

I know you’ve written a couple of papers on the subject and now multi-agents appear under this heading? Very very cool.

Posted by: Eric Forgy on September 12, 2009 3:30 PM | Permalink | Reply to this

### “Knowers” of finite number, countable knowledge; Re: Epistemic Logic; Re: Coalgebraic Modal Logic

For tractability to my limited Math powers, I also restricted the number of agents to a fixed value. Further assumptions, restrictions, are as summarized below. I do, as you indicated, use bisimulation and pointed Kripke model theory to prove to some results. But have I, with these restrictions, abstracted away what you feel needs to be n-categorified?

“The realization of knowledge (or truth) by new information can be seen as a specific form of what is called ‘knowability’ in philosophy.”

What do I mean, informally, by rational belief and knowledge in this context?
An agent can know (believe) these things:
(1) Axioms accepted by the agent;
(2) Theorems that the agent can prove from the axioms, under rules of deduction;
(3) Things announced by agents whom the given agent believes to always tell the truth;
(4) The negation of things announced by agents whom the given agent believes to always tell exactly the opposite of the truth (in a two-valued logic);
(5) Deductions made from announcements believed, or from those inverted by total skepticism of a pure liar.
(6) Things which the agent believed in the past, but now (in belief revision) retracted from belief and inverted, i.e. formerly believe to be true, now believe to be false;
(7) Things which the agent believed in the past, but now (in belief revision) retracted from belief and demoted, i.e. formerly believe to be true, now believe to be only possibly true;
(8) Deductions from revised beliefs.
An agent can NOT know these things:
(1) Since this is not a Paraconsistent logic, one cannot believe anything which one knows to be logically inconsistent or invalid, i.e. P and NOT P.
(2) Observations of the “real world.” The knower has no senses, and is not embedded in the real world, but in a “simulated” abstract logical world. We may later examine some traditional philosophical puzzles if we all a special agent, the Narrator, to announce to all other agents the circumstances of an abstract sensory world; or if there is an agent which represents the sensory knowledge of another agent, although this leads to both obvious problems of private versus public knowledge, and more subtle problem of sensory knowledge being incorrect, in the most extreme case, the radical doubt of Descartes;
(3) There are no explicitly irrational beliefs, hunches, feelings, as this is not a psychological model;
(4) The computational capability of agents is limited; there are no “oracles”, hence in this Post-Godelian world, an agent cannot know something which is provably undecidable. We defer discussion of whether one can believe something which is provably independent of the believed axioms.

Let me motivate this paper with the following definitions and examples, which will be made precise later. Assume a finite set of agents (people, creatures, computers, abstractly represented) A and a countably infinite set of logical atoms P (including those denotated Phi, Psi, and so forth).

We assume that the underlying Propositional Calculus is two-valued, that is, {True, False} as opposed to, say, {True, False, Unknown}, or [something with nice Lattice properties, Belknap] {None, True, False, Both}, as the unknown is handled instead by the truth value of a proposition which includes the Knowledge operator or its dual.

Posted by: Jonathan Vos Post on September 12, 2009 4:01 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

Set itself forms a monoidal category in two ways, one with the tensor product as the cartesian product and one with tensor product as the coproduct.

• A monoid object in $(Set, \times, 1)$ is a monoid.
• A monoid object in $(Set, +, 0)$ is
• a set $M$ equipped with
• a function $m:(M+M \cong \{0,1\} \times M) \to M$ and
• a function $e:0 \to M$ (there’s only one possibility, the trivial map) such that
• $m \circ (M+m) = m \circ (m+M)$, where

$\array{M+m:&3M &\to&2M\\&(t,x)&\mapsto&if (t=0) then x else m(t-1, x)}$

and similarly for $m+M;$
• $m \circ (M+e) = m \circ (e+M) = M$, where

$\array{M+e:&M&\to&2M\\&x&\mapsto&(0,x)}$

and

$\array{e+M:&M&\to&2M\\&x&\mapsto&(1,x).}$

This last condition means says that for all $x,$ $m(0,x) = m(1,x) = x,$ which means that $m$ must be the projection onto $M.$ So a monoid in $(Set, +, 0)$ is “just” a set, since we don’t get anything new.

$Set^{op}$ is a monoidal category in two ways as well. The cartesian product in $Set^{op}$ is disjoint union of sets, so

• A monoid object in $(Set^{op}, +, 0)$ is the empty set, because an arrow $e:0 \to M$ is a function $e:M \to 0,$ which doesn’t exist unless $M$ is empty.

The coproduct in $Set^{op}$ is the cartesian product in $Set$, so

• A monoid object in $(Set^{op}, \times, 1)$ is
• a set $M$ equipped with
• an arrow $m:M \times M \to M$, i.e. a function $m:M \to M \times M$ and
• an arrow $e:1 \to M$, i.e. a function $e:M \to 1$ such that
• $(M \times m) \circ m = (m \times M) \circ m$ (where these are thought of as functions)
• $(M \times e) \circ m = (e \times M) \circ m = M$
which look like the rules for duplication and deletion (of course). But I’d still like a bunch of examples to generalize from.
Posted by: Mike Stay on September 11, 2009 5:05 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

A monoid object in (Set op,+,0) is the empty set, because an arrow e:0→M is a function e:M→0, which doesn’t exist unless M is empty.

Yes, but a comultiplication map with the coassociativity condition alone might actually be worth looking at: it encodes something like binary repeatable measurement!

Posted by: Tobias Fritz on September 11, 2009 9:57 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

A monoid object in $(Set^op,\times,1)$

This is what I would call a ‘comonoid in $Set$’; that is, give $Set$ its usual monoidal structure, take the opposite of that monoidal category, then take a monoid in that.

All of your other answers were correct, but you didn't complete this one! It can be simplified further, and that's the interesting thing.

Posted by: Toby Bartels on September 11, 2009 6:23 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

A monoid object in $(Set^{op},\times ,1)$ is

• a set $M$ equipped with
• an arrow $m:M\times M\to M,$ i.e. a function $m:M\to M\times M$ and
• an arrow $e:1\to M$, i.e. a function $e:M\to 1$ such that
• $(M\times m)\circ m=(m\times M)\circ m$
• $(M\times e)\circ m=(e\times M)\circ m=M$

Now the only thing $e$ can be is deletion, the unique morphism into 1. The last equation says that after applying $m,$ deleting either component leaves what we started with, so $m$ has to be duplication. Thus $M$ is “just” a set here, too.

Posted by: Mike Stay on September 14, 2009 5:21 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

Right! And this argument works in any cartesian monoidal category.

On the other hand, comonoids in noncartesian monoidal categories can be more interesting. In theory, the study of comonoids in monoidal categories is equivalent to the study of monoids in monoidal categories, since the opposite of a monoidal category is just another monoidal category. But in practice, we tend to concentrate on specific categories, and a comonoid in $C$ is usually very different from a monoid in $C$.

Everyone knows that a monoid in $Ab$ is a (unital) ring, but what is a comonoid in $Ab$? It's not a familiar concept to most people!

Posted by: Toby Bartels on September 14, 2009 9:50 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

When you say “Ab”, which monoidal product do you mean?

Posted by: Mike Stay on September 15, 2009 12:21 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

When you say “Ab”, which monoidal product do you mean?

I mean the usual closed monoidal tensor product, the one such that a monoid object is a ring.

Note that it's not offered as a puzzle to ask you what is a comonoid object in $Ab$; you can describe it in more lowbrow language, of course, but you're not going to be able to say ‘Ah, that's just a […]’, because it really is something new.

Posted by: Toby Bartels on September 16, 2009 12:57 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

We never did hear the answer to Toby’s puzzle. If a comonoid object in $Ab$ is the same as a monoid object in $Ab^{op}$, and if $Ab^{op}$ is equivalent to the category of compact Hausdorff abelian topological groups, might we expect the answer to be

Compact Hausdorff topological (unital) ring?

Posted by: David Corfield on September 25, 2009 11:11 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

Or perhaps I should say

Dual of a compact Hausdorff topological (unital) ring.

And then I should tell you what kind of abelian group that is.

Posted by: David Corfield on September 25, 2009 2:38 PM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

Remember that just as not all endofunctors are monads nor are they all comonads. All we need for coalgebra/algebra in this sense is an endofunctor. So we might take $F(X) = 1 + X^2$ for $Set$. An algebra for this functor is merely a set $X$ equipped with a map $f: 1 + X^2 \to X$, or in other words a set with a named element and a binary operation. There are no equations. Your typical algebraic structures like monoid require you to add in equations for binary operation with named element, etc.

Coalgebras have a different flavour. Now we want a map $g: X \to 1 + X^2$. We can think of this as a partially defined map which on an element of $X$ either is undefined or else sends back two elements of $X$. A nice example of one of these sets is the set of binary trees. Either we have an empty tree or else there is a root with two (possibly empty) trees adjoined.

You can say that the algebraic way involves constructors, in the example, a term for the named element, and for every pair of elements a new element formed by the binary operation. Initial algebras are constructed using just this, modulo equations.

Coalgebras involve destructors. I give you a binary tree, you rip out the root and hand me back the left and right sub tree. Final/terminal coalgebras are often infinite - they need to capture all possible ways you destroy things of that kind. E.g., in the running example, you may go on ripping out and splitting trees forever, so the final algebra is the set of not necessarily finite binary trees.

Other functors give different flavours of coalgebra. A coalgebra for the power set functor is just a relation.

Posted by: David Corfield on September 11, 2009 8:54 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

If one thinks of a comonoid as a cogroupoid with one (co)object, it there as sense in which this generalises the old adage of Ronnie Brown about `subdivision as the inverse of composition’ (or something like that).

And perhaps a silly question: Are there logical versions of Hopf algebra type situations? I mean not based on vector spaces, so one gets a set of decompositions or destruction of an object not some sum of such things. More combinatorial / perhaps species based examples.

Posted by: Tim Porter on September 11, 2009 9:35 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

There are some notes by Alex Kurz (Leicester):

here

which gives a fairly non-categorical introduction to some of this stuff.

Posted by: Tim Porter on September 11, 2009 9:58 AM | Permalink | Reply to this

### Re: Coalgebraic Modal Logic

All we need for coalgebra/algebra in this sense is an endofunctor.

So we’re not necessarily looking only at coalgebras of a comonad, but rather coalgebras of an arbitrary endofunctor $T:C \to C$, which is just an object $X$ of $C$ and a morphism $h:X \to TX$. Is that right?

Coalgebras involve destructors. I give you a binary tree, you rip out the root and hand me back the left and right sub tree. Final/terminal coalgebras are often infinite - they need to capture all possible ways you destroy things of that kind. E.g., in the running example, you may go on ripping out and splitting trees forever, so the final algebra is the set of not necessarily finite binary trees.

Oh! I think I’ve seen something like this before, that data structures are dual to control flow. A bit is dual to if/then/else, and more generally a sum is dual to a switch/case statement. A pair is dual to doing two independent things; it’s not clear to me whether they can be done sequentially or not.

Posted by: Mike Stay on September 11, 2009 7:06 PM | Permalink | Reply to this

### Destructors kill Graph Reconstruction; Re: Coalgebraic Modal Logic

Correct me if I’m wrong, but isn’t part of the point of destructors a kind of irreversibility for infinite trees?

I first encountered this from discussions with Herbert J. Ryser circa 1969.

The Harary “graph reconstruction conjecture” breaks down for infinite forests as follows.

Let A be a countably infinite tree with every node having a countably infinite number of descendants. Let B be a countably infinite set of copies of A.

Now, if I rip away the roots in each case, I get the same thing, and can no longer reconstruct what I was given from the set of subtrees I was handed.

Things get stranger if I leave countability behind, of course.

Posted by: Jonathan Vos Post on September 12, 2009 4:14 PM | Permalink | Reply to this

### Re: Destructors kill Graph Reconstruction; Re: Coalgebraic Modal Logic

Correct me if I’m wrong, but isn’t part of the point of destructors a kind of irreversibility for infinite trees?

If you've really got a coinductive object, then its destructor will be invertible. In contrast, if you've merely got some coalgebra of an endofunctor, one which might not be final, then you cannot expect it to be invertible, although it might be.

It's a fun exercise for the categorially minded to prove that a final coalgebra of a functor $F$, that is a terminal object of the category of objects $A$ equipped with morphisms $A \to F(A)$ (all within a given ambient category), must be invertible, that is its morphism $A \to F(A)$ must be an isomorphism. (The dual theorem holds for initial algebras.)

In David's example with binary trees, $A$ is the set of binary trees, $F$ maps $X$ to $1 + X^2$, and the map $A \to F(A)$ really is invertible. This alone does not prove that $A$ is the final coalgebra of $F$, but it is. In your example, $A$ is a set of forests, $F$ seems to be the identity (since $F(A)$ is also a set of forests), and the map $A \to F(A)$ is not invertible. This tells us that $A$ cannot be the final coalgebra of $F$, although it is a coalgebra. (The actual final coalgebra of the identity is the singleton set, assuming that we're working in the category of sets.)

Posted by: Toby Bartels on September 12, 2009 5:41 PM | Permalink | Reply to this
Read the post The Arrow of Time in Cat
Weblog: The n-Category Café
Excerpt: Does the same broken symmetry that affects Set affect Cat?
Tracked: November 3, 2009 10:28 AM
Read the post Category Theoretic Modal Logic
Weblog: The n-Category Café
Excerpt: Category theoretic ideas on modal logic
Tracked: April 4, 2011 5:09 PM

Post a New Comment