2
$\begingroup$

I'm new to category theory, and I'm trying to define two categories which are not isomorphic, yet have identical graphs.

  1. Category $A$ has 3 objects: {0, 1, 2}. For each pair of objects $m, n \in A$ there is a morphism $f_{m} : m \xrightarrow{f_{m}} n$ iff $(m + m) \% 3 = n$. Each object additionally has a morphism $id_{m} : m \xrightarrow{id_{m}} m$. Composition $f_{n} \circ f_{m} = id_{m}$ whenever the codomain of $f_{m}$ is equal to the domain of $f_{n}$.

  2. The objects of category $B$ are 3 kinds of flowers: {"Bluebell", "Texas Bluebonnet", "Red Poppy"}. For each pair of (not necessarily distinct) flowers $p, r \in B$ there is a morphism $h_{pr} : p \xrightarrow{h_{pr}} r$ iff $p$ and $r$ have the same color petals (as implied by their names). The composition $h_{qr} \circ h_{pq}$ is equal to $h_{pr}$.

  3. Functor $F : A \rightarrow B$ maps objects $F(2) = $"Bluebell", $F(1) =$ "Texas Bluebonnet", and $F(0) = $"Red Poppy". It also maps identities of $A$ according to $F(id_{m}) = h_{F(m)F(m)}$, where $m \in A$, and maps the modulo morphisms of $A$ according to $F(f_{m}) = h_{F(m)F(n)}$ where $n = (m + m) \% 3$.

  4. Functor $G : B \rightarrow A$ maps objects $G($"Bluebell"$) = 2$, $G($"Texas Bluebonnet"$) = 1$, and $G($"Red Poppy"$) = 0$. It also maps morphisms of B according to $G(h_{pp}) = id_{G(p)}$, and $G(h_{pr}) = f_{G(p)}$, where $p,r \in B$ and $p \neq r$.

The categories are not isomorphic, because $F(f_{0}) = F(id_{0}) = h_{BB}$, while $G(h_{BB}) = id_{0}$ (abbreviating "Bluebell" as $_{B}$). But the graphs should still be the same, because identity morphisms do not appear in the graph of a category. Is this correct?

  • 2
    The definitions of $A$ and $B$ are unclear. Please elaborate.2012-04-18
  • 0
    Can you tell me what is unclear? I revised the whole question several times before posting, so it includes all the details I can think of. Please let me know what is missing.2012-04-18
  • 0
    @Byron: I'm writing an answer that will hopefully clear things up.2012-04-18

1 Answers 1

4

The definitions of the categories are fundamentally flawed. I suggest that you go back to the definition of a category and try to understand why what you've written down doesn't work out. A morphism is an arrow from one object to another, so "its only morphism is addition modulo $3$" doesn't make sense: addition modulo $3$ assigns a third number to two numbers, which isn't what we need to define a morphism. The same for path composition, which assigns a third path to two paths.

Here are three categories that have some similarity with what you've written; perhaps one or two of them are what you were trying to get at.

Category $A'$ has one object, the set $\mathbb Z_3=\{0,1,2\}$. For every $n\in\mathbb Z_3$, there is one morphism from $\mathbb Z_3$ to $\mathbb Z_3$, namely the function that sends $x$ to $x+n\bmod3$. Composing the morphisms corresponding to $n_1$ and $n_2$ yields the morphism corresponding to $n_1+n_2\bmod3$. The identity morphism for the only object is the one corresponding to $n=0$.

Category $A''$ has three objects, $0$, $1$ and $2$. There is one morphism for each pair of objects. Composition yields the only morphism between the appropriate objects, and the identity morphism for an object is the only morphism from that object to itself.

Category $B'$ has three objects, $a$, $b$ and $c$. There is one morphism from $x$ to $y$ for each path from $x$ to $y$ in the complete graph on $\{a,b,c\}$. Composition of morphisms is defined by composition of the corresponding paths. The identity morphism for an object is the path beginning and ending at that object without any edges.

