{"id":586,"date":"2008-01-24T16:12:09","date_gmt":"2008-01-24T16:12:09","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/01\/24\/capturing-more-symmetry-using-categories-groupoids\/"},"modified":"2008-01-24T16:12:09","modified_gmt":"2008-01-24T16:12:09","slug":"capturing-more-symmetry-using-categories-groupoids","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/01\/24\/capturing-more-symmetry-using-categories-groupoids\/","title":{"rendered":"Capturing More Symmetry using Categories: Groupoids"},"content":{"rendered":"

Today’s entry is short, but sweet. I wanted to write something longer, but I’m very busy at work, so this is what you get. I think it’s worth posting despite its brevity.<\/p>\n

When we look at groups, one of the problems that we can notice is that there are things
\nthat seem to be symmetric, but which don’t work as groups. What that means is that despite the
\nclaim that group theory defines symmetry, that’s not really entirely true. My favorite example of this is the fifteen puzzle.<\/p>\n

\"fifteen.png\"<\/p>\n

The fifteen puzzle is a four-by-four grid filled with 15 tiles, numbered from 1 to 15, and one empty space. You can make a move in the puzzle by sliding a tile adjacent to the empty
\nspace into the empty. In the puzzle, you scramble up the tiles, and then try to move them back so that they’re in numerical order. The puzzle, in its initial configuration, is shown to the right.<\/p>\n

If you look at the 15 puzzle in terms of configurations<\/em> – that is, assignments of the pieces to different positions in the grid – so that each member of the group describes a single tile-move in a configuration, you can see some very clear symmetries. For example, the moves that are possible when the empty is in any corner are equivalent to the moves that are possible when the empty is in any other corner. The possible moves when the space is in any given position are the same except for the labeling of the tiles around them. There’s definitely a kind of symmetry there. There are also loops – sequences of moves which end in exactly the same state as the one in which they began. Those are clearly symmetries.<\/p>\n

But it’s not a group. In a group, the group operation most be total – given any pair of values x and y in the group, it must be possible to combine x and y via x+y. But with the 15 puzzle, there moves that can’t be combined with other moves. If x = “move the ‘3’ tile from square 2 to square 6”, and y = “move the ‘7’ tile from square 10 to square 11”, then there’s no meaningful value for “x+y”; the two moves can’t be combined.<\/p>\n

<\/p>\n

To describe that symmetry, we need a less restrictive version of something like a group. What we end up with is called a groupoid<\/em>. Groupoids are easiest to describe in terms of category theory. Let’s take a look, and see the difference between a category theoretic definition, and the conventional algebraic definition.<\/p>\n

In algebra, we say: A groupoid<\/em> is a collection of objects G, along with an
\noperation “×” and a function -1<\/sup>, where:<\/p>\n

    \n
  1. × must be defined for some<\/em> pairs of members of G.<\/li>\n
  2. For all a, b, and c in G, if (a×b)×c is defined, then it must be equal to
    \na×(b×c). (This is a partial version of the associativity property of
    \ngroups.)<\/li>\n
  3. For all a in G, a-1<\/sup> is defined. (The inverse must be total.)<\/li>\n
  4. For all a and b in G, a×b is defined, then a×b×b-1<\/sup> = a,
    \nand a-1<\/sup>×a×b = b, and only the inverses can have this property. (This is the partial equivalent of the group identity; in a groupoid, you don’t need an identity value which can be combined with every other value in the groupoid; you just have the requirement that there be unique inverses for each value in the groupoid.)<\/li>\n
  5. For all a in G, a×a-1<\/sup> is always defined.<\/li>\n<\/ol>\n

    Now, in terms of category theory: a groupoid is a category in which every arrow is iso.<\/p>\n

    See what I mean? The category theory definitions of the necessary properties of arrows to be a category actually includes most of what makes a groupoid. A groupoid is just a category
    \nwhere every arrow is reversible. If you can understand the basic concept of a category, then
    \nyou’ve pretty much already got groupoids. And it’s very easy to get from groupoids to groups.\n<\/p>\n

    Now, what does the category theoretic understanding of groupoids really tell us? What’s really interesting (at least to me) is that if you take a single object O in a groupoid, and collect all of the morphisms that run from O to O, that object and group of morphisms defines a group. So the groupoid can be understood as a collection of closely related groups. For example, in the fifteen puzzle, starting with a given configuration, every sequence of moves that starts and ends in that configuration are a group of moves. The 15-puzzle groupoid is what you get when you entangle all of those groups together.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Today’s entry is short, but sweet. I wanted to write something longer, but I’m very busy at work, so this is what you get. I think it’s worth posting despite its brevity. When we look at groups, one of the problems that we can notice is that there are things that seem to be symmetric, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[76,26],"tags":[],"class_list":["post-586","post","type-post","status-publish","format-standard","hentry","category-category-theory","category-group-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-9s","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/586","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=586"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/586\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=586"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}