# Examples of categories where morphisms are not functions

Can someone give examples of categories where objects are some sort of structure based on sets and morphisms are not functions?

-
If you soften your "and" to "or" then that's easy: take the category of sets and relations. But it turns out to be isomorphic to a different category whose objects are structured sets and whose morphisms are functions. There is also a locally small category which is demonstrably not equivalent to any concrete category. See also here. –  Zhen Lin Feb 21 '13 at 0:23
In fact, the question (taken literally) is quite boring (see the answers). It is more interesting to ask for categories which have no faithful functor to $\mathsf{Set}$ at all (i.e. are not "concretizable"). Homotopy categories provide the most prominent examples. –  Martin Brandenburg Feb 21 '13 at 0:58
fyi: "I believe that algebraic topology is generally concerned with structures gotten by putting together finitely many, or countably many, finite-dimensional pieces; so their size has a bound lying within any universe, and as soon as we impose such a bound, we can concretize it within any universe. Further, given any category, if we assume the Axiom of Universes, we can pass to a larger universe where we can concretize it. So while Freyd's non-concretizability result is interesting, I think that more fundamental to one's understanding of the situation is Theorem 6.5.6" -- G.B. –  alancalvitti Feb 21 '13 at 2:45
G.B. = George Bergman, and he's referring to his book on universal algebra. –  alancalvitti Feb 21 '13 at 2:46

I think the Fukaya category of a symplectic manifold is an example. The objects are the Lagrangian submanifolds, while the morphisms are the intersection points of the Lagrangians.

-

Consider the category with exactly two objects $a$ and $b$ (they can be anything you want!) and which has exactly one non-identity morphism —going from $a$ to $b$— which is my chair.

-
But, assuming you put your chair on the table at night, your chair should be invertible. –  Miha Habič Feb 21 '13 at 1:09

Assuming suitable access to 'large sets', every category is isomorphic to a (possibly large) category of (possibly large) sets and (possibly large) functions.

We can replace each object $A$ with the (possibly large) set of all arrows with codomain $A$. Call this set $|A|$.

Then, we can replace each arrow $f : A \to B$ with the (possibly large) function $|A| \to |B|$ defined by $g \mapsto f \circ g$.

In many categories, we can restrict the sets $|A|$ to include only arrows coming from a particular (small) set of domains. When we can do this, we can avoid making use of large sets/functions.

-
this construction is Yoneda lemma-based, right? but I've never seen it explained this clearly. Can you post a reference which describes this issue the way you did? –  magma Feb 15 '14 at 22:58
@magma: Hrm. I know a couple very closely related notions: one is the Yoneda lemma as you described, another is in terms of category actions on a set, analogous to the Cayley representation of a group. But now that you've made me think about it, I'm not sure whether or not I've actually seen anyone give this exact construction. –  Hurkyl Feb 15 '14 at 23:11

Let $G$ be a directed graph. Then we can think of $G$ as a category whose objects are the vertices in $G$. Given vertices $a, b \in G$ the morphisms from $a$ to $b$ are the set of paths in the graph $G$ from $a$ to $b$ with composition being concatenation of paths. Note that we allow "trivial" paths that start at a given vertex $a$, traverse no edges, and end at the starting vertex $a$. We have to do this for the category to have identities.

Also we can create categories whose morphisms are not exactly maps but instead equivalence classes of maps. For example given an appropriately nice ring $R$ we can create the stable module category whose objects are $R$-modules. Given two $R$-modules $A$ and $B$ the set of morphisms from $A$ to $B$ is the abelian group of $R$-module homomorphisms from $A$ to $B$ modulo the subgroup of homomorphisms that factor through a projective $R$-module.

-

Algebras/any structures and binary relations or partial functions between them.

$n+1$-manifolds as arrows with $2$ pieces of $n$-dim. boundaries, called cobordism (like a cylinder, between two disks). The objects are the $n$-manifolds.

The objects are points in a topological space, and the arrows are paths. Or, the objects are the paths and the arrows are homotopopies between them. Moreover, we can make higher dimensional categories about this one..

Many many more...

-
An example is $\mathbf{Set}^{op}$, see this related Q –  alancalvitti Feb 21 '13 at 2:29

Also natural deduction can be considered as a category with formulas as objects and proofs as morphisms.

-

Suppose that $X$ is a set and$\mathcal{P}(X)$ is the collection of all subsets of $X$. Let the objects objects of the category be the elements of $\mathcal{P}(X)$. Let the morphisms be ordered pairs $(A, B)$ where $A \subseteq B$. Functions are sets of ordered pairs. The composition of $(A,B)$ and $(B, C)$ is $(A, C)$.

-
Arguably, those are still functions, namely the inclusions $A \hookrightarrow B$. :) –  Bruno Joyal Feb 21 '13 at 0:31
No, $(A,B)$ is not a function $A \to B$. But it can be interpreted as a function. But the same is true for almost all the other examples mentioned in the other answers. The most categories mentioned are concretizable. –  Martin Brandenburg Feb 21 '13 at 2:24

Topological spaces with continuous maps defined up to homotopy.

-
–  Martin Brandenburg Feb 15 '14 at 14:42
Yes, this is what i said, isn't it. –  Alexey Feb 15 '14 at 14:46