2
$\begingroup$

Background

Recently I was going through Peter Smith's Category Theory : A Gentle Introduction. There he writes (in section 1.1),

Definition 1. A category $\mathscr{C}$ comprises two kinds of things:

(1) $\mathscr{C}$ -objects (which we will typically notate by ‘$A$’, ‘$B$’, ‘$C$’, $\ldots$).

(2) $\mathscr{C}$ -arrows (which we typically notate by ‘$f$’, ‘$g$’, ‘$h$’, $\ldots$ ).

These objects and arrows are governed by the following axioms:

Sources and targets For each arrow $f$, there are unique associated objects $src(f)$ and $tar (f)$, respectively the source and target of $f$, not necessarily distinct.

We write ‘$f : A → B$’ or ‘$A\xrightarrow{f}B$’ to notate that $f$ is an arrow with $src(f) = A$ and $tar (f) = B$.

Composition For any two arrows $f : A → B, g : B → C$, where $src(g) = tar (f)$, there exists an arrow $g \circ f : A → C$, ‘$g$ following $f$’, which we call the composite of $f$ with $g$.

Identity arrows Given any object $A$, there is an arrow $1_A : A → A$ called the identity arrow on $A$.

$\ldots$

Associativity of composition. For any $f : A → B, g : B → C, h: C → D$, we have $h \circ (g \circ f) = (h \circ g) \circ f$. Identity arrows behave as identities. For any $f : A → B$ we have $f \circ 1_A = f = 1_B ◦ f$.

Now after writing this he continues with six remarks and in the fourth of them he writes,

In keeping with the functional paradigm, the source and target of an arrow are very often called, respectively, the ‘domain’ and ‘codomain’ of the arrow. But that usage has the potential to mislead when arrows aren’t (the right kind of) functions, which is again why I prefer our terminology.

Very shortly there after he proves Theorem 1 which I am quoting verbatim,

Theorem 1. Identity arrows on a given object are unique; and the identity arrows on distinct objects are distinct.

Proof. Suppose $A$ has identity arrows $1_A$ and $1'_A$. Then applying the identity axioms for each, $1_A = 1_A \circ 1'_A = 1'_A\circ 1_A$.

For the second part, we simply note that $A\ne B$ entails $src(1_A) \ne src(1_B)$ which entails $1_A \ne 1_B$.

Questions

  1. If the target of an arrow is analogous concept of codomain for a function then how can it be unique (as is said in the first axiom)?

  2. In the proof of the second part of Theorem 1, I understand that $A\ne B$ implies that $src(1_A)\ne src(1_B)$ but how from $src(1_A)\ne src(1_B)$ it follows that $1_A\ne 1_B$? For more details on this see I, II, III, IV (in this order), especially IV.

$\endgroup$
  • $\begingroup$ As stated, your second question is a fairly trivial one. However, judging from various comments I think you are trying to ask something less trivial -- if you want it answered you'll need to elaborate and clarify! And it may need to be formulated in a separate post, so that it can actually be the focus of a page. (so long as its in this post, the focus is likely to remain primarily on question 1, with question 2 treated as a trivial afterthought if at all) $\endgroup$ – Hurkyl Oct 29 '17 at 19:05
  • $\begingroup$ Thank you very much for your suggestion and thoughtful comments @Hurkyl. In fact I actually thought to do so. But given that (1) I have already exhausted so much energy in elaborating my question, was misunderstood and then finally understood, and (2) I have already gotten my answer, I will for the time being not consider writing a separate post on my second question alone. $\endgroup$ – user 170039 Oct 30 '17 at 3:44
  • $\begingroup$ However, if you are interested then I suggest you to look at the following four discussions, I, II, III, IV (in this order). Especially IV. $\endgroup$ – user 170039 Oct 30 '17 at 3:45
0
$\begingroup$

