i am a bit surprised with tom's line of reasoning: "it's not topology, so it shouldn't be mentioned"
I don't know what I wrote suggesting that I think that; I don't. In two of the papers advertised (first paragraph of the first paper and bottom of p.3 of the second), I listed some other types of self-similarity that I'd like to investigate. Let me expand on the possibilities. 1, 2. Set-theoretic and topological: these are the types of self-similarity that I understand by far the best at present. 3. Type-theoretic: recursive datatypes can be understood as self-similar objects, the best-known example being trees (which can be characterized as a final coalgebra). For instance, given a polynomial p(x) in N[x], you can consider solutions to x = p(x) (in rings, rigs, distributive categories, and rig categories): see the work of Robbie Gates, Peter Hines (TAC vol 6), Marcelo Fiore and I, and probably many others. 4. Conformal/analytic: this is the natural setting for discussing the self-similarity of Julia sets of complex rational functions. 5. Metric: e.g. the Koch snowflake is topologically just a circle, but has interesting metric self-similarity. 6. Measure-theoretic: cf. some of Peter's postings of 1999-2000 concerning integration. 7. Order-theoretic: both Peter's and Dusko's/Vaughan's characterizations of a real interval produce its ordering. (I have some idea of how to handle order in the much more general situation discussed in my papers, but it's early days.) 8. Categorical: e.g. the category of strict omega-categories is the terminal coalgebra for the endofunctor of CAT defined by V |--> V-Cat. (This was an idea of Carlos Simpson.) The same goes for globular sets (omega-graphs), changing V-Cat to V-Graph. 9. Statistical: there are so-called random fractals - e.g. take a black square; divide it into a 3x3 grid and white out each of the 9 subsquares with probability p; do the same to each black subsquare; continue ad infinitum. 10. Algebraic: the Thompson groups are in some sense highly self-similar. (These groups may be best known to readers of this list from Freyd and Heller's work on homotopy idempotents, but are also very tree-y in nature.) Here's a question belonging to (10), to which I don't know the answer. Let C be the category whose objects are triples (V, v_0, v_1) where V is a vector space and v_0 and v_1 are linearly independent vectors in V, and whose maps preserve linear structure and the `basepoints'. There's a `wedge' functor C x C --> C defined by (V, v_0, v_1) wedge (W, w_0, w_1) = ( (V + W)/~, v_0, w_1) where (V + W)/~ is the direct sum with v_1 identified with w_0. (So dim(V wedge W) = dim V + dim W - 1.) There's then an endofunctor G of C given by self-wedging. Question: what, if any, is the terminal G-coalgebra? (I suspect the answer is something to do with measure/integration - again see Peter's previous postings - but really have no idea.) Finally, re citations: I'll stick in a Pavlovic-Pratt reference, as suggested. All the best, Tom 26-Nov-2004 13:34:46 -0400,1447;000000000000-00000000
There is one important aspect of self-similarity, at least as it is understood in the context of:
4. Conformal/analytic: this is the natural setting for discussing the self-similarity of Julia sets of complex rational functions.
3. Type-theoretic: recursive datatypes can be understood as self-similar objects, the best-known example being trees (which can be characterized as a final coalgebra).
that seems to have been 'lost', or at least been made obscure enough that I could not see it anymore. The reason that proving self-similarity of some (conformal/analytic) fractals is quite difficult is because the definitions of self-similarity used always insist on 'bounded distortion', in other words you are allowed to diform the whole before re-injecting it as a part, but the distortion has to be bounded. For iterated function systems, since all the transformations are linear, this is trivial to show. But for Julia sets, since the 'natural' self-similarity involves non-linear transformations, proving bounded distortion is much more difficult. The 'puzzle pieces' of Yoccoz were invented explicitly to provide a tool for showing bounded distortion. One can show that most Julia sets are self-similar away for the orbits of critical points; for critical points embedded in the Julia set, there are known dynamical conditions which imply bounded-distortion, and then self-similarity. But there are definitely still some open cases. For some settings, like this bounded distortion is obvious, since there is *no* distortion at all. Did I just 'miss' some condition that would insure bounded distortion? [I admit to have only read Leinster's 'overview' paper, the other 2 papers are on my to-read-late pile]. Jacques 26-Nov-2004 19:47:23 -0400,1336;000000000001-00000000
doesnt the 0-dim vector space carry the final (terminal) coalgebra? (it has just one vector, so there is not much choice for v_0 and v_1.) -- dusko Tom Leinster wrote:
Here's a question belonging to (10), to which I don't know the answer. Let C be the category whose objects are triples (V, v_0, v_1) where V is a vector space and v_0 and v_1 are linearly independent vectors in V, and whose maps preserve linear structure and the `basepoints'. There's a `wedge' functor C x C --> C defined by
(V, v_0, v_1) wedge (W, w_0, w_1) = ( (V + W)/~, v_0, w_1)
where (V + W)/~ is the direct sum with v_1 identified with w_0. (So dim(V wedge W) = dim V + dim W - 1.) There's then an endofunctor G of C given by self-wedging. Question: what, if any, is the terminal G-coalgebra?
(I suspect the answer is something to do with measure/integration - again see Peter's previous postings - but really have no idea.)
Finally, re citations: I'll stick in a Pavlovic-Pratt reference, as suggested.
All the best, Tom
30-Nov-2004 08:04:37 -0400,3767;000000000000-00000000
Dusko Pavlovic wrote:
doesnt the 0-dim vector space carry the final (terminal) coalgebra? (it has just one vector, so there is not much choice for v_0 and v_1.)
Nope - v_0 and v_1 have to be linearly independent. (This is like the condition in Peter's result that the two distinguished points of the set be distinct, without which the result degenerates; and as in Peter's result, it can be regarded as a kind of flatness condition.) Incidentally, I was probably wrong to suspect that the answer is something to do with measure, as the question is posed over an arbitrary field. I now suspect that there's a similar question whose answer has to do with measure, but I won't attempt any further speculation here. Tom
Here's a question belonging to (10), to which I don't know the answer. Let C be the category whose objects are triples (V, v_0, v_1) where V is a vector space and v_0 and v_1 are linearly independent vectors in V, and whose maps preserve linear structure and the `basepoints'. There's a `wedge' functor C x C --> C defined by
(V, v_0, v_1) wedge (W, w_0, w_1) = ( (V + W)/~, v_0, w_1)
where (V + W)/~ is the direct sum with v_1 identified with w_0. (So dim(V wedge W) = dim V + dim W - 1.) There's then an endofunctor G of C given by self-wedging. Question: what, if any, is the terminal G-coalgebra?
(I suspect the answer is something to do with measure/integration - again see Peter's previous postings - but really have no idea.)
30-Nov-2004 08:03:55 -0400,1980;000000000000-00000000
oh. so then your objects are actually free algebras for the monad that adds two new vectors to a space... does this lead anywhere? let the objects of *V* be sets (of base vectors). a morphism from A to B is a linear operator from R^A to R^B (an AxB-"matrix"). the monad *V*--->*V* maps A |--> A+2, where 2 = {0,1}. it extends the linear operators so that the adjoined constants are preserved. let *K* be the kleisli category for (-)+2. the wedge functor V : *K* x *K* ---> *K* maps <A,B> |---> A + {m} + B. given two *K*-arrows, ie linear operators A--f--> 0+B+1 and C--g-->0+D+1, we need to define A+m+C ---fVg---> 0+B+m+D+1. conjoin the A -->1 minor of f and the C-->0 minor of g to get the m-component ("column") of f V g. now what might be the final coalgebra of WX = XVX? if all of the above happens over the category *S* of sets and functions, instead of *V* of sets and linear operators --- then the final coalgebra is (0,1). remember that this is just the generators, so when you really make the final coalgebra by adding 2, you get [0,1]. so this is just the freyd construction. the coalgebraic structure takes each number to one of its binary representations. when we work over *V*, and someone gives me a coalgebra X ---> WX in *K*, ie a linear operator X -----> 0+X+m+X+1, this coalgebra structure unfolds each x from X into a tree of real numbers. there are exactly 2|X|+3 branches coming out of each node that is not a leaf; 3 out of those are leaves, and each of the remaining 2|X| nodes has 2|X|+3 branches coming out of it. the final coalgebra Z -----> WZ would have to consist of such trees as well, of width 2|Z|+3. each tree induced by x from X would have to correspond to a unique Z-tuple of real numbers. hmm. it seems clear that Z must be wider than any X. but size is a bad reason for something not to exist. what if we have two universes? can we span all 2|X|+3-trees by the vectors from some base Z? g'night, -- dusko Tom Leinster wrote:
Dusko Pavlovic wrote:
doesnt the 0-dim vector space carry the final (terminal) coalgebra? (it has just one vector, so there is not much choice for v_0 and v_1.)
Nope - v_0 and v_1 have to be linearly independent. (This is like the condition in Peter's result that the two distinguished points of the set be distinct, without which the result degenerates; and as in Peter's result, it can be regarded as a kind of flatness condition.)
Incidentally, I was probably wrong to suspect that the answer is something to do with measure, as the question is posed over an arbitrary field. I now suspect that there's a similar question whose answer has to do with measure, but I won't attempt any further speculation here.
Tom
Here's a question belonging to (10), to which I don't know the answer. Let C be the category whose objects are triples (V, v_0, v_1) where V is a vector space and v_0 and v_1 are linearly independent vectors in V, and whose maps preserve linear structure and the `basepoints'. There's a `wedge' functor C x C --> C defined by
(V, v_0, v_1) wedge (W, w_0, w_1) = ( (V + W)/~, v_0, w_1)
where (V + W)/~ is the direct sum with v_1 identified with w_0. (So dim(V wedge W) = dim V + dim W - 1.) There's then an endofunctor G of C given by self-wedging. Question: what, if any, is the terminal G-coalgebra?
(I suspect the answer is something to do with measure/integration - again see Peter's previous postings - but really have no idea.)
participants (4)
-
Dusko Pavlovic -
Jacques Carette -
Tom Leinster -
Tom Leinster