{"id":594,"date":"2008-02-10T21:28:08","date_gmt":"2008-02-10T21:28:08","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/02\/10\/abstract-algebra-and-computation-monoids\/"},"modified":"2008-02-10T21:28:08","modified_gmt":"2008-02-10T21:28:08","slug":"abstract-algebra-and-computation-monoids","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/02\/10\/abstract-algebra-and-computation-monoids\/","title":{"rendered":"Abstract Algebra and Computation – Monoids"},"content":{"rendered":"

In the last couple of posts, I showed how we can start looking at group
\ntheory from a categorical perspective. The categorical approach gives us a
\ndifferent view of symmetry that we get from the traditional algebraic
\napproach: in category theory, we see symmetry from the viewpoint of
\ngroupoids – where a group, the exemplar of symmetry, is seen as an
\nexpression of the symmetries of a simpler structure.<\/p>\n

We can see similar things as we climb up the stack of abstract algebraic
\nconstructions. If we start looking for the next step up in algebraic
\nconstructions, the rings<\/a>, we can see a very different view of
\nwhat a ring is.<\/p>\n

Before we can understand the categorical construction of rings, we need
\nto take a look at some simpler constructions. Rings are expressed in
\ncategories via monoids. Monoids are wonderful things in their own right, not
\njust as a stepping stone to rings in abstract algebra. <\/p>\n

What makes them so interesting? Well, first, they’re a solid bridge
\nbetween the categorical and algebraic views of things. We saw how the
\ncategory theoretic construction of groupoids put group theory on a nice
\nfooting in category theory. Monoids can do the same in the other direction:
\nthey’re in some sense the abstract algebraic equivalent of categories.
\nBeyond that, monoids actually have down-to-earth practical applications –
\nyou can use monoids to describe computation, and in fact, many of the
\nfundamental automatons that we use in computer science are, semantically,
\nmonoids.<\/p>\n

<\/p>\n

Let’s start with the algebraic view – we’ll look at that, and then we’ll
\nshift gears and see how it looks categorically. In terms of abstract
\nalgebra, a monoid is an algebraic structure which captures the basic idea of
\nfunction composition<\/em>. That should be ringing some bells – the
\nfundamental concept of category theory is an abstract view of function
\ncomposition!<\/p>\n

A monoid is, like a group, a set of values with a single binary
\noperation. The monoid is a simpler construct though – since all it captures
\nis the idea of composition, it doesn’t need inverses. For a monoid, we say
\nthat it’s a set of values, M, and a binary operation º, with three
\nproperties:<\/p>\n

    \n
  1. Closure<\/em>: ∀a,m∈M: aºb ∈ M<\/li>\n
  2. Identity<\/em>: ∃ i∈M : ∀f∈M : iºf = fºi = f.<\/li>\n
  3. Associativity<\/em>: ∀ a,b,c∈M: (aºb)ºc = aº(bºc).<\/li>\n<\/ol>\n

    That’s really it. If you think of those properties in terms of functions
    \nand function composition, they all make really good sense. They’re looking
    \nat the most canonical form of functions – so all functions are treated as
    \nbeing, roughly, functions from natural numbers to natural numbers. Closure
    \nsays that if I’ve got two simple total functions a and b, then composing a
    \nand b is also a simple total function. Identity says that there’s a function
    \nf(x)=x which composes properly. And associativity says shifting the order in
    \nwhich I evaluate compositions doesn’t change the resulting composed
    \nfunction. Those are all very natural properties of function composition.<\/p>\n

    What happens if we treat a monoid like a group, and try to use it as an
    \naction? The answer is near and dear to the hearts of computer science folks
    \nlike me: what you get is basically a finite state machine!<\/p>\n

    Take a monoid, (M,º). We can define an action<\/em> of the
    \nmonoid on a set S. The action is an operation *:M×S→S – that is,
    \nfrom a value in M and a value in S to a value in S. This monoid
    \naction<\/em> of M on S has two properties – which are basically just
    \nextensions of the monoid properties through the action:<\/p>\n

      \n
    1. Identity<\/em>: ∀s∈S, i*s=s.<\/li>\n
    2. Associativity<\/em>: ∀a,b∈M, ∀s∈S: a*(b*s) = (aºb)*s.<\/li>\n<\/ol>\n

      What’s that mean? What we’ve done is add function application<\/em>
      \nto the monoid. The monoidal operation is the application of the functions in
      \nM. <\/p>\n

      So, what do we get if we have a collection of related composable
      \nfunctions that can be applied to particular set of values?<\/p>\n

      An automaton – that is, a mathematical model of a computing device.<\/p>\n

      How’s that an automaton?<\/p>\n

      With the monoidal operator, each member of the monoid is a
      \nfunction<\/em>, which maps a values to values. Monoidal composition
      \nchains those functions together. In terms of automata, each member of the
      \nmonoid is a step<\/em> in a computation. Monoidal composition is chaining
      \nthe steps of a computation in the automaton together in sequence. It’s not
      \nquite full computation yet – but it’s a huge step towards it, in an
      \nextremely simple form.<\/p>\n

      Think about it just a tad more. Remember lambda
      \ncalculus<\/a>? Lambda calculus is a tool from logic for describing
      \ncomputation in terms of nothing but functions. Guess what? We’ve just
      \nrecreated a substantial part of lambda calculus coming at it from the
      \ndirection of abstract algebra.<\/p>\n

      I’ll have more to say about that in future posts – but first I’ll need
      \nto show you what this all looks like in terms of category theory – because
      \nthe next big step is clearest in category land.<\/p>\n","protected":false},"excerpt":{"rendered":"

      In the last couple of posts, I showed how we can start looking at group theory from a categorical perspective. The categorical approach gives us a different view of symmetry that we get from the traditional algebraic approach: in category theory, we see symmetry from the viewpoint of groupoids – where a group, the exemplar […]<\/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":[69],"tags":[],"class_list":["post-594","post","type-post","status-publish","format-standard","hentry","category-abstract-algebra"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-9A","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/594","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=594"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/594\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=594"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=594"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}