Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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) –  Arturo Magidin Feb 14 '11 at 4:45
1  
(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? –  Arturo Magidin Feb 14 '11 at 4:47
    
@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 ... –  Abel Feb 14 '11 at 4:59
    
... arrive at the conclusion that $id_A$ has to be $1_A$, without guessing what $id_A$ could be. –  Abel Feb 14 '11 at 5:00
3  
@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$. –  Arturo Magidin Feb 14 '11 at 5:03

3 Answers 3

up vote 5 down vote accepted

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$.

share|improve this answer
    
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$). –  Abel Feb 14 '11 at 6:22

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$."

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.