{"id":3701,"date":"2019-02-20T12:53:07","date_gmt":"2019-02-20T17:53:07","guid":{"rendered":"http:\/\/www.goodmath.org\/blog\/?p=3701"},"modified":"2019-02-20T20:24:42","modified_gmt":"2019-02-21T01:24:42","slug":"category-theory-lesson-2-basics-of-categorical-abstraction","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2019\/02\/20\/category-theory-lesson-2-basics-of-categorical-abstraction\/","title":{"rendered":"Category Theory Lesson 2: Basics of Categorical Abstraction"},"content":{"rendered":"\n<p>In <a href=\"http:\/\/www.goodmath.org\/blog\/2018\/10\/14\/another-stab-at-category-theory-starting-with-monoids\/\">my last post about category theory<\/a>, I introduced the basic idea of typeclasses, and showed how to implement an algebraic monoid as a typeclass. Then we used that algebraic monoid as an example of how to think with arrows, and built it up into a sketch of category theory\u2019s definition of a monoid. We ended with an ominous looking diagram that illustrated what a categorical monoid looks like.<\/p>\n\n\n\n<p>In this post, we\u2019re going to take a look at some of the formal definitions of the basic ideas of category theory. By the end of this lesson, you should be able to look at the categorical monoid, and understand what it means. But the focus of this post will be on understanding initial and terminal objects, and the role they play in defining abstractions in category theory. And in the next post, we&#8217;ll see how abstractions compose, which is where the value of category theory to programmers will really become apparrent.<\/p>\n\n\n\n<p> Before I really get started: there\u2019s a lot of terminology in category theory, and this post has a lot of definitions. Don\u2019t worry: you don\u2019t need to remember it all. You do need to understand the concepts behind it, but specifically remembering the difference between, say, and endomorphism, and epimorphism, and a monomorphism isn\u2019t important: you can always look it up. (And I\u2019ll put together a reference glossary to help make that easy.)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Defining Categories<\/h2>\n\n\n\n<p>A category is basically a directed graph &#8211; a bunch of dots connected by arrows, where the arrows have to satisfy a bunch of rules.<\/p>\n\n\n\n<p>Formally, we can say that a category consists of a the parts: <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28O%2C%20M%2C%20%5Ccirc%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(O, M, \\circ)' style='vertical-align:1%' class='tex' alt='(O, M, \\circ)' \/>, where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><img src='http:\/\/l.wordpress.com\/latex.php?latex=O&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='O' style='vertical-align:1%' class='tex' alt='O' \/> is a collection of objects. We don\u2019t actually care what the objects are &#8211; the only thing we can do in category theory is look at how the objects related through arrows that connect them. For a category <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/>, we\u2019ll often call this collection Obj(C).<\/li><li><img src='http:\/\/l.wordpress.com\/latex.php?latex=M&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='M' style='vertical-align:1%' class='tex' alt='M' \/> is a collection of <em>arrows<\/em>, often called <em>morphisms<\/em>. Each element of <img src='http:\/\/l.wordpress.com\/latex.php?latex=M&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='M' style='vertical-align:1%' class='tex' alt='M' \/> starts at one object called its <em>domain<\/em> (often abbreviated <em>dom<\/em>), and ending at another object called its <em>codomain<\/em> (abbreviated <em>cod<\/em>). For an arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> that goes from <img src='http:\/\/l.wordpress.com\/latex.php?latex=a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='a' style='vertical-align:1%' class='tex' alt='a' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b' style='vertical-align:1%' class='tex' alt='b' \/>, we\u2019ll often write it as <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3Aa%20%5Crightarrow%20b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:a \\rightarrow b' style='vertical-align:1%' class='tex' alt='f:a \\rightarrow b' \/>. For a category <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/>, we\u2019ll often call this set Mor(C) (for morphisms of C).<\/li><li><img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ccirc&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\circ' style='vertical-align:1%' class='tex' alt='\\circ' \/> is a composition operator. For every pair of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3Aa%20%5Crightarrow%20b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:a \\rightarrow b' style='vertical-align:1%' class='tex' alt='f:a \\rightarrow b' \/>, and <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%3Ab%20%5Crightarrow%20c&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g:b \\rightarrow c' style='vertical-align:1%' class='tex' alt='g:b \\rightarrow c' \/>, there must be an arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%5Ccirc%20f%3A%20a%20%5Crightarrow%20c&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g\\circ f: a \\rightarrow c' style='vertical-align:1%' class='tex' alt='g\\circ f: a \\rightarrow c' \/> called the compositions of <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/>. <\/li><li>To be a category, these must satisfy the following rules:<ol><li><strong>Identity<\/strong>: For every object <img src='http:\/\/l.wordpress.com\/latex.php?latex=o%20%5Cin%20Obj%28C%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='o \\in Obj(C)' style='vertical-align:1%' class='tex' alt='o \\in Obj(C)' \/>, there must be an arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=o&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='o' style='vertical-align:1%' class='tex' alt='o' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=o&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='o' style='vertical-align:1%' class='tex' alt='o' \/>, called the <em>identity<\/em> of <img src='http:\/\/l.wordpress.com\/latex.php?latex=o&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='o' style='vertical-align:1%' class='tex' alt='o' \/>. We\u2019ll often write it as <img src='http:\/\/l.wordpress.com\/latex.php?latex=id_o%3Ao%20%5Crightarrow%20o&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='id_o:o \\rightarrow o' style='vertical-align:1%' class='tex' alt='id_o:o \\rightarrow o' \/>. For any arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3A%20x%20%5Crightarrow%20o%2C%20f%20%5Ccirc%20o%3Df&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f: x \\rightarrow o, f \\circ o=f' style='vertical-align:1%' class='tex' alt='f: x \\rightarrow o, f \\circ o=f' \/>; and for any arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%3Ao%20%5Crightarrow%20y%3A%20o%20%5Ccirc%20g%3Dg&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g:o \\rightarrow y: o \\circ g=g' style='vertical-align:1%' class='tex' alt='g:o \\rightarrow y: o \\circ g=g' \/>. That&#8217;s just a formal way of saying that composing an identity arrow with any other arrow results in the the other arrow.<\/li><li><strong>Associativity:<\/strong> For any set of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3Aw%20%5Crightarrow%20x%2C%20g%3Ax%20%5Crightarrow%20y%2C%20z%3Ay%20%5Crightarrow%20z%3A%20h%20%5Ccirc%20%28g%5Ccirc%20f%29%20%3D%20%28h%5Ccirc%20g%29%5Ccirc%20f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:w \\rightarrow x, g:x \\rightarrow y, z:y \\rightarrow z: h \\circ (g\\circ f) = (h\\circ g)\\circ f' style='vertical-align:1%' class='tex' alt='f:w \\rightarrow x, g:x \\rightarrow y, z:y \\rightarrow z: h \\circ (g\\circ f) = (h\\circ g)\\circ f' \/>.<\/li><\/ol><\/li><\/ul>\n\n\n\n<p>When talking about category theory, people often say that an arrow is a <em>structure preserving mapping <\/em>between objects. We\u2019ll see what that means in slightly more detail with some examples.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignright\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"161\" height=\"157\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/order.jpg?resize=161%2C157\" alt=\"\" class=\"wp-image-3757\"\/><\/figure><\/div>\n\n\n\n<p>A thing that I keep getting confused by involves ordering. Let&#8217;s look at a quick little diagram for a moment. The path from X to Z is <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%20%5Ccirc%20f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g \\circ f' style='vertical-align:1%' class='tex' alt='g \\circ f' \/> &#8211; because <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> comes after <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/>, which (at least to me) looks backwards. When you write it in terms of function application, it&#8217;s <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%28f%28x%29%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g(f(x))' style='vertical-align:1%' class='tex' alt='g(f(x))' \/>. You can read <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%20%5Ccirc%20f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g \\circ f' style='vertical-align:1%' class='tex' alt='g \\circ f' \/> as g <em>after<\/em> f, because the arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> comes after the arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> in the diagram; and if you think of arrows as functions, then it&#8217;s the order of function application.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example: The category Set<\/h3>\n\n\n\n<p>The most familiar example of a category (and one which is pretty canonical in category theory texts) is the category <strong>Set<\/strong>, where the objects are sets, the arrows between them are total functions, and the composition operator is function composition.<\/p>\n\n\n\n<p>That might seem pretty simple, but there\u2019s an interesting wrinkle to <strong>Set.&nbsp;<\/strong><\/p>\n\n\n\n<p>Suppose, for example, that we look at the function <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29%3Dx%5E2&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x)=x^2' style='vertical-align:1%' class='tex' alt='f(x)=x^2' \/> . That\u2019s obviously a function from to <strong>Int<\/strong> to <strong>Int<\/strong>. Since <strong>Int<\/strong> is a set, it\u2019s also an object in the category <strong>Set<\/strong>, and so <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29%3Dx%5E2&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x)=x^2' style='vertical-align:1%' class='tex' alt='f(x)=x^2' \/> is obviously an arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=Int%20%5Crightarrow%20Int&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Int \\rightarrow Int' style='vertical-align:1%' class='tex' alt='Int \\rightarrow Int' \/>. .But there\u2019s also a the set <strong>Int+<\/strong>, which represents the set of non-negative real numbers. <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29%3Dx%5E2&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x)=x^2' style='vertical-align:1%' class='tex' alt='f(x)=x^2' \/> is also a function from <strong>Int+<\/strong> to <strong>Int+<\/strong>. So which arrow represents the function?<\/p>\n\n\n\n<p>The answer is both &#8211; and many more. (It\u2019s also a function from the reals to complex numbers, because every real number is also a complex number.) And so on. A function isn\u2019t quite an arrow: an arrow is a categorical concept of some kind of mapping between two objects. In many ways, you can think of an arrow as something almost like a function with an associated type declaration: you can write many type declarations for a given function; any valid function with a type declaration that is an arrow in <strong>Set<\/strong>.<\/p>\n\n\n\n<p>We\u2019ll be looking at <strong>Set<\/strong> a lot. It\u2019s a category where we have a lot of intuition, so using it as an example to demonstrate category concepts will be useful.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example: The category <strong>Poset<\/strong><\/h3>\n\n\n\n<p><strong>Poset<\/strong> is the category of all partially ordered sets. The arrows between objects in posets are order-preserving functions between partially ordered sets. This category is an example of what we mean by structure-preserving mappings: the composition operator must preserve the ordering property.<\/p>\n\n\n\n<p> For that to make sense, we need to remember what partially ordered set is, and what it means to be an order preserving function. <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A set <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/> is partially ordered if it has a partial less-than-or-equal relation, <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Cle&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\le' style='vertical-align:1%' class='tex' alt='\\le' \/>. This relation doesn&#8217;t need to be total &#8211; some values are less than or equal to other values; and some values can&#8217;t be compared.<\/li><li>A function between two partially ordered sets <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AA%20%5Crightarrow%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:A \\rightarrow B' style='vertical-align:1%' class='tex' alt='f:A \\rightarrow B' \/> is order-preserving if and only if for all values <img src='http:\/\/l.wordpress.com\/latex.php?latex=x%2C%20y%20%5Cin%20A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x, y \\in A' style='vertical-align:1%' class='tex' alt='x, y \\in A' \/>, if <img src='http:\/\/l.wordpress.com\/latex.php?latex=x%20%5Cle%20y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x \\le y' style='vertical-align:1%' class='tex' alt='x \\le y' \/> in <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/>, then <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29%5Cle%20f%28y%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x)\\le f(y)' style='vertical-align:1%' class='tex' alt='f(x)\\le f(y)' \/> in <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/>.<\/li><\/ul>\n\n\n\n<p>The key feature of an object in Poset is that is possesses a partial ordering. So arrows in the category must preserve that ordering: if <img src='http:\/\/l.wordpress.com\/latex.php?latex=x&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x' style='vertical-align:1%' class='tex' alt='x' \/> is less than <img src='http:\/\/l.wordpress.com\/latex.php?latex=y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='y' style='vertical-align:1%' class='tex' alt='y' \/>, then <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x)' style='vertical-align:1%' class='tex' alt='f(x)' \/> must be less than <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28y%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(y)' style='vertical-align:1%' class='tex' alt='f(y)' \/>.<\/p>\n\n\n\n<p>That&#8217;s a typical example of what we mean by arrows as <em>structure&nbsp;preserving:&nbsp;<\/em>the objects of a category have some underlying structural property &#8211; and to be an arrow in the category, that structure must be preserved across arrows and arrow composition.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Commuting Diagrams<\/h2>\n\n\n\n<p>One of the main terms that you\u2019ll hear about category diagrams is about whether or not the diagram <em>commutes<\/em>. This, in turn, is based on <em>arrow chasing<\/em>. <\/p>\n\n\n\n<p>An arrow chase is a path through the diagram formed by chaining arrows together by composing them &#8211; an arrow chase is basically discovering an arrow from one object to another by looking at the composition of other arrows in the category.<\/p>\n\n\n\n<p>We say that a diagram <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ctextbf%7BD%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\textbf{D}' style='vertical-align:1%' class='tex' alt='\\textbf{D}' \/> commutes if, for any two objects <img src='http:\/\/l.wordpress.com\/latex.php?latex=x&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x' style='vertical-align:1%' class='tex' alt='x' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='y' style='vertical-align:1%' class='tex' alt='y' \/> in the diagram, every pair of paths between <img src='http:\/\/l.wordpress.com\/latex.php?latex=x&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x' style='vertical-align:1%' class='tex' alt='x' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='y' style='vertical-align:1%' class='tex' alt='y' \/> compose to the same arrow. Another way of saying that is that if <img src='http:\/\/l.wordpress.com\/latex.php?latex=P%28x%2C%20y%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='P(x, y)' style='vertical-align:1%' class='tex' alt='P(x, y)' \/> is the set of all paths in the diagram between <img src='http:\/\/l.wordpress.com\/latex.php?latex=x&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='x' style='vertical-align:1%' class='tex' alt='x' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/>, <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Cforall%20p_i%2C%20p_j%20%5Cin%20P%28x%2C%20y%29%2C%3A%20%20%5Ccirc%28p_i%29%20%3D%20%5Ccirc%28p_j%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\forall p_i, p_j \\in P(x, y),:  \\circ(p_i) = \\circ(p_j)' style='vertical-align:1%' class='tex' alt='\\forall p_i, p_j \\in P(x, y),:  \\circ(p_i) = \\circ(p_j)' \/>.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"199\" height=\"82\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/arrow-chase.png?resize=199%2C82\" alt=\"\" class=\"wp-image-3705\"\/><\/figure>\n\n\n\n<p>For example: In this diagram, we can see two paths: <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ h' style='vertical-align:1%' class='tex' alt='f\\circ h' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%5Ccirc%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g\\circ h' style='vertical-align:1%' class='tex' alt='g\\circ h' \/>. If this diagram commutes, it means that following <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> from <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h' style='vertical-align:1%' class='tex' alt='h' \/> from <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/> must be the same thing as following <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> from <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h' style='vertical-align:1%' class='tex' alt='h' \/> from <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/>. It doesn\u2019t say that <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> are the same thing &#8211; an arrow chase doesn\u2019t tell us anything about single arrows; it just tells us about how they compose. So what we know if this diagram commutes is that <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20h%3Dg%20%5Ccirc%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ h=g \\circ h' style='vertical-align:1%' class='tex' alt='f\\circ h=g \\circ h' \/>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Diagrams and Meta-level reasoning: an example<\/h3>\n\n\n\n<p>Let\u2019s look at a pretty tricky example. We\u2019ll take our time, because this is subtle, but it\u2019s also pretty typical of how we do things in category theory. One of the key concepts of category theory is building a category, and then using the arrows in that category, create a new category that allows us to do meta-level reasoning.<\/p>\n\n\n\n<p>We\u2019ve seen that there\u2019s a category of sets, called <strong>Set<\/strong>.<\/p>\n\n\n\n<p>We can construct a category based on the arrows of <strong>Set<\/strong>, called <strong>Set<\/strong><sup>\u2192<\/sup>. In this category, each of the arrows in <strong>Set<\/strong> is an object. So, more formally, if <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3A%20A%20%5Crightarrow%20B%20%5Cin%20%5Ctext%7BMor%7D%28%5Ctextbf%20%7BSet%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f: A \\rightarrow B \\in \\text{Mor}(\\textbf {Set})' style='vertical-align:1%' class='tex' alt='f: A \\rightarrow B \\in \\text{Mor}(\\textbf {Set})' \/> then <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AA%20%5Crightarrow%20B%20%5Cin%20%5Ctext%7BObj%7D%28%5Ctextbf%7B%20Set%7D%5E%7B%5Crightarrow%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:A \\rightarrow B \\in \\text{Obj}(\\textbf{ Set}^{\\rightarrow})' style='vertical-align:1%' class='tex' alt='f:A \\rightarrow B \\in \\text{Obj}(\\textbf{ Set}^{\\rightarrow})' \/>.<\/p>\n\n\n\n<p>The arrows of this new category are where it gets tricky. Suppose we have two arrows in <strong>Set<\/strong>, <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3A%20A%20%5Crightarrow%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f: A \\rightarrow B' style='vertical-align:1%' class='tex' alt='f: A \\rightarrow B' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%27%3AA%27%5Crightarrow%20B%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f':A'\\rightarrow B'' style='vertical-align:1%' class='tex' alt='f':A'\\rightarrow B'' \/>. These arrows are objects in <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ctextbf%7BSet%7D%5E%7B%5Crightarrow%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\textbf{Set}^{\\rightarrow}' style='vertical-align:1%' class='tex' alt='\\textbf{Set}^{\\rightarrow}' \/>} There is an arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f'' style='vertical-align:1%' class='tex' alt='f'' \/> in <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ctext%7BMor%7D%28%5Ctextbf%7B%20Set%7D%5E%7B%5Crightarrow%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\text{Mor}(\\textbf{ Set}^{\\rightarrow})' style='vertical-align:1%' class='tex' alt='\\text{Mor}(\\textbf{ Set}^{\\rightarrow})' \/> if there is a pair of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='a' style='vertical-align:1%' class='tex' alt='a' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b' style='vertical-align:1%' class='tex' alt='b' \/> in <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ctext%7BMor%7D%28%5Ctextbf%7BSet%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\text{Mor}(\\textbf{Set})' style='vertical-align:1%' class='tex' alt='\\text{Mor}(\\textbf{Set})' \/> such that the following diagram commutes:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignright is-resized\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/set-arrow-square.png?resize=155%2C150\" alt=\"\" class=\"wp-image-3710\" width=\"155\" height=\"150\"\/><figcaption>commuting diagram for arrows in set-arrow<\/figcaption><\/figure><\/div>\n\n\n\n<p>The diagram is relatively easy to read and understand; explaining it in works is more complicated: <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>an arrow in our category of Set-arrows is a mapping from one <strong>Set<\/strong>-arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> to another <strong>Set<\/strong>-arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f'' style='vertical-align:1%' class='tex' alt='f'' \/>.<\/li><li>That mapping exists when there are two arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='a' style='vertical-align:1%' class='tex' alt='a' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b' style='vertical-align:1%' class='tex' alt='b' \/> in <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Ctext%7BMor%7D%28%5Ctextbf%7BSet%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\text{Mor}(\\textbf{Set})' style='vertical-align:1%' class='tex' alt='\\text{Mor}(\\textbf{Set})' \/> where:<ul><li> <img src='http:\/\/l.wordpress.com\/latex.php?latex=a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='a' style='vertical-align:1%' class='tex' alt='a' \/> is an arrow from the domain of <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> to the domain of <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f'' style='vertical-align:1%' class='tex' alt='f'' \/>;<\/li><li><img src='http:\/\/l.wordpress.com\/latex.php?latex=b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b' style='vertical-align:1%' class='tex' alt='b' \/> is an arrow from the codomain of <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> to the codomain of <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f'' style='vertical-align:1%' class='tex' alt='f'' \/>; and<\/li><li><img src='http:\/\/l.wordpress.com\/latex.php?latex=b%20%5Ccirc%20f%20%3D%20f%27%5Ccirc%20a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b \\circ f = f'\\circ a' style='vertical-align:1%' class='tex' alt='b \\circ f = f'\\circ a' \/>. <\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Another way of saying that is that there\u2019s an arrow means that there\u2019s a structure-preserving way of transforming any arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%5Crightarrow%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A\\rightarrow B' style='vertical-align:1%' class='tex' alt='A\\rightarrow B' \/> into an arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%27%5Crightarrow%20B%27&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A'\\rightarrow B'' style='vertical-align:1%' class='tex' alt='A'\\rightarrow B'' \/>.<\/p>\n\n\n\n<p>Why should we care about that? Well, for now, it\u2019s just a way of demonstrating that a diagram can be a lot easier to read than a wall of text. But this kind of categorical mapping will become important later.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Categorizing Things<\/h2>\n\n\n\n<p>As I said earlier, category theory tends to have a lot of jargon. Everything we do in category theory involves reasoning about arrows, so there are many terms that describe arrows with particular properties. We\u2019ll look at the most basic categories now, and we\u2019ll encounter more in later lessons.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Monics, Epics, and Isos<\/h3>\n\n\n\n<p>The easiest way to think about all of these categories is by analogy with functions in traditional set-based mathematics. Functions and their properties are really important, so we define special kinds of functions with interesting categories. We have injections (functions from A to B where every element of A is mapped onto a unique element of B), surjections (functions from A to B where each element of B is mapped onto by an element of A), and isomorphisms. <\/p>\n\n\n\n<p>In categories, we define similar categories: <em>monomorphisms<\/em> (monics), <em>epimorphisms<\/em> (epics), and <em>isomorphisms<\/em> (isos).<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>An arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AY%20%5Crightarrow%20Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:Y \\rightarrow Z' style='vertical-align:1%' class='tex' alt='f:Y \\rightarrow Z' \/>in category <strong>C<\/strong> is <em>monic<\/em> if for any pair of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%3AX%20%5Crightarrow%20Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g:X \\rightarrow Y' style='vertical-align:1%' class='tex' alt='g:X \\rightarrow Y' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h%3AX%20%5Crightarrow%20Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h:X \\rightarrow Y' style='vertical-align:1%' class='tex' alt='h:X \\rightarrow Y' \/> in <strong>C<\/strong>, <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20g%20%3D%20f%5Ccirc%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ g = f\\circ h' style='vertical-align:1%' class='tex' alt='f\\circ g = f\\circ h' \/> implies that <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%20%3D%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g = h' style='vertical-align:1%' class='tex' alt='g = h' \/>. (So a monic arrow discriminates arrows to its domain &#8211; every arrow to its domain from a given source will be mapped to a different codomain when left-composed with the monic.)<\/li><li>An <em>epic<\/em> is almost the same, except that it discriminates with right-composition: An arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AX%20%5Crightarrow%20Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:X \\rightarrow Y' style='vertical-align:1%' class='tex' alt='f:X \\rightarrow Y' \/> in category <strong>C<\/strong> is epic if for any pair of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%3AY%20%5Crightarrow%20Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g:Y \\rightarrow Z' style='vertical-align:1%' class='tex' alt='g:Y \\rightarrow Z' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h%3AY%20%5Crightarrow%20Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h:Y \\rightarrow Z' style='vertical-align:1%' class='tex' alt='h:Y \\rightarrow Z' \/> in <strong>C<\/strong>, <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%5Ccirc%20f%20%3D%20h%5Ccirc%20f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g\\circ f = h\\circ f' style='vertical-align:1%' class='tex' alt='g\\circ f = h\\circ f' \/> implies that <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%20%3D%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g = h' style='vertical-align:1%' class='tex' alt='g = h' \/>. (So in the same way that a monic arrow discriminations arrows to its domain, an epic arrow discriminates arrows from its codomain.)<\/li><\/ul>\n\n\n\n<p>These definitions sound really confusing. But if you think back to sets, you can twist them into making sense. A monic arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AY%20%5Crightarrow%20Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:Y \\rightarrow Z' style='vertical-align:1%' class='tex' alt='f:Y \\rightarrow Z' \/> describes an injection in set theory: that is, a function maps every element of <img src='http:\/\/l.wordpress.com\/latex.php?latex=X&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='X' style='vertical-align:1%' class='tex' alt='X' \/> onto a unique element of <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/>. So if you have some functions <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h' style='vertical-align:1%' class='tex' alt='h' \/> that maps from some set <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/> onto <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/>, then the only way that <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ g' style='vertical-align:1%' class='tex' alt='f\\circ g' \/> can map onto <img src='http:\/\/l.wordpress.com\/latex.php?latex=Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Z' style='vertical-align:1%' class='tex' alt='Z' \/> in the same way as <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ h' style='vertical-align:1%' class='tex' alt='f\\circ h' \/> is if <img src='http:\/\/l.wordpress.com\/latex.php?latex=g&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g' style='vertical-align:1%' class='tex' alt='g' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=h&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='h' style='vertical-align:1%' class='tex' alt='h' \/> map onto <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/> in exactly the same way.<\/p>\n\n\n\n<p>The same basic argument (reversed a bit) can show that an epic arrow is a surjective function in <strong>Set<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>An isomorphism is a pair of arrows <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%3AY%20%5Crightarrow%20Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f:Y \\rightarrow Z' style='vertical-align:1%' class='tex' alt='f:Y \\rightarrow Z' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5E%7B-1%7D%3A%20Z%20%5Crightarrow%20Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f^{-1}: Z \\rightarrow Y' style='vertical-align:1%' class='tex' alt='f^{-1}: Z \\rightarrow Y' \/> where <img src='http:\/\/l.wordpress.com\/latex.php?latex=f&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f' style='vertical-align:1%' class='tex' alt='f' \/> is monic and <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5E%7B-1%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f^{-1}' style='vertical-align:1%' class='tex' alt='f^{-1}' \/>is epic, and where <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5Ccirc%20f%5E%7B-1%7D%3D%20id_Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f\\circ f^{-1}= id_Z' style='vertical-align:1%' class='tex' alt='f\\circ f^{-1}= id_Z' \/>, and <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%5E%7B-1%7D%5Ccirc%20f%20%3D%20id_Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f^{-1}\\circ f = id_Y' style='vertical-align:1%' class='tex' alt='f^{-1}\\circ f = id_Y' \/>.<\/li><\/ul>\n\n\n\n<p>We say that the objects <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=Z&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Z' style='vertical-align:1%' class='tex' alt='Z' \/> are isomorphic if there\u2019s an isomorphism between them.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Initial and Terminal Objects<\/h3>\n\n\n\n<p>Another kind of categorization that we look at is talking about special objects in the category. Categorical thinking is all about arrows &#8211; so even when we\u2019re looking at special objects, what make them special are the arrows that they\u2019re related to.<\/p>\n\n\n\n<p>An initial object 0 in a category <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/> is an object where for every object <img src='http:\/\/l.wordpress.com\/latex.php?latex=c%20%5Cin%20%5Ctext%7BObj%7D%28%5Ctextbf%7BC%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='c \\in \\text{Obj}(\\textbf{C})' style='vertical-align:1%' class='tex' alt='c \\in \\text{Obj}(\\textbf{C})' \/>, there\u2019s exactly one arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=%200_c%20%5Cin%20%5Ctext%7BMor%7D%28%5Ctextbf%7BC%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title=' 0_c \\in \\text{Mor}(\\textbf{C})' style='vertical-align:1%' class='tex' alt=' 0_c \\in \\text{Mor}(\\textbf{C})' \/>. Similarly, a terminal object <img src='http:\/\/l.wordpress.com\/latex.php?latex=1&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='1' style='vertical-align:1%' class='tex' alt='1' \/> in a category <img src='http:\/\/l.wordpress.com\/latex.php?latex=%7B%5Ctextbf%20C%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='{\\textbf C}' style='vertical-align:1%' class='tex' alt='{\\textbf C}' \/> is an object where for every object <img src='http:\/\/l.wordpress.com\/latex.php?latex=c%20%5Cin%20%5Ctext%7BObj%7D%28%5Ctextbf%7BC%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='c \\in \\text{Obj}(\\textbf{C})' style='vertical-align:1%' class='tex' alt='c \\in \\text{Obj}(\\textbf{C})' \/>, there is exactly one arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=%201_c%20%5Cin%20%5Ctext%7BMor%7D%28%5Ctextbf%7BC%7D%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title=' 1_c \\in \\text{Mor}(\\textbf{C})' style='vertical-align:1%' class='tex' alt=' 1_c \\in \\text{Mor}(\\textbf{C})' \/>.<\/p>\n\n\n\n<p>For example, in the category <strong>Set<\/strong>, the empty set is an initial object, and singleton sets are terminal objects.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">A brief interlude: <\/h2>\n\n\n\n<p>What\u2019s the point?In this lesson, we\u2019ve spent a lot of time on formalisms and definitions of abstract concepts: isos, monos, epics, terminals. And after this pause, we\u2019re going to spend a bunch of time on building some complicated constructions using arrows. What\u2019s the point of all of this? What does any of these mean?<\/p>\n\n\n\n<p>Underlying all of these abstractions, category theory is really about thinking in arrows. It\u2019s about building structures with arrows. Those arrows can represent import properties of the objects that they connect, but they do it in a way that allows us to understand them solely in terms of the ways that they connect, without knowing what the objects connected by the arrows actually do.<\/p>\n\n\n\n<p>In practice, the objects that we connect by arrows are usually some kind of aggregate: sets, types, spaces, topologies; and the arrows represent some kind of mapping &#8211; a function, or a transformation of some kind. We\u2019re reasoning about these aggregates by reasoning about how mappings between the aggregates behave.<\/p>\n\n\n\n<p>But if the objects represent some abstract concept of collections or aggregates, and we\u2019re trying to reason about them, sometimes we need to be able to reason about what\u2019s inside of them.  Thinking in arrows, the only way to really be able to reason about a concept like membership, the only way we can look inside the structure of an object, is by finding special arrows.<\/p>\n\n\n\n<p>The point of the definitions we just looked at is to give us an arrow-based way of peering inside of the objects in a category. These tools give us the ability to create constructions that let us take the concept of something like membership in a set, and abstract it into an arrow-based structure.<\/p>\n\n\n\n<p>Reasoning in arrows, a terminal object is an object in a category that captures a concept of a single object. It\u2019s easiest to see this by thinking about sets as an example. What does it mean if an object, T, is terminal in the category of sets?<\/p>\n\n\n\n<p>It means that for every set <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/>, there\u2019s exactly one function from <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='T' style='vertical-align:1%' class='tex' alt='T' \/>. How can that be? If <img src='http:\/\/l.wordpress.com\/latex.php?latex=T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='T' style='vertical-align:1%' class='tex' alt='T' \/> is a set containing exactly one value <img src='http:\/\/l.wordpress.com\/latex.php?latex=t&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='t' style='vertical-align:1%' class='tex' alt='t' \/>, then from any other set <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/>, the <em>only<\/em> function from <img src='http:\/\/l.wordpress.com\/latex.php?latex=S%20%5Crightarrow%20T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S \\rightarrow T' style='vertical-align:1%' class='tex' alt='S \\rightarrow T' \/> is the constant function <img src='http:\/\/l.wordpress.com\/latex.php?latex=f%28x%29%20%3D%20t&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='f(x) = t' style='vertical-align:1%' class='tex' alt='f(x) = t' \/>. If <img src='http:\/\/l.wordpress.com\/latex.php?latex=T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='T' style='vertical-align:1%' class='tex' alt='T' \/> had more than one value in it, then it would be possible to have more than one arrow from <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='T' style='vertical-align:1%' class='tex' alt='T' \/> &#8211; because it would be possible to define different functions from <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=T&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='T' style='vertical-align:1%' class='tex' alt='T' \/>.<\/p>\n\n\n\n<p>By showing that there\u2019s only one arrow from any object in the category of sets to T, we\u2019re showing that can\u2019t possibly have more than one object inside of it.<\/p>\n\n\n\n<p>Knowing that, we can use the concept of a terminal object to create a category-theoretic generalization of the concept of set membership. If <img src='http:\/\/l.wordpress.com\/latex.php?latex=s&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='s' style='vertical-align:1%' class='tex' alt='s' \/> is an element of a set <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/>, then that set membership can be represented by the fact that there is an arrow from the terminal object <img src='http:\/\/l.wordpress.com\/latex.php?latex=%7Bc%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='{c}' style='vertical-align:1%' class='tex' alt='{c}' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/>. In general, for any object <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/> in a category, if there is an arrow from a terminal object <img src='http:\/\/l.wordpress.com\/latex.php?latex=%7Bt%7D&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='{t}' style='vertical-align:1%' class='tex' alt='{t}' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='S' style='vertical-align:1%' class='tex' alt='S' \/>, then in some sense, <img src='http:\/\/l.wordpress.com\/latex.php?latex=t%20%5Cin%20S&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='t \\in S' style='vertical-align:1%' class='tex' alt='t \\in S' \/>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"> Constructions<\/h2>\n\n\n\n<p>We\u2019re finally getting close to the real point of category theory. Category theory is built on a highly abstracted notion of functions &#8211; arrows &#8211; and then using those arrows for reasoning. But reasoning about individual arrows only gets you so far: things start becoming interesting when you start constructing things using arrows. In lesson one, we saw a glimpse of how you could construct a very generalized notion of monoid in categories &#8211; this is the first big step towards understanding that.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Products<\/h3>\n\n\n\n<p>Constructions are ways of building things in categories. In general, the way that we work with constructions is by defining some idea using a categorical structure &#8211; and then abstracting that into something called a universal construction. A universal construction defines a new category whose objects are instances of the categorical structure; and we can understand the universal construction best by looking at the terminal objects in the universal construction &#8211; which we can understand as being the atomic objects in its category.<\/p>\n\n\n\n<p>When we\u2019re working with sets, we know that there\u2019s a set-product called the cartesian product. Given two sets, A and B, the product <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%20%5Ctimes%20B%3D%7B%28a%2C%20b%29%20%3A%20a%20%5Cin%20A%2C%20b%20%5Cin%20B%7D.&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A \\times B={(a, b) : a \\in A, b \\in B}.' style='vertical-align:1%' class='tex' alt='A \\times B={(a, b) : a \\in A, b \\in B}.' \/><\/p>\n\n\n\n<p>The basic concept of a product is really useful. We\u2019ll eventually build up to something called a closed cartesian category that uses the categorical product, and which allows us to define the basis of lambda calculus in category theory.<\/p>\n\n\n\n<p>As usual, we want to take the basic concept of a cartesian product, and capture it in terms of arrows. So let\u2019s look back at what a cartesian product is, and see how we can turn that into arrow-based thinking.<\/p>\n\n\n\n<p>The simple version is what we wrote above: given two sets A and B, the cartesian product maps them into a new set which consists of pairs of values in the old set. What does that mean in terms of arrows? We can start by just slightly restating the definition we gave above: For each unique value <img src='http:\/\/l.wordpress.com\/latex.php?latex=a%20%5Cin%20A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='a \\in A' style='vertical-align:1%' class='tex' alt='a \\in A' \/>, and each unique value <img src='http:\/\/l.wordpress.com\/latex.php?latex=b%20%5Cin%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='b \\in B' style='vertical-align:1%' class='tex' alt='b \\in B' \/>, there\u2019s a unique value <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28a%2C%20b%29%20%5Cin%20A%20%5Ctimes%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(a, b) \\in A \\times B' style='vertical-align:1%' class='tex' alt='(a, b) \\in A \\times B' \/>.<\/p>\n\n\n\n<p>But what do we actually mean by <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28a%2C%20b%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(a, b)' style='vertical-align:1%' class='tex' alt='(a, b)' \/>? Mathematicians have come up with a lot of different ways of constructing ordered pairs. But we want to create a general model of an ordered pair, so we don&#8217;t want to limit ourselves to any specific construction: we want to capture the key property of what the ordered pair <em>means<\/em>.<\/p>\n\n\n\n<p>It doesn\u2019t matter which one we use: what matters is that there\u2019s a key underlying property of the product: there are two functions and, called<em> projection function<\/em>s, which map elements of the product back to the elements of A and B. If <img src='http:\/\/l.wordpress.com\/latex.php?latex=p%3D%28a%2Cb%29%20%5Cin%20A%5Ctimes%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='p=(a,b) \\in A\\times B' style='vertical-align:1%' class='tex' alt='p=(a,b) \\in A\\times B' \/>, then <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Clambda%28p%29%20%3D%20a&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\lambda(p) = a' style='vertical-align:1%' class='tex' alt='\\lambda(p) = a' \/> (where <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Clambda&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\lambda' style='vertical-align:1%' class='tex' alt='\\lambda' \/> is the name of the <em>left&nbsp;projection)<\/em>, and <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Crho%28p%29%20%3D%20b&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\rho(p) = b' style='vertical-align:1%' class='tex' alt='\\rho(p) = b' \/> (where <img src='http:\/\/l.wordpress.com\/latex.php?latex=%5Crho&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='\\rho' style='vertical-align:1%' class='tex' alt='\\rho' \/> is the name of the <em>right&nbsp;projection<\/em>).<\/p>\n\n\n\n<p>That\u2019s going to be the key to the categorical product: it\u2019s going to be defined primarily by the projection functions. We know that the only way we can talk about things in category theory is to use arrows. The thing that matters about a product is that it\u2019s an object with projections to its two parts. We can describe that, in category theory, as something that we\u2019ll call a wedge:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignright\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"123\" height=\"103\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/wedge.png?resize=123%2C103\" alt=\"\" class=\"wp-image-3723\"\/><figcaption>The wedge: a candidate for a product.<\/figcaption><\/figure><\/div>\n\n\n\n<p><br>A wedge is basically an object, like the one in the diagram to the right, which we\u2019ll call <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%20%5Cland%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A \\land B' style='vertical-align:1%' class='tex' alt='A \\land B' \/>. This object has two special arrows, <img src='http:\/\/l.wordpress.com\/latex.php?latex=l&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='l' style='vertical-align:1%' class='tex' alt='l' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=r&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='r' style='vertical-align:1%' class='tex' alt='r' \/>, that represent projections from <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%5Ctimes%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A\\times B' style='vertical-align:1%' class='tex' alt='A\\times B' \/> to its components in <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/>. <\/p>\n\n\n\n<p>Now we get to the tricky part. The concept of a wedge captures the structure of what we mean by a product. But given two objects A and B, there isn&#8217;t just one wedge! In a category like Set, there are many different ways of creating objects with projections. Which object is the <em>correct<\/em> one to use for the product?<\/p>\n\n\n\n<p>For example, I can have the set of triples <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28A%2C%20B%2C%20C%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(A, B, C)' style='vertical-align:1%' class='tex' alt='(A, B, C)' \/>. I can easily define a left project from <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28A%2C%20B%2C%20C%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(A, B, C)' style='vertical-align:1%' class='tex' alt='(A, B, C)' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/>, and a right projection from <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28A%2C%20B%2CC%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(A, B,C)' style='vertical-align:1%' class='tex' alt='(A, B,C)' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/>. But clearly <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28A%2C%20B%2C%20C%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(A, B, C)' style='vertical-align:1%' class='tex' alt='(A, B, C)' \/> is not what we mean by the product of <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%20%5Ctimes%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A \\times B' style='vertical-align:1%' class='tex' alt='A \\times B' \/>. It\u2019s close, but it\u2019s got extra noise attached, in the form of that third element <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/>.<\/p>\n\n\n\n<p>If, for two objects <img src='http:\/\/l.wordpress.com\/latex.php?latex=A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A' style='vertical-align:1%' class='tex' alt='A' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='B' style='vertical-align:1%' class='tex' alt='B' \/>, there are many wedges with left and right projections, which one is the real product?<\/p>\n\n\n\n<p>Just a little while ago, we talked about initial and terminal objects. A terminal object can be understood as being a rough analog to a membership relation. We\u2019re going to use that.<br>We can create a category of wedges <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%20%5Cland%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A \\land B' style='vertical-align:1%' class='tex' alt='A \\land B' \/>, where there is an arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=m&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='m' style='vertical-align:1%' class='tex' alt='m' \/> from <img src='http:\/\/l.wordpress.com\/latex.php?latex=X&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='X' style='vertical-align:1%' class='tex' alt='X' \/> to <img src='http:\/\/l.wordpress.com\/latex.php?latex=Y&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='Y' style='vertical-align:1%' class='tex' alt='Y' \/> when the diagram below commutes in our original category:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignright\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"151\" height=\"158\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/terminal-wedge.png?resize=151%2C158\" alt=\"\" class=\"wp-image-3724\"\/><figcaption>The ideal product: the terminal in the category of wedges.<\/figcaption><\/figure><\/div>\n\n\n\n<p>In the category of wedges, what that means is that Y is at least as strict of a wedge than X; X has some amount of noise in it (noise in the sense of the C element of the triple from the example above), and Y cannot have any more noise than that. The true categorical product will be the wedge with no excess noise: an wedge which has an arrow from every other wedge in the category of wedges.<br>What\u2019s an object with an edge from every other object? It\u2019s the terminal object. The categorical product is the terminal wedge: the unique (up to isomorphism) object which is stricter than any other wedge. <br>Another way of saying that, using categorical terminology, is that there is a universal property of products: products have left and right projections. The categorical product is the exemplar of that property: it is the unique object which has exactly the property that we\u2019re looking at, without any extraneous noise. Any property that this universal object has will be shared by every other product-like object.<\/p>\n\n\n\n<p>This diagram should look familiar: it\u2019s the same thing as the diagram for defining arrows in the category of wedges. It\u2019s the universal diagram: you can substitute any wedge in for C, along with its project arrows (f, g). <\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignright\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" width=\"261\" height=\"167\" src=\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2019\/02\/image91.png?resize=261%2C167\" alt=\"\" class=\"wp-image-3722\"\/><figcaption>The categorical product.<\/figcaption><\/figure><\/div>\n\n\n\n<p>We can pull that definition back to our original category, and define the product without the category of wedges. So given two objects, A and B, in a category, the categorical product is defined as an object which we\u2019ll call <img src='http:\/\/l.wordpress.com\/latex.php?latex=A%20%5Ctimes%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='A \\times B' style='vertical-align:1%' class='tex' alt='A \\times B' \/> along with two arrows and , which have the property that for any object <img src='http:\/\/l.wordpress.com\/latex.php?latex=C&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='C' style='vertical-align:1%' class='tex' alt='C' \/> which has arrows<img src='http:\/\/l.wordpress.com\/latex.php?latex=%20f%3A%20C%20%5Crightarrow%20A&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title=' f: C \\rightarrow A' style='vertical-align:1%' class='tex' alt=' f: C \\rightarrow A' \/> and <img src='http:\/\/l.wordpress.com\/latex.php?latex=g%3AC%20%5Crightarrow%20B&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='g:C \\rightarrow B' style='vertical-align:1%' class='tex' alt='g:C \\rightarrow B' \/>, there is a unique arrow <img src='http:\/\/l.wordpress.com\/latex.php?latex=%28f%2Cg%29%3AC%20%5Crightarrow%20%28A%5Ctimes%20B%29&#038;bg=FFFFFF&#038;fg=000000&#038;s=0' title='(f,g):C \\rightarrow (A\\times B)' style='vertical-align:1%' class='tex' alt='(f,g):C \\rightarrow (A\\times B)' \/> for which the diagram to the right commutes.<\/p>\n\n\n\n<p>On its own, if we\u2019re looking specifically at sets, this is just a complicated way of defining the cartesian product of two values.  It doesn\u2019t really tell us much of anything new. What makes this interesting is that it isn\u2019t limited to the cartesian product of two sets: it\u2019s a general concept that takes what we understand about simple sets, and expands it to define a product of any two things in categories. The set-theoretic version only works for sets: this one works for numbers, posets, topologies, or anything else. <\/p>\n\n\n\n<p>In terms of programming, products are pretty familiar to people who write functional programs: a product is a tuple. And the definition of a tuple in a functional language is pretty much <em>exactly<\/em> what we just described as the categorical product, tweaked to make it slightly easier to use.<\/p>\n\n\n\n<p>For example, let&#8217;s look at the <a href=\"https:\/\/github.com\/scala\/scala\/blob\/v2.12.1\/src\/library\/scala\/Product.scala#L1\">product type<\/a> in Scala.<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">trait Product extends Any with Equals {<br>  def productElement(n: Int): Any<br>  def productArity: Int<br>...<br>}<\/pre>\n\n\n\n<p>The product object intrinsically wraps projections into a single function which takes a parameter and returns the result of applying the projection. It could have been implemented more categorically as:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">trait CatProduct extends Any with Equals {<br>  def projection(n: Int): () =&gt; Any<br>  ...<br>}<\/pre>\n\n\n\n<p>Implemented the latter way, to extract an element from a product, you&#8217;d have to write <code>prod.projection(i)()&nbsp;<\/code>which is more cumbersome, but does the same thing. <\/p>\n\n\n\n<p>More, if you look at this, and think of how you&#8217;d use the product trait, you can see how it relates to the idea of terminal objects. There are many different concrete types that you could use to implement this trait. All of them define <em>more<\/em> information about the type. But every implementation that includes the concept of product can implement the Product trait. This is exactly the relationship we discussed when we used terminal objects to derive the ideal product: there are many abstractions that include the concept of the product; the categorical product is the one that abstracts over all of them.<\/p>\n\n\n\n<p>The categorical product, as an abstraction, may not seem terribly profound. But as we\u2019ll see in a the next post, in category theory, we can <em>compose<\/em> abstractions &#8211; and by using composition to in a compositional way, we&#8217;ll be able to define an abstraction of exponentiation,  which generalizes the programming language concept of currying.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In my last post about category theory, I introduced the basic idea of typeclasses, and showed how to implement an algebraic monoid as a typeclass. Then we used that algebraic monoid as an example of how to think with arrows, and built it up into a sketch of category theory\u2019s definition of a monoid. We [&hellip;]<\/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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[76],"tags":[],"class_list":["post-3701","post","type-post","status-publish","format-standard","hentry","category-category-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-XH","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/3701","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=3701"}],"version-history":[{"count":46,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/3701\/revisions"}],"predecessor-version":[{"id":3766,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/3701\/revisions\/3766"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=3701"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=3701"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=3701"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}