12
$\begingroup$

I've been trying to wrap my head around the basic concepts of category theory, and I thought I would attempt to illustrate what I understand with the category of sets, probably the easiest example. Particularly, I've been trying to prove that $id_A$ (the identity morphism on $A$, for all $A \in Obj(\mathbf{Set})$) is $1_A \colon A \rightarrow A, x \mapsto x$.

This is a very intuitive and reasonable statement, and it's trivial to prove that $1_A$ is indeed an identity morphism on $A$, and I suppose uniqueness of $id_A$ can be demonstrated analogously to uniqueness of the identity element in a monoid (considering the subcategory which has $A$ as its only object, and endofunctions on $A$ as its only morphisms).

In this manner, it is not hard to prove that the proposition in the title is true, but this demonstration requires to make an assumption or guess as to what could $id_A$ be. Specifically, the scheme of the proof is: assume $id_A$ = $1_A$, see that it works with the definition of an identity morphism, show that the identity morphism is unique, and, in conclusion, $id_A$ can only be $1_A$. What I'm looking for, nonetheless, is a somehow more direct proof, that doesn't assume $id_A$ = $1_A$ at the start. I want to place myself in a state of little or no knowledge about sets and functions, and under this assumption, why would I assume $id_A$ = $1_A$ at first? Why not try with $id_\mathbb{Z}$ = $f \colon \mathbb{Z} \to \mathbb{Z}, x \mapsto x^2 + 1$, for example? It wouldn't work, but I don't have any reason to think that $1_\mathbb{Z}$ is a better guess for $id_\mathbb{Z}$.

I suppose that the proof for which I'm asking would work for categories of sets with additional structure, and probably for posets as well, although I'm not clear as to what modifications it would require to work.

Thanks.

  • 2
    What do you mean, "prove from the axioms of categories"? You have the axioms of categories, and you want to *interpret* them in Set to show that Set, with set-theoretic functions, are a category. So you say, "the objects are the sets", "the morphism between A and B are the functions between A and B", "composition of morphisms is composition of functions", and "the identity morphism is the identity function", and then you prove/verify that this interpretation satisfies the axioms of a Category... (cont)2011-02-14
  • 2
    (cont...) Now, you can prove that the identity morphism in any category is unique (yes, using the same argument as the uniqueness of the identity in a monoid); then you can take that proof, that holds in *any* category, and *interpret* it in Set under your intepretation. Is that, perhaps, what you mean?2011-02-14
  • 0
    @Arturo: I understand your point, but that is not what I'm asking for. What I want to say is "Suppose I have a collection (defined in some way as to avoid Russell's paradox) of sets, together with a collection of functions between them, with the usual concepts of composition, associativity, domain and codomain. Does this object have a compositional identity in order for it to be a category? Which function is this identity morphism?" I don't want to prove this in the indirect way, starting from the guess that $1_A$ might be such a morphism and proving that it is the only one, but rather ...2011-02-14
  • 0
    ... arrive at the conclusion that $id_A$ has to be $1_A$, without guessing what $id_A$ could be.2011-02-14
  • 5
    @Abel: In that generality, it need *not* be the the case that $id_A=1_A$. Take $A=\{1,2\}$, $B=\{a,b\}$, $M(A,B)=\{f\}$, where $f(1)=f(2)=a$, $M(B,A) = \emptyset$, $M(A,A) = \{g\}$ with $g(1)=g(2)=1$, adn $M(B,B)=\{h\}$ where $h(a)=h(b)=a$. This is a category, with $g = id_A$, $h=id_B$, even though $g\neq 1_A$ and $h\neq 1_B$.2011-02-14
  • 0
    @Abel: However, if you define the morphisms between two set-objects as being *all* set-theoretic functions between the two objects, then you *can* prove that $1_A$ has to be $id_A$, simply by considering $M(A,A)$ and treating it like a monoid.2011-02-14
  • 0
    @Arturo: Oops. I see I introduced a greater level of generality that what I intended. You are right in thinking that I want to consider all functions between the two objects. I guess my categorical formulation was maybe unnecessary. Still, it is this last part what is giving me trouble: proving that $id_A$ is $1_A$, without first making a guess as to what $id_A$ is. My problem is in the method of proof, not the existence of a proof itself. ...2011-02-14
  • 0
    ... Maybe I'm not being clear enough. Why guess $id_A$ is $1_A$? Why not $f \colon \mathbb{Z} \rightarrow \mathbb{N}, \mapsto x^2 + 1$, for example (in a category whose object set is $\lbrace\mathbb{Z}, \mathbb{N}\rbrace$)? Granted, it wouldn't work, and there isn't any function other than $1_A$ that would, but why try with that one first? I'm trying to place myself under the assumption that I don't know much about functions and sets.2011-02-14
  • 0
    @Abel: Okay, I think what you are at. I would suggest editing your question a bit. I'll write up an answer.2011-02-14
  • 0
    @Abel: How's that? Closer to what you were thinking?2011-02-14
  • 0
    @Arturo: That's exactly what I was thinking. I've clarified the question a bit. Thanks.2011-02-14

