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.
    • CommentAuthorRodMcGuire
    • CommentTimeDec 22nd 2014
    • (edited Dec 22nd 2014)

    Is there a different notion of subobject in a category that uses epis rather than monos? (which I am here calling cosubobject for lack of any better term)

    Here is a crude definition of subobject (mono):

    When an object, oo, consists of sets a,b,ca, b, c, then a subobject of it, oo', consists of sets a,b,ca', b', c' along with injections of them into those of oo, namely ia:aaia: a' \to a, ib:bbib: b' \to b', and ic:ccic: c' \to c .

    The co-definition replaces the injections with the surjections: sa:aasa: a \to a', sb:bbsb: b \to b', and sc:ccsc: c \to c' .

    Conceptually the standard mono definition forms subobjects by throwing away elements of sets while the epi definition forms them by merging elements together.

    Both definitions seem to give the same results on the category SetSet.

    The second seems to work better when the objects are graphs. Say I define an type of edge labeled directed graph object that consists of sets verts,arrows,namesverts, arrows, names where each vertvert has one outgoing arrowarrow for every element of namesnames.

    arrows:verts×namesvertsarrows: verts \times names \to verts

    (this is just an action of namesnames on vertsverts. However the nLab page action is so abstract it doesn’t mention actions of sets, much less discuss subobjects of actions.)

    Under the “throw away” definition, it is hard to form subobjects because if you throw away a vertvert then you have to also throw away each arrowarrow that points to it, the vertverts those arrowarrows come from, and so on. However throwing away a namename is simple - you only also have to throw away the arrowarrows with that namename and the deletion doesn’t cascade.

    Under “merge together”, graph/action subobjects may make more sense. If you merge v 1v_{1} and v 2v_{2} then you have to merge the arrowarrows coming from them by namename, and to merge same namenamed arrowarrows a 1a_{1} and a 2a_{2} you have to merge the vertverts they point to. Merging namenames is also somewhat simple.

    The epi definition seems to give a better notion of subgraph, at least for what I am working on, though I might prefer a definition where vertverts and arrowarrows are merged while namenames are thrown away.

    Then again I’m no graph theorist and may be confused about subobjects.

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeDec 22nd 2014

    Probably the word you’re looking for is “quotient”. I’m not sure what you mean by “give the same results on Set”, though; the collection of subsets of a given set is not the same as the collection of its quotients.

    • CommentRowNumber3.
    • CommentAuthorThomas Holder
    • CommentTimeDec 22nd 2014
    • (edited Dec 22nd 2014)

    It might be useful in this context to have a look at Sebastiano Vigna’s nice ’guided tour in the topos of graphs’ which discusses subobjects and labelled graphs from a topos theory perspective (pdf). Further discussion of labelled reversible graphs can be found in Lawvere’s ’qualitative distinctions’ paper (see the references e.g. at quality type). Another classic is Bumby/Latch ’categorical constructions in graph theory’ (easy to find online).

    For an ’action of a set’ you might consult a text on automata theory (categorically this was ’pioneered’ by Michael Arbib, Ernie Manes and Joseph Goguen et al.). The structures go then by the name of ’labelled transition system’.

    Vigna shows that labelled transition systems are the separated objects in the topos of labelled graphs hence they form a quasi topos which suggests that it might be more natural to consider strong subobjects in this context than subobjects.

    • CommentRowNumber4.
    • CommentAuthorRodMcGuire
    • CommentTimeDec 22nd 2014

    Probably the word you’re looking for is “quotient”.

    Thanks Mike. I’ll take a while to digest that. And also thank you Thomas.

    Meanwhile I’ve added the below to the Idea section of action#idea as a simpler intro before jumping into delooping. Maybe some of the text in the footnote should be incorporated into the body, and I haven’t changed anything that follows to jibe with it. I made a nForum post action if this addition needs any discussion.

    The simplest notion of action involves one set, XX, acting on another YY as a the function act:X×YYact\colon X \times Y \to Y. This can be curried as act^:YY X \hat{act}\colon Y \to Y ^ X where Y XY ^ X is the (monoidal) set of functions from XX to YY.1

    Generalized notions of action use entities from categories other than SetSet and involve an exponential object such as Y XY ^ X.

    1. In the category Set there is no difference between the above left action and the right action actR:Y×XYactR\colon Y \times X \to Y because the product commutes. However for the action of a monoid on a set (sometimes called M-set or M-act) the product of a monoid and a set does not commute so the left and right actions are different. The action of a set on a set is the same as an arrow labeled directed graph arrows:vertices×labelsverticesarrows\colon vertices \times labels \to vertices which specifies that each vertex must have a set of arrows leaving it with one arrow per label, and is also the same as a simple (non halting) deterministic automaton transition:inputs×statesstatestransition\colon inputs \times states \to states

    • CommentRowNumber5.
    • CommentAuthorDavidRoberts
    • CommentTimeDec 23rd 2014

    Are you thinking of taking retractions, in #1, of the monomorphisms? This works in Set, and some other categories, but not always. And the second implies the first in Set only in the presence of AC (or more generally, all epis split). From a set theory perspective monos give the relation \leq on cardinalities, which epis give the relation *\leq^*.