3
$\begingroup$

While there is a lot of work in category related to notions of realizability and computability, etc... I've failed to find work on categories that are computable in the sense of having object and morphism sets that are recursive or recursively enumerable.

For example, consider the following definition: An category is RE-basic if the set of its objects, arrows, and the graph of it's composition function are recursively enumerable.

Has this (or similar concepts) been studied extensively?

In particular, one could imagine a software package that works with these RE-basic categories.

$\endgroup$

2 Answers 2

4
$\begingroup$

It sounds like what you're talking about is computable structure theory, applied to categories in particular.

In computable structure theory, say we have a structure $\mathcal{S}$ consisting of a set $X$ together with some operations $f_i$, some constants $c_i$, and some relations $R_i$. (This signature is usually finite; if infinite, we usually demand that it be appropriately computable.) Then $\mathcal{S}$ is computably presentable if, well, it has a computable presentation: there is some isomorphic structure $\mathcal{A}\cong\mathcal{S}$ whose domain is a computable subset of $\omega$ and such that the relations and functions of the signature are each computable when restricted to the domain. (If the signature is infinite, we need a "uniformity" condition.) The bible of computable structure theory is the book by Ash and Knight: https://www.elsevier.com/books/computable-structures-and-the-hyperarithmetical-hierarchy/ash/978-0-444-50072-4

It turns out this has a bunch of different equivalent formulations. For example, we could demand that the domain be merely computably enumerable, or all of $\omega$; as long as $\mathcal{S}$ is infinite this would make no difference. Also, the graph of a function being c.e. is the same as the graph of a function being computable, so long as its domain is computable. So there's a lot of flexibility present. On the other hand, c.e.-ness versus computability is a serious issue for relations - see for example any of the papers:

which study computably enumerable partial orderings. But in your case, the way you're presenting categories is purely functional, so the subtleties don't come up.

Note that we can represent any structure by a transitive graph, in a suitably effective way; so computable category theory is already as broad as computable structure theory, full stop. So it's unclear what, specifically, categories will add to the equation, and in general there will be nothing nice which holds of categories which isn't just always true.

However, there's a couple neat dimensions that categories add to the situation, which interest me in particular. First, enrichment. I think there's a lot of interesting wiggle room to talk about what a "computable category enriched over topological spaces" (for example) ought to be. Actually, even pinning down what a "computable topological space" is is quite complicated - see e.g. http://www.jucs.org/jucs_15_6/elementary_computable_topology or http://ac.els-cdn.com/S016800720300054X/1-s2.0-S016800720300054X-main.pdf?_tid=3a1b6ed2-b316-11e4-b0e1-00000aacb35e&acdnat=1423787057_f06075c4a90fa6635a8c42f24e059e12 - so maybe a better place to start is something more algebraic like "computable category enriched over abelian groups." One immediate question right off the bat is how much uniformity we demand of the abelian-ness between different hom-sets; between "totally uniform" and "arbitrary," I think there's room for some interestingness.

Second, most interesting categories are uncountable, and everything I've described only makes sense for countable structures. There's a few ways to go, here (in general, the volume "Effective mathematics of the uncountable" is really interesting for this sort of thing). There are several versions of computability theory which make sense for uncountable objects, such as $\alpha$- or $E$-recursion; unfortunately, they often rely on the universe being appropriately well-orderable, or some similarly strong criterion. On the other hand, we can also look at what happens when we collapse a structure to be countable via forcing; see http://arxiv.org/abs/1405.7456. In many senses this is very well-behaved; on the other hand, for non-algebraic objects - e.g. topological spaces - this seems very destructive. So, figuring out the right perspective for computable uncountable categories could be very interesting.

$\endgroup$
2
  • $\begingroup$ Side note: an important topic in computable structure theory is relative complexity. We want to say $\mathcal{A}$ is simpler than $\mathcal{B}$ if every copy (=isomorphic copy with domain $\omega$) of $\mathcal{B}$ computes a copy of $\mathcal{A}$; however, we run into problems when we try to specify the amount of uniformity demanded in this computation. For instance, "uniform," "nonuniform," and "uniform modulo finitely many parameters" are all inequivalent, which is very annoying! (See logcom.oxfordjournals.org/content/early/2010/09/10/…) $\endgroup$ Feb 13, 2015 at 9:08
  • $\begingroup$ Reading this answer again, thanks. It would be nice if category theorists took this computable structure theory (more?) seriously and applied it to category theory in practice. Do they? Or somehow embraced/studied/pursued some form of foundational "low power", "low cardinality", "concrete", "computable", or "combinatorial" lean formulation of category theory that didn't need high power set theory as a foundation dependency, applicable to the analysis of systems of strength equal to or less than the system of Second Order Arithmetic. Including bare PRA. Maybe this deserves a full MO question. $\endgroup$
    – Rex Butler
    Mar 8 at 0:38
1
$\begingroup$

Is this what you are looking for?

http://www.cs.man.ac.uk/~david/categories/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.