{"id":1753,"date":"2012-04-02T20:07:32","date_gmt":"2012-04-03T00:07:32","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1753"},"modified":"2020-08-04T09:16:38","modified_gmt":"2020-08-04T13:16:38","slug":"categorical-equalizers","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2012\/04\/02\/categorical-equalizers\/","title":{"rendered":"Categorical Equalizers"},"content":{"rendered":"

Category theory is really all about building math using composition. Everything we do, we do it by defining things completely in terms of composition. We’ve seen a lot of that. For example, we defined subclasses (and other sub-things) in terms of composition. It sounds strange, but it took me an amazingly long time to really grasp that. (I learned category theory from some not-very-good textbooks, which were so concerned with the formalisms that they never bothered to explain why any of it mattered, or to build any intuition.)<\/p>\n

One thing that’s really important that we haven’t talked about yet is equality<\/em>. In category theory, we define equality on arrows using something called a pullback<\/em>. We’ll use that notion of equality for a lot of other things – like natural transformations. But before we can do pullbacks, we need to look at a weaker notion of arrow equality – something called the equalizer<\/em> of a pair of arrows.<\/p>\n

As part of my attempt to be better than those books that I complained about, we’ll start with intuition, by looking at what an equalizer is in terms of sets. Suppose we have two functions f, g : A \\rightarrow B.<\/p>\n

Now, in addition, suppose that they have a not-empty intersection: that is, that there’s some set of values x \\in A for which f(x) == g(x). We can take that set of values, and call it C. C is the equalizer<\/em> of the functions f and g. It’s the largest set C where if you restrict the inputs to the functions
\nto members of C, then f and g are equal.<\/p>\n

Now, let’s look at the category theoretic version of that. We have objects<\/em> A and B. We have two arrows f, g : A \\rightarrow B. This is the category analogue of the setup of sets and functions from above.<\/p>\n

To get to the equalizer, we need to add an object C which is a subobject<\/em> of A (which corresponds to the subset of A on which f and g agree in the set model).<\/p>\n

The equalizer of A and B is the pair of the object C, and an arrow i : C \\rightarrow A. (That is, the object and arrow that define C as a subobject of A.) This object and arrow must satisfy the following conditions:<\/p>\n

    \n
  1. f \\circ i = g \\circ i<\/li>\n
  2. (\\forall j: D \\rightarrow A) if f \\circ j = g \\circ j then (\\exists 1 k : D \\rightarrow C) such that i \\circ k = j<\/li>\n<\/ol>\n

    That second one is the mouthful. What it says is:<\/p>\n

      \n
    • Suppose that I have any arrow j from some other object D to A:<\/li>\n
    • if f and g agree on composition about j, then there can only be one<\/em> unique<\/em> arrow from C to D which composes with j to get to A.<\/li>\n<\/ul>\n

      In other words, (C, i) is a selector<\/em> for the arrows on which A and B agree; you can only compose an arrow to A in a way that will compose equivalently with f and g to B if you go through (C, i).<\/p>\n

      Or in diagram form, k in the following diagram is necessarily unique:<\/p>\n

      \"equalizer.jpg\"<\/p>\n

      There are a couple of interesting properties of equalizers that are worth mentioning. The morphism in an equalizer is a always<\/em> monic arrow (monomorphism); and if it’s epic (an epimorphism), then it must also be iso (an isomorphism).<\/p>\n

      The pullback is very nearly the same construction as the equalizer we just looked at; except it’s abstracting one step further.<\/p>\n

      Suppose we have two arrows pointing to the same target: f : B \\rightarrow A and g : C \\rightarrow A. Then the pullback of of f and g is the triple of an object and two arrows (B \\times_A C, p : B \\times_A C \\rightarrow B, q : B\\times_A C \\rightarrow C). The elements of this triple must meet the following requirements:<\/p>\n

        \n
      1. f \\circ p = g \\circ q<\/li>\n
      2. (f \\circ p) : B\\times_A C \\rightarrow A<\/li>\n
      3. for every triple (D, h : D \\rightarrow B , k : D \\rightarrow C), there is exactly one unique arrow \\langle h,k \\rangle_A : D \\rightarrow B \\times_A C where p \\circ \\langle h,k \\rangle_A = h, and q \\circ \\langle h,k \\rangle_A = k.As happens so frequently in category theory, this is clearer using a diagram.\n

        \"pullback.jpg\"<\/p>\n

        If you look at this, you should definitely be able to see how this corresponds to the categorical equalizer. If you’re careful and clever, you can also see the resemblance to categorical product (which is why we use the \u00d7A<\/sub> syntax). It’s a general construction that says that f and g are equivalent with respect to the product-like object B\u00d7A<\/sub>C.<\/p>\n

        Here’s the neat thing. Work backwards through this abstraction process to figure out what this construction means if objects are sets and arrows are functions, and what’s the pullback of the sets A and B?<\/p>\n

        { (x,y) \\in A \\times B : f(x) = g(y) }<\/p>\n

        Right back where we started, almost. The pullback is an equalizer; working it back shows that.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

        Category theory is really all about building math using composition. Everything we do, we do it by defining things completely in terms of composition. We’ve seen a lot of that. For example, we defined subclasses (and other sub-things) in terms of composition. It sounds strange, but it took me an amazingly long time to really […]<\/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],"tags":[],"class_list":["post-1753","post","type-post","status-publish","format-standard","hentry","category-category-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-sh","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1753","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=1753"}],"version-history":[{"count":3,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1753\/revisions"}],"predecessor-version":[{"id":3868,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1753\/revisions\/3868"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1753"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1753"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1753"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}