Now we can define a functor $F$ from $B'$ to $A''$ that assigns to the objects $a$, $b$, $c$ the objects $0$, $1$, $2$, respectively, and to the morphism corresponding to a path from $x$ to $y$ the only morphism from $F(x)$ to $F(y)$. We can also define a functor $G$ from $A''$ to $A'$ that assigns to each object in $A''$ the only object in $A'$, and to the morphism from $x$ to $y$ the morphism that maps $x$ to $y$. We can also define the composition $H=G\circ F$ from $B'$ to $A'$.

  • 0
    Yes, $A''$ and $B'$ are precisely what I was meaning to define. Given these corrections, can we say that $F$ and $F^{-1}$ are isomorphic functors? It's unclear to me whether $F \circ F^{-1} = id_{A''}$. In particular, I don't understand exactly how one ought to define $F(id_{A''})$. Perhaps it depends on how $id_{A''}$ is defined, and there seem to be 2 options: **1.** $id_{A''}(x) = x$ **2.** $id_{A''}(x) = (x + 0) \% 3$ (i.e., it is selected from among the other $A''$ morphisms)2012-04-18
  • 0
    By the way, I don't actually see the difference between your definitions of $A''$ and $B'$ and my definitions of $A$ and $B$. I didn't intend to introduce any third object in the morphisms. Can you help me understand what is incorrect about the way I defined them?2012-04-18
  • 0
    @Byron: A lot of your first comment is again fundamentally flawed. a) No $F^{-1}$ has been defined, and I don't see how to define one. b) Your use of $\operatorname{id}_{A''}$ is inconsistent. In $F \circ F^{-1} = \operatorname{id}_{A''}$ it seems to be a functor whereas in $F(\operatorname{id}_{A''})$ it seems to be a morphism. c) I don't see the difference between 1. and 2., since $(x+0)\%3=x$. About your second comment: But addition modulo $3$ *does* introduce a third object. I think you should spell out your definition of $A$; that would make it easier to see what's wrong with it.2012-04-18
  • 0
    Thanks for your help, I really appreciate. Do you perhaps know of any online documents that give examples of small, specific category definitions like the one I am attempting here? I just don't have a clue how to specify the components of the category. If I could just see a few dozen examples, fully elaborated with all the details, then I could start to see how one properly articulates the definition.2012-04-19
  • 0
    @Byron: I don't, unfortunately. My impression is that you may be confusing objects and sets. Keep in mind that one of the main points of category theory is to abstract away from the view of structures as sets and characterize the objects purely in terms of their morphisms. Also, again I would suggest that you try to spell out very explicitly your attempted definition of $A$. Either you will notice in the process of having to spell it out what goes wrong, or if not, at least it will allow us to point out more explicitly what's wrong.2012-04-19
  • 0
    I've redefined $A$ and $B$ in the original post, and withdrawn my functor definitions because I'm stuck at that point. Your help would be greatly appreciated (as noted in the new version).2012-04-19
  • 0
    btw, I do realize that my "categories" here are pointlessly simplistic, and that in general the objects of $A$ and $B$ ought to be structures instead of atomic units. The thing is, I'm doing research in programming languages and type theory, which requires having a very specific grasp of the way the concepts of category theory correlate to their constituent elements. So I am making example categories with "hyper trivial" object domains, as a way to verify that I understand all the detailed implications of each theoretical concept.2012-04-19
  • 1
    @Byron: You're absolutely right to start out with these simple examples. I wouldn't say that in general the objects "ought to be" structures instead of atomic units -- it's perfectly usual to consider objects without internal structure e.g. in a [poset category](http://en.wikipedia.org/wiki/Partially_ordered_set#In_category_theory). Regarding your new definitions, I don't understand them. First, for $A$, you define six morphisms, one for each ordered pair of distinct objects. This would preclude the existence of identity morphisms, since those have to be from an object to itself.2012-04-19
  • 0
    @Bryon: Then you write that "The identity morphism is trivially $\forall m \in A : id_{m} = m$." Is that supposed to be the definition of further morphisms? If not, it must be wrong, since the previously defined morphisms weren't identity morphisms. If yes, "trivially" would be misleading, since it seems to imply a deduction rather than a definition. Also, it's not clear to me what the intent would be of calling this identity morphism by the same name $m$ as the object -- that seems to just create confusion. Or are you saying that there's some reason for the two to be identical?2012-04-19
  • 0
    @Byron: A further problem with the definition of $A$ is that you say that the morphisms can be composed, as indeed they should, but in fact they can't, since e.g. composing the one from $0$ to $1$ with the one from $1$ to $0$ should lead to one from $0$ to $0$, but no such morphism has been defined.2012-04-19
  • 0
    Category $A$ does have 9 morphisms, and in $id_{m} = m$, the subscript $ _{m}$ just means "the one that goes from $m$ to $m$". These $id$ morphisms should resolve the composition issue you mentioned, right? As for the format, my textbook always describes $id$ morphisms separately from the others, just like I have done here. It sounds like this is not conventional?2012-04-19
  • 0
    @Byron: I understand that the subscript $m$ indicates that this is the identity morphism from $m$ to $m$. What I don't understand is why you write that this is equal to $m$. I guess there's nothing to keep you from saying that, but it seems extremely confusing to me and I don't see the point of it. I've never seen objects and morphisms mixed up before; it seems like a certain recipe for chaos. Why do you want to equate the identity morphism and the object?2012-04-19
  • 0
    @Byron: As to the format, yes, I don't think that's conventional. I'd define all the morphisms in one go, not define some, then talk about their composition, which makes no sense without the missing ones, and only then define the missing ones. Also, I don't understand why you're bringing modulo $3$ into it at all. If you do have all $9$ morphisms for all $9$ ordered pairs of objects, then indeed as you say this is the same as my $A''$; but the connection with modulo $3$ now seems very artificial and it's much easier to just say there's one morphism between every pair of objects.2012-04-19
  • 0
    Right, I was focused on defining the categories and lost track of what they are supposed to contain. I've updated the original post with new $A$ and $B$ that have the kind of content I originally intended.2012-04-19
  • 0
    @Byron: About $A$: Now you've defined six morphisms, $f_0:0\to0$, $f_1:1\to2$, $f_2:2\to1$, $\def\id{\operatorname{id}}\id_0:0\to0$, $\id_1:1\to1$, $\id_2:2\to2$, but you haven't said how they compose. Most of that is determined by the domains, codomains and identities, but you still have to specify whether $f_0\circ f_0$ is $f_0$ or $\id_0$, and it wouldn't hurt to also describe the remaining compositions, even though they're determined. About $B$: I have no idea what colours the petals of those flowers have; a definition that requires encyclopedic research strikes me as very inconvenient.2012-04-19
  • 0
    Sure, I can add the composition details. But the colors of the flower petals are right there in the flower names: two have blue petals, one has red petals. So is there a way to make a functor between 2 categories like this, where the morphisms are not logically related?2012-04-19
  • 0
    @Byron: Yes, there is. Those two categories are very similar, the only difference is that $A$ has one more morphism. If we let $F(0)=\text{Red Poppy}$, $F(1)=\text{Bluebell}$ and $F(2)=\text{Texas Bluebonnet}$, then five of the morphisms correspond to each other, and we have to map $f_0$ to $\operatorname{id}_{\text{Red Poppy}}$ since that's the only morphism with the right domain and codomain. We can similarly define a functor $G$ in the other direction, but then $f_0$ has no preimage, so the two functors aren't inverses of each other.2012-04-19
  • 0
    @Byron: By the way, even if the structure weren't so similar, you can always define a trivial functor from any category to any other simply by mapping all objects to the same object and mapping all morphisms to that object's identity morphism. (About the colours: I saw that there are colours in the names, but I didn't know whether the flowers also had petals in other colours besides the ones in their names.) (And about "composition details": Those aren't just details. You haven't fully specified a category because you haven't specified the composition law and it's not determined by the rest.)2012-04-19
  • 0
    I've attempted to define the functors according to what you suggested. Let me know what you think when you get a chance. (By the way, how do you get an "at" sign in your comments? It disappears when I try...)2012-04-20
  • 0
    @Byron: The "at" sign serves two purposes, a) getting someone notified of a comment and b) indicating whom the comment is directed at. In the present case, neither is necessary, since a) I get notified of comments under my own post anyway and b) no-one else has commented on this post so the comment can only be directed at me anyway. The software realizes this and deletes the "at" construction, but you should be able to use it in other comment threads (or as soon as someone else chimes in here).2012-04-20
  • 0
    @Byron: About your functors: There's a reason I mapped $0$ to $\text{Red Poppy}$ in my definition; I don't think there's a functor that maps $0$ to $\text{Bluebell}$. But more fundamentally than that, your definition is incomplete because it contains a function $f$ that you haven't defined. If I may offer some advice after what has now been quite an extensive exposure to your ideas: You appear to be very seriously confused about a lot of things. You might want to go back and gain more experience with more basic aspects of mathematics before tackling something as abstract as category theory.2012-04-20
  • 0
    @Byron: Your functor $G$ also doesn't work out; I believe this too has to map $\text{Red Poppy}$ to $0$ to work. For $G$ to be a functor, $G(h_{pr})$ has to be a morphism from $G(p)$ to $G(r)$, but for $p=\text{Bluebell}$ and $r=\text{Texas Bluebonnet}$, the morphism $G(h_{pr})=f_{G(p)}=f_0$ is a morphism from $0$ to $0$, not from $G(p)=0$ to $G(r)=1$.2012-04-20
  • 0
    Well, I honestly think it's more of a typo. When I typed in the mapping for ($0 \rightarrow $ "Bluebonnet"), I was thinking ($2 \rightarrow $ "Bluebonnet"), but was also thinking about too many other things to notice the typo. I corrected the indexes so the functors align properly now. Regarding $f$: I am taking $f_{m}$ to be synonymous with $f(m)$, both referring to the morphism of $A$. Is this not allowable?2012-04-20
  • 0
    @Byron: Sure you can consider $f(m)$ and $f_m$ as synonymous. It doesn't exactly increase clarity to introduce one and then use the other, though. The reason I didn't infer that this is what you meant is that this makes your definition of $F(f_m)$ circular. Regarding the typo, I'll be quite frank: I think you'd be fooling yourself if you think that this is just a question of isolated typos. Every single one of your attempts contained fundamental flaws, and my overall impression is that you're rather confused about quite basic things, let alone category theory. I'd try something easier first.2012-04-20
  • 0
    I think it's a notational problem again. The syntax admits resolution in two different sequences, and I see now that in the environment of category theory, only one of those resolution orders is permissible. The new version explicitly resolves $f_{m}$ to $(m + m) \% 3$ in the intended manner.2012-04-20
  • 0
    @Byron: OK, I think you're almost there now. One more problem (perhaps just a typo? ;-) is that "$h_{rq} \circ h_{pr}$ is $h_{rr}$" should be "$h_{rp} \circ h_{pq}$ is $h_{rq}$". About the graphs: I still haven't understood why you keep treating identity morphisms separately. However, even if for some reason you omit the identity morphisms from the graphs, they would still be different since the graph for $A$ would have a loop for $f_0$ at $0$ and the graph for $B$ wouldn't have any loops.2012-04-20
  • 0
    Yes, a typo. Note that there are 2 conventions for composition: one in which the rightmost is applied first, another in which the leftmost is applied first. Authors in category theory point this out, and usually state which one they are using. Here (after my correction) the former is used. As for the graphs, that's the original reason for this post--at a conceptual level there's something I don't understand. One textbook author says it is possible for 2 categories to have identical graphs yet not be isomorphic. But if every graph edge represents a morphism, how could this ever be?2012-04-20
  • 0
    @Byron: I see your point about the order of composition; however, it's still wrong, since the result should be $h_{pr}$. Perhaps you're not that confused after all and just staggeringly careless? About the graphs: The graphs don't contain information about composition. Two categories could have the same number of morphisms between any two objects, and thus the same directed graph, and yet not be isomorphic. The simplest example would be a category with a single object and two morphisms, where in one case the squares are both the identity and in the other case one of the squares isn't.2012-04-20
  • 0
    Sorry to be a bother with my syntactic difficulties, but it looks correct to me. As I understand it, $f_{qr} \circ f_{pq}$ yields $p \rightarrow q \rightarrow r$, which given the structure will be the same as $f_{pp}$, since $r$ and $p$ will always refer to the same object.2012-04-20
  • 0
    I'm not grasping the non-isomorphism in your example. How can a morphism be directed from a single object to itself and not be an identity? Apologies if it's a dumb question, but I'm just not able to see the exact semantics of "identity" in this context.2012-04-20
  • 0
    ...and those are meant to be $h$ in my first comment--too late to edit again now.2012-04-20
  • 0
    @Byron: No, you could have $p=q=\text{Bluebell}$ and $r=\text{Texas Bluebonnet}$, then $h_{pr}\ne h_{pp}$. (Something tells me that your response will involve somehow treating the identity morphisms separately. :-) About your other question: You yourself *created* this example in which $f_0$ is a morphism from $0$ to $0$ that's distinct from the identity morphism on $0$. In the "real world", a typical example of this would be an [endomorphism](http://en.wikipedia.org/wiki/Endomorphism) from a group to itself or from a vector space to itself (e.g. a rotation).2012-04-20
  • 0
    Right, I made a mistake in the logic for composition in $B$. I didn't think of that possibility. So it's corrected now.2012-04-20
  • 0
    Suppose category $C$ has one object $x$. A morphism $t : x \rightarrow x$ can transform $x$ such that, within the context of $x$, it is an endomorphism and not an identity. Suppose a second morphism is defined, $s : x \rightarrow x$, having no transformation. When I compare $t$ and $s$ in the context of $C$, are they still distinct? I can see it two possibilities: 1) $C$ only recognizes a distinction between two morphisms when the distinction occurs in the terms by which $C$ is defined. 2) $C$ recognizes all distinctions of morphisms, even those wholly contained within one of its objects.2012-04-20
  • 0
    In the case of 1) category $C$ regards $s = t$. In the case of 2) it regards $s \neq t$. Again, sorry if it's a dumb question, but this kind of semantic distinction is not discussed in the textbooks. I've got to ask someone about it, otherwise I'll never know which way it works.2012-04-20
  • 0
    @Byron: No, this is not at all a dumb question; now we're finally getting to the stuff that's interesting about category theory. The idea in category theory is to fully abstract from the internals of objects and discuss the objects *solely* in terms of the morphisms between them. So there's no talk in category theory about the morphism $t$ "transforming" the object $x$, or about something happening "within" one of the objects. But that doesn't mean that category theory can't distinguish between $t$ and $s$. The distinction can be expressed entirely in terms of the compositional behaviour of...2012-04-20
  • 0
    ... the morphisms. $s$ is the identity morphism on $x$, with the unique property that composing it with any other morphism $m$ yields $m$. That's not the case for $t$. (If there were two identity morphisms $t$ and $s$ for an object, then $t\circ s=t$ and $t\circ s=s$ would imply $t=s$.)2012-04-20
  • 0
    An example would be linear maps between vector spaces. There are all sorts of endomorphisms on a vector space, i.e. linear maps mapping it to itself. But there's only one identity map, and that's the only one with the property that if you compose it with any linear map $L$ to or from the vector space, you end up with $L$ again.2012-04-20
  • 0
    Ah, excellent, now I'm starting to see how it works :-) But is it allowable to define $t$ as having the identity property, even though it does a transformation on $x$? Supposing, for example, that I want my category $C$ to consider this transformation negligible. Would it be incorrect to assert $t$ as an identity?2012-04-20
  • 0
    @Byron: As I wrote above, there can be only one identity morphism per object, since you can use the properties of an identity morphism to show that any two identity morphisms for the same object are equal. Your formulation "even though it does a transformation on $x$" has no place in category theory. You can define any morphisms you want as long as they satisfy the basic axioms for composition of morphisms, and one of the consequences of those axioms is that there is exactly one identity morphism per object.2012-04-20
  • 0
    Apologies, I should have reformulated the whole example (so category $C$ has only the one morphism $t : x \rightarrow x$). Generally speaking, it sounds like the only thing that really "counts" is the composition rule. From the perspective of the category, if its morphism has the compositional behavior of an identity, then--for that reason--it is an identity. Is this correct?2012-04-20
  • 0
    @Byron: Yes, that's absolutely correct.2012-04-20
  • 0
    Awesome--that actually answers about 15 other questions I was having about category basics. And now I see why my original examples were so badly disoriented. Many thanks for your patience!2012-04-20
  • 1
    @Byron: You're welcome -- I'm glad to hear it paid off in the end :-)2012-04-20