User aleks kissinger - MathOverflow

Answer by Aleks Kissinger for Understanding Penrose diagrammatical notation

2013-04-16T21:01:39Z

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:

http://www.mathstat.dal.ca/~selinger/papers.html#graphical

Computing colimits in a Lawvere theory

2010-08-15T00:23:22Z

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:

http://ncatlab.org/nlab/show/database+of+categories

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.

Does anyone know of a reference or proof that such colimits exist, or even better, how to go about computing them?

Where are some interesting places where the axiom of choice crops up in category theory?

2009-10-31T16:18:16Z

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.

Categories whose objects are CW-complexes

2010-08-03T17:02:14Z

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?

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.

Re-seating a monad

2010-09-15T19:52:56Z

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.

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?

Co-ends as a trace operation on profunctors

2011-03-28T20:25:36Z

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:

$F\circ G := \int^{d\in D} F(-, d) \times G(d, -)$

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:

$\xi := \int^{b \in B} \psi(-,b,-,-) \times \phi(b,-)$

This then looks a lot like contraction of tensors:

$\xi_{e}^{a,c,d} := \sum_{b\in B} \left( \psi_{b}^{a,c,d} \phi_{e}^{b} \right)$

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:

To what extent can the analogy between tensor contraction and profunctor composition be made precise?

Algebras with a degenerate trace form

2011-05-01T18:58:11Z

Let the bilinear trace form of a finite-dimensional associative algebra be defined as:

$(u,v) \mapsto Tr(L_u L_v)$

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?

Is there a characterization for an associative algebra $A$ whose bilinear trace form, considered as a linear map $V \to V^*$ is rank 1?

In particular, when $A$ is unital and commutative, there seems to be only one possibility for the trace form, if its rank 1:

$(u,v)\mapsto \frac{1}{dimV} Tr(L_u)Tr(L_v)$

This seems like quite the coincidence. Could anyone shed some light on this?

Rig of fractions, including zero denominators

2011-01-13T13:21:03Z

For some integral domain $R$, one forms the field of fractions $R^*$ 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.

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 $R^*$ , except you also have a sort of "infinity" element $1/0$ and a sort of "undefined" element $0/0$, neither of which have multiplicative or additive inverses.

This type of structure seems to arise quite naturally when considering algebras over 1D projective space. So, my questions are

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?

Are sieves in locally small categories still sets?

2010-09-07T20:38:37Z

In "Sheaves in Geometry and Logic", M&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

\[S = \{\, f : \exists A . f \in Q(A) \}\]

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?

In what cases does a Yoneda-like embedding preserve monoidal structure?

2010-08-20T15:48:20Z

What kinds of Yoneda-like situations induce an embedding that preserves the tensor product for some arbitrary monoidal category?

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)$.

Are there $V$-enriched cases where the generalised embedding

$$ Y : C \to V^{C^{op}} $$

does preserve the tensor product for interesting monoidal categories $C$?

Profunctors corresponding to "partial functors"

2010-08-16T18:36:40Z

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?

Answer by Aleks Kissinger for conditions for natural transformations to exist?

2010-08-16T13:31:55Z

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.

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$.

An elegant formulation for typed sets

2010-08-06T10:09:21Z

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.

Objects: Pairs ($X$, $\tau : X \rightarrow T$)
Arrows: Functions $f : X \rightarrow Y$ that respect type subsumption, i.e. $\tau(x) \leq \sigma(f(x))$

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?

Answer by Aleks Kissinger for Is there a standard notation for binary relations in category theory?

2010-08-04T23:24:47Z

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.

AS A (MONOIDAL) CATEGORY

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.

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.

The category FRel of finite sets and relations (as well as FHilb, the category of finite dimensional Hilbert spaces, and many more) forms a dagger-compact closed category. 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:

http://arxiv.org/abs/0808.1032

And Pete Selinger introduces the whole zoo of such categories in "A survey of graphical languages for monoidal categories".

http://www.mscs.dal.ca/~selinger/papers/graphical.pdf

AS SPANS

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).

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.

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:

http://math.ucr.edu/home/baez/groupoidification/

AS PROFUNCTORS

Another way you can think of a binary relation between sets is as a function $\chi_R$ out of 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 characteristic function of the relation $R$.

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 profunctor 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.

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 inside 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.

Answer by Aleks Kissinger for creating high quality figures of surfaces

2010-07-25T21:51:38Z

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.

http://www.texample.net/tikz/examples/spherical-and-cartesian-grids/

When are modules and representations not the same thing?

2010-07-20T13:42:51Z

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:

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.

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.

But then, Ab is monoidal closed, so these are the same concept under the iso

$$\hom(R\otimes A, A) \cong \hom(R, [A,A])$$

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?

Why did people originally like Frobenius algebras?

2010-07-16T15:51:27Z

These days, lots of people are excited by Frobenius algebras because commutative Frobenius algebras are the same thing as 2D topological quantum field theories.

...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?

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?

Answer by Aleks Kissinger for When are all split monomorphisms complemented?

2010-05-21T11:22:28Z

This is true in boolean categories (extensive + terminal object + (T : 1 → 1 + 1) is subobject classifier), but for any monic, not just split monics. There's quite a nice and easy read on extensive categories from 93:

Carboni et al. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra (1993) vol. 84 pp. 145-158

However, modulo axiom of choice, all monics in Set split, and I suspect this could be true for any boolean category.

