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

Discussion Tag Cloud

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.
    • CommentAuthorPaoloPerrone
    • CommentTimeDec 2nd 2016

    Consider sets and functions. A relation between two sets can then be expressed as a subset of a Cartesian product, in other words, we can define it and describe it using functions.

    Viceversa, can we describe functions using relations as the “fundamental” arrows? That is, can we define and describe functions without using other functions, only relations?

    • CommentRowNumber2.
    • CommentAuthorDavidRoberts
    • CommentTimeDec 2nd 2016
    • CommentRowNumber3.
    • CommentAuthorPaoloPerrone
    • CommentTimeDec 3rd 2016

    Very nice! Thank you!

    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 3rd 2016

    Yes, that functions are precisely left adjoints in the bicategory of relations is a good exercise. Their right adjoints are their relational opposites.

    Try getting a hold of Categories, Allegories by Freyd and Scedrov – allegories take relations as primary and give axiom systems for them. Similarly you should get a hold of some of the literature on cartesian bicategories, e.g. Cartesian Bicategories I by Carboni and Walters.

    • CommentRowNumber5.
    • CommentAuthorDavid_Corfield
    • CommentTimeDec 3rd 2016
    • (edited Dec 3rd 2016)

    Of course we ought to be considering whether such information is adequately represented on the nLab. We have functional relation. Anything clearer at the blog post of #2 than here?

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 3rd 2016

    I added to functional relation some narrative and argumentation, and references including Robin’s blog post, but didn’t labbify to the extent of sticking the arguments in proof environments. Most but not all the points in the blog post were touched upon; on the other hand, some arguments which Robin left to the reader are spelled out.

    • CommentRowNumber7.
    • CommentAuthorKeithEPeterson
    • CommentTimeDec 4th 2016
    • (edited Dec 4th 2016)

    Are adjunctions in Rel internal to a different topos other than Set also functions?

    Edit: internal to, not enriched in.

    • CommentRowNumber8.
    • CommentAuthorJohn Baez
    • CommentTimeDec 4th 2016
    • (edited Dec 4th 2016)

    I’m not sure it makes sense to talk about RelRel “enriched” in another topos, but you can define a bicategory Rel TRel_T of relations internal to any topos TT, and then I believe the adjunctions in Rel TRel_T correspond to morphisms in TT, just as in the case T=SetT = Set.

    I have not checked this, but I think this basic sort of stuff works just as well in any topos.

    Does the same sort of result hold if TT is a regular category? When I mentioned allegories to a couple of famous Australian category theorists, many years ago, one of them sniffed that they’d been subsumed by the theory of regular categories.

    • CommentRowNumber9.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 4th 2016

    Right: the statements when suitably internalized hold in any topos and more generally in any regular category.

    I don’t think the sniffer was entirely accurate. There’s pretty much a perfect dictionary between regular categories and (unitary) tabular allegories (where every arrow is “tabulated” by a span-pair of left adjoints, as in the picture at functional relation). But I do think that allegories cast a slightly different light on things, and can be useful. For example, examples of realizability toposes can be rather neatly described in allegorical terms. Taking a step back, I think it can be useful to consider relations as primary and functions derived, just as it can be useful to consider bimodules as basic in enriched category theory.

    Maybe I’d think it more accurate to say that allegories are something of an acquired taste for certain crowds. To a category theorist, the Freyd modular law on which the whole theory hangs may look a little bizarre, and I have to say I’m spiritually in agreement with Bob Walters where he subordinates the modular law to a “more natural-looking” Frobenius condition which is connected with 2d cobordism theory. Thus, the notion of bicategory of relations, which also takes relations as basic, may seem nicer to category theorists. But to someone more inclined to lattice theory, I can imagine the allegory axioms being pregnant with meaning, and the whole development sort of exciting.

    • CommentRowNumber10.
    • CommentAuthorTobyBartels
    • CommentTimeDec 4th 2016

    From another perspective on the question, SEAR is a development of elementary structural set theory in which binary relations are fundamental and functions are derived.

    • CommentRowNumber11.
    • CommentAuthorMike Shulman
    • CommentTimeDec 4th 2016

    One advantage of allegories over regular categories is that quotients of equivalence relations in allegories (and “framed allegories”) can be described as an enriched weighted colimit therein.

    • CommentRowNumber12.
    • CommentAuthorPaoloPerrone
    • CommentTimeDec 4th 2016

    Thanks Todd Trimble for updating the “functional relation” page, this is all very interesting.

    By the way, what is the higher equivalent of a relation? (Or, what is the categorification of Rel analogous to Cat for Set?)

    • CommentRowNumber13.
    • CommentAuthorMike Shulman
    • CommentTimeDec 4th 2016

    Prof.

    • CommentRowNumber14.
    • CommentAuthorKeithEPeterson
    • CommentTimeDec 4th 2016

    A profunctor.

    • CommentRowNumber15.
    • CommentAuthorPaoloPerrone
    • CommentTimeDec 6th 2016
    • (edited Dec 6th 2016)

    A profunctor is contravariant in one argument. So is the symmetry of Rel only a coincidence in low dimension?

    (Also, what happens to ternary and higher-ary relations?)

    • CommentRowNumber16.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 6th 2016

    Re #15: it’s based on the fact that a set when seen as a discrete category is equivalent to its opposite. You could say that the low dimension is partly to “blame”, but note that a groupoid GG is also equivalent to its opposite, where morphism inversion gives a functorial equivalence G opGG^{op} \to G.

  1. Speaking of which, does anyone if there is a name for the “posetal compromise” between Rel and Prof, i.e., the bicategory whose objects are posets A,BA,B, morphisms M:ABM : A ⇸ B are downwards closed subsets MA op×BM \subseteq A^{op} \times B, and 2-cells MNM \Rightarrow N are inclusions MNM\subseteq N?

    • CommentRowNumber18.
    • CommentAuthorDavid_Corfield
    • CommentTimeDec 7th 2016

    Re #15

    (Also, what happens to ternary and higher-ary relations?),

    do we just take the product of the covariant arguments, and also of the contravariant arguments, and then look at profunctors between these products?

    • CommentRowNumber19.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 7th 2016

    Noam, in the post of Robin Houston linked to above, he calls them “relational profunctors”. Not sure how widespread that is. Personally, I’m content to call them 2-enriched profunctors (and like the word “bimodule” even more than “profunctor”).

  2. Hadn’t read the blog post yet…that’s great, thanks!

    • CommentRowNumber21.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 7th 2016
    • (edited Dec 7th 2016)

    Re #18: that’s what I’d say. In some sense such are subsumed under ordinary profunctors A opBVA^{op} \otimes B \to V where A=A 1A mA = A_1 \otimes \ldots \otimes A_m and B=B 1B nB = B_1 \otimes \ldots \otimes B_n, although there is a faint suggestion of thinking more in terms of composing along morphisms in just one A iA_i or B jB_j at a time, rather than jointly.