I would like to point out that Maarten Fokkinga's 1992 introduction to category theory, A Gentle Introduction to Category Theory: the calculational approach, addresses this head-on by defining a notion of "pre-category" where hom-sets are not required to be disjoint. This, arguably, more naturally fits many of the examples we have. In particular, the set-theoretic definition of function doesn't uniquely determine the codomain (as opposed to the range) and thus, sets and functions more naturally form a pre-category rather than a category. Of course, it's easy to turn a pre-category into a category.

This introduction overall is rather unique in many ways. While I don't personally recommend doing category in the style espoused, I do recommend exposing yourself to this style to have a different perspective.

Finally, the term "precategory" is used for two other closely related but quite different notions. Indeed, I suspect this paper (or possibly some other papers by the same or related authors) is the only place "pre-category" is used in the above sense.

$\endgroup$
  • $\begingroup$ Excellent reference. But just to be more clear, the fact that $1_A=1_B$ implies $A=B$ follows directly from the unique-type axiom (in the paper), right? Probably this is something that is meant by "[f]or each arrow there is a unique source and target". $\endgroup$ – user 170039 Oct 28 '17 at 14:52
  • $\begingroup$ In response second question of OP, one needs to define, what does it mean for two morphisms, say $f$ and $g$ to be equal. In an arbitrary category, it is defined as, if $f=g$, then $source(f)=source(g)$ and $target(f)=target(g)$. In a specific category, say $Set$ where objects are sets and morphisms are functions between sets, this definition can be supplemented with more requirements such as, if $f, g:A\rightarrow B$, $f=g$ iff $\forall a \in A, f(a)=g(a)$. $\endgroup$ – jaspreet Oct 28 '17 at 16:02
  • $\begingroup$ @jaspreet: You may enjoy the discussion that I had with user21820 in this room. $\endgroup$ – user 170039 Oct 28 '17 at 16:05
  • 1
    $\begingroup$ @jaspreet: As mentioned in the room, there is no notion of definition here in Peter's text. (Of course, you could email him and clarify, if you think I'm interpreting him wrongly.) Specifically, in his text $src,tar$ are function-symbols in his chosen first-order language of category theory, so mere substitution (=-elimination) is enough to get from $f=g$ to $src(f)=src(g)$ and $tar(f)=tar(g)$. Your example of extensionality as a possible further requirement is correct, and you need an axiom if you want that. $\endgroup$ – user21820 Oct 28 '17 at 16:21
4
$\begingroup$

1. There are slightly different conceptions of function. What you're assuming is the formalization usually presented in the context of set theory, where a function is simply a set of ordered pairs satisfying certain conditions. In that case it is unambiguous what the domain and range of the function is, but the "codomain" can be taken to be any (proper or not) superset of the range.

However, in many other places, a "function" is considered to be something that inherently knows what its codomain is. In that case we would model it set-theoretically as a triple $(D,R,C)$ where $D$ and $C$ are sets and $R$ is a subset of $D\times C$ that satisfies certain conditions. In this case the codomain of $f=(D,R,C)$ is by definition $C$, and therefore a function can have only one codomain.

This is not as strange as it may sound as first if you're used to the former variant. Consider, for example, that even introductory courses happily talks about whether a function is "surjective" or not -- and in order to make sense of that at all, it needs to be the kind of "function" that knows what its codomain is.

It is the latter conception of function that is analogous to Peter Smith's presentation of arrows in a category.

