# In the morphisms-are-functions view of category theory, how are poset categories explained?

Some people have taken the view that morphisms in category theory ought to simply be called functions.

However, not all morphisms look like functions at first sight. For example, in categories of partial orders, such as the category in which the objects are the natural numbers and a morphism exists between two numbers x and y if and only if x < y: How is, say, the morphism that corresponds to the fact "2 < 3" viewed as a function? What is its domain and codomain?

• one thing is that morphisms be called functions and another is that they be functions. – Mariano Suárez-Álvarez Jan 22 '13 at 6:50
• Well, they aren't functions! For example, there is category with one object and one arrow, and the arrow is my table. – Mariano Suárez-Álvarez Jan 22 '13 at 6:52
• can you point to any person who takes the view that morphisms ought to be called functions? – Ittay Weiss Jan 22 '13 at 7:24
• "Some people have taken the view that morphisms in category theory ought to simply be called functions". Some people? what people? Oh please! – magma Jan 22 '13 at 12:13
• Morphisms in an arbitrary category are functions on the generalized elements. So, there is nothing wrong with the concept of a function. The classical notion of an element is too restrictive, though. – Martin Brandenburg Feb 11 '16 at 7:58

By Cayley's representation (for small categories, like posets, at least) every small category can be embedded in $\Bbb{Set}$, as follows:

for an object $A$ we map the set of arrows ending in $A$, i.e. $$F(A):= \bigcup_X \,(X,A) = \{f: \mathrm{cod} f=A\}$$ and for an arrow $f:A\to B$, the mapping $g\mapsto f\circ g,\ F(A)\to F(B)$.

In this view, the morphisms are presented as functions.

In the example of the poset $(\Bbb N,\le)$, we can consider the "morphism" $2\le 3$ as the ordered pair $\langle 2,3\rangle$, then, strictly applying the above, we get

$F(2)=\{\langle 0,2\rangle;\ \langle 1,2\rangle;\ \langle 2,2\rangle \}$, $\ F(3)=\{\langle 0,3\rangle;\ \langle 1,3\rangle;\ \langle 2,3\rangle;\ \langle 3,3\rangle \}$ and

$F(\langle 2,3\rangle)\$ maps $\ \langle x,2\rangle\$ to $\ \langle x,3\rangle$.

• Since the cardinality of $F(n)$ is less than the one of $F(m)$ if $n<m$, could we define $F(\langle n,m\rangle)$ to work as 'decreasing inclusion' (I mean, for example, $F(\langle n,m\rangle)$ maps $\langle x,n\rangle$ to $\langle m-x,m\rangle$)? – Sigur May 6 '16 at 14:45
• @Sigur only if you define what "subtraction" means, and then verify that your proposed mapping is isomorphic to the mapping that Berci gives. As a general principle (or disclaimer), you will see the words "up to isomorphism" commonly used in such discussions. So, generically, in category theory, different representations are considered to be "the same" when they are isomorphic, and this is implicitly assumed almost everywhere. – Linas Apr 2 at 18:54

[It is better to put "function" in quotes, because we don't mean here what a mathematician normally means by a function, but some more abstract, intuitive idea.]

Whenever we build an algebraic theory of something, we often end up with degenerate examples that fit the theory but don't look anything like what we are trying to model. Partial orders (and preorders) are such degenerate examples of categories.

However, something of the "function" idea can be salvaged even in this case. If you allow me to think of posets whose elements are sets of some kind and their partial order is set inclusion, then it is easy enough to think of inclusions as a particular kind of "functions". They are injections that preserve the identity of the set elements.

In fact, your example of the natural number poset can be thought of in this way. In standard set theory, a natural number n is defined as the set $\{0,...,n-1\}$. The partial order of natural numbers is just the inclusion of these sets.

Another view is that preorders are categories where different morphisms $A \to B$ have been identified (by "brute force?"), and posets are categories where further brute force has been applied to identify all isomorphic objects as well. There are projects called "groupoidification" and "categorification", which attempt to undo the brute force that might have been applied to the basic mathematical concepts and unearth the real mathematics that underlies them. If you are interested, here is a starter blog post by John Baez.

Let me offer another point of view.

I do not think that invoking Cayley's theorem may justify calling morphisms functions, because such a representation generally does not give a full subcategory of sets, and non-full subcategories rarely inherit interesting properties from they embedding category. It would be better perhaps to invoke the Yoneda lemma, which says that a locally small category $\mathbb{C}$ fully embeds into the category of presheaves $\mathbf{Set}^{\mathbb{C}^{op}}$. A presheaf $F \colon \mathbb{C}^{op} \rightarrow \mathbf{Set}$ is essentially a (somehow generalised) $\mathbb{C}$-sorted algebra, where $\mathbb{C}$ may be though as a generalised "signature together with equations". A morphism of such algebras $h \colon F \rightarrow G$ consists (as usual) of a family of functions (so yes, technically, it is not a function, but a family of functions, but it is easy to represent such a family as a single function) between carriers $h_C \colon F(C) \rightarrow G(C)$ compatible with the operations taken from the signature. This means, that every category can be realized as a full subcategory of generalized algebras and algebra homomorphisms (BTW: the Cayley's theorem is obtained form the above by "gluing" carriers of the algebras).

Nonetheless, I do not think invoking the Yoneda lemma is a good idea either. What I think, is that one should first ask what a function is. And because we are interested in mathematical foundations, we cannot just say that a function is a subset of a Cartesian product of two sets satisfying some properties, without saying what our sets are, or more accurately, what set theory are we willing to work in. Accidentally, it seems to be a difficult task to give one right answer. Some may say that a function is something that lives inside ZF set theory, or any consistent extension of ZF. However, there are other theories that we are willing to accept as “set theories” which are not in any sense extensions of ZF.

Categorically, one could say that a "set theory" is an elementary topos. However, again, there are “set theories” without the full power-set axioms, which constitute some weaker systems (like $\Pi$($W$)-pretoposes). Moreover, in computer science, the concept of a function is even more general --- a function is no longer though as a set of mere points linking arguments with results, but as a kind of a computational process which on given input produces a result. Such functions are defined in various lambda calculi. For example, simply typed lambda calculi are tantamount to Cartesian closed categories, and untyped lambda calculi correspond to categorical Lambek’s C-monoids.

What I would like to argue is that to speak about functions we do need far less structure then we have in a "set theory", in a "topos", and even less then we have in a "Cartesian closed category" --- in some sense the concept of a category is the best attempt to give a purely abstract axiomatization for the concept of function!

Let me also point that it is crucial to distinguish the concepts from our meta-theory, from the internal concept that we have to define inside the theory. It is clear, that Mariano’s table (see the comments to the original question) is not an external function, but it does not mean, that it cannot be though as an internal function in a category --- similarly the fact that there exists a model of ZFC build upon natural numbers, does not imply that functions in ZFC are natural numbers (and not functions!).