6
$\begingroup$

I'm trying to pin down a notion of inductive definability in category-theoretic terms.

The sorts of inductively defined sets (and classes) I'm most interested in are those that admit of induction and recursion. So far, I've noticed that (weakly?) initial algebras of an endofunctor do a pretty good job of this.

We can capture natural number objects (and therefore $\mathbb{N}$) and other inductive types this way. But what about things like the constructive ordinals (or number classes) or even segments of the cumulative hierarchy?

I want to exclude things like the classical continuum, but not through cardinality, since the cumulative hierarchy is certainly quite large. And polynomial functors don't seem to cut it since the powerset functor isn't polynomial and doesn't have a smallest fixed point (and thus not an initial algebra). Should I restrict the powerset functor a certain way to get one? Based on inaccessible cardinals?

Is there a unified characterization of 'inductive' in category theory that would apply to these sorts of cases?

$\endgroup$
6
$\begingroup$

It is indeed the case that initial algebras for functors are the category-theoretic manifestation of inductive definitions. There's a whole industry surrounding this idea.

You are more specifically asking about (pieces of) the cumulative hierarchy. On that topic you should look at algebraic set theory (AST). A good overview of the subject was written up by Benno van den Berg and Ieke Moerdijk in arXiv:0710.3066. Do not be put off by all the talk about constructive set theories. They're just generalizing the ordinary (classical) set theory to natural cateogry-theoretic settings where excluded middle does not hold.

In AST we study categories of classes. Such categories have a notion of small map. The intuition is that a map between classes is "small" if the inverse image of every point is a set (rather than a class). This is a generalisation of the distinction "classes are large, sets are small" because a class $C$ is a set, and only if, the unique map $C \to 1$ is small. Smallness is axiomatised by some fairly straightforward axioms.

Next, to get the cumulative hierarchy, we study ZF-algebras. A ZF-algebra is a (large) poset $(P, {\leq})$ which is closed under small suprema and is equipped with a unary operation $s : P \to P$. The initial ZF-algebra $(V, {\sqsubseteq}, s)$ can be seen as the cumulative hierarchy, where $\sqsubseteq$ corresponds to subset inclusion and $s$ to the singleton map $x \mapsto \{x\}$. See section 4 of the van den Berg & Moerdijk's notes.

It should be possible to cook up chunks of $V$ by taking variations on a theme. For instance, $V_\omega$ ought to arise if we require closure under finite suprema (I have not checked this.)

By the way, we can get $V$ as the initial algebra of the small powerset functor in the category of classes. Let $\mathcal{C}$ be the (large) category of all classes. Define $P : \mathcal{C} \to \mathcal{C}$ by $P(X) = \{S \mid S \subseteq X\}$, i.e., $P(X)$ is the class of all subsets of $X$. Then $V$ is the initial $P$-algebra, isn't it?

$\endgroup$
1
  • $\begingroup$ Thank you very much! This addressed my explicit worry about $\mathcal{V}$ in category theory, both in terms of the small powerset functor, but also the algebraic set theory view on ZF-algebras, which I was wholly unfamiliar with. This also addressed a larger issue which I had been wondering about (rather vaguely) on how (and whether!) category theorists spend much time on categorifying axiomatic set theory. $\endgroup$ – Patrick Mar 16 '17 at 21:48

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.