(There are other presentations of category theory where an arrow doesn't necessarily know, by itself, what its domain and codomain are. In those formalizations you need to keep track of which hom-sets the things you are speaking about come from yourself).

2. If you accept that an arrow has only one source (that is, $\rm src$ is an inherent property of every arrow), then it is impossible for $1_A$ to equal $1_B$ yet have different sources -- because two things (such as arrows, or anything in mathematics) that are equal are the same thing and therefore cannot have different properties depending on what you call them.

$\endgroup$
  • $\begingroup$ Concerning 2., I am sorry but I don't understand it yet. Suppose $src(1_A)\ne src(1_B)$ but $1_A=1_B$. But in that case I can't derive any contradiction simply because I don't know what it means for two arrows to be equal (at least what it mean in this case). However if you assume that for any two arrows $f:A\to B$ and $g:A\to B$ we will say $f=g$ iff $src(f)=src(g)$ and $tar(f)=tar(g)$ then there is no problem. $\endgroup$ – user 170039 Oct 28 '17 at 4:56
  • 2
    $\begingroup$ @user170039: It does not make any sense to say that "$\operatorname{src}(1_A)\ne \operatorname{src}(1_B)$ but $1_A=1_B$"! If you're supposing that $1_A=1_B$ you're supposing that $1_A$ and $1_B$ are simply different names for the same thing, and the source of that thing will be equal to itself, no matter which of the two names you use to speak about the thing whose source you're taking. $\endgroup$ – Henning Makholm Oct 28 '17 at 5:02
  • 1
    $\begingroup$ "For each arrow there is a unique source and target" means that if $1_A$ is indeed the same arrow as $1_B$, then their sources must be the same, i.e. $src(1_A)=src(1_B)$. There's your contradiction, if you also assume $src(1_A)\neq src(1_B)$. $\endgroup$ – pseudocydonia Oct 28 '17 at 5:04
  • 1
    $\begingroup$ @user170039: You're still making it much more complicated than it is. $\endgroup$ – Henning Makholm Oct 28 '17 at 15:30
  • 1
    $\begingroup$ @user170039: I can't even grasp what it is you're trying to do. Do you agree that in general if $g$ is some function, then $x=y$ implies $g(x)=g(y)$? And similarly that $g(x)\ne g(y)$ implies $x\ne y$? $\endgroup$ – Henning Makholm Oct 28 '17 at 16:48
1
$\begingroup$

I needn't add anything of substance to Henning Makholm's answer.

Except perhaps to note that if you'd read on all the way as far as p. 7 of my notes, your question would have been answered!

I there explicitly note how in the category Set, the arrows aren't functions-as-usually-defined-in-set-theory, but functions-with-an-assigned-codomain.

Moral: always a good idea to look at an author's examples given to illustrate an abstract definition in order to check your understanding.

$\endgroup$
  • $\begingroup$ You are right that at page 7 my first question has been answered. However what about my second question? Is it also answered later in your book? $\endgroup$ – user 170039 Oct 29 '17 at 4:32
  • 1
    $\begingroup$ It's trivial logic. Again as Henning says. $\endgroup$ – Peter Smith Oct 29 '17 at 11:00
0
$\begingroup$

1) Apparently the target of $f:A\to B $ is $B $... It is part of the definition of the arrow $f $.

2) Equal arrows would have to have the same source...

$\endgroup$
  • $\begingroup$ Usually one uses notation like $f(A)$ for the image of $f$, not the codomain. The target of $f : A \to B$ is $B$. $\endgroup$ – Hurkyl Oct 28 '17 at 5:57
  • $\begingroup$ @Hurkyl ok. You taught me something. I hadn't thought about this much... I have tried to correct it in my edit. .. $\endgroup$ – Chris Custer Oct 28 '17 at 6:37
0
$\begingroup$

In usual treatments of set theory one defines a function $f$ from $A$ to $B$ as the set $\{(a,f(a)):a\in A\}$. Then for instance, the identity map $\Bbb Q\to \Bbb Q$ and the inclusion map $\Bbb Q\to \Bbb R$, are represented by the same set. Are these really the same function? In category theory, these are regarded as different morphisms in the category of sets, as each arrow determines it target.

One way to model this in set theory would be to identify a function $f:A\to B$ as the ordered triple $(A,B,\{(a,f(a)):a\in A\})$.

$\endgroup$
  • $\begingroup$ I don't think one ever defines a function $A\to B$ to be merely a subset of $B$. $\endgroup$ – Kevin Carlson Oct 28 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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