Morphism that is not a mapping

For any preordered set $X$, one can define a category whose objects are the elements of $X$, such that $\mathrm{Mor}(x,y)$ has one element if $x\leq y$ and is empty otherwise. This defines a category because $x\leq x$ for all $x\in X$, and if $x\leq y$ and $y\leq z$ then $x\leq z$.

For another example, any monoid $M$ defines a category with one object, whose set of morphisms is the monoid $M$. The composition law is given by the monoid operation.

One of my favorite "counterexamples" to preconceived notions about categories is matrix algebra:

• The objects are natural numbers
• The arrows are matrices ($\hom(m,n)$ is the collection of $n \times m$ matrices)
• Composition of arrows is the matrix product

Here's a naturally-occurring example (coming from computability theory) of a category whose morphisms really aren't "maps" in any good sense:

• The objects are just the sets of natural numbers.

• A pre-morphism from $A$ to $B$ is a Turing machine $\Phi_e$ such that $\Phi_e^A=B$.

We say that two pre-morphisms $\Phi_{e_0}, \Phi_{e_1}: A\rightarrow B$ are equivalent (and write $e_0\sim e_1$) if for every $X, n$, $$\Phi_{e_0}^X(n)\cong \Phi_{e_1}^X(n)$$ (where "$P\cong Q$" means "either both $P$ and $Q$ are undefined, or $P$ and $Q$ are both defined and are equal to each other").

• A morphism is then an equivalence class of pre-morphisms: $$Hom(A, B)=\{\{e_1: e_1\sim e_0\}: \Phi_{e_0}^A=B\}.$$

Now each object is a set . . . but the morphisms don't act as functions between those sets! (This is the fundamental difference between many-one reduction and Turing reduction.) Meanwhile, each morphism is a function - specifically, a partial function from $2^\omega$ to $2^\omega$ - but this functional behavior isn't really reflected in what a given morphism does to a given object! So this category doesn't really satisfy the intuition that morphisms are functions between objects.