User aleks kissinger - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:23:14Z http://mathoverflow.net/feeds/user/800 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76217/understanding-penrose-diagrammatical-notation/127755#127755 Answer by Aleks Kissinger for Understanding Penrose diagrammatical notation Aleks Kissinger 2013-04-16T21:01:39Z 2013-04-16T21:01:39Z <p>To the best of my knowledge, no abstract formulation and soundness theorem of the full Penrose notation (with symmetriser, antisymmetriser, covariant derivative, etc) exists. There is, however, a veritable zoo of graphical languages for various kinds of monoidal categories (with a regrettably small subset of them having published soundess/completeness proofs). The best place to start is Selinger's survey paper from 2011:</p> <p><a href="http://www.mathstat.dal.ca/~selinger/papers.html#graphical" rel="nofollow">http://www.mathstat.dal.ca/~selinger/papers.html#graphical</a></p> http://mathoverflow.net/questions/35612/computing-colimits-in-a-lawvere-theory Computing colimits in a Lawvere theory Aleks Kissinger 2010-08-15T00:23:22Z 2012-09-20T13:27:58Z <p>Let Prod(C, D) be the set of finite-product preserving functors from C to D. Is it true that for any Lawvere theory L, Prod(L, Set) has small colimits? This seems to be the case, as it is invoked here:</p> <p><a href="http://ncatlab.org/nlab/show/database+of+categories" rel="nofollow">http://ncatlab.org/nlab/show/database+of+categories</a></p> <p>Where do this colimits come from? In the case of sifted colimits, pointwise calculation works, as sifted colimits commute with finite products in Set. However, it doesn't seem at all obvious that an arbitrary colimit of product-preserving functors would also be product-preserving.</p> <p>Does anyone know of a reference or proof that such colimits exist, or even better, how to go about computing them?</p> http://mathoverflow.net/questions/3557/where-are-some-interesting-places-where-the-axiom-of-choice-crops-up-in-category Where are some interesting places where the axiom of choice crops up in category theory? Aleks Kissinger 2009-10-31T16:18:16Z 2012-08-27T23:54:29Z <p>The two that come to mind are splitting epics in Set and taking the Skel of a category. Surely there are lots of other interesting (and maybe upsetting) places where this comes up.</p> http://mathoverflow.net/questions/34414/categories-whose-objects-are-cw-complexes Categories whose objects are CW-complexes Aleks Kissinger 2010-08-03T17:02:14Z 2011-12-16T18:21:29Z <p>For a category whose objects are CW-complexes (with a chosen cell structure), what is the most natural notion of morphism? Are there choices, and if so, what are the pros and cons?</p> <p>Types of maps that immediate come to mind would be continuous maps where the direct image a cell in X is a cell Y, or where the inverse image of a cell in Y is a cell in X. There are probably lots of elegant ways to get to maps like this, perhaps involving conditions on chain maps. It seems such an obvious thing to do that surely there are good references on this.</p> http://mathoverflow.net/questions/38863/re-seating-a-monad Re-seating a monad Aleks Kissinger 2010-09-15T19:52:56Z 2011-12-02T18:20:55Z <p>Let $\mathcal C$ and $\mathcal D$ be categories with suitable limits and colimits for the following discussion. Is it possible to re-interpret, or "re-seat" a monad $T : \mathcal C \to \mathcal C$ as a monad over $\mathcal D$? When $T$ is finitary, I know at least one way to do this. Compute the Kleisli category $\mathcal C_T$ and consider $(\mathcal C_T)^{op}$ as a Lawvere theory. Then models of $(\mathcal C_T)^{op}$ on $\mathcal C$ are the same as $T$-algebras. If we then consider models of $(\mathcal C_T)^{op}$ on $\mathcal D$, we have a canonical, monadic forgetful functor $[(\mathcal C_T)^{op},\mathcal D] \to \mathcal D$ from which we can build a new finitary monad $T' : \mathcal D \to \mathcal D$. My question is as follows.</p> <blockquote> <p>Is there an direct way to obtain $T'$ from $T$ (i.e. that doesn't go via the Lawvere theory)? If so, can it be extended to work for arbitrary monads?</p> </blockquote> http://mathoverflow.net/questions/59892/co-ends-as-a-trace-operation-on-profunctors Co-ends as a trace operation on profunctors Aleks Kissinger 2011-03-28T20:25:36Z 2011-06-27T23:32:03Z <p>The n-lab site on profunctors (http://ncatlab.org/nlab/show/profunctor) describes profunctor composition as using a co-end to "trace out" the connecting variable:</p> <p>$F\circ G := \int^{d\in D} F(-, d) \times G(d, -)$</p> <p>Naturally, one could picture for more general profunctors, $\psi : A \times B^{op} \times C \times D \rightarrow Set$, $\phi : B \times E^{op} \rightarrow Set$ a more generalised composition as co-end'ing together an input from one with an output from the other:</p> <p>$\xi := \int^{b \in B} \psi(-,b,-,-) \times \phi(b,-)$</p> <p>This then looks a lot like contraction of tensors:</p> <p>$\xi_{e}^{a,c,d} := \sum_{b\in B} \left( \psi_{b}^{a,c,d} \phi_{e}^{b} \right)$</p> <p>Even in the use of the language "trace out" (and the fact that both operations form abstract trace operations $Tr(-)$ in their respective traced monoidal categories), this analogy seems to be implied. This also seems to be a useful way to think about profunctor composition, and it appears quite feasible that tensor contraction could be described as a co-end of suitably-enriched profunctors. However, it doesn't seem obvious how to go about unifying these two operations. So, my question is:</p> <blockquote> <p>To what extent can the analogy between tensor contraction and profunctor composition be made precise?</p> </blockquote> http://mathoverflow.net/questions/63631/algebras-with-a-degenerate-trace-form Algebras with a degenerate trace form Aleks Kissinger 2011-05-01T18:58:11Z 2011-05-02T09:44:11Z <p>Let the bilinear trace form of a finite-dimensional associative algebra be defined as:</p> <p>$(u,v) \mapsto Tr(L_u L_v)$</p> <p>For $L_u$ the linear map given by multiplication on the left by $u$. In the literature, there seem to be good characterizations of algebras where this form is non-degenerate (semi-simple, special Frobenius), but what about the other extreme?</p> <blockquote> <p>Is there a characterization for an associative algebra $A$ whose bilinear trace form, considered as a linear map $V \to V^*$ is rank 1?</p> </blockquote> <p>In particular, when $A$ is unital and commutative, there seems to be only one possibility for the trace form, if its rank 1:</p> <p>$(u,v)\mapsto \frac{1}{dimV} Tr(L_u)Tr(L_v)$</p> <p>This seems like quite the coincidence. Could anyone shed some light on this?</p> http://mathoverflow.net/questions/51952/rig-of-fractions-including-zero-denominators Rig of fractions, including zero denominators Aleks Kissinger 2011-01-13T13:21:03Z 2011-01-13T22:16:50Z <p>For some integral domain $R$, one forms the field of fractions <code>$R^*$</code> by considering (equivalence classes of) formal pairs {$r/s : r \in R, s\in R\backslash 0$} and defining $+$ and $*$ as you'd expect for fractions.</p> <p>What happens when you replace $R\backslash 0$ with $R$? Clearly you don't get a field, or even a ring. The result would be a commutative rig that looks a lot like <code>$R^*$</code>, except you also have a sort of "infinity" element $1/0$ and a sort of "undefined" element $0/0$, neither of which have multiplicative <em>or additive</em> inverses.</p> <p>This type of structure seems to arise quite naturally when considering algebras over 1D projective space. So, my questions are</p> <blockquote> <p>Is this construction well studied, or at least have an accepted name? If so, where is a good starting place w.r.t. relevant literature or results?</p> </blockquote> http://mathoverflow.net/questions/38005/are-sieves-in-locally-small-categories-still-sets Are sieves in locally small categories still sets? Aleks Kissinger 2010-09-07T20:38:37Z 2010-09-07T20:38:37Z <p>In "Sheaves in Geometry and Logic", M&amp;M define a sieve of an object $C$ as a downward-closed set of arrows $S$ with codomain $C$. They go on to say that for a locally small category, a sieve of $C$ is the same thing as a subfunctor of $\hom(-,C)$, under the rule</p> <p><code>$S = \{\, f : \exists A . f \in Q(A) \}$</code></p> <p>Is this always a set for a locally small category? It doesn't seem to be, taking for instance $Q = \hom(-,1)$. Then $S \cong \textrm{ob}(\mathcal C)$, which would imply that $\mathcal C$ is small. Is there something subtle going on here?</p> http://mathoverflow.net/questions/36199/in-what-cases-does-a-yoneda-like-embedding-preserve-monoidal-structure In what cases does a Yoneda-like embedding preserve monoidal structure? Aleks Kissinger 2010-08-20T15:48:20Z 2010-08-20T16:49:29Z <p>What kinds of Yoneda-like situations induce an embedding that preserves the tensor product for some arbitrary monoidal category?</p> <p>The cases where the monoidal product is given by a limit or colimit give this immediately for the usual Yoneda embedding, but this breaks down for "real" monoidal categories like $(Vect, \otimes)$.</p> <p>Are there $V$-enriched cases where the generalised embedding</p> <p>$$Y : C \to V^{C^{op}}$$</p> <p>does preserve the tensor product for interesting monoidal categories $C$?</p> http://mathoverflow.net/questions/35784/profunctors-corresponding-to-partial-functors Profunctors corresponding to "partial functors" Aleks Kissinger 2010-08-16T18:36:40Z 2010-08-18T14:01:28Z <p>Suppose we have a span of categories $C \overset{F}{\hookleftarrow} D \overset{G}{\rightarrow} E$, where $F$ is a subcategory embedding. We can lift these normal functors to profunctors $\hat F$ and $\hat G$ and compose the "formal" adjoint $\hat F^\dagger$ with $\hat G$ to obtain a profunctor $\hat G \hat F^\dagger : C \nrightarrow E$. To what extent could one think of this as a partial functor, and what nice behaviours could it inherit from $F$ and $G$? For instance, if $F$ reflects products and $G$ preserves them, does $\hat G \hat F^\dagger$ preserve them where ever it is defined?</p> http://mathoverflow.net/questions/35731/conditions-for-natural-transformations-to-exist/35761#35761 Answer by Aleks Kissinger for conditions for natural transformations to exist? Aleks Kissinger 2010-08-16T13:31:55Z 2010-08-16T13:31:55Z <p>In general, there are probably no conditions for the existence of natural transformations that are simpler than just using the definition of naturality itself. In a category Z with a zero object, the zero natural transformation between functors $F,G : C \rightarrow Z$ always exists, but this is quite a degenerate example.</p> <p>Often, you can arrive at an intuition as to whether a natural transformation exists if you consider what such a thing would mean in the specific categories involved. For instance, functors from $(\bullet \rightrightarrows \bullet)$ into Set are just graphs. A natural transformation $G\Rightarrow H$ then exists precisely when there is a graph homomorphism from $G$ to $H$.</p> http://mathoverflow.net/questions/34750/an-elegant-formulation-for-typed-sets An elegant formulation for typed sets Aleks Kissinger 2010-08-06T10:09:21Z 2010-08-06T10:09:21Z <p>Fix a poset $T$, which we'll think of as a set of "types," interpreting $a \leq b$ as "$a$ is more general than $b$." Construct a category of TSet as follows.</p> <p><strong>Objects:</strong> Pairs ($X$, $\tau : X \rightarrow T$)<br /> <strong>Arrows:</strong> Functions $f : X \rightarrow Y$ that respect type subsumption, i.e. $\tau(x) \leq \sigma(f(x))$</p> <p>In the case where $T$ is a suitably nice poset (e.g. a frame, distributive lattice, cHA, ...), is there a slick formulation for such a category which makes it clear which (co)limits are hanging around and what properties they have?</p> http://mathoverflow.net/questions/33978/is-there-a-standard-notation-for-binary-relations-in-category-theory/34570#34570 Answer by Aleks Kissinger for Is there a standard notation for binary relations in category theory? Aleks Kissinger 2010-08-04T23:24:47Z 2010-08-04T23:24:47Z <p>In categorical literature, the notation $f: X \rightarrow Y$ only means "$f$ is a function from $X$ to $Y$" in the case where the category you are working in is Set, that is the category of sets and functions. In the category of sets and relations, the same notation means $f$ is a relation from $X$ to $Y$. To answer (perhaps more verbosely) you question about interest, there is actually loads of interest in binary relations. With a bit of digging, one sees that they crop up in various guises all over category theory.</p> <p><br /> <strong>AS A (MONOIDAL) CATEGORY</strong></p> <p>For starters, the category Rel of sets and binary relations is a perfectly good category, and its properties are well understood. Perhaps the reason Rel isn't well covered in the CT classics is because it is primarily of interest as a monoidal category. These are categories that have a notion of "product" that is much weaker than the usual, in that they don't satisfy the usual universal properties, but still form an associative, unital operation one can apply to objects and arrows. While this isn't too far out of the categorical mainstream, you may not necessarily meet them in an introductory course on category theory. </p> <p>Axiomatically, the category of relations is much more like the category of vector spaces. To see this intuitively, picture a relation from $A$ to $B$ as a matrix $M$ whose columns are indexed by the elements of $A$ and whose rows are indexed by the elements of $B$. Then, let $M_{a,b} = 1$ if $a M b$ and $M_{a,b} = 0$ otherwise. Relational composition is just matrix multiplication, replacing $+$ with OR and $*$ with AND. From this point of view, its easy to see that the cartesian product of relations is is much more closely resembles the tensor product of linear maps than it does the cartesian product of functions.</p> <p>The category FRel of finite sets and relations (as well as FHilb, the category of finite dimensional Hilbert spaces, and many more) forms a <em>dagger-compact closed category</em>. If you become familiar with this definition and associated literate, it sums up a good chunk of what categories like FRel are like and what they are good for. There are lots of ways to get stuck in to this. These categories are presented in a quite accessible, physics-oriented format in Bob Coecke's paper: "Introducing categories to the practicing physicist". You can get it here:</p> <p><a href="http://arxiv.org/abs/0808.1032" rel="nofollow">http://arxiv.org/abs/0808.1032</a></p> <p>And Pete Selinger introduces the whole zoo of such categories in "A survey of graphical languages for monoidal categories".</p> <p><a href="http://www.mscs.dal.ca/~selinger/papers/graphical.pdf" rel="nofollow">http://www.mscs.dal.ca/~selinger/papers/graphical.pdf</a></p> <p><br /> <strong>AS SPANS</strong></p> <p>As @Mikola already mentioned, Spans (which are a generalisation of relations) are often used in the place of binary relations in arbitrary categories. A span is just a pair of arrows $f: K \rightarrow X$, $g : K \rightarrow Y$ from a common domain $K$. In categories with products the connection to relations is especially easy to see. Because of the universal property of products, such a pair of arrows determines a unique third arrow $h : K \rightarrow A \times B$. In the case that $h$ is monic, this is just the same as a subset of $A \times B$, i.e. relations as you normally think of them (c.f. @Andrej).</p> <p>Spans are a beautiful and elegant way to deal with maps that are "relation-like" in suitably rich categories. In fact, any category with pullbacks has a natural notion of a "category of spans of C", whose objects are objects of C, whose arrows are spans (i.e. generalised relations), and where composition of spans is by a pullback-based construction that is much like how one composes relations.</p> <p>John Baez has some interesting papers about taking spans of groupoids rather than just spans of sets. In line with the intuition that relations are a bit like matrices over the booleans, he treats spans of groupoids as things that are a bit like matrices over the positive real numbers. The place to start on this is:</p> <p><a href="http://math.ucr.edu/home/baez/groupoidification/" rel="nofollow">http://math.ucr.edu/home/baez/groupoidification/</a></p> <p><br /> <strong>AS PROFUNCTORS</strong></p> <p>Another way you can think of a binary relation between sets is as a function $\chi_R$ <em>out of</em> a cartesian product $A \times B$ of sets onto the two element set {$0, 1$}. Then let $a R b$ iff $\chi_R(a,b) = 1$. Such a function can be used to define any relation, and is called the <em>characteristic function</em> of the relation $R$.</p> <p>We can generalise this in quite a natural way from sets and functions to categories and functors. However, in the category Cat of categories and functors, it turns out the most natural thing to send "characteristic" functors to is the category of Sets. A functor $F : C^{op} \times D \rightarrow Set$ is called a <em>profunctor</em> from the category $C$ to the category $D$. I won't spell out to many details here (for instance, the category $C$ is "op-ed" for a good reason), but suffice it to say that such a map behaves very analogously to a binary relation and comes with natural notions of composition, etc.</p> <p>These become a very powerful tool when working with internal and higher categories, because certain structures you can put on profunctors let you define the notion of a category <em>inside</em> another category. This is a good example of a structure that is quite deep (and that people are only beginning to fully appreciate!) that essentially generalises the basic notion of a binary relation. When you have built up sufficient courage, the canonical reference for profunctors is Bénabou's "Distributors at Work." For the applications I described, they are detailed in papers by Steve Lack and Paul-Andre Mellies, and probably many others.</p> http://mathoverflow.net/questions/25902/creating-high-quality-figures-of-surfaces/33333#33333 Answer by Aleks Kissinger for creating high quality figures of surfaces Aleks Kissinger 2010-07-25T21:51:38Z 2010-07-25T21:51:38Z <p>For figures in tex papers, pgf/tikz is usually my go-to package. However, if interactively is a concern, this is certainly not the way to go (tweak, build, tweak, build, ....). It can certainly do high quality ornamented 3d stuff though, e.g.</p> <p><a href="http://www.texample.net/tikz/examples/spherical-and-cartesian-grids/" rel="nofollow">http://www.texample.net/tikz/examples/spherical-and-cartesian-grids/</a></p> http://mathoverflow.net/questions/32637/when-are-modules-and-representations-not-the-same-thing When are modules and representations not the same thing? Aleks Kissinger 2010-07-20T13:42:51Z 2010-07-20T19:10:30Z <p>I've been trying for a while to get a real concrete handle on the relationship between representations and modules. To frame the question, I'll put here the standard situation I have in mind:</p> <p>A ring $R$ lives in the category Ab of Abelian groups as an internal monoid $(\mu_R, \eta_R)$. A module is then just an Abelian group $A$ and a map $m : R \otimes A \rightarrow A$ that commutes with the monoid structure in the way you'd expect.</p> <p>Alternatively, take an Abelian group $A$ and look at its group of endomorphisms $[A,A]$. This has an internal monoid $(\mu_A, \eta_A)$ just taking composition and identity. Then a representation is just a monoid homomorphism $(R, \mu_R, \eta_R) \rightarrow (A, \mu_A, \eta_A)$ in Ab. I.e. a ring homomorphism.</p> <p>But then, Ab is monoidal closed, so these are the same concept under the iso</p> <p>$$\hom(R\otimes A, A) \cong \hom(R, [A,A])$$</p> <p>This idea seems to work for any closed category where one wants to relate a multiplication to composition. So, my question is, since these things are isomorphic in such a general context, why are they taught as two separate concepts? Is it merely pedagogical, or are there useful examples where modules and representations are distinct?</p> http://mathoverflow.net/questions/32193/why-did-people-originally-like-frobenius-algebras Why did people originally like Frobenius algebras? Aleks Kissinger 2010-07-16T15:51:27Z 2010-07-16T20:07:58Z <p>These days, lots of people are excited by Frobenius algebras because commutative Frobenius algebras are the same thing as 2D topological quantum field theories.</p> <p>...but this seems like teaching an old dog new tricks. Can anyone sum up (using only diet representation theory :-P), why Frobenius algebras were invented and what was so good about them?</p> <p>Also, any nice texts and/or papers along this line would be much appreciated. I'm working through the old Nakayama papers now, but perhaps this material exists in a friendlier and more modernised form somewhere?</p> http://mathoverflow.net/questions/25418/when-are-all-split-monomorphisms-complemented/25469#25469 Answer by Aleks Kissinger for When are all split monomorphisms complemented? Aleks Kissinger 2010-05-21T11:22:28Z 2010-05-21T11:22:28Z <p>This is true in boolean categories (extensive + terminal object + (T : 1 &rarr; 1 + 1) is subobject classifier), but for <em>any</em> monic, not just split monics. There's quite a nice and easy read on extensive categories from 93:</p> <p>Carboni et al. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra (1993) vol. 84 pp. 145-158</p> <p>However, modulo axiom of choice, all monics in Set split, and I suspect this could be true for any boolean category.</p> http://mathoverflow.net/questions/25187/resources-for-graphical-languages-penrose-notation-feynman-diagrams-birdtra/25364#25364 Answer by Aleks Kissinger for Resources for graphical languages / Penrose notation / Feynman diagrams / birdtracks? Aleks Kissinger 2010-05-20T13:49:15Z 2010-05-20T16:28:20Z <p>I've been working on a GUI for typesetting tensor/monoidal diagrams in TikZ.</p> <p><a href="http://tikzit.sourceforge.net/" rel="nofollow">http://tikzit.sourceforge.net/</a></p> <p>It's especially geared at applications to quantum mechanics, namely "dot"-style diagrams of Frobenius algebras for complementary observables (Coecke, Duncan, arXiv:0906.4725) and entangled states (Coecke, me, arXiv:1002.2540).</p> <p>Given Dave's already quite extensive list of what's out there on the monoidal side of things, I can only really refine what he's said.</p> <p>Bob Coecke's short book (or long paper :-P) "Categories for the Practising Physicist" gives a pretty gentle buildup from physical principals, through Dirac notation for QM, to graphical notation, explaining some of the intuitions along the way.</p> <p><a href="http://web.comlab.ox.ac.uk/people/Bob.Coecke/ctfwp1_final.pdf" rel="nofollow">http://web.comlab.ox.ac.uk/people/Bob.Coecke/ctfwp1_final.pdf</a></p> <p>I found Ross Street's slides on Frobenius algebras to be a quick and easy (though sketchy) intro to the topic:</p> <p><a href="http://www.maths.mq.edu.au/~street/FAMC.pdf" rel="nofollow">http://www.maths.mq.edu.au/~street/FAMC.pdf</a></p> <p>The contemporary paper (Street. Frobenius monads and pseudomonoids. J. Math. Phys. (2004) vol. 45 (10) p. 3930) is very good, but considerably more technical, as it works in the language of higher categories.</p> <p>** edit</p> <p>I just realised that John's paper, "A Prehistory of n-Categorical Physics" hasn't been mentioned. This one puts the whole monoidal/graphical physics thing in a historical context starting from Maxwell and going through Feynman, Penrose, Mac Lane, Joyal, and all the other usual suspects. This is a long one, but it seems quite comprehensive.</p> http://mathoverflow.net/questions/22906/is-it-possible-to-define-a-graph-that-has-two-vertices-that-are-infinitely-far-ap Is it possible to define a graph that has two vertices that are infinitely far apart? Aleks Kissinger 2010-04-28T23:04:41Z 2010-04-30T00:37:27Z <p>Equivalently, is there a graph that contains an infinite simple path that has a start and an end point. My intuition is that there is no such graph, but I'm finding it hard to articulate why.</p> http://mathoverflow.net/questions/4897/where-does-the-easy-definition-of-a-weak-n-category-fail Where does the "easy" definition of a weak n-category fail? Aleks Kissinger 2009-11-10T17:51:56Z 2009-11-10T19:16:38Z <p>Okay, I'm going to ask a naiive question that surely has an interesting answer. So, a first approximation of defining a (small) weak n-category probably goes something like this. Take a pre-n-category C of all the cells, source and target maps that do the right thing (i.e. are globular), and a composition defined for each r in {0,...,n}.</p> <p>For C, define a family of coherent sets $(\Sigma_1, \Sigma_1, \ldots)$ as a family of sets $\Sigma_r$ of r-cells in C such that</p> <ol> <li>$f : a \rightarrow b \in \Sigma_r \Rightarrow \exists f' : b \rightarrow a \in \Sigma_r$</li> <li>$f, f' : a \rightarrow b \in \Sigma_r \Rightarrow \exists \alpha : f \rightarrow f' \in \Sigma_{r+1}$</li> </ol> <p>Now, suppose C admits such a family of coherent sets and all r-cells have associators, uniters, and interchangers in $\Sigma_{r+1}$, one might be tempted to say C is an $\infty$-category. If for all $r \geq n+1$, $\Sigma_r$ is only identites, one might say this defines an n-category.</p> <p>So, the reason I say "one might be tempted to say" is that, if it were that easy, someone much smarter than me would have done it already. :) So, where does the above recipe fail? Or is this definition unsatisfactory because it doesn't express the structure using a finite generating set of commutative diagrams (cf. Mac Lane's coherence etc.)?</p> http://mathoverflow.net/questions/1354/what-are-examples-of-good-toy-models-in-mathematics/3808#3808 Answer by Aleks Kissinger for What are examples of good toy models in mathematics? Aleks Kissinger 2009-11-02T16:03:42Z 2009-11-02T16:03:42Z <p>Relations are a toy model for linear maps. In fact, they can be thought of as matrices over the boolean semi-ring.</p> http://mathoverflow.net/questions/3184/philosophical-meaning-of-the-yoneda-lemma/3657#3657 Answer by Aleks Kissinger for "Philosophical" meaning of the Yoneda Lemma Aleks Kissinger 2009-11-01T11:27:09Z 2009-11-01T11:27:09Z <p>Barr and Wells (Toposes, Triples, and Theories, 84) talks about arrows as a general kind of elements. In Set, arrows from {*}&rarr;A are the usual elements of A, and arrows from bigger sets X&rarr;A are the X-elements of A, or elements of A parameterised in X. Of course the latter makes sense in any category, so we can use this language the state the Yoneda lemma as:</p> <p>The Hom(-,A)-elements of F are just the usual elements of FA.</p> <p>I find this to be, at least, a useful mnemonic, but also justifies the intuition that an object "is" its collection of probes.</p> http://mathoverflow.net/questions/2802/what-is-the-comultiplication-of-a-matrix-frobenius-algebra What is the comultiplication of a matrix frobenius algebra? Aleks Kissinger 2009-10-27T11:41:43Z 2009-10-31T23:38:07Z <p>One of the easiest examples I can think of for frobenius algebras is a plain ol' matrix algebra with tr : V &rarr; k as the co-unit (or equivalently, tr(a&sdot;b) as the frobenius form). This is enough data to generate a comultiplication &delta; : V &rarr; V &otimes; V. This turns out to be &mu;<sup>&dagger;</sup>, for multiplication &mu;. Is there any intuition for what this map does (aside from the obvious "do multiplication on the dual space")?</p> http://mathoverflow.net/questions/1497/when-do-prop-morphisms-induce-adjunctions/2631#2631 Answer by Aleks Kissinger for When do PROP-morphisms induce adjunctions? Aleks Kissinger 2009-10-26T15:57:15Z 2009-10-26T15:57:15Z <p>Paul-André Melliès has quite an interesting paper on this topic:</p> <p><a href="http://hal.archives-ouvertes.fr/docs/00/33/93/31/PDF/free-models.pdf" rel="nofollow">http://hal.archives-ouvertes.fr/docs/00/33/93/31/PDF/free-models.pdf</a></p> <p>...but phrased in the more general terms of T-algebras of a pseudomonad. The idea is that a pseudomonad on a 2-category (especially Cat), let you put algebraic structures on categories the same way monads let you put them on objects of a category, like sets. This is motivated by the need to put PROPs, PROBs, PROs, Lawvere theories, etc. all under one roof.</p> <p>He begins by talking about how a T-algebra homomorphism (a monoidal functor in the case where the T-algebras are monoidal categories) j : A -> B induces a forgetful functor U_j from Models(B,C) to Models(A,C) in the way you mentioned. Looking for left adjoint to U_j amounts to looking for a way to push some functor backwards along j in a suitably natural way. As Tom already mentioned, this is the left Kan extension. This process is functorial, and usually written Lan_j : [A,C] -> [B,C]. Furthermore, Lan_j -| U_j.</p> <p>But if we were done there, all PROPs would have free algebras, which we know is not true in general (cf. bialgebras). The hard part is proving the Lan_j is a <em>T-algebraic</em> left Kan-extension. In the case of Lawvere theories, this is easy, because the product structure guarantees all natural transformations of cartesian functors are cartesian, but in the monoidal case, this stuff all needs to be checked.</p> <p>This is where the story starts to get more complicated. It seems quite tricky to come up with suitably weak conditions under which Lan_j is T-algebraic. Mellies phrases these in terms of distributers (aka profunctors, modules, depending on who you ask and what country you are in :-P). If functors are like functions, this are a bit like relations. The nice thing about them is they always come in adjoint pairs f_* and f^* for any functor f.</p> <p>So, thm 1 in the paper is (roughly) this. If j and j^* are T-algebraic in the suitable 2-categories, C is (T-algebraically) complete and co-complete, and for any model f : A -> C, f_* o j^* factors through the up-star of the Yoneda embedding y : C -> Psh(C), then U_j has a left adjoint computed as Lan_j that is indeed the free functor.</p> <p>This is quite heavy-duty (pro-arrow equipment, ends, etc.), but it seems to get the job done. It would be nice to see more concrete/specific examples of this.</p> http://mathoverflow.net/questions/1166/can-the-objects-of-every-concrete-category-themselves-be-realized-as-small-catego/1424#1424 Answer by Aleks Kissinger for Can the objects of every concrete category themselves be realized as small categories? Aleks Kissinger 2009-10-20T13:29:22Z 2009-10-20T13:29:22Z <p>One way to think of categories algebraically is as a "monoid-oid". So, do for monoids what you do for groups to make groupoids. A (small) category is a set, with an associative, unital, partial multiplication, i.e. composition. So, anything that is an example of this, (monoids, groups, abelian groups, groupoids, etc) is certainly representable as a category.</p> <p>But there are other examples of things which we aren't used to thinking of as partial monoids. Pre-orders for instance can be thought of as a set of arrows, where the identities are the set elements in a the usual sense and multiplication "witnesses" transitivity. This seems to be kindof a "Lawvere-esque" way of thinking about the category (cf. elementary theory of abstract categories, ETAC).</p> <p>Warning: this could be a digression... A better way to recover lots of concrete things in a categorical way is to look at functors that preserve some structure (e.g. products or monoidal structure) as the "things" and natural transformations as the "thing homomorphisms". Lawvere theories give a good example of this, and provide a general way to talk about groups, rings, etc. Incidentally, they do pretty much the same job as monads (and there are some nice equivalences). PROPs are another good example. These are both specific cases of a type of 2-monad called a Doctrine. For a prolonged, but interesting discussion, see <a href="http://golem.ph.utexas.edu/category/2006/09/doctrines.html" rel="nofollow" title="Doctrines at n-Category Cafe">here</a>.</p> http://mathoverflow.net/questions/1140/category-theory-sans-much-motivation/1415#1415 Answer by Aleks Kissinger for Category theory sans (much) motivation? Aleks Kissinger 2009-10-20T12:22:54Z 2009-10-20T12:22:54Z <p>I've found a major stumbling block when trying to introduce category theory to new people is a tendency to think of objects as "things" instead of "types of things". So, after coping just fine with definitions of the category of sets, groups, etc., when asked to build their own category, one gets things that miss the point entirely.</p> <p>Often these first attempts look more like finite state machines than categories, which is perhaps because the use of diagrams in this case misleads. It makes a person think there is some spacial or temporal separation of objects in a commutative diagram, rather than a logical separation, namely a distinction of type. Thinking of categories as a typing system (esp. coming from a CS background), was my first "ah-ha" moment.</p> <p>Of course, whether you can say the work "type" without thinking the word "set" is another issue.</p> http://mathoverflow.net/questions/1114/whats-a-groupoid-whats-a-good-example-of-a-groupoid/1409#1409 Answer by Aleks Kissinger for What's a groupoid? What's a good example of a groupoid? Aleks Kissinger 2009-10-20T11:57:07Z 2009-10-20T11:57:07Z <p>To follow on from what Qiaochu said, one of the interesting things about groupoids is their cardinality. Whereas the cardinality of a set is a natural number, the cardinality of a groupoid is a positive rational. This gives us a combinatorial way to inject "numbers" into an abstract system.</p> <p>For example, a way to think of matrices of natural numbers is just taking spans of finite sets, A &lt;- S -> B. The "numbers" come from counting the paths from A, through S, to B. Composition by pullback then just amounts to matrix multiplication. Incidentally, this is one of the nicest ways to think about commutative bi-alebras, but that's another story (see Stephen Lack - "Composing PROPs" if you're interested).</p> <p>However, if you take spans of finite groupoids instead, you get computation with matrices of positive rational numbers. If you take spans of "nice" infinite groupoids, you get positive real numbers. John Baez and co. have a nice paper, called <a href="http://arxiv.org/abs/0908.4305v1" rel="nofollow">Higher-Dimensional Algebra VII: Groupoidification</a>, that works a lot of this out an applies it to quantum physics. It's one of the things that convinced me that groupoids were pretty cool gadgets.</p> http://mathoverflow.net/questions/38863/re-seating-a-monad/82497#82497 Comment by Aleks Kissinger Aleks Kissinger 2011-12-04T23:09:47Z 2011-12-04T23:09:47Z Thanks Tom! I'd just about given up on that one. http://mathoverflow.net/questions/34750/an-elegant-formulation-for-typed-sets Comment by Aleks Kissinger Aleks Kissinger 2011-10-07T11:32:27Z 2011-10-07T11:32:27Z In this case, by type I mean &quot;an element of a poset&quot;. Perhaps a better term for it would be &quot;unifiable data&quot;, since examples I have in mind are things like expressions with free variables, with &quot;s &lt;= t&quot; interpreted as &quot;there exists a substitution of free variables that turns s into t&quot;. http://mathoverflow.net/questions/59892/co-ends-as-a-trace-operation-on-profunctors/59897#59897 Comment by Aleks Kissinger Aleks Kissinger 2011-03-30T13:59:16Z 2011-03-30T13:59:16Z What a interesting and (seemingly) strange thing! Is any of this stuff written up somewhere, or all folklore? http://mathoverflow.net/questions/59892/co-ends-as-a-trace-operation-on-profunctors/59897#59897 Comment by Aleks Kissinger Aleks Kissinger 2011-03-29T00:38:15Z 2011-03-29T00:38:15Z This reminds me of something a colleague of mine was pondering a while back... For a category C, do you know what the set COEND^d [ hom(d,d) ] = cap o cup = tr(1_C) represents? For finite-dimensional vector spaces, this is always dimension, so this seems like it could be an important invariant of a category. http://mathoverflow.net/questions/59892/co-ends-as-a-trace-operation-on-profunctors Comment by Aleks Kissinger Aleks Kissinger 2011-03-29T00:32:23Z 2011-03-29T00:32:23Z Chalk one up to wishful thinking. :) There must be a deeper connection than the observation that both are compact closed. I can think of a few categories (e.g. 2-Cob, and Rel with disjoint union) with traces that don't look like sums over some kind of indexing object, so there should be something more to say here. Perhaps <i>really</i> understanding co-ends (and even partial traces for that matter!) can shed some light on things. http://mathoverflow.net/questions/51952/rig-of-fractions-including-zero-denominators/52010#52010 Comment by Aleks Kissinger Aleks Kissinger 2011-01-14T14:13:01Z 2011-01-14T14:13:01Z That's exactly why the thing can't be a ring. As Stasinkski pointed out, its actually an algebraic wheel. Inversion is replaced by a unary operator &quot;/&quot; that is <i>almost</i> the same at the inverse. However, 0 != 0/0 != 1, where 0/0 is a new element that &quot;swallows&quot; everything. Also, note that multiplication by 0 doesn't always yield 0. Because of this distributivity and the zero laws have to be tweaked. However, it all seems to work, and can be axiomatised, so you get a category of wheels and wheel HMs. http://mathoverflow.net/questions/51952/rig-of-fractions-including-zero-denominators/51957#51957 Comment by Aleks Kissinger Aleks Kissinger 2011-01-13T17:08:01Z 2011-01-13T17:08:01Z unknown: I suppose what I meant to say is the symmetric closure of the relation ~. Ie. (r,s) ~ (t,u) iff exists k != 0 s.t. (r,s) = (k*t,k*u) or (k*r,k*s) = (t,u). Yes, this is basically the formal addition of infinity and undef. I've seen this from a topological or order-theoric angle, e.g. compactification of the naturals or the reals, but never from an algebraic one. A Stasinski: This is either exactly what I'm looking for, or very close. Thanks! http://mathoverflow.net/questions/51952/rig-of-fractions-including-zero-denominators Comment by Aleks Kissinger Aleks Kissinger 2011-01-13T15:25:52Z 2011-01-13T15:25:52Z Yes, in the case of the field of fractions for an integral domain, I mean equiv. classes over the relation &quot;user 9072&quot; alludes to below. In the case where we consider 0 denominators, it seems to become a bit more delicate. http://mathoverflow.net/questions/51952/rig-of-fractions-including-zero-denominators/51957#51957 Comment by Aleks Kissinger Aleks Kissinger 2011-01-13T15:23:24Z 2011-01-13T15:23:24Z Aha! The usual quotient seems to collapse too much if one wants zero denominators. Following the convention for projective spaces over a field, the relation I have in mind is: (r,s) ~ (t,u) iff exists k != 0 s.t. (r,s) = (k*t, k*u). Then, at least over examples like N, Z, R, Q, C, ..., all the fractions you expect to be equal are equal. This is a weaker equivalence relation. For instance, it's no longer true that (1,0) ~ (0,1), and (0,0) ~ everything. However, as I mentioned, it loses its ring structure. http://mathoverflow.net/questions/34750/an-elegant-formulation-for-typed-sets Comment by Aleks Kissinger Aleks Kissinger 2011-01-13T12:53:15Z 2011-01-13T12:53:15Z What I have in mind is reasoning about rewrite systems on algebraic structures whose constituents might have types. In its own right, the category T-Set is not that interesting, but consider e.g. the category of graphs that have a typed set of vertices rather than a set. Then the ordering on T plays the role of the type-unification step on the vertices when matching the LHS of a rewrite rule. http://mathoverflow.net/questions/34750/an-elegant-formulation-for-typed-sets Comment by Aleks Kissinger Aleks Kissinger 2011-01-13T12:52:10Z 2011-01-13T12:52:10Z Interesting stuff! It seems quite different from my original intention however, which was to define a category of sets relative to a (fixed) type system and think of a function as a kind of &quot;matching&quot;. I.e. for x to be mapped on to f(x), its type must be more general than the type of f(x). http://mathoverflow.net/questions/38005/are-sieves-in-locally-small-categories-still-sets Comment by Aleks Kissinger Aleks Kissinger 2010-09-09T19:37:31Z 2010-09-09T19:37:31Z Great! That clears it up. http://mathoverflow.net/questions/35784/profunctors-corresponding-to-partial-functors/35969#35969 Comment by Aleks Kissinger Aleks Kissinger 2010-08-19T18:15:20Z 2010-08-19T18:15:20Z I guess this analogy goes through by replacing the notion of &quot;subset where the image of a function is defined&quot; with &quot;subcategory where the image of a profunctor is representable.&quot; Interesting that a yes or no question is replaced by a question of approximations. Are there interesting ways one can gauge how good such approximations are? The examples I'm thinking of are categories of matrices over various rigs, especially Mat(C) &lt;--&lt; Mat(R+) --&gt;&gt; Rel. http://mathoverflow.net/questions/17532/does-linearization-of-categories-reflect-isomorphism Comment by Aleks Kissinger Aleks Kissinger 2010-08-16T12:41:06Z 2010-08-16T12:41:06Z Just a comment on terminology. The inclusion functor L : C --&gt; RC reflects isos in the usual sense. That is, if L(g) is an iso iff g is an iso. I think the hard thing to show here is actually the L creates isomorphisms. That is, for an iso L(x) --&gt; y, there exists y', i' such that L(y') = y and i' : x --&gt; y' is an iso. Of course, L is identity on objects, so the existence of i' is the interesting part. http://mathoverflow.net/questions/35612/computing-colimits-in-a-lawvere-theory/35615#35615 Comment by Aleks Kissinger Aleks Kissinger 2010-08-15T10:44:05Z 2010-08-15T10:44:05Z The proof of this is actually how I got interested in the question. For a Lawvere theory L, and F = FinSet^op. Then Prod(F,Set) is iso to Set, and the canonical functor U : F --&gt; L induces a forgetful functor (-- o U) : Prod(L,Set) --&gt; Prod(F,Set). Since sifted colimits commute with products, (-- o U) creates reflexive coequalisers. It has a left adjoint, namely the left Kan ext'n, so by Beck's monadicity thm, T(--) := LanU(--) o U is a monad and Set^T is iso to Prod(L,Set).