Can anyone help me with the following final coalgebra questions 1. Let X be a fixed Set. What is the final coalgebra of the functor [X,_]:Set -> Set. If you wish to make X finite then that's fine by me. 2. Consider the functor [[_,2],2]:Set -> Set. This functor doesnt have a final coalgebra for cardinality reasons. However one may define a finitary variant of this functor as follows: First let TX = [[X,2],2] if X is finitely presentable. Thus T:Set_fp -> Set is a functor from the full subcategory of fintely presentable objects of Set into Set. Next define T' to be the left Kan extension of T along the inclusion Set_fp -> Set. In other words T'X is the filtered colimit of all the TX_0 where X_0 is a finitely presentable subobject of X Now, T' is clearly finitary and from general nonsense we know that it has a final coalgebra. But what is it concretely? Thanks for any help you can offer Neil 17-Jan-2002 09:04:05 -0400,2670;000000000001-00000000
On Thu, 17 Jan 2002, N Ghani wrote:
Can anyone help me with the following final coalgebra questions
1. Let X be a fixed Set. What is the final coalgebra of the functor [X,_]:Set -> Set. If you wish to make X finite then that's fine by me.
For any functor T on any category with an initial object 0, T0 = 0 implies that 0 is the initial T-algebra. In this case, [X,1] = 1 implies that 1 is the final coalgebra. Not very interesting.
2. Consider the functor [[_,2],2]:Set -> Set. This functor doesnt have a final coalgebra for cardinality reasons. However one may define a finitary variant of this functor as follows:
First let TX = [[X,2],2] if X is finitely presentable. Thus T:Set_fp -> Set is a functor from the full subcategory of fintely presentable objects of Set into Set. Next define T' to be the left Kan extension of T along the inclusion Set_fp -> Set. In other words T'X is the filtered colimit of all the TX_0 where X_0 is a finitely presentable subobject of X
Now, T' is clearly finitary and from general nonsense we know that it has a final coalgebra. But what is it concretely?
Unless I am missing something, a finitely presented (or finitely generated) set is just finite. Now the functor 2^{2^-} is the free complete atomic boolean algebra triple (or rather the functor part thereof). The best way to see this is that 2^- is adjoint to itself on the right and tripleable so that the category of algebras is Set^op. The same argument for finite sets gives free boolean algebras and the colimit extension to all sets gives the same since the theory is finitary. The functor T' produces finite sets of finite subsets. Although not related to Neil's question, it is interesting to point out that the duality between finite sets and finite boolean algebras extends to a duality between the limit completion of one and the colimit completion of the other. Applied in one way this gives Stone duality between boolean algebras and profinite sets (i.e. Stone spaces) and the other way gives the duality between sets and profinite boolean algebras, which is complete atomic boolean algebras.
Thanks for any help you can offer
Neil
18-Jan-2002 08:31:49 -0400,1382;000000000001-00000000
Hi, 1. That's pretty easy. Since [X,_] maps the one-element (final) set onto itself, i.e., it preserves the final object, the final coalgebra of this functor is nothing but the one-element-set itself. Of course one need not use this abstract argument ("the forgetful functor U:Set_F --> Set creates any limit which the functor F:Set->Set preserves") but can give a direct proof. 2. That's much more complicated. I do not know any elementary description. For one possible description as a quotient of an automaton you may refer to H. Peter Gumm, Tobias Schroeder : Coalgebras of bounded type. Mathematical Structures in Computer Science, to appear which you can find Peter Gumm's homepage (http://www.mathematik.uni-marburg.de/~gumm/Papers/publ.html) and the papers quoted there. ... If somebody could offer a really nice description of that final coalgebra this would be quite interesting I assume. Hope that helps a bit Tobias Schroeder -----Original Message----- From: N Ghani To: categories@mta.ca Cc: coalgebras@iti.cs.tu-bs.de Sent: 17.01.02 12:23 Subject: coalgebras: Final Coalgebra Question Can anyone help me with the following final coalgebra questions 1. Let X be a fixed Set. What is the final coalgebra of the functor [X,_]:Set -> Set. If you wish to make X finite then that's fine by me. 2. Consider the functor [[_,2],2]:Set -> Set. This functor doesnt have a final coalgebra for cardinality reasons. However one may define a finitary variant of this functor as follows: First let TX = [[X,2],2] if X is finitely presentable. Thus T:Set_fp -> Set is a functor from the full subcategory of fintely presentable objects of Set into Set. Next define T' to be the left Kan extension of T along the inclusion Set_fp -> Set. In other words T'X is the filtered colimit of all the TX_0 where X_0 is a finitely presentable subobject of X Now, T' is clearly finitary and from general nonsense we know that it has a final coalgebra. But what is it concretely? Thanks for any help you can offer Neil 18-Jan-2002 08:31:46 -0400,3073;000000000001-00000000
1. Let X be a fixed Set. What is the final coalgebra of the functor [X,_]:Set -> Set. If you wish to make X finite then that's fine by me.
you mean exponentiation? why isn't 1 --->[X,1] final?
2. Consider the functor [[_,2],2]:Set -> Set. This functor doesnt have a final coalgebra for cardinality reasons. However one may define a
[snip]
Now, T' is clearly finitary and from general nonsense we know that it has a final coalgebra. But what is it concretely?
depends on how we represent the final coalgebra for the finite powerset functor [-,2]_fin. if you like to view its elements as finitely branching apgs, then the final coalgebra for [[-,2],2]_fin presumably consists of *bipartite* finitely branching apgs: the root is blue, its successors are red, the successors of successors are blue again, and so on. (given a coalgebra X-->[[X,2],2], write Y = [X,2]. this is the set of the red nodes of this apg; X is the set of the blue nodes. each of the red nodes the char function of its blue successors. and the structure map X-->[Y,2] tells the red successors of each blue node. so each elt of X induces, as its trace through the coalgebra, a bipartite apg with a blue root. this gives the final coalgebra homomorphism from X to the blue-rooted bipartite apgs. unless i am wrong.) -- dusko 18-Jan-2002 08:34:03 -0400,897;000000000000-00000000
participants (4)
-
Dusko Pavlovic -
Michael Barr -
N Ghani -
Tobias.Schroeder@sdm.de