25
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Zhen Lin Feb 21 '13 at 0:23
  • 2
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Feb 21 '13 at 0:58
  • $\begingroup$ 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. $\endgroup$ – alancalvitti Feb 21 '13 at 2:45
  • $\begingroup$ G.B. = George Bergman, and he's referring to his book on universal algebra. $\endgroup$ – alancalvitti Feb 21 '13 at 2:46
8
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ But, assuming you put your chair on the table at night, your chair should be invertible. $\endgroup$ – Miha Habič Feb 21 '13 at 1:09
  • 1
    $\begingroup$ How is the word “chair” a morphism? I do not get the concept on this one… $\endgroup$ – Luke Feb 28 '15 at 23:33
  • 1
    $\begingroup$ The idea is that a morphism can be anything you want as far as they satisfy the definition of a category... $\endgroup$ – Arbër Ll Jan 10 '16 at 10:58
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – magma Feb 15 '14 at 22:58
  • $\begingroup$ @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. $\endgroup$ – Hurkyl Feb 15 '14 at 23:11
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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...

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

Topological spaces with continuous maps defined up to homotopy.

$\endgroup$
  • $\begingroup$ See en.wikipedia.org/wiki/Homotopy_category $\endgroup$ – Martin Brandenburg Feb 15 '14 at 14:42
  • 1
    $\begingroup$ Yes, this is what i said, isn't it. $\endgroup$ – Alexey Feb 15 '14 at 14:46
  • 1
    $\begingroup$ This is a very good one because is not even concretizable, so it is, in some sense, intrinsecally non-set based $\endgroup$ – mattecapu Oct 21 '18 at 7:22
2
$\begingroup$

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)$.

$\endgroup$
  • 2
    $\begingroup$ Arguably, those are still functions, namely the inclusions $A \hookrightarrow B$. :) $\endgroup$ – Bruno Joyal Feb 21 '13 at 0:31
  • 2
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Feb 21 '13 at 2:24
2
$\begingroup$

Here is another example, much simpler than the previous one I gave: the category of integer matrices of all (finite) dimensions. (Any associative ring of coefficients could be used instead of integers.)

The morphisms of this category are matrices with the usual operation of multiplication (playing the role of composition of morphisms), and the objects are natural numbers. A matrix $m\times n$ is a morphism from $n$ to $m$ (or from $m$ to $n$, passing to the opposite category).

Generally speaking, the true elements of a category are morphisms, and objects are just opaque labels to keep track of when two morphisms can be composed. A category is just a generalisation of a group (where not every element is invertible and not every pair of elements is composable).

However, this may be not a good example, because the question was about objects that "are some sort of structure based on sets," and natural numbers are not exactly "based on sets."

If desired, here is a version for sets as objects: let morphisms between sets $A$ and $B$ be "matrices" $B\times A$ with only finitely many non-zero entries. That is, the objects are arbitrary sets and morphisms $A\to B$ are functions $B\times A\to\mathbf{Z}$ which take non-zero values on finitely many arguments. Define the composition of morphisms as the multiplication of these "matrices."

$\endgroup$
  • $\begingroup$ Your first matrix example also fits with the objects being based on sets. The natural numbers have several set-theoretic constructions. For example Von Neumann ordinals: 0 = { }, 1 = {{ }}, 2 = {{ }, {{ }}}, 3 = {{ }, {{ }}, {{ }, {{ }}}}, ... where each natural number is equal to the set of all natural numbers less than it; and Zermelo ordinals: 0 = { }, 1 = {{ }}, 2 = {{{ }}}, ... where each natural number is equal to the set containing only its predecessor. $\endgroup$ – Fonebone Feb 26 at 21:43

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.