A Young Author’s Illustrated Primer (to Category Theory) · 8:36am Jan 2nd, 2017
Here’s an easy problem. I offer you a bet where I flip a fair coin. If it lands tails, you owe me one dollar. If it lands heads, I owe you two dollars. Do you take the bet?
Most people that aren’t overthinking things (there are no trick questions here) would say yes. If you stand to lose one or gain two with even chances, this is clearly in your favor. Ezpz. A classic textbook example.
Here’s the same problem. I offer you two doors, of which you may open one. Behind one of them is nothing. Behind the second are three dollars that you can take. It’ll cost you one dollar to open a door. Do you open a door?
They’re not literally the same problem, but they’re similar. Moreover, they’re similar in a very specific way. They’re analogous. Each can be used as an analogy for the other. How can we describe the analogy?
Supposing you take the bet in both cases, landing tails is like opening the door with nothing: in both cases, you lose one dollar overall. Landing heads is like opening the door with money behind it: in both cases, you gain two dollars overall. The two outcomes have equal probability in both cases. In both cases, it’s me offering the bet, and in both cases you get to decide whether you want to take it.
If you draw this analogy, someone that accepts your coin-flipping answer should accept your door-opening answer, and someone that accepts your door-opening answer should accept your coin-flipping answer. All that’s needed is for that someone accept that the analogy is appropriate. So how might this someone decide whether to accept the analogy? What exactly is it that makes some analogies appropriate and some not?
This, in a nutshell, is what category theory is about. By the time you’re done reading this post, you’ll be appropriating analogies like a master.
Why you should care
Analogies let you reason intuitively when you don’t know how to reason logically. Given that we’re not all perfect math machines capable of observing the universe in terms of truth itself, that fallback tends to get used more often that we’d maybe like to admit. Getting a better grasp of analogies, and by extension your own intuition, can go a long way towards helping you be reasonable when you don’t know how to be logical.
And, you know, readers dig writers that can be reasonable.
You need an example. Take the problem of structuring a blog post. What’s the right way to do it? I don’t have a clue, but why should that stop me from trying to do it well? I know what I want to discuss, and it’s some heavy stuff for an audience not perfectly suited to understand it. There’s a sense of depth and awe and mystery I want to get across regarding the extent of this thing, I want to convey my feelings of importance so that maybe people can take it as seriously as I do. I need examples to make it make sense, and there are a few concepts that are foundational. How do I put it together into something that won’t drive people away disappointed and confused?
What would a brave writer do?’
This is something stories excel at, isn’t it? Getting across an idea to an audience that might not be fully receptive to it if presented at face value. Getting people to read between the lines to find hidden depth. Getting them to adopt a new perspective, if even for a short while. Seamlessly pulling together a number of maybe-related concepts to paint a bigger picture. Hopefully keeping the reader entertained and engaged throughout.
Maybe structuring the blog post well doesn’t have to be too different from structuring a story well.
There are two characters here: a teacher and, for relatability reasons, a faceless student. I hope you’ll humor me and let me play the teacher. The resolution has to be me getting these ideas through to you, so the conflict should be the struggle to do so. Maybe I can start immediately by introducing the conflict, and in the process introduce the teacher.
It has to be somewhat intense to be a decent hook, so maybe I can end the intro with something emotional. I can follow it up with something easier and lower-stakes that evolves into ever higher highs until the climax. That’s a pretty standard progression.
I need a theme. Without that, there’s no coherence or gravity to this blob of text. Something about category theory? No, it has to be something you already recognize as valuable. It has to be something I can come back to over and over again, starting from the very beginning. It has to be…
No spoilers.
In any case, it’s not a perfect analogy, but it’s all I need to figure out how I want to structure this blog post. I can make meaningful progress on a problem I otherwise would be struggling with. If I want to go further, I need some way to pick apart where this analogy breaks down, and to do that, I need to understand…
What makes an analogy appropriate
It’s about preserving the relationships that matter. If you want to produce better analogies, you should think more in terms of relationships.
In the coin flip scenario, the chances of heads and chances of tails are equal. If that’s important, then there must be a corresponding relationship between opening each door (since heads and tails correspond to doors). Flipping heads also results in you gaining more money than you would lose on tails. That’s another relationship that needs a correspondence. If it matters that you get to choose whether you want to take the bet, then you can draw a connection between yet another pair of relations (each one between you and the choice between the two outcomes… by the way that choice is related to each of the two outcomes as well).
Here’s an important point: analogies might only work in one direction. If I didn’t give you a choice on the coin flipping scenario (meaning I forced you to take the bet), you can still use the door scenario as an analogy for the coin scenario. You have more things to consider in the door scenario, so the reverse might not be true.
You can use the door scenario as an analogy for the coin scenario so long as every relationship in the coin scenario has a corresponding relationship in the door scenario. In other words, you can use the door scenario as an analogy for the coin scenario if you can embed the coin scenario inside the door scenario. If you ignore relationships in the coin scenario, that just makes it easier to draw the analogy, but it might make your analogy less useful or convincing.
The fact that an analogy can be made less useful by ignoring relationships suggests that analogies themselves can be meaningfully related to one another. Is that too recursive? Maybe it would help to think of…
Analogies in stories
If a story takes place in its own world, then it’s up to an author to draw parallels between the real world and that world to make events in the story world meaningful. In other words, the author has to make sure some story elements can be treated as references to aspects of the real world, or whatever other work. That’s some of what an author does, at least. Let’s focus on that part of storytelling for now.
In this case, you can draw a line between the referential elements of a story and the fantastical elements. Any story elements that are analogous to aspects of the real world can be called referential. Everything else can be called fantastical.
Here’s an important point: the line isn’t entirely objective. The author can choose to not draw a parallel. The reader can choose to not accept one. An author can take one set of events and tell two stories that serve two very different purposes by shuffling around which aspects are made to seem referential and which are not. An author might choose to tweak the line to strike a balance between adding more meaning to a story, which would require drawing more parallels, and adding more focus to a story, which would require drawing exactly the parallels needed for the theme, or whatever other purpose the story serves.
To complete the comparison, an author can take an existing story and take away meaning by removing parallels, and the author can take away focus by writing in new parallels. The result is a new story that is naturally related to the original. In this sense, there exists a least meaningful telling of story events, where everything in the story is treated as pure fantasy, and there exists a least focused telling of story events, where everything in the story is treated as a reference. Somewhere in the middle is the one the author actually wants to tell.
Similarly, an analogy between the coin scenario and the door scenario can be given more meaning by making it a more complete embedding, and it can be given more focus by giving it exactly the embedding necessary to make the answer (of whether or not to take the bet) the same.
By drawing a comparison (an analogy, really) between analogies and stories, it’s a little more obvious that the relationships between analogies don’t have to be about stating that one is better or worse, just as the relationships between stories don’t have to be about which is better or worse. There’s a deeper, more nuanced meaning that was made more obvious by drawing the comparison.
By understanding the comparisons that can be made between analogies and other analogy-like things, you can start to develop a deeper understanding of analogies and their function. In other words, you can start to understand…
The purpose of analogies
First consider why it’s possible to gain insight into analogies by looking at stories. Stories provide a bigger world in which analogies play a part. In that bigger world, we can see what role analogies play. That gives us clues as to which roles analogies can play in general.
But keep in mind that after finding a role for analogies, I could have thrown literally anything I wanted into that bigger world, or written anything I wanted into the story. That doesn’t mean all of those things necessary say reasonable thing about analogies. It’s important to keep in mind that the bigger world can only give indications as to which roles analogies can play. It’s up to you to take those indications and figure out which ones make sense.
I said in the beginning that analogies let you reason intuitively when you don’t know how to reason logically. I can now make that more precise.
Analogies let you reason approximately when you can’t reason accurately. Their use is in letting you reason around in a hypothetical world intertwined with logical connections that you can’t logically justify using.
And with that, we’ve (finally) come full-circle.
Closing words
This isn’t the end, but it’s as close as I can get without dropping you into abstraction hell. Functors, on which my ideas on analogies are based, make up one of the two basic building blocks of category theory. After 70 years of research, they’re still being studied in their various generalizations. There’s still a ton more to cover here regarding just the basics.
The second basic building block, universal objects, is nuanced enough that, combined with functors, it yields a coherent theory of Platonic Forms. Unfortunately, that’s the interesting part about universal objects so there’s no getting around explaining that nuance, and doing so without the abstract language of category theory sounds, at the moment, prohibitively difficult.
If there’s one thing I want to get across, it’s that there’s a lot of depth and interconnectedness to things that is worth investigating, and analogies happen to be key to getting those investigations kicked off. Moreover, it’s not just there in a void accessible only to the most faithful of students. Analogy, and more generally category theory, becomes intuitive quickly because it’s a way of thinking your brain particularly likes. It is a valuable tool if you want to better understand yourself, the way you think, and the things you want to explore, and it's worth using more explicitly.
I know the public material on category theory is nigh impenetrable. I hope this post at least made sense.
The language of category theory
When I said that the resolution of this story should be me getting these ideas through to you, I lied a little. That was your resolution, and this is mine.
A few months ago, someone promised this post on my behalf. I think five of you followed me because of that promise, of which 2-3 will probably see this post.
For the most part, this is me admitting defeat and dumping what I think I can deliver on. This post was originally supposed to be about limitations of the English language and how category theory addresses them. I tried writing that post for a while before realizing, twice, that it was an utterly hopeless task.
I do still think that such a post would be worthwhile, as the language is arguably one of the greatest accomplishments of mathematics, and its philosophical significance is nothing less than awe inspiring. It really does resolve some core issues with our language. It’s not something I can write just yet though, so this post will have to settle for being a small foreword to another (longer, stranger, more beautiful) story, one that probably won’t be told by me. It took me a little too long to make peace with that.
Thanks, Bad Horse and GaPJaxie, for spending a ludicrous amount of time arguing with me and unwittingly helping me clarify my thoughts on this topic. Thanks, Bad Horse again, for pressuring me into writing this. I learned a lot from it.
4366015
Keep in mind that Medieval philosophers didn't have a consistent interpretation of what "analogy" meant. It seemed to have changed pretty drastically around Aquinas' time, and it might have changed again with future Medieval philosophers.
I wasn't able to find the paper you're referencing, so most of this will be guesswork. Based on Stanford's encyclopedia on philosophy, it seems like Aquinas was one of the first philosophers to distinguish "two concepts described by the same word" and "two related concepts described by the same word" (i.e., accidentally sharing a description vs. deliberately sharing a description). His ideas on analogies seem to be largely consistent with my post. I suspect we get a lot of our modern interpretation of Plato's Forms from Aquinas.
Regarding the statement "analogies are objective features of the natural world" in terms of Aquinas. I suspect you're interpreting it to have a lot more meaning than it does. Based on section 6 on Stanford's page, it seems Aquinas treated features of the natural world as analogies of some prior reality. "Objective features" could be referencing either, say, a dog or the Form of a dog, and it's a little ambiguous which one the statement is referring to. Aquinas did seem to believe that the latter was objective. It's not clear to me whether he thought the former was as well.
So when do you start teaching us category theory? I've read bits of it. The general problem I notice with it is that it's very good for doing topology and algebra (and thus logic, especially logic), but most of the math people want to do is really analysis, which AFAICT category theory is less helpful for.
Downside! You posted this before I had a chance to read the draft and leave comments.
Upside! It's excellent enough I'm not sure I would have had much to say anyway. This is quite good.
I love your new additions, and I think they really round out the draft I read earlier, but there's one thing I have to comment on specifically.
pinkie.mylittlefacewhen.com/media/f/rsz/mlfw705_small.jpg
Because you're already halfway there!
If I had to boil this entirely lovely post down to one or two inelegant sentences, they would be this: "Analogies are a critical component of how humans understand the world around them and tell stories. Category Theory is a cleaner, more exact way to describe analogies and how they work, much like formal math is a cleaner way to describe numbers than counting on your fingers."
After that, I don't think you'd actually have much trouble coming up with examples. For instance, let's say I said: "Siren Song is about drug addiction because they both focus on chemical dependency," and someone else replied, "Wrong! Not having your pot doesn't make you mutate and die. Siren Song is about religion. All the ponies who turned away from God (AKA, Celestia) are doomed to a life of sin and depravity."
Neither of those descriptions is wrong, exactly, but both of them are woefully incomplete, and two people who fundamentally agree on the underlying situation may argue because they can't express their points in sufficient, clear detail. Or the classic example of the English sentence: "It's a pretty little girls school" Is it a pretty, small school for girls? Is it a school for pretty little girls? Is it a somewhat little school for girls? Etc.
After reading this blog post, I totally believe you can do it.
Believe in me who believes in you! Also, can provide editing and stuff!
4366500
I've started a bit. Treating functors as a gateways to richer categories was one of Grothendieck's signature moves, and it's what made mathematicians take category theory seriously for geometry.
My original attempt was to teach category theory more directly, starting with objects and morphisms. The responses were almost universally to the tune of "What the crap is going on?" It involved enough misunderstandings that I thought it would have been counterproductive for all but the tiny few that would power through it. To be fair, that was my first response as well, and it took me about a month to get through it.
I tried to address this by giving a less abstract introduction. The responses were to the tune of "Why are you doing this?" I thought I had covered my bases on this since I originally started studying it to try to understand definitions. It turns out most people don't care about that! At least not directly.
So the third attempt is me starting with some of the deeper uses. The problem is that I seem to have to do this first, but explaining the mechanics of category theory is such an information overload and I can't do that in the same post. I did put some of the definitional and mechanical parts in this post, but it's incognito for now.
If that's not enough warning to deter you, then here's the first attempt that covers more directly what I think you're looking for: https://docs.google.com/document/d/1L7VCHmcHW2d_TV8uSXYsmoIE5VU-g8Um_Ps6sg9n728/edit
Note that it's incomplete. There were enough issues getting people past the third page.
Category theory has two drastically different uses in algebra and topology. One of them is what this post is about: embeddings into richer categories, frequently through sheaves for algebra and topology. Functors are key to this approach. The second is what the incomplete linked doc is about: it makes definitions cleaner, which makes logic cleaner. The object-morphism view and universal objects are key to this approach.
4366524
Yes!
And yes! In an earlier revision of this post, I had a couple paragraphs dedicated to decomposing the two things an analogy/functor does: (1) translating in a way that preserves relevant meaning (i.e., preserving all important relationships) and (2) specifying which aspects of the analogous scenario are relevant. Translated to story terms, these would correspond respectively to references and focus. Your two examples violate both of them, and now you’ll have an easier time debunking them in ways that are convincing! Or updating your story so it's more clear.
I removed the decomposition because it was teetering over the edge of how much abstraction I thought would be tolerable. For the math people (everyone else, avert your eyes), this is analogous to decomposing a function into a surjection (the map from the domain onto the image of the function) and an injection (the map from the image of the function to the codomain/range). The surjection collapses irrelevant distinctions/meaning, and the injection specifies the relevant parts of the codomain/range.
4366524
What you're looking at is an iceberg. I'm like 1% of the way there
.
Functors actually have two "elemental" uses: analogies and abstractions, of which I've covered one. Universal objects in regular categories are one thing, but they get a huge power-up when they're applied to categories of functors. Now I have to explain categories of functors, which means explaining relationship-preserving relationships between analogies. I had a couple paragraphs on this in an earlier revision, but that was a special kind of abstraction hell (though it's one I think I can navigate some with effort). Then I need to legitimize the use of universals on functor categories and explain how they correspond to definition-by-properties, which correspond to Platonic Forms. Then I have to deal with the usual arguments against Platonic Forms, the counters to which don't make sense without an explanation of how Russel's paradox actually has two solutions, one of which is given by ZF set theory and prohibits self-participation of objects, and the other which is given by category theory and mandates self-participation of objects. Now I have to explain what self-participation means, why it's important, how set theory and category theory address the question differently, and how the category theory answer can be interpreted as a generalization of the set theory one. Welcome to Topos Theory! What's that you say? Well...
4366683
I agree this was probably good to cut from the blog post, but the more I think about that method of thinking about it, the more I like it.
There has to be a simpler way to express that.
4367248
I started discussing it here:
What's missing is the jump from "X is what analogies can do in stories" to "analogies can only do Y, which is a generalization of X." I don't think I'll be able to explain why analogies can be decomposed generally like they can be in stories unless I can somehow explain that functional relationships can describe all analogies. I don't know how to do that (yet) without going down to the math behind this.
But NSFW blog posts aren't allowed!
Is category theory like topology, where you find sets that are topologically equivalent, disgregarding numerical measurements? In that case it wouldn't matter if the expected profit were the same, only that it were greater for the bets from each scenario that are mapped to each other.
I suppose it depends on whether analogies are recursively enumerable.
Sounds like you're taking about allegories, not stories in general. I hope you don't trigger my "stories are not allegories and allegories are not stories" rant.
Triggered! But you said that in such an interesting way that I'm going to reformulate my rant.
If that were so, then a complete allegory in which everything maps onto something in the real world would have maximal meaning. But they communicate no information, just because they match exactly something we already know.
Medieval writers wrote allegories because they did not believe they could themselves make new information. They seemed at times to think that the ancients had known everything that was knowable.
And allegories suck as literature because they convey no information.
(This is part of my argument why medieval art was objectively bad. The medieval worldview was, in many ways, fundamentally opposed to and denied the possibility of art itself. One of these ways was its denial that artists could have new ideas, which led them to make "art" that merely repeated old ideas.)
If we want to communicate new meaning (information), but still related to things we already know, we need some intermediate level of reference--not so little that the new information can't be made sense of, but not so much that we say only what we already know.
This is extremely similar to how complexity is maximized somewhere between stasis (complete order) and noise.
I don't think this statement makes a real distinction. * "Accuracy" and "approximate" both mean "some unspecified level of precision." It sounds like it's making a distinction because people from the rationalist Western tradition automatically read "accurately" as "exactly".
* That turned out to be a pun. It does not make a distinction to people used to thinking in real numbers.
Um. What? I take Platonic Forms to be things that should not have a theory, because they're ontological nonsense. (Literally.)
I don't have any idea how to progress from here. How did you learn category theory? Do you recommend a book?
4372312
I don't know how to teach category theory, which is why I'm going for intuitive connections. I started learning category theory from Wikipedia, nlab, and Bartosz Milewski’s blog, after which I started reading these papers/books by Ellerman and Kostecki and watching occasional youtube videos by Lurie and a few others. There were several other blogs and mathoverflow posts I read along the way, but I can't remember them now. The only reason this worked for me is because I felt compelled to put in however much time it took to understand it, which was several months. I've tried several times to teach category theory the way I learned it, and it just doesn't work.
Every introduction to category theory I've seen assumes familiarity with higher mathematics (group theory, vector spaces, R-modules, abstract algebra, and so on), so I can't recommend them. (I'm convinced, though, that higher mathematics is not a prerequisite for understanding or applying category theory.)
I'm going to copy text from a few other places because my thoughts are a bit scattered.
I'm working on a second blog post, following which I have a comment I wish I included with this blog post.
I wrote the following as an introduction to universal properties for someone else. It's a partial rewrite of the Wikipedia page on universal properties. Keep in mind that "a function from A to B" means something like "f(x) = 2x is a function from the set of integers to the set of integers".
If you understand this, then the next step is making sense of limits and colimits. After that, you can read Wikipedia pages and not feel crushing despair, so things are a bit easier.
4372304
It's fine if we just call it "math"
.
Yes, actually. In topology, two sets are considered equivalent if they're isomorphic, meaning there exists a one-to-one mapping of points that preserves neighborhoods. In category theory, two categories are considered equivalent if there exists a one-to-one mapping of morphisms/relationships that preserves compositions. Composition in the same sense that f composed with g gives you a function f(g(x)).
I'm not! I'm not saying that the story has to be about some real-world aspect. It just has to make some references to real-world aspects. Something that readers can understand and picture in place of some story things as they're reading through the story. There has to be some way for the reader to imprint some of what they know onto at least some part of story, but beyond that anything goes. If the reader can't do that much, then the story is just nonsense as far as the reader is concerned.
A story that's made up purely of references can still convey information by pulling together references from multiple sources. Such a "story" would be more like a theory of how various phenomena are all interconnected.
I'm not particularly fond of my usage of the word "meaning" to describe this, but I can't think of a better word.
I've added clarification here 4372574. Specifically, I meant point #2 of the following:
You're right that the two are equivalent in empirical contexts, but there's a difference in mathematical contexts. I think that's what you meant in your point about rationalists. I have another comment from the next blog post that might make the reason for the distinction clearer. (4366500 might be interested in this too.)
Explanation here 4372574. Platonic Forms as thought up by Plato had a lot of garbage to them, but the general notion of a universe/category that explains/factors our understanding of various intuitively related concepts turns out to be concretely definable, incredibly useful, and applicable to every area of mathematics.
4372574 But the Wikipedia definition of an initial morphism does not say that the morphism's target has to be a "shadow" of an initial object. Moreover, in the example with tensor algebras given on that page, T(V) is not an initial object in the category of unital associative algebras (unless V is zero-dimensional).
4372629
The morphism's target U(Y) doesn't have to be a shadow of an initial object, it has to be a shadow of some object Y in a category D with an initial object A. There needs to also be a morphism Φ to the shadow of the initial object U(A) , but there can be more targets. The Bottle category has one initial Bottle, but it can have any number of bottles. Each of those bottles has a shadow, and each of those shadows is a target.
T(V) doesn't have to be an initial object in the category of unital associative algebras. It has to be the shadow of an initial object in the category of K-algebras. That initial object is restricted to being unital and associative, but it has other restrictions as well since K has to be a specific field. Keep in mind that the domain of U is the category of K-algebras, not the category of unital associative algebras.
T(V) happens to be an initial object of some subset of K-Alg in a way that's easy to mistake it being an initial object of K-Alg. You can call it a coincidence for now because Wikipedia sucks at giving good first examples.
It's because every object V of K-Vect has a corresponding T(V) that, together with U, satisfies the initial property. Since that's the case for every V of K-Vect, it's easy to mistakenly think that T(V) is the initial object of all of them. Keep in mind that every vector space V of K-Vect has its own T(V) that is not necessarily shared by all of K-Vect. In this case, it's definitely not shared.
4372654
When I was talking about morhism and its target, I meant Ф and U(A). You're saying "There needs to also be a morphism Φ to the shadow of the initial object U(A)", but Wikipedia does not say that A has to be initial in D.
You seem to be misunderdtanding their example. In the example, T(V) is not a shadow, it's the original object A in the category D, which is the category of unital associative K-algebras. The functor U is the forgetful functor from the category of unital associative K-algebras to the category C of vector spaces over K, so the shadow of T(V), U(T(V)), is the vector space of T(V). Ф is the inclusion map from V to U(T(V)). T(V) is not initial in the the category of unital associative K-algebras, but for any unital associative K-algebra Y and for any linear map f from V to U(Y), there is exactly one algebra homomorphism g from T(V) to Y such that f is the composition of U(g) and Ф.
4372683
Ah, you're right. A does not have to be initial in D.
The K-Vect, K-Alg example makes more sense with that. I've been trying to rework it with other similar examples after posting that, and I kept getting inconsistent results mapping it back to the Wikipedia example
. I have zero intuition for algebra.
Thanks for clearing things up.
4372700 For me, it's the other way around: I do have some intuition for algebra, but I have a very hard time getting concepts from category theory, past the very basic ones, into my head.
It doesn't help reading you that my intuitive picture of a category is quite different from what you seem to have. When I imagine a category, I think of a category where objects are sets with some structure and morphisms are maps which preserve this structure – e.g., the categories of sets, groups, algebras, etc. (If I'm not mistaken, they are called concrete categories.) So, for example, if I was asked what concept of category theory I would compare analogies to, I would say "morphisms", not "functors". For me, functors are something of a higher level.
4372762
There are a few differences between that view and my view. The easy one to explain is that the only structure that morphisms have to preserve is identity. So long as id○f = f○id, anything goes as far as morphisms are concerned. That's general enough to represent any functional relationship, not just ones that are intuitively structure-preserving. You can specify which morphisms you actually care about, but you may not always be able to determine a set of rules explaining why you care about them or what structure they preserve. In this case, the specification of morphisms itself can be seen as a description of the structure you want to preserve, and having the preserved structure be explicit through morphisms makes it clearer what's going on and what you can do with it, even if the rules for morphisms are unspecified. (It's a middle ground that lets you be as specific as you want while giving you a concrete way to specify potentially-ambiguous things.) That's why I prefer to think of analogies as functors rather than morphisms.
The other difference is a little harder to explain, and take this with the caveat that I don't have a formal education in mathy things. If something doesn't make sense to you, it's more likely an indication that my understanding is off.
I don't think of functors as being fundamentally distinct from morphisms. They just define a second level of structure that needs to be preserved. You can treat functors as morphisms and frequently morphisms as functors. The former is the common way to use it, so I'll give an example of the latter (treating morphisms as functors).
Group theory defines four requirements that each group object in the category of groups needs to preserve. To turn a group homomorphism into a functor, think of the group object as a category where each element is represented by a single object or morphism (i.e., take the unstructured unit of the group object as the objects of the new category). Note that in this view, there can only be zero or one morphisms between any two objects of the new category because each object there is a singleton. For groups in particular, there is always exactly one, and each morphism can be represented by a group element (because b-a is always a specific group element).
The intuitive view of the new morphisms is to imagine each binary operation as a morphism. a+b would be a morphism +b from a.
You can represent each of the group theory axioms in the new category like this:
* Closure: for every chain of morphisms a, b in the category their composition a○b is also in the category.
* Associativity: for every composition of morphisms a→b→ c in the category, the order of composition is irrelevant.
* Identity: every object has an identity morphism.
* Inverse: every morphism is an isomorphism.
Now group homomorphisms look like functors with structure defined entirely by arrows. It also happens to be that 3 of these are axioms of category theory (closure, associativity, identity). The easy way to generalize this now is to let each object of this new category represent an arbitrary object instead of a singleton. This is how you get groupoids. This is why groupoids are seen as generalizations of groups. That they preserve the axioms of category theory makes them particularly nice for studying higher category theory.
Rings can be seen as an abelian group with endomorphisms. Whereas groups have a shared representation between only inner elements and inner morphisms (respectively each group element x and operation +x), rings have a shared representation between inner elements, inner morphisms, and outer morphisms (respectively x, +x, and *x).
Modules are rings with inner elements replaced with an abelian group. The ring elements and the abelian elements don't necessarily share a representation. So you have outer morphisms (ring multiplication) and inner morphisms (ring addition) sharing a representation, then inner elements (abelian group) with a potentially distinct representation.
I haven't spent time with non-total algebras or non-associative algebras, but I suspect there's a similar tiered representation of them. (I haven't spent that much time with groups, rings, or modules either as I'm still piecing everything together, but the above seems consistent with everything I know about them.)
4373383 I agree that morphisms and functors are of similar nature. It's just that it's harder for me to think this way.
If I understand correctly your description of group as a category, for every group element a your category has a corresponding object, let's denote it O_a, and for every couple of elements a, b there is a morphism (+b)_a: O_a -> O_{a+b}. From what I've read, a more conventional way to represent a group as a category is to have a category where there is one object, and group elements correspond to morphisms of this object to itself. This way is simpler, and it's also better in the following way: in the standard representation, every group homomorphism corresponds to a functor, and every functor between two such categories corresponds to a group homomorphism. In your representation (as I understand it), every group homomorphism corresponds to a functor, but not every functor corresponds to a homomorphism. For example, for any given group element d we can construct a functor of this group's category to itself which maps O_a to O_{d+a} and (+b)_a to (+b)_{d+a}. Unless d=0, this functor does not correspond to a group's homomorphism to itself: it maps O_0 to O_d, not to itself.
4372574 What would the morphisms in the category of all bottles be? You're saying that they are relationships; "A is heavier than B", "B is of the same colour as C" – are these valid examples of relationships? That is, do they describe morphisms from A to B and from B to C (or maybe from B to A and from C to B)? If yes, then what is the composition of these two morphisms?
4373988
That is a more conventional view of a group as a category, and I do use that view of groups as well sometimes. It's useful when you want to find group structure in things not labeled as groups, but less so when you want to find meaningful generalizations of groups. If you add just two or three levels of depth to the conventional view, you'll quickly lose track of what's going on, and you'll run into some hideous issues trying to specify how functors and morphisms are supposed to relate to one another. If you split up the object, it's a lot more manageable. Just the module example with two levels of abelian groups is difficult to picture in the conventional view.
Keep in mind that the category was constructed by treating all elements as unstructured units. The 0 object doesn't have any special meaning, and all object labels are arbitrary. Morphism labels are also arbitrary except where cycles are involved (eg., +a○-a needs to be equal to id). If the object in the conventional group category has one element for each group element, our two views are equivalent in this regard.
Those are valid examples of relationships. The proper composition depends on what the goal of the analogy is (i.e., what aspects of A-heavier-than-B and B-same-color-as-C need to be preserved for the analogy to be useful). This kind of analogy might be useful as a (really vague) reference in a story, in which case morphisms can be seen as an inclusion map of some information (in the information theory sense) about the underlying reference. You can imagine something like a vector of bits where each morphism corresponds to a bitwise AND mask for the most straightforward case.
Transferring information like that is the most generic case though, and I don't think that's a common application of analogies. It's almost certain that such a case would end up being about probabilities rather than categorical logic, so I'd recommend using statistical mechanics instead of category theory. The point of category theory, as I'm trying to sell it, is to provide a useful option to leverage intuition. That's not really applicable in your scenario as there's no intuition to leverage.
4372762
Which ones do you have trouble with?
4374006 Ah, so you don't mind having several functors representing the same homomorphism. But it seems to me that even then you have functors which don't correspond to any homomorphism.
For example, consider Z/2Z, the group of residues modulo 2, and let its category consist of objects A and B. And let Z/3Z's category consist of objects C, D and E. The only homomorphism from Z/2Z to Z/3Z is the trivial one. The way I see it, it corresponds to functors which map both A and B to the same element of {C,D,E} and map all morphisms to the corresponding id. Now, as I understand it, for any couple of objects X and Y in the kind of category you describe there is exactly one morphism from X to Y. So there is the following functor between these two categories: it maps A to C, B to D, id_A to id_C, id_B to id_D, the morphism from A to B to the morphism from C to D, and the morphism from B to A to the morphism from D to C. It doesn't seem to correspond to any homomorphism.
The reason for it as I see it is that for a given group element b all the morphisms marked as +b (but having different source objects) are supposed to represent the same element, but this is not reflected in any way in the category structure (unless b is the neutral element), so there is no guarantee that a functor maps them to morphisms which are all marked the same. The conventional approach doesn't have this problem because there is only one +b morphism there.
4374092
Huh, you're right. There were rules implicit to the representation (giving the same labels to different morphisms) that weren't captured by the structure.
That actually makes it more clear what the difference is between groups and groupoids. With groupoids, the view of which morphisms are available is local to each object, whereas with groups that view is global. I guess that means you can turn a groupoid into a group by transforming all local morphism views into global ones.
The process for converting a groupoid to a group seems straightforward. I worked this out below using the singleton objects view of groups as the groupoid.
I'll treat each morphism as a matrix with these representations:
* Each object is given an index.
* The local morphism view is an N by N matrix of N by N matrices. The outer matrix is diagonal, and the inner matrices are not. Each inner matrix contains a 1 at (column D, row C) if the morphism has the D'th object as the domain and the C'th object as the codomain. If you multiply one of these inner matrices with a vector where the D'th element is 1, you'll get a vector where the C'th element is 1. The ordering of morphisms along the outer diagonal is arbitrary. This matrix is constructed for each object X, and it contains only the morphisms where X is the domain.
I need a perspective matrix as well so I can specify how the global view of morphisms relates to the local view:
* The identity morphism of the object at index X is represented by the N by N square matrix where the element at (column X, row X) 1, and all other elements are 0.
* The perspective transformation for an object at index X is an N by N matrix where all of the diagonal elements are set to the identity morphism of the X'th object.
If you treat each local view as the product of a "perspective" transformation with a global view, you get:
G * P_X = S_X * L_X
Where P_X is the perspective transformation, G is the global view of morphisms, S_X is a matrix that just shuffles around morphisms, and L_X is the local view of morphisms. S_X, P_X, and L_X are all specific to each object of the groupoid, while G is shared by all objects. The goal is to find the mapping from L_X for all X to G so that a functor can map morphisms from the groupoid to the group.
If you sum both sides over all indices, you get:
G * Identity = Σ S_Y*L_Y
G = Σ S_Y*L_Y
We're left with:
Σ S_Y * L_Y * P_X = S_X * L_X
Which doesn't depend on the global view, and where the only free variables are S_X for all X. After finding a solution for S_X, you can plug it back into the equation for G to find the mapping from L_X to G, which is the functor we're looking for.
If you work this out for the Z/2Z case, you get a global morphism view of two matrices along the diagonal: identity and [[0, 1], [1, 0]], which correspond to +0 and +1 respectively.
4375193 I will need some time to digest this. But let me check some things first: is this description applicable only to the grupoids you've described before, the ones that are supposed to represent groups, or is it something that should work for any groupoid?
4372574
I have a BS in math. Feel free to recommend one, though I can't imagine reading it anytime soon.
I'm thinking maybe you mean a morphism from X to U(the set of all bottles)? U is itself a morphism. You can view a morphism as a set, and define another morphism as being from one set onto the set denoting that morphism. Is that really what you want to do?
I'm confused that you call some morphisms "functors".
Mathematics, sure. But Platonic Forms are not a mathematical concept. They are the claim that reality is mathematical. There are 3 main problems with Forms:
1. They claim that categories of human thought can be defined analytically. They aren't and can't be. Talking about Bottles in your example implies the Forms can be applied to terms of human language, but they can't. If you use a system based on that kind of formalizing for philosophy or for addressing real-world problems, you're going to have to be very, very careful not to fall into the traps of rationalism. I wouldn't start down a path like that myself. I would begin with linguistically, psychologically, neurobiologically plausible theories of how categories and category membership works. Otherwise you're going to end up recreating logical positivism.
If you can generalize it to say "I have this function bottleness(X): <States of timespace> -> [0,1]", without trying to define a Bottle form, I would be more hopeful. That would be more psychologically plausible. Concepts are produced from observing a large number of instances, not from pre-existing forms. You shouldn't ever have to create or invoke the Form, only to work with functions which are trained from instances to judge category membership. The Form, I think, should always remain implicit in such functions. It is an abstraction, not a reality.
2. They claim that the set of possible categories is fixed; that no new concepts can ever be invented. This is part of why the Middle Ages sucked so hard: people did not believe in creativity.
3. They portray the world we live in as deceptive and meaningless, and so call empiric observation "deception". They prioritize abstract rationalizing over empiric truth, which inevitably leads to fanaticism and religion. Post-modernists don't think it's strange to say reality isn't real because they're just repeating Plato.
4376516
Try reading this (http://www.fuw.edu.pl/~kostecki/ittt.pdf) until you get to Yoneda's Lemma.
Try this (https://bartoszmilewski.com/2015/09/01/the-yoneda-lemma/) and this (https://ncatlab.org/nlab/show/Yoneda+embedding) to understand Yoneda's Lemma and the Yoneda Embedding. I find that the diagram in the second link helps a lot. (Count the arrows.)
Continue reading this (http://www.fuw.edu.pl/~kostecki/ittt.pdf) until you get to adjunctions.
Read this (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.404.7981&rep=rep1&type=pdf) to understand adjunctions.
Continue reading this (http://www.fuw.edu.pl/~kostecki/ittt.pdf).
I'm still flipping back-and-forth between the last two. As I was looking into this, I fell behind on machine learning papers. I'm trying to get caught on up those now before I continue with adjoints and topos theory.
That's correct. Whenever you see something like "a morphism from object X to morphism (or functor) Y", it usually (always?) means "a morphism (or morphisms) from object X to the image of Y". The language (saying there's a morphism from an object to a morphism) seems to be a reference to comma categories, which are used to define a lot of categorical concepts concisely.
A functor is just a special kind of morphism. A morphism within a category is called a morphism. A morphism between two categories is called a functor. A functor maps object-to-object and morphism-to-morphism from one category to another in a way that preserves equality relationships. On the Wikipedia page for Universal Property, A, Y, and g belong to one category, and X, U(A), U(Y), Φ, f, and U(g) belong to a different category. Since U translates objects and morphisms from one category to another, it's called a functor.
I was using the bottle example because it's more inline with the idea of Platonic Forms, and because I thought it would be easy to grasp by anyone familiar with Platonic Forms (as opposed to Platonic Forms and X mathematical concept). I don't think bottles specifically can be modeled that way. I'm lying. I think of an initial Bottle as being analogous to a generative model of bottles, and a terminal Bottle as being analogous to a recognizer of bottles, both of them in both the machine learning sense and computing sense. As you read more of limits and colimits, you might find that it's natural to think of them as well as generators and recognizers respectively. I think that at least shows that universals in category theory don't have to be anti-empirical.
4375530
I'll try it out and get back to you.
4375530
It's a little nuanced exactly what G is. I have a more abstract version of the construction that's more intuitive and that makes the limitations more clear. For this, I'm going to assume that exponential maps and limits always exist. (You can get this by embedding the groupoid in the category of contravariant functors from the groupoid to Set. The embedding doesn't introduce any bad objects or morphisms for the construction because the only extra object/morphisms used are the ones we're trying to construct.)
1. Let G be the
limitproduct of all Hom(X,Y) for all X,Y in the groupoid,excluding identity morphisms.2. G defines
the limit ofautomorphisms for thecolimit of all objectsproduct of all domains in the groupoid (with duplicates, wherever there is an automorphism). (Note: This only works because all morphisms are isomorphisms.)Step 1 is only possible when there are a finite number of morphisms in the groupoid. This is easy to get around though because we only care about non-decomposable morphisms.
Step 2 is easier to see if you imagine each morphism as a table with two columns. For each morphism, have the entries in one column list out the domain, and have entries in the other column list out the corresponding element of the image. The product of any two tables
is a table with three columns: one for the domain, and one for each of the morphisms concatenation of the two tableshas a product value in each cell.Since G is defined as a
limitproduct of morphisms in the groupoid, we know it preserves enough information to recover the groupoid and doesn't introduce any unnecessary morphisms.Since G acts on the colimit of all objects in the groupoid, we know we can map all objects in the groupoid to a single object without changing G (i.e., without adding or removing any entries in the table defined by G).I think there is only one requirement for this to define a group: all morphisms need to have inverses,
and (2) keeping in mind that G was defined without any of the identity morphisms in the groupoid, there cannot be any identity mapping entries in the table describing G. The second requirement exists to make sure the composition of two morphisms x,y in G equal identity only when x and y are inverses of one another. Otherwise you could be allowing some weird group homomorphisms on the result.You always end up getting a group with the kinds of groupoids I described before because those only ever have singleton objects, so inverses always exist where isomorphisms exist. Groupoids in general are not necessarily the same as groups.EDIT: Note the crossed-out parts for simplifications and corrections. I need to stop writing posts at 5am. Also, apparently with groupoids, morphisms are not only invertible, but have inverses. I guess in that case, yes, any groupoid can be turned into a group. But the way I did it in this post, the G from my previous example here 4375193 would be seen as a single morphism. So all I really did here was show that groupoids are groups with inner structure...
4376944 I'm afraid that this is getting too deep into category theory for me...
What do you mean by product here? Do you consider Hom(X,Y) as sets or as something more?
"All domains" means the same as "all objects", right? So I have a similar question: what does product mean for them?
4378492
I do. If there are two morphisms from W to X, then Hom(W,X) is a set containing those two morphisms. If there is one morphism between Y and Z, then Hom(Y,Z) is a set containing one morphism.
Letting Hom(W,X) be {A, B} and letting Hom(Y,Z) be {C}, the product contains two product morphisms: {(A, C), (B, C)}. The product morphism (A, C) takes the domain (W, Y) to the codomain (X, Z). If you imagine each morphism to be a table with one column representing the domain and one the range, then each entry of the product morphism (A,C) would map to a unique entry in A and a unique entry in C.
The coproduct morphism A+C would take the domain W+Y to the codomain X+Z. This would be like concatenating the tables describing A and C. In the table representation, each entry in A would map to some unique entry in A+C, and each entry in C would map to some unique entry in A+C.
The domain for each morphism. Taking the three morphisms A, B, and C above, the domains would be W and Y. Taking the product with duplicates would mean (W, W, Y). W is represented twice because there are two morphisms with domain W: A and B.
Let's say there's a groupoid with these morphisms:
A: X→Y (isomorphism)
B:X→X (automorphism)
C:Y→X (isomorphism)
The product morphisms would be {(A, B, C)}, which has the following table. Note that [X, X, Y] should expand to include all of the elements in the product of objects X, X, and Y.
[X, X, Y] → [Y, X, X]
And the object (Y, X, X) is isomorphic to (X, X, Y), I'm assuming there's a morphism that takes (Y,X,X) to (X,X,Y), which is mostly just an inclusion map. This is just so I can treat it the product morphism as an automorphism by composing (X,X,Y)→(Y,X,X)→(X,X,Y).
The number of automorphisms in the product is equal to the (scalar) product of the size of the hom sets. In this case, it's just 1*1*1. If there were two isomorphisms from X to Y in the groupoid instead of one, there would be 2*1*1 automorphisms in the created group.
Since each morphism in a groupoid has an inverse, every product morphism will also have an inverse. Since all of the product morphisms for a groupoid are automorphisms and since they all have inverses, they form a group.
4378547
Aha, so it's the Cartesian product of sets. Got it.
You probably want to take only non-empty Hom(X,Y), or you can restrict yourself to connected groupoids.
Do I understand correctly that you actually take product over all pairs of objects (X,Y), not over all morphisms? So in the example above, you would take product corresponding to (A,C) or (B,C), not (A,B,C)?
So you consider groupoids where objects are sets and morhisms are (not necessarily all) maps between them?
A groupoid has to have at least one morphism from Y to Y as well, id_Y. But OK.
Yes, but there is more than one isomorphism between them. In this example, you can map (y, x_1, x_2) into (x_1, x_2, y) or into (x_2, x_1, y). And it's not clear to me that the grouphs obtained from different isomorphisms would be isomorphic.
And, of course, different groupoids can produce isomorphic groups. But I suppose that you don't mind this.
Also, I don't see what would be the corresbondence between functors between groupoids and homomorphisms between groups obtained in this way.
Was your goal to be able to obtain an arbitrary group from some groupoid in such a manner? It seems to me that for most groups the only way to obtain them this way would be from the conventional representation by a groupoid with a single object. (That is, if you restrict yourself to connected groupoids.)
4378920
Curses, I forgot. I mentioned it in 4376944 but not in 4378547, and I never expanded on it. The category of functors I handwaved in refers to the codomain of the Yoneda embedding of the groupoid, which is a category of functors to Set. You can think of exponential objects and limits/colimits in that category of functors in terms of exponential objects and limits/colimits in Set.
Good point point on using non-empty hom sets. I missed the vacuous case.
That's right.
I know, but identity morphisms and compositions don't impact the conversion.
The image of any product morphism here always contains exactly the same elements as the domain, and the set of product morphisms is independent of the inclusion maps, so different groups defined by different inclusion maps will always be isomorphic. If you think of them as permutations, it might be more clear that they're isomorphic. Also, each product morphism contains enough information to permute its own image to be in the same order as its domain.
To see why the image of any product morphism always contains the same elements as the domain, you can look at two aspects of the product morphisms.
First, every time you take a product morphism, you end up with exactly the objects you started with. This is because every morphism is an isomorphism, and so the count of each object in the product domain is going to be the same as the count of each object in the product codomain. (X,X,Y) and (Y,X,X) contain the same numbers of X objects and Y objects, and they always will because for every morphism X→Y there is a corresponding morphism Y→X.
Second, every product morphism in the product of groupoid hom sets has an inverse. If (A,B,C) is a product morphism, then its inverse is (A',B',C') with A' being the inverse of A, B' being the inverse of B, and C' being the inverse of C. The product morphism (A',B',C') must exist because A', B', and C' exist in distinct hom sets of the groupoid when and only when A, B, and C exist in distinct hom sets of the groupoid. This happens because (1) every morphism in the groupoid has an inverse, and (2) distinct hom sets remain distinct when the domain and codomain are swapped. The second part means that Hom(A,B) and Hom(A,C) are distinct, and therefore so are Hom(B,A) and Hom(C,A) so long as all these hom sets are non-empty.
Do you mean different groupoids should be able to produce isomorphic groups? I don't think the above method allows it. The morphisms in the new group are defined by a direct product, so it will be possible to recover the original groupoid from the group. I think if you replace all products with limits, you can have different groupoids producing isomorphic groups, but other things might need to change for that to define a group.
I was originally trying to recover the single-object group morphisms from the split-object group morphisms. I thought there might be a way to do it, which is what 4375193 was about. In writing 4376944, I realized that the method didn't give me the result I was looking for in the general case. In the end, I think all I ended up doing was restating the "groupoids are groups with inner structure" sentiment in a more complicated way.
It did make one thing clear though. I originally said that groupoids can be turned into groups if all of the per-object "views" in the groupoid can be converted to some shared global "view". The group you end up getting in the end depends on how this conversion is done, and there are probably multiple "correct" answers that preserve whatever information you want. The method I described uses the product of all views to determine the global view. You can almost certainly come up with a method that uses coproducts instead, or other limits or colimits. All of these are going to be universal in some sense, but they're not always going to be isomorphic to one another.
I'm not sure either, and there might not be one if you use products to define the groups. I'll try to see if there's another definition that forces groupoid homomorphisms to preserve group structure.
4378920
I'm going to call the functor from the groupoid to the group G.
In a connected groupoid with objects X and Y, let f be a morphism from X to Y. For any automorphism m1 on X, there corresponds an automorphism m2 on Y such that:
f○m1 = m2○f
Proof:
f○m1○f' = m2○f○f' = m2
Where f' is the inverse of f.
Since this can be done for any automorphism on X or Y, we can use only one object's automorphisms to define all automorphisms m in the connected groupoid. With this, we have:
G(f) ○ G(m1) ○ G(f)' = G(m2)
For m1 in automorphisms on X, for m2 in automorphisms on Y.
You might be able to use this equation to generate all of G from a groupoid. Hom(X,X) forms a group. G(f) needs to be added as an element of the group or needs to be mapped to an element in Hom(X,X). If it's mapped to an element of Hom(X,X) (I think in this case it needs to be mapped to identity unless X has no non-identity automorphisms), then the equation above describes an automorphism, and all automorphisms on Y need to be mapped to automorphisms in X. Otherwise all automorphisms on Y need to be mapped to distinct elements (other than identity, which f must preserve).
After f, you can move onto other morphisms in Hom(X,Y), then other connected objects.
In the end, each automorphism group in the groupoid gets mapped to some subgroup, and so the set of non-automorphism isomorphisms must also form a group. I suspect that either those isomorphisms all get mapped to identity, or all automorphisms on all objects in the groupoid get mapped to identity. It might be possible to sidestep that requirement in some cases...
That'll have to wait until after sleep though.
Sorry, I don't know what the Yoneda embedding, exponential objects, limits and colimits are. I haven't gotten this far yet.
Maybe they can't be isomorphic as groups with additional structure, but they can be isomorphic as just groups. You mentioned yourself here: 4376944 that the groupoids you described here: 4373383 all produce a group with a single element, even if this groupoids have different amount of objects and are thus non-isomorphic. Alternatively, if some groupoid produces group G, you can also obtain G (or rather an isomorphic group) from its conventional representation by a groupoid with a single object, even if your original groupoid had more than one element.
That is, if for every group element you have its representation as a morphism product, then you can probably reconstruct the groupoid, but this representation is not a part of group structure. If all you have is group's multiplication table, it may be possible to obtain this group from different non-isomorphic groupoids.
I would say that a better way to look at a groupoid is as, well, kind of several copies of the same group. Here is what I mean: let G be a group and let S be a set. Consider groupoid, let's denote it as Gr(G, S), where:
-- the set of objects is S;
-- for objects X, Y, the set Hom(X,Y) is the Cartesian product G×{X}×{Y} (essentially, it's just a copy of the group G) with the composition given by (h, Y, Z)∘(g, X, Y) = (gh, X, Z).
Then, if I'm not mistaken, assuming the axiom of choice, every connected small groupoid is isomorphic to a groupoid of this form. The proof goes like this: if we have a groupoid Gr, let S be the set of its objects. Choose some object T from S. Hom(T, T) has group structure due to composition; let G be this group. For every object X from S, choose an arbitrary morphism f_X from T to X. Then we have an isomorphism from Gr to Gr(G, S) given by this: every object is mapped to itself, and a morpism m from X to Y is mapped to ((f_Y)^{-1}∘m∘f_X, X, Y). It's easy to see that it preserves composition, and it's invertible because every f_X is invertible.
Also, one can see from this proof that if Gr_1 and Gr_2 are two connected small groupoids, X_1 is an object of Gr_1 and X_2 is an object of Gr_2, then Gr_1 and Gr_2 are isomorphic if and only if their sets of objects have the same cardinality and Hom_{Gr_1}(X_1, X_1) is isomorphic to Hom_{Gr_2}(X_2, X_2) as a group.
Edit: I didn't see 4380023 when I started to write this comment. I see now that you're going in a similar direction there.
4380036
I think that's right, but there must be some implication to having multiple objects that are all isomorphic to one another.
I think I have some idea on what to do with the non-auto isomorphisms. It looks like the non-auto isomorphisms in a groupoid also form a group structure.
Proof:
Let f be any morphism in Hom(X,Y), and let g be any morphism in Hom(Y,X).
f∘g is then a morphism in Hom(X,X).
f∘g has an inverse.
The set of all f∘g in Hom(X,X) forms an automorphism group on X.
For shorthand, I'm going to call the set of all f∘g Hom(X,Y,X).
Moreover, the group structure of isomorphisms is related to the group structure of the objects.
Proof:
Hom(X,Y,X) in Hom(X,X) forms an automorphism group on X.
The set of all h in Hom(X,X) forms an automorphism group on X.
There is an inclusion map from the set of all Hom(X,Y,X) to the set of all h.
You can extend the proof to Hom(X,Y,Z,X) to say that it forms a subgroup of Hom(X,X), and to any cycle of morphisms in the groupoid.
What's interesting about this is that you can use it to factor arbitrary group auto-homomorphisms, even simple ones. This makes me think that that hom sets from one object to another should be equivalent...
Proof:
Suppose there are two distinct morphisms f, g in Hom(X,Y) for some arbitrary X,Y in a connected groupoid.
Suppose there is at least one isomorphism h in Hom(Y,Z) for some arbitrary Z in the connected groupoid.
There is a second isomorphism in Hom(Y,Z).
Subproof:
There are two distinct isomorphisms h∘f and h∘g in Hom(X,Z).
There are two distinct isomorphisms f'∘h' and g'∘h' in Hom(Z,X).
There are two distinct isomorphisms h∘g∘f' and h∘f∘g' in Hom(Y,Z). (QED subproof)
Repeat until all hom sets have the same number of isomorphisms.
Moreover, these hom sets are isomorphic to each automorphism hom sets in the same groupoid.
Proof:
Since the objects X, Y, and Z were selected arbitrarily in the previous proof, we can let X=Y.
Constructing a groupoid using one group for two objects lets you introduce something like the square root of a group automorphism. Doing the same with three objects lets you introduce the cubic root of a group automorphism. The only requirement is that the group's automorphisms must be isomorphic to the set of group auto-homomorphisms (e.g., for abelian groups, the group must be closed under both addition and multiplication).
... So we're back to "groups with inner structure"
.
My bad. An exponential object is just an object that represents a morphism in the same category. A limit is an initial object in a diagram. A colimit is a terminal object in a diagram. For limits and colimits, replace each object of the diagram with an element in that object such that the diagram commutes. The set of all commuting tuples is the limit, and the union of all such commuting tuples is the colimit.
For the (covariant) Yoneda embedding, you map each object X in the groupoid to the set Hom(X,X), then each object Y to the set Hom(Y,X), then each object Z to the set Hom(Z,X), and so on. (Morphisms in the groupoid get mapped to the right-compose operator.) This defines a contravariant functor from the groupoid to a diagram in Set. Repeat for each object in the groupoid to get a separate functor for each object. All those functors form a diagram in the category of functors. In that category of functors, the set of natural transformations corresponding to Hom(X,Y) turns out to be isomorphic to Hom(X,Y) in the groupoid, and this is true for all X,Y in the groupoid.
The nice thing about that diagram of functors is that it can by extended by all finite limits, colimits, and exponential objects by analogy with the same objects in Set.
4381198
Yes, this is what I meant here: 4380036 . I'm sorry that I didn't write it in more details. And I suppose that my description of a groupoid as "kind of several copies of the same group" was somewhat misleading: I didn't mean that you get a copy of the same group for every object; you get a copy of the same group for every ordered pair of objects. In my description of Gr(G,S), every set Hom(X,Y) is a copy of the same group G.
The set Hom(X,Y) doesn't come automatically with a group structure if X<>Y, but if you choose an object T, a functor f_X from T to X and a functor f_Y from T to Y, then you can introduce group structure on Hom(X,Y) with operation which I will denote ∘_{T, f_X, f_Y}, by setting g ∘_{T, f_X, f_Y} h = g ∘ f_X ∘ (f_Y)^{-1} ∘ h. The unit element in this group is f_Y ∘ (f_X)^{-1}, and the inverse element of g is f_Y ∘ (f_X)^{-1} ∘ g^{-1} ∘ f_Y ∘ (f_X)^{-1}. Mapping g to (f_Y)^{-1} ∘ g ∘ f_X gives an isomorphism between this group and Hom(T,T).
Which group are you talking about? If you're talking about Hom(X,X) (let's denote it H), then I don't understand what you mean. If you're talking about the big group G you constructed here: 4376944 , then I guess you can look at an automorphism of H as a root of an automorphism of G, but:
1) Only a subset of all groups can be obtained in such a way from a groupoid with more than one object. As all these isomorphisms show, if the groupoid has n objects, G is isomorphic to the direct product of n^2 copies of H. Most groups cannot be represented as a direct product of more than 1 copy of another group.
2) When a groupoid has more that one object, only some automorphisms of G would have a root. If you have fixed isomorphisms between all groups Hom(X,X) and you apply the same automorphism to each of these groups, that would correspond to an automorphism of G. But you can also obtain an automorphism of G by applying different automorphisms to different Hom(X,X) or even by switching objects between themselves.
So, for example, the only finite group that fits is the one-element group? For any other group, any automorphism is an auto-homomorphism, but there is at least one auto-homomorphism which is not an automorphism: the trivial one. If the group is finite, then these sets are also finite and therefore are of different size.
Edit: I fixed some things and expanded the group description.
4381319
Yeah, I see. That's pretty clever. This works so long as f_X and f_Y are iso, though I guess that's a weaker requirement than saying they have an inverse, which is necessary for the construction anyway. But this only shows that all Hom(X,Y) are isomorphic to one another. If you want to show that they're all copies of one another, you need to show that they're equal as well, and that's a stronger requirement.
I'm talking about Hom(X,X), H. The roots of Hom(X,X) are not in Hom(X,X), they're in Hom(X,Y). Also, only one morphism in Hom(X,X) can be given a root at a time (though by giving that morphism a root, others might get one as well).
Let Hom be the automorphisms of group H. Every Hom(X,Y) is isomorphic to (but not necessarily equal to) Hom in the groupoid. Even if you let every Hom(X,X) be equal to (and not just isomorphic to) one another, it's still not necessarily true that every Hom(X,Y) is equal to one another. You can see why this happens if you look into H. We're looking for some H1 and H2 where the automorphisms on H1 are equal to the automorphisms on H2, but where H1 is not equal to H2.
Let x0 and x1 elements of H. There exists a morphism f in Hom that takes x0 to x1:
f(xn) = xn * x0⁻¹ * x1
Since we're assuming that every Hom(X,X) in the groupoid is equal to Hom, we know that f exists in Hom(X,X) for all objects X in the groupoid. That does not mean though that x0 and x1 exist in all objects Y in the groupoid.
Proof that the morphism f defined by some x0 and x1 can exist in Hom(Y,Y):
Let x0 = myx*y0, let x1 = myx*y1, and so on for all elements xn in X and for all elements yn in Y (meaning Y is isomorphic to X, and the bimorphism from Y to X is given by operation with some myx).
f(yn) = yn * (myx*y0)⁻¹ * (myx*y1)
f(yn) = yn * (y0⁻¹*myx⁻¹ * myx*y1)
f(yn) = yn * (y0⁻¹*y1)
Note that this is possible even when myx doesn't belong to H. This is because myx cancels itself out in morphism in Hom. For the above proof to work, you need to extend the group operation of H to work on elements of both X and Y. When you do that, you can find myx by taking xn * yn⁻¹. You can do this for all xn in X and all yn in Y. The * now corresponds to a groupoid operation, not just a group operation.
This construction only works when myx corresponds mostly to a group homomorphism. Phrased in a different way, myx * (group operations in Y) = (group operations in X). The only reason myx doesn't have to correspond exactly to a group homomorphism is because it doesn't have to preserve the identity morphism.
You get square roots if you let Hom(X,Y) = Hom(Y,X). Proof:
x0 = myx * y0, this defines myx as an isomorphism from Y to X
y1 = myx² * y0, this defines y1 from the above. Since myx is an isomorphism, so is myx².
y1 * y0⁻¹ = myx²
Since y0 and y1 are in Y...
yn = myx², this defines yn from the above
Since Y is isomorphic to Hom(Y,X,Y),
there existsI suspect there exists a myx for each yn in Y satisfying the above.Keep in mind that Hom(X,Y) does not contain all square roots of automorphisms. The square root of just one automorphism is enough to define all of Hom(X,Y), and you can select any automorphism to define Hom(X,Y).
I was wrong in my previous post in saying that the group automorphisms have to be iso with with group auto-homomorphisms. I confused myself by thinking of morphisms between objects as group homomorphisms.
This can be done with any group. If you do this with one-element groups, then each Hom(X,Y) corresponds to a root of unity (i.e., a rotation).
4383350
Isn't an isomorphism by definition a morphism that has a two-sided inverse? So these requirements are identical.
I'm not sure that I understand what you mean by "equal". From my point of view, the only way for two different Hom-sets to be equal is for them both to be empty. If X and Y are two different objects, then an element of Hom(X,Y) cannot be equal to an element of, let's say, Hom(Y,X), because, for example, the source of an element of Hom(X,Y) is X and the source of an element of Hom(Y,X) is Y; if they were equal, they would have equal everything.
So when I said that all Hom(X,Y) can be considered as copies of the same group, what I meant was that:
1) For every X,Y, there is a bijection from Hom(X,Y) to this group. If we choose an object T, and for every object X choose a morphism f_X from T to X, then we can set the group to be Hom(T,T) and the bijections to be P_{X,Y}: Hom(X,Y) -> Hom(T,T) defined as P_{X,Y}(g) = (f_Y)^{-1} ∘ g ∘ f_X.
2) This collection of bijections preserves composition/group operation: if g is a morphism from X to Y and h is a morphism from Y to Z, then P_{X,Z}(h ∘ g) = P_{Y,Z}(h) ∘ P_{X,Y}(g). In particular, a bijection P_{X,X} is a group isomorphism. (Also, if one introduces group structure on Hom(X,Y) as described in 4381319 , then P_{X,Y} is a group isomorphism as well.)
The f you describe is not a group homomorphism. It does not preserve composition: f(a * b) = a * b * x0⁻¹ * x1 is not the same as f(a) * f(b) = a * x0⁻¹ * x1 * b * x0⁻¹ * x1.
And in general, there doesn't have to be a group homomorphism that would map a given x0 to a given x1. For example, take x0 = id_X and let x1 be any other element of H, then a homomorphism cannot map x0 to x1. Or, more generally, if the order of x1 does not divide the order of x0, a homomorphism cannot map x0 to x1 (and for an automorphism to map x0 to x1, their orders have to be equal).
By the way, how did you manage to use a superscript in that formula? Fimfiction doesn't seem to support HTML tags sub and sup, so I've been using LATEX notations instead.
Er... yes. I thought it was just a pair of bimorphisms, but looking back now, it seems that was just a quirk of whatever I was reading while starting off.
Keep in mind that the morphisms here are supposed to represent operation with groupoid elements. There's a generalized operation here, which I'm calling the groupoid operation, that acts across objects when done with certain groupoid elements. If groupoid operation with the same element can describe morphisms in two directions, I'm saying that the two morphisms are equal. That's an aspect of groupoids not captured by the structure alone (in our representation, at least) but is necessary for a one-to-one translation between morphisms (or at least equivalence classes of morphisms) and operation with groupoid elements.
For example, let one object X in the groupoid be the set of rationals k closed under addition by rationals k, and let a second object Y be the set of k*sqrt(-1) closed under addition by rationals k. Hom(X,X) and Hom(Y,Y) correspond to groupoid operation with the same set of groupoid elements (addition by rationals). In this specific case, Hom(X,Y) and Hom(Y,X) also correspond to groupoid operation with the same set of groupoid elements (addition by rationals-times-sqrt(-1)), though those sets are different from Hom(X,X) and Hom(Y,Y).
You can also write out the equations using only compositions and inverses to find that two morphisms can be equal even when they don't operate on the same set of objects. This is possible when, for example, you can say that the identity element/morphism of a groupoid is unique, and that therefore all morphisms representing the identity element are equal.
I know in a literal sense there's a distinction between the two homsets, and so they're not equal. The category theoretic representation though is adding a distinction that doesn't exist in the structure we're trying to reason about, so at the very least it would make sense to put morphisms into the same equivalence class when they represent the same underlying relation, at least when we're talking about groupoids.
I meant they're the morphisms within a group, not the group homomorphisms acting on a group. The morphisms in a groupoid don't have to be group homomorphisms for at least the reason you pointed out.
They're unicode characters. I just copied and pasted them from another website.
x² x³ x¹
x⁰ xⁱ x⁴ x⁵ x⁶ x⁷ x⁸ x⁹ x⁺ x⁻ x⁼ x⁽ x⁾ xⁿ
x₀ x₁ x₂ x₃ x₄ x₅ x₆ x₇ x₈ x₉ x₊ x₋ x₌ x₍ x₎
xₐ xₑ xₒ xₓ xₔ xₕ xₖ xₗ xₘ xₙ xₚ xₛ xₜ
EDIT: Addition would have made more sense for my example than multiplication. Updated.
My impression is it's not nearly abstract enough. Good old functions and types in programming languages may work well instead of pure math:
(or I'm woefully overestimating number of people familiar with programming languages like that
)
And aren't analogies usually formalized as natural transformations?
5532698
I did a terrible job with this blog post, probably because I didn't understand the topic nearly as well as I should have when I wrote it. In category theory, functions and types are both dealt with abstractly as (respectively) morphisms and objects. Haskell in particular tries to bring category theoretical concepts into normal software development.
It's an interesting question: what's more abstract, category theory or programming languages? I suspect that in theory, programming languages let you work usefully with more abstractions, but in practice, category theory wins out for now for a lot of special cases, and that it will continue to win out until people "complete the bridge" between mathematical intuition and computation. The problem has to do with the underlying representations required to get anything done. Computers require everything to be convertible to known verifiable representations. Math doesn't care about the underlying representations. With category theory, you can have a thousand people representing objects and morphisms in different ways, and all of them can read and verify the same proof with equal consistency. With a programming language, you're limited to representing things that are convertible to basic datatypes, and enough conversions must be known, otherwise it's not possible to check if you even have a valid program.
In other words, the barrier to encoding proofs in category theory is much lower than the barrier to encoding proofs in (today's) programming languages. It's not clear to me whether that's because category theory is more abstract than today's programming languages or whether it's because category theory is more natural than today's programming languages.
Here's an example:
The proof is really simple:
You need to know almost nothing about morphisms and categories to follow the proof, but you need to do a LOT of programming before any software can verify the proof. Is that because category theory lets you work more abstractly, or is it because it's easier to encode this particular kind of proof in category theory than in (modern) programming languages?
5535456
It's not that bad. This typechecks in Agda:
And the theorem proof is kinda shorter than it's statement. Although I cheated a bit by stripping everything that isn't necessary from premises and using concrete category of types (kind 1 types) and functions. But you're right about that stuff being intuitionistic.
5535717
Even with the cheats, that's pretty cool. Do you happen to know why Agda requires you to choose a concrete category?
When I read categorical proofs, it's not like the statements themselves are intuitive to me. I've attached intuitive wording and mental imagery to categorical statements so I can reason through statements intuitively while (hopefully) being able to pull up actual proofs as needed when my mental imagery falls short. Objects are simultaneously spaces and quantities; morphisms are simultaneously embeddings and selections; hom objects are possibilities; morphisms simultaneously embed a basis and define a decomposition; functors take the shape of the domain and the color of the codomain; etc. A lot of it is just mental imagery I've iterated on that was definitely not intuitive when I started. I'll probably find that my intuition is still wrong in subtle ways as I learn more.
As far as I can tell, the language of category theory deals with the thing that spaces and quantities have in common, whatever that is, and it deals pretty much only with that thing. Even that's too general though, and people only seem to care about objects that come with some notion of structure and basis, and about categories that are rich enough to have some notion of extrapolation. So category theory may deal with very general things, but a lot of that generality seems to be unnecessary except maybe to narrow the space of proofs. I wouldn't be surprised if the software notion of types is general enough to cover everything people actually care about when they work with categories.
5535975
It's not a requirement, I just wanted the example to be self-contained (that's why it manually defines equality and function composition) and short. You can define general category as record of universes of objects and morphisms, identities, composition, etc. and proofs for all essential properties, kinda like that, and proof from below would be almost identical, sans everything parametrized with category.
Yeah, I usually try to imagine type and functions (although for Khovanov homology (well, cohomology, but no one cares
) it didn't work all that well)
That general idea even have dedicated name.
5536244
How does the types-and-functions view work? Is there a natural interpretation for lifts and extensions in the types-and-functions view? I can probably figure the rest out from that.
I've seen the Curry-Howard correspondence, but I didn't (and still don't) understand it. Most categorical concepts require you to work with functors and natural transformations, which aren't represented. Is that because functors and natural transformations can somehow be derived from the other concepts, or because they're easy to represent in software? I also see sum and product types, but they don't seem general enough to cover limits and colimits. Is that because they can be derived somehow, or is it because it's easy to create limits and colimits in software? Are true and false supposed to correspond to terminal and initial objects? What's the programming equivalent of an object that's both initial and terminal?
You should write a blog post on these things. I'd read it.
5536457
Unfortunately in Haskell it's made a bit ad-hoc via monads (monads were in standard library from the very beginning, and have special syntax extension for them); stuff to begin would be Functor, liftM, join from Control.Monad and monad transformers. They later made breaking change by adding Applicative trying to make it more general, but it's still not great.
There's Functor typeclass in Haskell and functions of type "∀ t . A t -> B t" tend to be natural transformations if A and B are functors:
With corresponding functions they're analogous to (co)products and indeed less general. There were definition for (co)limits in special category theory packages, but I didn't looked at them (or maybe I did too long time ago).
Singleton and empty types correspondingly (there's always one function that maps empty set on everything and there's one function that maps anything on set of size 1). Non-terminating and failing computations (which are totally a thing in Haskell since it's a general-purpose programming language) are usually ignored, since they break everything, so there's no type which is both.
Honestly, I don't think I'm qualified enough to add something new
I quitted the field, like, 7 years ago and forgot most things (I quickly doublechecked what I said above about Haskell, but it still can be outdated), and "accessible category theory for programmers" thing is well established enough to be a meme decade ago.
5536982
The use of category theory in computer science and software is really weird to me. In (my limited view of) math, lifts and extensions seem to be central, and usually finding them is the whole point of proofs. But in computer science, they seem to be either ignored or afterthoughts. My impression is that math uses category theory primarily for extrapolating constructions sometimes for abstracting results, while computer science uses category theory primarily for abstracting constructions.
You don't have to add anything new. You could just signal-boost things that are interesting or of potential use. Honestly, the stuff I blog about probably isn't that useful to anyone except me, given that they're usually just me playing with concepts in my head with little regard for whether those same concepts are also in other people's heads.
5537126
If I understand historical context correctly, when they were designing Haskell standard library there was a discussion about how to implement Input/Output with different options available: monads, linear types, actor model and some weird provisional stuff they initially had. Monads eventually won and they probably added minimum to support it (which wasn't all that small, actually)
Well, people want to write libraries which are as widely-applicable as possible