Not signed in (Sign In)

Start a new discussion

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

(0 1)-category-theory 2-category 2-category-theory 2-monad abelian-categories accessible adjoint algebra algebraic algebraic-geometry analysis arithmetic beauty book bug bundle categories category category-theory chern-simons-theory cohesion cohesive-homotopy-type-theory cohomology combinatorics complex-geometry conference connection constructive constructive-mathematics cosmology database deformation-theory descent differential differential-cohomology differential-geometry duality enriched enriched-category-theory enrichment examples factorization-system fiber fibration forms foundation foundations functional-analysis functor galois-theory gauge-theory gebra general topology geometric geometric-quantization geometry gravity group-theory higher higher-algebra higher-category-theory higher-geometry higher-lie-theory higher-topos-theory history homological homological-algebra homotopy homotopy-theory homotopy-type-theory homtopy-type-theory infinity-groupoid integration-theory internal-categories kan lie lie-algebras lie-theory limit limits linear linear-algebra locale localization localization-theory logic manifolds mathematics measure measure-theory mechanics meta modal-logic model model-category-theory monoidal monoidal-category monoidal-category-theory morphism n-groups newpage noncommutative noncommutative-geometry object operator operator-algebra order-theory philosophy physics predicative pretopology pro-object probability-theory quantum quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry set set-theory sheaf simplicial site space stable-homotopy-theory stack string string-theory subobject supergeometry symplectic-geometry tannaka tensor terminology theory topologica-quantum-field-theory topology topos topos-theory torsor tqft type type-theory universal weighted-limit

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

nLab > Latest Changes: finite category

Bottom of Page

