Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics comma complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration finite foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorMike Shulman
    • CommentTimeNov 13th 2017

    Blute-Cockett-Seely-Trimble describes a string diagram / circuit diagram / proof net calculus for linearly distributive categories, which is significantly complicated by the presence of units; as discussed in section 2.3 of the paper, some of the unit and counit links have to be “attached” to other strings to prevent diagrams that should be distinct from getting identified. However, the example given there depends on the fact that the units \top and \bot for the tensor and cotensor products are different; as noted therein, if \top in the example were replaced by \bot then the two problematic diagrams would represent the same morphism. This makes me wonder, if we have a linearly distributive category that happens to satisfy =\top=\bot, then does the whole string diagram calculus work without these extra attachments?

    This would be especially convenient because any closed monoidal category (C,,)(C,\otimes,\top) can be embedded by a closed functor into a linearly distributive (indeed *\ast-autonomous) category in which =\top=\bot, namely Chu(C,)Chu(C,\top). So we could soundly use linearly distributive string diagrams to reason about closed monoidal categories, without the need for the clunky “boxes” that are sometimes used to deal with internal-homs.

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeNov 13th 2017

    Oops, I’m not sure why I thought the embedding of CC in Chu(C,d)Chu(C,d) is closed; it’s strong monoidal but doesn’t preserve internal-homs. So that’s not as interesting as I thought it was.

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 25th 2017

    Sorry, I’ve been away from the nForum for a while. I’m pretty certain that the usual string diagram calculus (or the calculus of ordinary proof nets or Kelly-Mac Lane graphs) suffices for the case =\top = \bot. I think this equation is sometimes referred to as the “mix” rule, and that a reference for the claim might be Blute’s thesis.

    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeNov 25th 2017

    Ah, interesting; I hadn’t made the connection, but now I can see that that’s similar to the mix rule. I’ve usually seen the mix rule as

    ΓΔΦΨΓ,ΦΔ,Ψ \frac{\Gamma \vdash \Delta \qquad \Phi \vdash \Psi}{\Gamma,\Phi\vdash\Delta,\Psi}

    which I can see follows from =\top=\bot and a cut. I guess there should be a 0-ary mix rule

    \frac{\quad}{\quad\vdash\quad}

    as well? Do these two rules suffice to prove =\top=\bot?

    • CommentRowNumber5.
    • CommentAuthorSam Staton
    • CommentTimeNov 26th 2017

    Hi, one reference is Cockett and Seely, Proof theory for full intuitionistic linear logic, bilinear logic, and mix categories. An “isomix” category is one where ⊤≅⊥ — Lemma 6.6.

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 26th 2017

    Thanks, Sam; that is also, I imagine, a better reference than Blute’s thesis for the claim about coherence.

    • CommentRowNumber7.
    • CommentAuthorMike Shulman
    • CommentTimeNov 29th 2017

    Ah, thanks! I’ve read other parts of that paper, but always skipped the bit about mix. (-: I created mix rule to record this.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 29th 2017

    Thanks, Mike!

    • CommentRowNumber9.
    • CommentAuthorSam Staton
    • CommentTimeDec 1st 2017
    • (edited Dec 3rd 2017)

    Thanks. I added a link from compact closed categories.

    I think mix gives a different perspective on composition and perhaps hypergraphs are the right place to consider mix.

    Say a “hypergraph” on a set of vertices VV is a species coloured by VV, ie a presheaf on the free symmetric monoidal category generated by VV.

    Then we can say a “mix hypergraph” is a monoid for the Day convolution structure. It’s a model of linear logic without any connectives, without cut, but with mix.

    If we consider hypergraphs with an involution ** on VV, then we can also define “traced **-hypergraph” as one where every edge on (Γ,A,A*)(\Gamma,A,A*) has an associated trace edge on Γ\Gamma, satisfying some conditions.

    And then I think we can define “traced mix **-hypergraph”, by putting on some more coherence conditions. Polycategory-like composition can then be defined by first using mix and then tracing. So traced mix **-hypergraphs can be thought of as polycategories, and hopefully the representable ones are precisely the compact closed categories.

    • CommentRowNumber10.
    • CommentAuthorMike Shulman
    • CommentTimeDec 3rd 2017

    Shouldn’t you consider directed hypergraphs, maybe as presheaves on F(V×V)F(V\times V)?

    • CommentRowNumber11.
    • CommentAuthorSam Staton
    • CommentTimeDec 3rd 2017
    • (edited Dec 3rd 2017)

    I was thinking of one sided sequents. So for each list Γ\Gamma of vertices, there is a set of edges. And mix associates to each edge pp on Γ\Gamma, and each edge qq on Δ\Delta, an edge (p|q)(p|q) on (Γ,Δ)(\Gamma,\Delta).

    But for the 2-sided formulation, I agree, a directed hypergraph should have, for each pair of lists of edges, a set of vertices. I suppose you meant F(V+V)F(V+V)?

    • CommentRowNumber12.
    • CommentAuthorMike Shulman
    • CommentTimeDec 3rd 2017

    Yes, F(V+V)F(V+V). It seems to me like if you want something with “no connectives” your sequents should be 2-sided; making things 1-sided generally presupposes a negation connective.

    • CommentRowNumber13.
    • CommentAuthorMike Shulman
    • CommentTimeDec 3rd 2017

    Is there a standard notion of “mix polycategory”? It seems like kind of the “dual” of a properad: a polycategory composes only simply connected graphs, a properad composes connected ones, a prop composes arbitrary ones, while a “mix polycategory” would I guess compose disjoint unions of simply connected ones.

    • CommentRowNumber14.
    • CommentAuthorSam Staton
    • CommentTimeDec 12th 2017

    Hi Mike, I have been meaning to come back to this because the literature on these things seems sparse and perhaps you or others understand it better than me. Regarding the role of negation,

    • When you form F(V+V)F(V+V), it seems that you are freely adding a strict negation, in a similar way to the way that a multicategory is a coloured PRO, is that right?

    • In many presentations of classical linear logic, it seems that negation is not a “connective” but something more primitive. e.g. wikipedia

    • Do you know examples of naturally occurring linear distributive categories that are not *-autonomous, but that still feel like models of classical linear logic? (so other than distributive lattices and when the two monoidal structures coincide?)

    • CommentRowNumber15.
    • CommentAuthorMike Shulman
    • CommentTimeDec 12th 2017

    Good questions.

    • I don’t think so; if XX is a presheaf on F(V+V)F(V+V) then X(inl(x),inr(y),inl(z))X(inl(x),inr(y),inl(z)) means a morphism (x,z)(y)(x,z) \to (y), and there’s no operation that mixes the inlinl’s and the inrinr’s.

    • Right, it took me a long time to really understand this. The key phrase that helped me is negation normal form, which means a way of expressing a formula in which all the negations are “pushed all the way inside”. The provable laws of ordinary classical (linear) logic, in which negation is a connective, imply that every formula is equivalent to one in negation normal form. This suggests that we could set up a system in which only formulas in negation normal form are permitted, where “negation” is an operation on formulas (i.e. on syntax) rather than a connective (an inductive constructor of syntax). It’s actually the same sort of thing as cut-elimination: every derivation is equivalent to one in “normal form” that doesn’t use cut, so we can set up a system in which only cut-free derivations exist, with cut as an operation on cut-free derivations (i.e. given cut-free derivations of ΓA,Δ\Gamma\vdash A,\Delta and Φ,AΨ\Phi,A\vdash \Psi we can construct a cut-free derivation of Γ,ΦΔ,Ψ\Gamma,\Phi\vdash \Delta,\Psi).

    • No. (-:

    • CommentRowNumber16.
    • CommentAuthorMike Shulman
    • CommentTimeDec 13th 2017

    Re: the third question, I don’t know whether to consider Dialectica-like models as “naturally occurring”, but they do give examples. E.g. if you apply a Dialectica construction to the fibration of subobjects in a cartesian closed coherent (but not Boolean) category, I think you get a linearly distributive category that is not *\ast-autonomous, not a distributive lattice, and whose two monoidal structures don’t coincide.

    • CommentRowNumber17.
    • CommentAuthorSam Staton
    • CommentTimeDec 13th 2017
    • (edited Dec 13th 2017)

    Hi, Thanks for the Dialectica idea, I’ll have a look.

    Regarding 1 in #16. I’ll say that a “strict *-polycategory” is a polycategory with involution where A =AA^{\bot\bot}=A and C(Γ,A ;Δ)=C(Γ;A,Δ)C(\Gamma,A^\bot;\Delta)=C(\Gamma;A,\Delta). And I’ll assume all polycategories are symmetric. So a strict *-polycategory might as well be one-sided. We could even define it this way, with a one-sided composition C(;Γ,A )×C(;A,Δ)C(;Γ,Δ)C(;\Gamma,A^\bot)\times C(;A,\Delta)\to C(;\Gamma,\Delta). I think many naturally occurring models of CLL are of this form.

    Now what I meant was that if CC is a polycategory with objects VV then it seems we can define a strict *-polycategory C*C* with objects (V+V)(V+V) by saying that C*(inl(Γ);inl(Δ))=C(Γ;Δ)C*(inl(\Gamma);inl(\Delta))=C(\Gamma;\Delta), and that (inl(v)) =inr(v)(inl(v))^\bot=inr(v), and something about the permutation action. (This might well be a free construction.) And now I think we can regard a polycategory over VV as the same thing as a strict *-polycategory over (V+V)(V+V) that satisfies the last two conditions.

    This seems to be in line with how you were defining directed hypergraphs. The point I was trying to make is that just as sometimes coloured PROs seem more basic than multicategories (and vice versa), so the same might be true for 1- versus 2-sided sequent calculi.

    • CommentRowNumber18.
    • CommentAuthorMike Shulman
    • CommentTimeDec 13th 2017

    I agree that you can freely generate a *\ast-polycategory from any polycategory in that way, and that you should be able to recover the original polycategory in sort of the same way that you can recover a multicategory from the monoidal category that it freely generates. But in such an *\ast-polycategory a morphism has both a source and a target, each of which can contain both objects and their duals, so there is a formal distinction between “AA in the domain” and “A A^\perp in the codomain” that isn’t present in F(V+V)F(V+V).

    This may be what you’re trying to get at with a “strict” *\ast-polycategory, if by “C(Γ,A ;Δ)=C(Γ;A,Δ)C(\Gamma,A^\bot;\Delta)=C(\Gamma;A,\Delta)” you mean a literal equality of ZFC-style sets. But that sort of definition is fraught with problems, so if that’s what you want I think it’s better to actually define it one-sidedly. (In the literature on cyclic operads, the one-sided versions are called “entries-only”.) So we’re not “freely adding” a strict negation, we’re just representing domains and codomains in a different equivalent way.

    By the way, although one of the early definitions of “PRO” included the assumption that it was generated by a multicategory (i.e. every morphism with target x 1x nx_1\otimes\cdots\otimes x_n is a tensor product of morphisms with target x ix_i), nowadays people don’t usually include that. So not every PRO is generated by a multicategory.

    • CommentRowNumber19.
    • CommentAuthorSam Staton
    • CommentTimeDec 13th 2017
    • (edited Dec 13th 2017)

    Thanks Mike. Yes, that’s what I meant. (I also prefer the one-sided version than the strict thing I wrote, but I got the impression that you didn’t like one-sided things, perhaps mistakenly.) I’d still like to put a =aa^{\perp\perp}=a, if you don’t mind. So can I put it like this?:

    To give a polycategory with object set VV is to give an entries-only *-polycategory with object set (V+V)(V+V) where inl(v) =inr(v)inl(v)^{\perp}=inr(v) such that a permutation condition holds.

    (I think the permutation condition is that the presheaf on F(V+V)F(V+V) comes from a presheaf on F(V)×F(V)F(V)\times F(V).)

    I did think this would be a free construction, left adjoint to a forgetful functor (EntriesOnly-*Poly) \to(Poly), but I haven’t checked.

    • CommentRowNumber20.
    • CommentAuthorMike Shulman
    • CommentTimeDec 14th 2017

    In general I prefer two-sided things, but I prefer honestly one-sided things over one-sided things that are pretending to be two-sided. (-:

    Would you like to make star-polycategory?