3 Answers 3

11

Okay, based on the extensive discussion in comments, it seems that you want to consider the following:

Suppose that we have a well-defined collection of sets, which we want to make into a category by letting them be the objects, taking the collection of morphisms to be all set-theoretic functions between the two sets, and using regular composition and domain/codomain identifications. Can we prove that under these circumstances, for us to have a category then the categorical identity arrow must be the identity function for the set?

The key is that you have enough functions to "separate points". Given any $a,b\in A$, $a\neq b$, there exists a function $g\colon A\to A$ such that $g(a)\neq g(b)$. For example, define $g$ to be the function that maps $b$ to $a$, and maps everything else to $b$. (Compare this with the example I gave in the comments, where this does not hold).

So, fix a set $A$, and suppose that $f\colon A\to A$ is the arrow that satisfies the identity conditions (for all objects $B$ and $C$, and all arrows $g\colon A\to B$ and $h\colon C\to A$, $gf = g$ and $fh = h$).

Pick any $a$ and $b$ in $A$, $a\neq b$. Let $g$ be a function with $g(a)\neq g(b)$; then $gf(a) = g(a)$, so it follows that $f(a)\neq b$. This holds for every $b\in A-\{a\}$, so the only possibility is that $f(a)=a$. This holds for all $a\in A$, so $f$ must be the identity map.

You can generalize this to any set-based category in which you can either separate points, or "hit" any point: if for every object $A$ and every elements $a,b\in A$ with $a\neq b$, there either exists an object $B$ and a morphism $h\in\mathcal{C}(A,B)$ such that $h(a)\neq h(b)$; or else there exists an object $C$, and a morphism $g\in\mathcal{C}(C,A)$ for which there exists an element $c\in C$ such that $g(c)=a$; then the identity morphism of $A$ must be the identity map of $A$.

Indeed, suppose that $f$ is the identity morphism, and let $a\in A$. For each $b\in A$, $b\neq a$, either we have $B$ and $h$ as above, and $hf(a) = h(a)$ implies that $f(a)\neq b$; or else there exists $C$, $c$ and $g$ as above with $g(c) = a$. Then $fg = g$ gives that $f(a)\neq b$ (since $f(g(c))=b$ and $g(c)=a$ implies $a=b$). Either way, you get that for all $b\in A$ with $b\neq a$, $f(a)\neq b$. So the only possibility left is that $f(a)=a$. This holds for all $a\in A$, so $f=1_A$.

Note. In a sense, the condition is both necessary and sufficient, though for silly reasons: if the condition is not met by $A$ and $a$, then the identity map of $A$ cannot be the identity morphism, simply because the identity map of $A$ satisfies the given conditions: for all $b\neq a$ you have $1_A(a)\neq 1_A(b)$, and $1_A(a)=a$.

Added. This argument applies to categories such as topological spaces (because you always have the map from the $1$-element topological space to your toplogical space mapping the unique point to $a$); pointed topological spaces (the discrete 2-element pointed topological space maps the non-distinguished point to your favorite point); groups (you have maps from the cyclic group to any group, mapping the generator to your element $a$); and others. It's hard to make it work with posets as categories, because posets as categories are not really set-based categories (the objects are not usually sets and arrows set-theoretic functions between them); you can model them as set-based categories, but then the result need not hold: the example I gave in the comments can be thought of as the totally ordered set with two elements, for example, and here you don't have $id_A = 1_A$.

  • 0
    This is exactly what I was looking for. Thanks. Regarding the application to posets, what I meant is that the set of identity morphisms in a poset considered as a category (i.e., the elements of the poset under the relation $\le_R$ are the objects of the category and there exists a morphism between two elements $a$, $b$ in the category iff $a\le_Rb$) is the identity relation, which is, now that I think about it, quite obvious and probably meaningless ($id_a \in M(a,a)$, and the only morphism in $M(a,a)$ corresponds to $a\le_Ra$, for every $a$).2011-02-14
3

I think the most you can say in general is that $\text{id}_A$ acts as the identity function on the hom-sets $\text{Hom}(B, A)$ for all $B$ in the category. That uniquely specifies it by the Yoneda lemma, so there's no ambiguity here, and it is the appropriate generalization of "acts as the identity on points of $A$" to arbitrary categories: you should think of it as "acts as the identity on generalized points of $A$."

3

i don't think this is that hard, at least for the category Set. what we know is that $id_A$ is an element $f$ of Hom(A,A) such that:

$f\circ g = g$ and $h\circ f = h$ for any $g$ in Hom(B,A) and $h$ in Hom(A,C).

in particular, let B be a singleton set {*}, then we can identify any $g$ in Hom(B,A) with an element $a$ of A, so that $f\circ g = g$ means that $f(a) = a$ for all $a$ in A.

thus $1_A$ is the only viable candidate for $id_A$.