4
$\begingroup$

I am confused about the definition of a category given in the Wikipedia article on Category theory:

It seems to me that the structure being described (the "arrows" between objects in some class) is just a binary relation that is both reflexive and transitive. If so, what is meant by the set of all morphisms (arrows) from one object to another? The definition says that every morphism (arrow) has a unique source object and target object. Is there not then at most one arrow from one object to another?

EDIT 1

I am looking for formal axioms of category theory expressed only in the notation of first-order logic and set theory -- no words, just variables, functions, logical connectors, quantifiers, predicates, '=' signs, '$\in$', etc.

EDIT 2

How about: class $ob$ is a category iff...

  1. $\forall a,b \in ob\exists hom \forall f(f\in hom \leftrightarrow \forall d\in a(f(d)\in b)) $

  2. $\forall a\in ob\exists i \forall b\in a(i(b)=b)$

Note that the required properties of composition are a direct result of functionality of each morphism.

EDIT 3

I must be trying the patience of the moderators here. Sorry guys! This has turned into a rather open-ended discussion. To be continued at the sci.logic and sci.math newsgroups:

https://groups.google.com/group/sci.logic/browse_frm/thread/bd8d78c920e1d28c#

EDIT 4

I'm not sure this is right either, but you might consider the following.

I define the Category and Arrow predicates as follows:

$\forall x (Category(x) \leftrightarrow \forall y\in x \exists f \forall z\in y (f(z)=z))$

This would be redundant if the elements of x were all sets because you can prove the existence of an identity function on every set.