Answer by Aleks Kissinger for Resources for graphical languages / Penrose notation / Feynman diagrams / birdtracks?

2010-05-20T13:49:15Z

I've been working on a GUI for typesetting tensor/monoidal diagrams in TikZ.

http://tikzit.sourceforge.net/

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).

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.

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.

http://web.comlab.ox.ac.uk/people/Bob.Coecke/ctfwp1_final.pdf

I found Ross Street's slides on Frobenius algebras to be a quick and easy (though sketchy) intro to the topic:

http://www.maths.mq.edu.au/~street/FAMC.pdf

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.

** edit

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.

Is it possible to define a graph that has two vertices that are infinitely far apart?

2010-04-28T23:04:41Z

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.

Where does the "easy" definition of a weak n-category fail?

2009-11-10T17:51:56Z

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}.

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

$f : a \rightarrow b \in \Sigma_r \Rightarrow \exists f' : b \rightarrow a \in \Sigma_r$
$f, f' : a \rightarrow b \in \Sigma_r \Rightarrow \exists \alpha : f \rightarrow f' \in \Sigma_{r+1}$

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.

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.)?

Answer by Aleks Kissinger for What are examples of good toy models in mathematics?

2009-11-02T16:03:42Z

Relations are a toy model for linear maps. In fact, they can be thought of as matrices over the boolean semi-ring.

Answer by Aleks Kissinger for "Philosophical" meaning of the Yoneda Lemma

2009-11-01T11:27:09Z

Barr and Wells (Toposes, Triples, and Theories, 84) talks about arrows as a general kind of elements. In Set, arrows from {*}→A are the usual elements of A, and arrows from bigger sets X→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:

The Hom(-,A)-elements of F are just the usual elements of FA.

I find this to be, at least, a useful mnemonic, but also justifies the intuition that an object "is" its collection of probes.

What is the comultiplication of a matrix frobenius algebra?

2009-10-27T11:41:43Z

One of the easiest examples I can think of for frobenius algebras is a plain ol' matrix algebra with tr : V → k as the co-unit (or equivalently, tr(a⋅b) as the frobenius form). This is enough data to generate a comultiplication δ : V → V ⊗ V. This turns out to be μ^†, for multiplication μ. Is there any intuition for what this map does (aside from the obvious "do multiplication on the dual space")?

Answer by Aleks Kissinger for When do PROP-morphisms induce adjunctions?

2009-10-26T15:57:15Z

Paul-André Melliès has quite an interesting paper on this topic:

http://hal.archives-ouvertes.fr/docs/00/33/93/31/PDF/free-models.pdf

...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.

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.

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 T-algebraic 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.

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.

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.

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.

Answer by Aleks Kissinger for Can the objects of every concrete category themselves be realized as small categories?

2009-10-20T13:29:22Z

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.

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).

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 here.

Answer by Aleks Kissinger for Category theory sans (much) motivation?

2009-10-20T12:22:54Z

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.

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.

Of course, whether you can say the work "type" without thinking the word "set" is another issue.

Answer by Aleks Kissinger for What's a groupoid? What's a good example of a groupoid?

2009-10-20T11:57:07Z

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.

For example, a way to think of matrices of natural numbers is just taking spans of finite sets, A <- 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).

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 Higher-Dimensional Algebra VII: Groupoidification, 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.

Comment by Aleks Kissinger

2011-12-04T23:09:47Z

Thanks Tom! I'd just about given up on that one.

Comment by Aleks Kissinger

2011-10-07T11:32:27Z

In this case, by type I mean "an element of a poset". Perhaps a better term for it would be "unifiable data", since examples I have in mind are things like expressions with free variables, with "s <= t" interpreted as "there exists a substitution of free variables that turns s into t".

Comment by Aleks Kissinger

2011-03-30T13:59:16Z

What a interesting and (seemingly) strange thing! Is any of this stuff written up somewhere, or all folklore?

Comment by Aleks Kissinger

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.

Comment by Aleks Kissinger

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 really understanding co-ends (and even partial traces for that matter!) can shed some light on things.

Comment by Aleks Kissinger

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 "/" that is almost the same at the inverse. However, 0 != 0/0 != 1, where 0/0 is a new element that "swallows" 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.

Comment by Aleks Kissinger

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!

Comment by Aleks Kissinger

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 "user 9072" alludes to below. In the case where we consider 0 denominators, it seems to become a bit more delicate.

Comment by Aleks Kissinger

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.

Comment by Aleks Kissinger

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.

Comment by Aleks Kissinger

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 "matching". I.e. for x to be mapped on to f(x), its type must be more general than the type of f(x).

Comment by Aleks Kissinger

2010-09-09T19:37:31Z

Great! That clears it up.

Comment by Aleks Kissinger

2010-08-19T18:15:20Z

I guess this analogy goes through by replacing the notion of "subset where the image of a function is defined" with "subcategory where the image of a profunctor is representable." 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) <--< Mat(R+) -->> Rel.

Comment by Aleks Kissinger

2010-08-16T12:41:06Z

Just a comment on terminology. The inclusion functor L : C --> 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) --> y, there exists y', i' such that L(y') = y and i' : x --> y' is an iso. Of course, L is identity on objects, so the existence of i' is the interesting part.

Comment by Aleks Kissinger

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 --> L induces a forgetful functor (-- o U) : Prod(L,Set) --> 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).