1 to 29 of 29

  1.  
    • CommentRowNumber1.
    • CommentAuthorEric
    • CommentTimeOct 20th 2009
    This comment is invalid XHTML+MathML+SVG; displaying source. <div> <p>I added a statement to <a href="http://ncatlab.org/nlab/show/finite+category">finite category</a> that needs blessing by the experts.</p> <blockquote> For any <a href="http://ncatlab.org/nlab/show/finite+category">finite category</a> <img src="http://nforum.mathforge.org/extensions//vLaTeX/cache/latex_ca43fb5496104dcafda44acbe4014b0e.png" title="C" style="vertical-align: -20%;" class="tex" alt="C"/>, there is a <a href="http://ncatlab.org/nlab/show/directed+graph">directed graph</a> <img src="http://nforum.mathforge.org/extensions//vLaTeX/cache/latex_0643966166b879e3e23697a6b846efd7.png" title="G" style="vertical-align: -20%;" class="tex" alt="G"/> such that its <a href="http://ncatlab.org/nlab/show/quiver">quiver</a> <img src="http://nforum.mathforge.org/extensions//vLaTeX/cache/latex_488df68f0543043cfe8c6e7d68900662.png" title="Q(G)" style="vertical-align: -20%;" class="tex" alt="Q(G)"/> is equivalent to <img src="http://nforum.mathforge.org/extensions//vLaTeX/cache/latex_ca43fb5496104dcafda44acbe4014b0e.png" title="C" style="vertical-align: -20%;" class="tex" alt="C"/>. </blockquote> <p>I wanted to say "is equal to" but was scared in this crowd :)</p> </div>
    • CommentRowNumber2.
    • CommentAuthorEric
    • CommentTimeOct 20th 2009
    • (edited Oct 20th 2009)

    One of the reasons for me to add this is that I wanted to think about a functor

    F: FinCat \to DiGraph

    that forgets morphisms that are composites and keeps only those morphisms that cannot be written as a composite with some other non-identity morphism. These composite morphisms can be recovered from the graph by constructing its quiver. In other words, given a finite category, I want the smallest graph whose quiver is equivalent to the original finite category.

    By the way, are there nontrivial endomorphism allowed in a finite category? If a non-identity endomorphism f:X\to X is in a finite category, then so is f^2 and f^3 etc leading to an infinite number of morphisms. So to keep things finite, it seems you cannot have endomorphisms. Is that correct? What about if f^2 = 1? In other words, if f^3 = f, are they considered different morphisms?

    Thanks!

    • CommentRowNumber3.
    • CommentAuthorTobyBartels
    • CommentTimeOct 20th 2009

    Mike and I have demolished your hopes back at finite category, but your motivation is still interesting. The usual forgetful functor Fin Cat \to Digraph remembers all arrows and simply forgets the commutative diagrams, but one certainly could consider your functor that remembers only objects and ‘irreducible’ arrows. I think that, for a finite category, it's still true that the original category is a quotient of the quiver of this digraph, even though (thanks to nontrivial commutative diagrams) it will usually not actually be equivalent to that quiver.

    You can nontrivial endomorphisms in a finite category, but they must satisfy some nontrivial equation f^n = f^m, such as f^2 = 1 or f^3 = f (which is weaker). Thus, if a digraph has loops, then its quiver will not be a finite category, although some quotients may be.

    • CommentRowNumber4.
    • CommentAuthorEric
    • CommentTimeOct 20th 2009

    Thanks! I moved my "statement" to a "query".

    • CommentRowNumber5.
    • CommentAuthorUrs
    • CommentTimeOct 20th 2009

    There is something close, though: for every category there is a poset such that both are equivalent in the Thomason model structure (do we have an entry on that). Meaning: both have the "same" oo-groupoid as their Kan fibrant replacement.

    • CommentRowNumber6.
    • CommentAuthorEric
    • CommentTimeOct 20th 2009

    I wish I knew the path that takes me from where I am now to where I could understood that last statement gulp :)

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeOct 20th 2009

    In words it means this:

    you can take a category and then freely add weak inverses to all morphisms.

    Meaning: to each morphism that is non-invertible you add a morphism going the other way, which is an inverse up to some new 2-morphism which you throw in, which is invertible up to a new 3-morphism and so ever on and on.

    The result is an oo-category that is an oo-groupoid. And the statement is: up to equivalence of oo-groupoids, every oo-groupoid is obtained this way alreday when starting with a category that is a poset.

    A poset is not quite a free category on a graph, but it is in a qay a category with very little structure. One way to say this precisely is to realize that it is a (0,1)-category, so hardly more than a set.

    Now remember that posets are also the natural candidate for encoding (globally hyperbolic) pseudo-riemannian spaces by abstract nonsense. Then I guess you may like this.

    • CommentRowNumber8.
    • CommentAuthorEric
    • CommentTimeOct 20th 2009
    • (edited Oct 20th 2009)

    I like it I like it. I just wish I understood it better :)

    Let me try to retype what you wrote to see if I get it.

    Start with a poset. For each morphism, add a morphism that is inverse up to 2-morphisms that are invertible up to 3-morphisms that are invertible up to 4-morphism etc etc.

    We end up with an oo-groupoid.

    Not only that, but EVERY oo-groupoid has a poset at its heart for which this construction reproduces that oo-groupoid.

    Is that primordial poset unique? Given an oo-groupoid, is it possible to extract this poset?

    That does sound fascinating, but I'm sure I'm at least partially confused.

    • CommentRowNumber9.
    • CommentAuthorTobyBartels
    • CommentTimeOct 20th 2009

    Not only that, but EVERY oo-groupoid has a poset at its heart for which this construction reproduces that oo-groupoid.

    That's not what Urs said, however. He said that every oo-groupoid that has a category at its heart for which this construction reproduces that oo-groupoid also has a poset at its heart for which this construction reproduces that oo-groupoid. But there may be yet other oo-groupoids. (Is there a clear counterexample, Urs?)

    • CommentRowNumber10.
    • CommentAuthorEric
    • CommentTimeOct 21st 2009
    • (edited Oct 21st 2009)

    Is there some kind of "adjoint" that goes the other way? Instead of starting with a category and constructing an oo-groupoid, could you construct an oo-category from an oo-groupoid?

    I am thinking of diamonation. If we start with a simple groupoid G

    \bullet\rightleftarrows\bullet

    we might construct a directed cylinder G_0\times\mathbb{Z} and force each morphism to require one "tick" of the discrete clock. We'd get a category which is an infinite criss cross ladder pattern with no real inverses. If that makes any sense.

    I think of groupoids as "spaces" and categories as "spacetimes" so taking a category and constructing a groupoid, to me, feels like "projecting from spacetime down to space along time".

    I'm interested in the opposite of extruding a space into spacetime by forming a directed cylinder.

    • CommentRowNumber11.
    • CommentAuthorMike Shulman
    • CommentTimeOct 21st 2009

    It is true that every ?-groupoid can be generated by freely adding inverses to a category. That's the content of the Quillen equivalence between Thomason's model structure for categories and the standard model structure on simplicial sets.

    However, I'm actually not sure whether I believe that posets suffice. I've heard this quoted before, but I believe the justification is that Thomason claims that all the cofibrant objects in his model structure are posets, whereas I've also heard that there is an error in that argument. I haven't read it carefully myself.

    • CommentRowNumber12.
    • CommentAuthorUrs
    • CommentTimeOct 21st 2009

    Thanks, Mike.

    After I posted this yesterday I thought to myself: what actually is a reference for the poset statement? I know this statement from hearing it from people who should know.

    Hm, our entry Thomason model structure could be slightly more detailed... :-)

    • CommentRowNumber13.
    • CommentAuthorUrs
    • CommentTimeOct 21st 2009

    re Eric's question:

    certainly what you indicate is a valid operation: you can take any oo-groupoid and take its cartesian product (as (oo,1)-categories) with some poset (say that of integers, which you indicated) to get an (oo,1)-category whose morphisms are generated from those that are part of the original oo-groupoid and those that "increase poset time", if you wish.

    I'd think it is also generally posisble then to throw out those morphism that don't "increase poset time". i.e. all cartesian products of an oo-groupoid morphism with a poset identity morphism. This is what you have in mind.

    But right this moment I can't quite seem to think of a nice abstract way to say this. Hmmm.

    • CommentRowNumber14.
    • CommentAuthorEric
    • CommentTimeOct 21st 2009
    I left a question about "walking commutative square" at finite category.
    • CommentRowNumber15.
    • CommentAuthorUrs
    • CommentTimeOct 21st 2009

    I added a - supposedly helpful - remark to the discussion at finite category.

    • CommentRowNumber16.
    • CommentAuthorEric
    • CommentTimeOct 22nd 2009

    I added some figures and some more thoughts. I think I'm starting to understand some things. Thank you!

    • CommentRowNumber17.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 22nd 2009

    Added some more comments on top of what Eric put down.

    • CommentRowNumber18.
    • CommentAuthorTobyBartels
    • CommentTimeOct 22nd 2009

    I'd think it is also generally posisble then to throw out those morphism that don't "increase poset time". i.e. all cartesian products of an oo-groupoid morphism with a poset identity morphism. This is what you have in mind.

    You can't quite throw out all pairings (not 'products'!) of an \infty-groupoid morphism with a poset identity morphism, since you must keep the pairings of identity \infty-groupoid morphisms with identity poset morphisms, which are the identity morphisms in the resulting (\infty,1)-category.

    But notice that this is evil; applying this to equivalent \infty-groupoids may lead to inequivalent (\infty,1)-categories. In particular, Eric's original \infty-groupoid is contractible (equivalent to the point), yet the resulting (\infty,1)-groupoid is not equivalent to the poset of integers.

    I see two ways to deal with this:

    • Accept it; this means that you are not really starting with a space up to weak homotopy equivalence but instead a space equipped with a collection of points to take as the objects of a semistrict \infty-groupoid.
    • Keep the pairings that Urs said to throw out. Then Eric's directed cylinder will have a bunch of horizontal arrows as well as the diagonal ones. And if you start with a contractible space, then the resulting (\infty,1)-groupoid is equivalent (as a weak (\infty,1)-groupoid) to the poset \mathbb{Z} itself.
    • CommentRowNumber19.
    • CommentAuthorEric
    • CommentTimeOct 22nd 2009
    • (edited Oct 22nd 2009)

    I wouldn't mind horizontal morphisms if they were pairings of identity morphisms. Does that help?

    The important thing I'd like to maintain is that each non-identity morphism of the original category should "advance the clock" by one tick in the new category. It is ok (and expected) that identity morphisms in the original category do not advance the clock.

    PS: Think zitterbewegung.

    • CommentRowNumber20.
    • CommentAuthorTobyBartels
    • CommentTimeOct 22nd 2009

    I wouldn't mind horizontal morphisms if they were pairings of identity morphisms. Does that help?

    Not with the evil.

    It's a good thing that you don't mind horizontal morphisms if they're pairings of identity morphisms; if you want an (\infty,1)-category at all, then you must have identity morphisms, so you've got no choice about that! It's the nonidentity horizontal morphisms that are the problem.

    If I understand your vision, you really need to take my first option (accept it); then you're not really starting from a space (up to weak homotopy equivalence) or an \infty-groupoid (up to equivalence) but something like a semistrict \infty-groupoid up to some strict notion of equivalence (semistrict equivalence?).

    In particular, if you happen to start with a groupoid, then you care about it up to isomorphism, not just up to equivalence.

    • CommentRowNumber21.
    • CommentAuthorEric
    • CommentTimeOct 22nd 2009
    • (edited Oct 22nd 2009)

    To make things simpler, I'm happy to confine attention to groupoids with a finite number of objects if that helps.

    One thing I might try is to "forget all non-trivial inverses", i.e. pick a non-identity morphism and remove its inverse. Continue until no non-identity morphism has an inverse. This is a category (Edit: We probably need to be more careful when deleting morphisms to make sure that the result is still actually a category, but that shouldn't be hard to do.) and I think we can recover the original groupoid via Kan fibrant replacement.

    If this category is finite (which I'm happy to confine attention to), then we can find a directed n-graph that recovers this finite category (in the way I'm trying to work out at finite category).

    So we've effectively gone from a groupoid to directed graph. I'm also happy (Edit: No so sure I'm happy about this on second thought.) to confine attention to finite categories in which all paths commutes (is that a preorder?).

    NOW, we can construct the cyclinder G\times\mathbb{Z}. THEN perform the operation of moving the target of each morphism up one time step. Reinsert morphisms from the target of each old morphism to the source of the old morphism, but UP one more time step so that the round trip along a morphism and its "inverse" requires TWO time steps. THEN, we can form the quiver of THIS graph.

    I wonder if that gives you anything interesting? :)

    I think that if we do this, then we could project the category down along \mathbb{Z} to recover the original groupoid.

    • CommentRowNumber22.
    • CommentAuthorTobyBartels
    • CommentTimeOct 22nd 2009

    So we've effectively gone from a groupoid to directed graph.

    Again, you've done this in an evil way; you've really gone from a strict groupoid to a directed graph. That's OK, as long as you really care about your groupoid up to isomorphism and not just up to equivalence; it's just that, if you think of your groupoid as coming from a space, you must be caring about more than the space's weak homotopy type.

    confine attention to finite categories in which all paths commutes (is that a preorder?)

    Yes, it is precisely a finite preorder.

    I've also got a new comment at finite category.

    • CommentRowNumber23.
    • CommentAuthorUrs
    • CommentTimeOct 24th 2009
    • (edited Oct 24th 2009)

    Eric,

    I just lookeed at the entry again: maybe you could change one of your graphics, then all four would be correct and could usefully be moved out of the discussion section into the main entry, or the entry on quiver:

    namely the figure labeled "1-quiver" isn't quite right. The equality sign in the middle should be an inequality sign. Currently what is depicted is the "walking commuting square" which is not a free category.

    We should also beware that we here are probably the only people in the world who systematically use "quiver" as a synonym for "free category". I think this is well justied by the way quivers are actually used. Instead of talking abut quivers, people ought to be talking about free categories! But I am not sure if that implies that we should coversely say quiver for a free category. I would prefer not to say quiver much at all.

    Finally, concerning higher free categories, there is a bit of blog disucssion at freely generated omega-categories about that (which is synonymously related to the computads that Todd mentions in the discussion section at finite category).

    • CommentRowNumber24.
    • CommentAuthorTobyBartels
    • CommentTimeOct 24th 2009

    I don't like the term ‘free category’, because by default I expect that to mean the free category on a set (which is a discrete category). I would either say ‘free category on a graph’ (meaning a directed pseudograph as my version of graph, hopefully clear from context) or, of course, ‘quiver’.

    • CommentRowNumber25.
    • CommentAuthorUrs
    • CommentTimeOct 24th 2009

    Right, free category on a graph.

    • CommentRowNumber26.
    • CommentAuthorMike Shulman
    • CommentTimeOct 24th 2009

    I don't like the term ‘free category’, because by default I expect that to mean the free category on a set

    That's interesting; I don't expect that. Free categories on sets are fairly uninteresting, and besides we already have a word for them, namely "discrete." I would expect "free category" to mean the clearly more interesting and useful notion of a free category on a directed graph.

    • CommentRowNumber27.
    • CommentAuthorTobyBartels
    • CommentTimeOct 24th 2009

    I guess when I see the word ‘free’ I just take it to have a standard meaning (albeit relative to some forgetful functor to Set, but that's usually obvious) rather than one that depends on what is interesting and useful.

    • CommentRowNumber28.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 24th 2009

    It feels funny to me to say just "free category" rather than "free category on a ___", but my own default would be to take ___ = "directed graph". In general I think I might default to ____ = "set" only if the forgetful functor to Set is monadic, and otherwise default to whatever is the "most obvious" monadic functor lying around.

    • CommentRowNumber29.
    • CommentAuthorMike Shulman
    • CommentTimeOct 24th 2009

    I guess when I see the word ‘free’ I just take it to have a standard meaning (albeit relative to some forgetful functor to Set, but that's usually obvious)

    Of course, there are multiple forgetful functors from Cat to Set. We can take a category to its set of objects, or to its set of morphisms, or even to its set of isomorphism classes of objects. It's not clear to me that the first is more obvious than the others. The second one has the advantage of being faithful.

    I think I'm with Todd, that "free" defaults to me for the most obvious monadic functor lying around, and for me the functor from Cat to DiGraph is the most obvious monadic functor defined on Cat.

1 to 29 of 29

  1.  
Add your comments
  • Please login, or your comments will be posted as "Guest".
     
     
     
     
     
    Type the two words.
     
     
    Get a new recaptcha
    Get an audio challenge
    Help
     
     
     
  • Format comments as (Help) (Help)
 
Back to Discussions Top of Page