$\forall x\forall a,b\in x (Arrow(x,a,b) \leftrightarrow a\in x \land b\in x \land \exists f \forall c\in a (f(c)\in b) \land \forall c\in b \rightarrow \exists d\in a (f(d)=c)$

It is then easy to prove that the Arrow relation is reflexive:

$\forall x (Category(x) \rightarrow \forall a\in x Arrow(x,a,a))$

And that the Arrow relation is transitive:

$\forall x (Category(x)\rightarrow \forall a,b,c\in x (Arrow(x,a,b) \land Arrow(x,b,c) \rightarrow Arrow(x,a,c)))$

Thanks all for your help.

  • 2
    Regarding your second edit: (1) note that "morphisms" need not be actual functions. (2) To quote Awodey: "One important slogan of category theory is _It's the arrows [morphisms] that really matter!_"2012-10-10
  • 1
    Maybe a drastically different concrete example would help: matrix algebra is a category. The morphisms are matrices. The product of morphisms is given by matrix multiplication. Objects are natural numbers. The source and target of a morphism are its dimensions.2012-10-10
  • 0
    Another standard example is the suspension of a monoid $M$: the category with a single object (it doesn't matter what the object is: we usually call it `*`), and $\hom(*, *) = M$. (composition of morphisms is given by the product in $M$)2012-10-10
  • 0
    For an axiomatisation as asked for in Edit 1, see http://www.proofwiki.org/wiki/Definition:Morphisms-Only_Metacategory2012-10-11
  • 0
    For an axiomatization without words and using the usual definition with objects (as opposed to morphisms-only) versions, see http://us.metamath.org/mpegif/df-cat.html2018-06-03

5 Answers 5

11

You're misinterpreting the meaning of the word "unique" (which was poor word choice on the part of whoever wrote that, so I am removing it). It just means that an arrow doesn't have more than one source or target.

Here is a formal definition of a small category (this will allow me to ignore size issues which I think are irrelevant when first trying to understand category theory). I'm afraid I'm too attached to words to follow the "no words" edict, but I hope this will be formal enough. A category consists of the following data:

  • A set $\text{Ob}$ (objects),
  • For every $a, b \in \text{Ob}$, a set $\text{Hom}(a, b)$ (morphisms from $a$ to $b$),
  • For every $a \in \text{Ob}$, an element $\text{id}_a \in \text{Hom}(a, a)$ (identity),
  • For every $a, b, c \in \text{Ob}$, a function $\circ : \text{Hom}(a, b) \times \text{Hom}(b, c) \to \text{Hom}(a, c)$ (composition).

(I am writing function composition in the opposite of the usual order. You should think of a morphism $f \in \text{Hom}(a, b)$ as an arrow $f : a \to b$ pointing from $a$ on the left to $b$ on the right.)

This data is subject to the following axioms:

  • Identity: for every $f \in \text{Hom}(a, b)$, we have $\text{id}_a \circ f = f$, and for every $g \in \text{Hom}(b, a)$, we have $g \circ \text{id}_a = g$.
  • Associativity: for every $f \in \text{Hom}(a, b), g \in \text{Hom}(b, c), h \in \text{Hom}(c, d)$, we have $f \circ (g \circ h) = (f \circ g) \circ h$.

Some concrete classes of examples to keep in mind ("categories-as-mathematical-objects" rather than "categories-as-settings-to-study-mathematical-objects") are the following:

  • A monoid is a category with one object; that is, $\text{Ob}$ is a one-element set. The elements of the monoid are the morphisms from the unique object to itself.
  • A poset is a category in which $\text{Hom}(a, b)$ has either $1$ or $0$ elements (corresponding to whether $a \le b$ or not); moreover, if $\text{Hom}(a, b)$ and $\text{Hom}(b, a)$ both have one element, then $a = b$. The existence of identities expresses reflexivity, the composition law expresses transitivity, and associativity is automatic.
  • A groupoid is a category in which every morphism $f : a \to b$ has an inverse $g : b \to a$, which is a morphism satisfying $f \circ g = \text{id}_a, g \circ f = \text{id}_b$. Groupoids are a simultaneous generalization of groups, equivalence relations, and group actions. An important example is the fundamental groupoid $\Pi_1(X)$ of a topological space $X$, which is the groupoid whose objects are the points of $X$ and whose morphisms are the homotopy classes of paths between points in $X$; composition is given by concatenating paths.

One example of "categories-as-settings-to-study-mathematical-objects":

  • The "matrix category" $\text{Mat}$ is the category whose objects are the non-negative natural numbers $\mathbb{Z}_{\ge 0}$ and whose morphisms $\text{Hom}(n, m)$ are the $n \times m$ matrices, say over some ring (or $m \times n$; whichever convention makes composition correspond to matrix multiplication).
  • 0
    Alternately, you could talk about the set $\text{Mor}$ of all morphisms, but then composition becomes a partial function. If you don't want to deal with partial functions in whatever system you're working with, then composition can be thought of as a function $\text{Mor} \times \text{Mor} \times \text{Mor} \to 2$ describing the possible triples of composable arrows.2012-10-09
  • 0
    Would you check the first sentence of what you wrote about posets, starting at *moreover*?2012-10-09
  • 0
    @Brian: caught it. Thanks.2012-10-09
  • 0
    Are you sure this is right? Provided I don't miss anything, this definition allows $\text{Hom}(a,b)\cap\text{Hom}(c,d) \not=\emptyset$. So you either have to add the restriction that the sets $\text{Hom}(a,b)$ are pairwise disjoint, or define them via source and target maps.2012-10-09
  • 3
    @roman: in my version of set theory, it is not even possible to ask the question of whether two sets (which are not given as subsets of a common superset) are disjoint. (Alternately, in my version of set theory, sets are disjoint unless I say explicitly otherwise.) To me, intersection is an operation defined on subsets of a given set. It is not an operation defined on sets.2012-10-09
  • 0
    @QiaochuYuan What exactly is a "morphism" here? Is it just an element of a reflexive and transitive relation on $Ob$?2012-10-09
  • 0
    @Dan: A morphism is simply an element of (the class of arrows of) the category. Just like a vector is merely an element of a vector space.2012-10-09
  • 1
    @Dan: no. A morphism from $a$ to $b$ is an element of the set $\text{Hom}(a, b)$. Ignoring composition (but composition is the most important part!), you can think of the collection of objects and morphisms as the vertices and edges of a directed multigraph. Again, if you would prefer, I could write down an axiomatization that talks about the set of all morphisms, but stating some of the axioms would be more awkward, I think.2012-10-09
1

There can be many distinct arrows between two given objects. For example, consider the category of sets: The objects are all sets (or all sets in a given Grothendieck universe, to avoid foundational issues), and the arrows are functions between sets. If $X, Y$ are sets, there are usually many different functions $f: X \to Y$, and each function is an arrow from $X$ to $Y$. The situation is similar in many other commonly used categories.

Category theory is best learned by example; it's difficult to get intuition for it in the abstract. If you're having trouble understanding some categorical concept, see how it applies in a few familiar categories, like sets, groups, or modules.

  • 0
    Daniel Hast: So, these "objects" are really classes or sets. And the "morphisms" are functions mapping the elements of one of these "objects" to the elements of another? (I haven't been able to make sense of any of the usual examples. My preference now is to start from the abstract, as I would with, say, group theory.)2012-10-09
  • 0
    @Dan: The typical first example $\bf{Set}$ is like that, as are "concrete" categories. Depending on suitable foundational choices, it turns out one can to represent any category in such a fashion (in a way very similar to how any group can be represented via a group action on its underlying set), but it would be a rather awkward way to think about things.2012-10-09
  • 1
    In the category of sets, the objects are sets and the morphisms are functions between sets. Many categories follow this pattern: the objects are sets with some additional structure (e.g., groups, rings, topological spaces) and the morphisms are structure-preserving maps (e.g., homomorphisms, linear maps, continuous functions). However, not all categories are like that, so just think of these as motivating examples. From the perspective of category theory, you can't look at the internal structure of an object (it might not have any); you can only analyze it by the structure of its arrows.2012-10-09
  • 0
    @DanielHast The formal axioms for algebraic structures like groups and rings can be given using the language of first-order logic and set theory. Can anyone point me to the formal axioms for category theory using the same kind of language? There are far too many words for my liking in the so-called formal definitions I have found online. I want mathematics, not philosophy.2012-10-09
  • 1
    @DanChristensen: Here's an introductory book on category theory, made available online by the authors: [Abstract and Concrete Categories: The Joy of Cats](http://katmat.math.uni-bremen.de/acc/acc.pdf). The first chapter grounds it pretty solidly in set theory. However, category theory has the nickname "general abstract nonsense" for good reason; even if you ordinarily prefer a more abstract approach (as do I), speaking from personal experience, category theory is one area where you really won't get far without familiarity with lots of examples and motivation.2012-10-09
  • 0
    @DanielHast I will look at this book, but your comment leads me to believe this is going to be more about "philosophy" than mathematics. Sigh....2012-10-09
  • 2
    No, it's very much pure mathematics. I'm not sure what you mean by "philosophy", but examples and motivation are certainly part of mathematics; otherwise, you'd just be manipulating strings of symbols without any ideas behind it. Looking at your edit, what you want is perhaps more along the lines of formal proof-checking programs or something, because mathematicians don't work purely in low-level symbols like that — leave that sort of thing to computers.2012-10-09
  • 0
    @DanielHast If you can't run it through a formal proof-checking program, it is not very well defined, is it?2012-10-09
  • 2
    @DanChristensen: If everything is well-defined, then in principle, you could run it through a sufficiently advanced proof-checking program. However, that would usually be impractical, so it's generally sufficient that everything _could_ be made as formal as necessary, without actually writing it down in that sort of ultra-formal notation. You're unlikely to find most mathematical ideas presented with that level of formality, because it's assumed that a knowledgeable reader will be able to fill in the gaps and formalize as needed.2012-10-09
  • 2
    @DanChristensen: Your statement about requiring that a definition be capable of being read by a computer in order for something to be (mathematically) _well-defined_ is much more akin to a _philosophical_ assertion than the definition of a category provided by Wikipedia.2012-10-09
  • 3
    @Dan: How much real mathematics have you ever seen that you could run through a formal proof-checking program?2012-10-09
  • 0
    I'm not talking about formal proofs. I know that's unreasonable to ask of most mathematicians. I just want a list of easily formalizable axioms/definitions for category theory -- like the axioms/definition of a group theory.2012-10-09
  • 0
    @DanChristensen: The "Joy of Cats" book I linked has the formal axioms and definitions. Another standard text is MacLane's "Categories for the Working Mathematician", which also gives both set-theoretic and axiomatic definitions and is careful about foundational issues.2012-10-09
  • 0
    @DanielHast The "formal" axioms and definitions in "The Joy Cats" seems a bit too verbal for my purposes as well. Could you (or anyone else) post the axioms and definitions from MacLane? BTW, I am trying to formalize the category of sets. If I succeed, I hope to be able to generalize for all categories. I will post the results here if all goes well.2012-10-09
  • 3
    @DanChristensen: Sorry, but MacLane also uses words, and despite your apparent dislike of words, both books are still perfectly formal about it. If you want to have the definitions in purely symbolic form, you could always convert it to that notation yourself. I don't see the point of doing so, though.2012-10-09
  • 0
    @DanChristensen Bill Lawvere has done much work on axiomatizing the category of sets. I have no evidence that he prefers symbolic language to verbal language, and yet you might like to check him out. (The Basic Theory of the Category of Sets, 1964, or something.)2012-10-11
0

Paraphrased from Categories, Allegories by Freyd and Scedrov:

The theory of CATEGORIES is given by two unary operations and a binary partial operation. The elements are called "morphisms" or "maps". The operations are pronounced as

  • $\square x$ : the source of $x$
  • $x \square$ : the target of $x$
  • $xy$ : the composition of $x$ and $y$

the axioms are

  • $xy$ is defined iff $x \square = \square y$
  • $(\square x)\square = \square x$
  • $\square(x\square) = x \square$
  • $(\square x)x = x$
  • $x(x\square) = x$
  • $\square(xy) = \square(x(\square y))$
  • $(xy)\square = ((x\square)y)\square$
  • $x(yz) = (xy)z$

(in the above, in any equation, one side is defined iff the other side is defined)

Note that this set of axioms is modeled after syntax where functions act on the right, rather than on the left as usual. Note that if the target of $x$ is the source of $y$, then $xy$ is the product guaranteed to be defined, rather than $yx$.

In this definition, the notion of "object" is defined to be any morphism of the form $\square x$.

  • 0
    This axiomatization doesn't seem to include identities.2012-10-09
  • 2
    @QiaochuYuan: If $x (y \square)$ is defined, $x \square = \square(y\square) = y\square$. Thus, $x (y \square) = x (x \square) = x$, making every element of the form $y \square$ a right identity. Similarly, every element of the form $\square x$ is a left identity. Finally, if $(y \square) z$ is defined, $(y \square) z = (\square (y \square)) z = z$, meaning $y \square$ is a two-sided identity morphism.2012-10-09
0

You can find find a fully formal theory of categories in nlab:

http://ncatlab.org/nlab/show/fully+formal+ETCS

This is an "arrows only" axiomatization.

-3

Concrete Categories

Let $ob$ be a class such that

$\forall a (a\in ob \leftrightarrow P(a))$

for some property $P$.

Then $ob$ is a concrete category iff...

(1) $\forall a,b \in ob(\exists hom (\forall f(f\in hom \leftrightarrow (\forall d\in a(f(d)\in b) \land \exists d\in ob \forall e\in d\exists g\in a (f(g)=e)))))$

where the $f$'s are morphisms (functions) that map set $a$ to set $b$ preserving property P, and $hom$ is the set of all such morphisms.

(2) $\forall a\in ob(\exists i \forall b\in a(i(b)=b))$

where the $i$'s correspond to identity morphisms.

  • 1
    In your attempted definition of abstract category, it seems you're still not accounting for the possibility of more than one arrow between two objects. You need some sort of multi-relation. In (1) of your concrete cat. definition, since you don't restrict the quantification over $f$, every hom-set in a concrete category will contain every function between its domain and codomain, so we can't define, for example, the category of groups. For the same reason your axiom (2) appears redundant. Why did you require your $f$s to be surjections? How do you formalize "property"?2012-10-11
  • 0
    @KevinCarlson (1) There can be two arrows (one in each direction) between a pair of objects in an abstract category. How many do you want? (2) For groups, $P$ would represent properties of a group. (3) Requiring morphisms to be surjections would preserve the properties given by $P$. (4) I'm not convinced that axiom #2 is redundant.2012-10-11
  • 1
    @Dan: there can be an _arbitrary number of arrows_ between a pair of objects in a category.2012-10-11
  • 0
    @QiaochuYuan As I understand, not in an abstract category.2012-10-11
  • 5
    @Dan: you understand incorrectly.2012-10-11
  • 0
    @KevinCarlson On second thought, requiring morphisms to be surjections is too restrictive, as you point out. Instead, to preserve the properties given by $P$, it should only be necessary for the codomain of each morphism to be an element of $ob$. Thanks. (I will update axiom #1 at a later date to reflect this change.)2012-10-11
  • 0
    @QiaochuYuan Could you be confusing concrete and abstract categories? I think they are quite different in this respect.2012-10-11
  • 3
    @Dan: whatever you mean by the term "abstract category," it doesn't seem to be what anyone else means by the term. You are free to study sets with reflexive and transitive relations on them to your heart's content. They are called preorders: http://en.wikipedia.org/wiki/Preorder. Most categories _are not preorders._2012-10-11
  • 0
    @QiaochuYuan Can you give a simple example of an abstract category with more than 2 arrows between a pair of objects.2012-10-11
  • 3
    @Dan: yes. Take any group $G$ with more than two elements. There is a category $BG$ with one object and morphisms the elements of $G$ (from that one object to itself). Composition is given by the group operation in $G$. All of this is in the answer I wrote.2012-10-11
  • 0
    @Dan, the problem I expressed about groups is not that you can't select the right set of objects, but that your definition of the set of morphisms doesn't do anything to restrict to group homomorphisms. As you likely know, not every function between the underlying sets of a group is a homomorphism.2012-10-11
  • 0
    @QiaochuYuan Your example is not an abstract category. It is concrete. See: http://en.wikipedia.org/wiki/Concrete_category and http://mathprelims.wordpress.com/2009/02/24/concrete-and-non-concrete-categories-informally/2012-10-11
  • 2
    The [homotopy category](http://en.wikipedia.org/wiki/Homotopy_category) is known to be non-concrete and has multiple morphisms between objects.2012-10-11
  • 0
    @KevinCarlson See my latest version of axiom #1. I restrict the morphisms to functions the codomains (range) of which must be elements of $ob$2012-10-11
  • 0
    @ZhenLin I think the homotopy category is concrete. The objects are not atomic individuals, but sets with some underlying structure. See the links in my comment above to QY.2012-10-11
  • 5
    @DanChristensen it isn't a matter of opinion. Here is a reprint of the paper in which Zhen's result was established by Freyd. There is no faithful functor for the homotopy category to Set, which is even a stronger result. http://www.tac.mta.ca/tac/reprints/articles/6/tr6.pdf You're still making all your morphisms surjective, which I still don't understand, and your axiom still permits the function $f(0)=f(1)=1$ from the cyclic group of order 2 to itself in the category of groups.2012-10-11
  • 0
    @KevinCarlson (1) I am not restricting morphisms to surjections. Between groups $a$ and $b$, for example, I allow $\forall x\in a(f(x)=Ib)$ where Ib is the identity element in $b$. (2) I can't begin to follow Freyd's paper, but the result is clear enough. I will have to withdraw my definition of abstract categories.2012-10-11
  • 0
    Required edits made to my answer.2012-10-11