{"id":47,"date":"2006-06-27T16:19:27","date_gmt":"2006-06-27T16:19:27","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/06\/27\/categories-products-exponentials-and-the-cartesian-closed-categories\/"},"modified":"2006-06-27T16:19:27","modified_gmt":"2006-06-27T16:19:27","slug":"categories-products-exponentials-and-the-cartesian-closed-categories","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/06\/27\/categories-products-exponentials-and-the-cartesian-closed-categories\/","title":{"rendered":"Categories: Products, Exponentials, and the Cartesian Closed Categories"},"content":{"rendered":"

Before I dive into the depths of todays post, I want to clarify something. Last time, I defined categorical products. Alas, I neglected to mention one important point, which led to a bit of confusion in the comments, so I’ll restate the important omission here.
\nThe definition of categorical product defines what the product looks like *if it’s in the category*. There is no requirement that a category include the products for all, or indeed for any, of its members. Categories are *not closed* with respect to categorical product.
\nThat point leads up to the main topic of this post. There’s a special group of categories called the **Cartesian Closed Categories** that *are* closed with respect to product; and they’re a very important group of categories indeed.
\nHowever, before we can talk about the CCCs, we need to build up a bit more.
\nCartesian Categories
\n——————–
\nA *cartesian category* C (note **not** cartesian *closed* category) is a category:
\n1. With a terminal object t, and
\n2. ∀ a, b ∈ Obj(C), the objects and arrows of the categorical product a×b are in C.
\nSo, a cartesian category is a category closed with respect to product. Many of the common categories are cartesian: the category of sets, and the category of enumerable sets, And of course, the meaning of the categorical product in set? Cartesian product of sets.
\nCategorical Exponentials
\n————————
\nLike categorical product, the value of a categorical exponential is not *required* to included in a category. Given two objects x and y from a category C, their *categorical exponential* xy<\/sup>, if it exists in the category, is defined by a set of values:
\n* An object xy<\/sup>,
\n* An arrow evaly,x<\/sub> : xy<\/sup>×y → x, called an *evaluation map*.
\n* ∀ z ∈ Obj(C), an operation ΛC<\/sub> : (z&cross;y → x) → (z → xy<\/sup>). (That is, an operation mapping from arrows to arrows.)
\nThese values must have the following properties:
\n1. ∀ f : z×y → x, g : z → xy<\/sup>:
\n* valy,x<\/sub> º (ΛC<\/sub>(f)×1y<\/sub>)
\n2. ∀ f : z×y → x, g : z → xy<\/sup>:
\n* ΛC<\/sub>(evaly,x<\/sub> *ordm; (z×1y<\/sub>)) = z
\nTo make that a bit easier to understand, let’s turn it into a diagram.
\n\"exponent.jpg\"
\nYou can also think of it as a generalization of a function space. xy<\/sup> is the set of all functions from y to x. The evaluation map is simple description in categorical terms of an operation that applies a function from a to b (an arrow) to a value from a, resulting in an a value from b.
\n(I added the following section after this was initially posted; a commenter asked a question, and I realized that I hadn’t explained enough here, so I’ve added the explanation.<\/em>
\nSo what does the categorical exponential mean? I think it’s easiest to explain in terms of sets and functions first, and then just step it back to the more general case of objects and arrows.
\nIf X and Y are sets, then XY<\/sup> is the set of functions from Y to X.
\nNow, look at the diagram:
\n* The top part says, basically, that g is a function from Z to to XY<\/sup>: so g takes a member of Z, and uses it to select a function from Y to X.
\n* The vertical arrow says:
\n* given the pair (z,y), f(z,y) maps (z,y) to a value in X.
\n* given a pair (z,y), we’re going through a function. It’s almost like currying:
\n* The vertical arrow going down is basically taking g(z,y), and currying it to g(z)(y).
\n* Per the top part of the diagram, g(z) selections a function from y to x. (That is, a member of XY<\/sup>.)
\n* So, at the end of the vertical arrow, we have a pair (g(z), y).
\n* The “eval” arrow maps from the pair of a function and a value to the result of applying the function to the value.
\nNow – the abstraction step is actually kind of easy: all we’re doing is saying that there is a structure<\/em> of mappings from object to object here. This particular structure has the essential properties of what it means to apply a function to a value. The internal values and precise meanings of the arrows connecting the values can end up being different things, but no matter what, it will come down to something very much like function application.
\nCartesian Closed Categories
\n—————————-
\nWith exponentials and products, we’re ready for the cartesian closed categories (CCCs):
\nA Cartesian closed category<\/em> is a category that is closed with respect to both products and exponentials.
\nWhy do we care? Well, the CCCs are in a pretty deep sense equivalent to the simply typed lambda calculus. That means that the CCCs are deeply tied to the fundamental nature of computation. The *structure* of the CCCs – with its closure WRT product and exponential – is an expression of the basic capability of an effective computing system.
\nWe’re getting close to being able to get to some really interesting things. Probably one more set of definitions; and then we’ll be able to do things like show a really cool version of the classic halting problem proof.<\/p>\n","protected":false},"excerpt":{"rendered":"

Before I dive into the depths of todays post, I want to clarify something. Last time, I defined categorical products. Alas, I neglected to mention one important point, which led to a bit of confusion in the comments, so I’ll restate the important omission here. The definition of categorical product defines what the product looks […]<\/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,24],"tags":[],"class_list":["post-47","post","type-post","status-publish","format-standard","hentry","category-category-theory","category-goodmath"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-L","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/47","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=47"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/47\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}