It is well known (if you're a topos-theorist, you will call it the definition), that the natural numbers $\mathbb{N}$ together with the zero constant $0$ and the successor function $1\xrightarrow{\ 0\ }\mathbb{N}\xrightarrow{+1}\mathbb{N}$ are initial in the category of such diagrams of sets $1\longrightarrow X\longrightarrow X$ (this is known as the principle of inductive definition).

Suppose we work in some class theory like NBG.

Is it true that the natural numbers are still initial in the (meta-)category of such diagrams of classes? Or in set-theoretical terms, does inductive definition work for classes?

Originally, I was thinking about the following: Suppose we replace the classical Axiom of Infinity by the

Axiom of an NNO: There exists a Natural Numbers Object in $\mathbf{Set}$.

Can I show that finite cardinals form a set by recursively defining a function $\mathbb{N}\xrightarrow{\ \ f\ \ }(\text{Class of all Sets})$ by $f(0)=\emptyset$ and $f(n+1)=f(n)\cup\{f(n)\}$ and then applying the Axiom of replacement?

  • $\begingroup$ What is the meaning of 'meta-category'? $\endgroup$ – Hanul Jeon Feb 1 '15 at 10:24
  • $\begingroup$ @tetori Basically something which works like a category but might be too large to fit in somebody's preferred definition of a category. I borrowed the term from CWM: ncatlab.org/nlab/show/metacategory $\endgroup$ – Jakob Werner Feb 1 '15 at 10:27
  • $\begingroup$ I guess, yes, $\Bbb N$ remains the natural number object in the metacategory ${\bf Class}$ of classes. $\endgroup$ – Berci Feb 2 '15 at 23:13

Start by assuming $\omega$ is the smallest set containing $\emptyset$ and closed under the operation $x \mapsto x \cup \{ x \}$. (Such a thing is guaranteed to exist in ZFC and NBG.) We want to show that $\omega$ is an NNO in the category of classes.

Let $X$ be a class, let $x_0 \in X$, and let $F : X \to X$ be a class-function. By the axiom of class comprehension, we may form the class $A$ of all partial functions $f : \omega \to X$ such that $f (\emptyset) = x_0$ and $f (x \cup \{ x \}) = F (f (x))$. (Of course, by ‘partial function’ I mean a set of pairs satisfying the obvious conditions.) It is non-empty: the partial function $\{ (\emptyset, x_0) \}$ is a member of $A$. Moreover, by ordinary induction, we can show that, for every $n \in \omega$, there is $f \in A$ with $(n, x_n) \in f$ for some $x_n \in X$; moreover, since $F$ is functional, for every $n \in \omega$, there is a unique $x_n \in X$ such that $(n, x_n) \in f$ for all $f \in A$ such that $(n, x) \in f$ for some $x \in X$. This defines a class-function $\omega \to X$ (by class comprehension), so we are done.

It appears to me that the above goes through for ZFC, provided we interpret "class" and "class comprehension" correctly.


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.