Not signed in

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

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorRodMcGuire
   • CommentTimeDec 22nd 2014
   • (edited Dec 22nd 2014)
   • PermaLink
   Author: RodMcGuire
   Format: MarkdownItexIs 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, $o$, consists of sets $a, b, c$, then a subobject of it, $o'$, consists of sets $a', b', c'$ along with injections of them into those of $o$, namely $ia: a' \to a$, $ib: b' \to b'$, and $ic: c' \to c$ . The co-definition replaces the injections with the surjections: $sa: a \to a'$, $sb: b \to b'$, and $sc: 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 $Set$. 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, names$ where each $vert$ has one outgoing $arrow$ for every element of $names$. $$arrows: verts \times names \to verts$$ (this is just an action of $names$ on $verts$. 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 $vert$ then you have to also throw away each $arrow$ that points to it, the $vert$s those $arrow$s come from, and so on. However throwing away a $name$ is simple - you only also have to throw away the $arrow$s with that $name$ and the deletion doesn't cascade. Under "merge together", graph/action subobjects may make more sense. If you merge $v_{1}$ and $v_{2}$ then you have to merge the $arrow$s coming from them by $name$, and to merge same $name$d $arrow$s $a_{1}$ and $a_{2}$ you have to merge the $vert$s they point to. Merging $name$s 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 $vert$s and $arrow$s are merged while $name$s are thrown away. Then again I'm no graph theorist and may be confused about subobjects.

   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, $o$, consists of sets $a, b, c$, then a subobject of it, $o'$, consists of sets $a', b', c'$ along with injections of them into those of $o$, namely $ia: a' \to a$, $ib: b' \to b'$, and $ic: c' \to c$ .

   The co-definition replaces the injections with the surjections: $sa: a \to a'$, $sb: b \to b'$, and $sc: 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 $Set$.

   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, names$ where each $vert$ has one outgoing $arrow$ for every element of $names$.

   $$arrows: verts \times names \to verts$$

   (this is just an action of $names$ on $verts$. 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 $vert$ then you have to also throw away each $arrow$ that points to it, the $vert$s those $arrow$s come from, and so on. However throwing away a $name$ is simple - you only also have to throw away the $arrow$s with that $name$ and the deletion doesn’t cascade.

   Under “merge together”, graph/action subobjects may make more sense. If you merge $v_{1}$ and $v_{2}$ then you have to merge the $arrow$s coming from them by $name$, and to merge same $name$d $arrow$s $a_{1}$ and $a_{2}$ you have to merge the $vert$s they point to. Merging $name$s 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 $vert$s and $arrow$s are merged while $name$s are thrown away.

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

2. • CommentRowNumber2.
   • CommentAuthorMike Shulman
   • CommentTimeDec 22nd 2014
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexProbably 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.

   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.

3. • CommentRowNumber3.
   • CommentAuthorThomas Holder
   • CommentTimeDec 22nd 2014
   • (edited Dec 22nd 2014)
   • PermaLink
   Author: Thomas Holder
   Format: MarkdownItexIt 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](http://arxiv.org/pdf/math/0306394)). 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.

   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.

4. • CommentRowNumber4.
   • CommentAuthorRodMcGuire
   • CommentTimeDec 22nd 2014
   • PermaLink
   Author: RodMcGuire
   Format: MarkdownItex> 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](http://nforum.mathforge.org/discussion/6394/action/) if this addition needs any discussion. > The simplest notion of action involves one set, $X$, acting on another $Y$ as a the function $act\colon X \times Y \to Y$. This can be [[currying|curried]] as $ \hat{act}\colon Y \to Y ^ X $ where $Y ^ X$ is the (monoidal) [[function set|set of functions]] from $X$ to $Y$.[^SetActions] [^SetActions]: In the category [[Set]] there is no difference between the above left action and the right action $actR\colon Y \times X \to Y$ because the product commutes. However for the action of a [[monoid]] on a set (sometimes called [[MSet| 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\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\colon inputs \times states \to states$. > Generalized notions of action use entities from categories other than $Set$ and involve an [[exponential object]] such as $Y ^ X$.

   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, $X$, acting on another $Y$ as a the function $act\colon X \times Y \to Y$. This can be curried as $\hat{act}\colon Y \to Y ^ X$ where $Y ^ X$ is the (monoidal) set of functions from $X$ to $Y$.¹

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

   ---

   1. In the category Set there is no difference between the above left action and the right action $actR\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\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\colon inputs \times states \to states$. ↩

5. • CommentRowNumber5.
   • CommentAuthorDavidRoberts
   • CommentTimeDec 23rd 2014
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexAre 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^*$.

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