# Transfinite induction for collections that are not classes

In ZFC, a class is typically defined as the collection of sets $x$ that satisfy some formula $\varphi(x, p_1, \ldots, p_n)$ for parameters $p_1, \ldots, p_n$. We therefore have that all sets are classes and there is a class of all sets etc. But since there are only countably many formulas, it seems that "most" "collections" of sets are still not classes (for some naive notion of "most" and "collection"). Is this correct?

Many results in ZFC are stated (only) for classes. Take for example the transfinite induction theorem: If $C$ is a class of ordinals such that $\alpha \in C$ implies $\alpha + 1 \in C$, and for limit ordinals $\alpha$ with $\forall \beta < \alpha \ \beta \in C$, we have $\alpha \in C$, then $C$ is the class of all ordinals.

This raises two questions: Is there a precise way to define a notion of a collection of sets such that "everything" is a collection? If so, is it consistent with ZFC that there is such a collection of ordinals that satisfies the two conditions of transfinite induction, but is not the collection of all ordinals?

• You might refer the NBG set theory, in which everything is a class. – Hanul Jeon Jan 30 '17 at 11:29

As you mentioned, classes in ZF(C) is just a renaming of formulas. Such convention appears in ZFC just because ZFC can't describe the notion of classes as a its object. ZFC does not have a notion of classes. However, some variants of ZFC such as NBG and MK can describe classes as its objects and we can formalize your question over such theories. It may be an answer of your first question.

You have proved there are classes which is not definable by formulas, by a cardinality argument. There are subtle traps in your argument, comes from the term definability. We should formalize the term definability before to use it.

The naive way to define the term definability is as follows: a set $x$ is definable if there is a formula $\phi$ and parameters $b$ such that, $\phi(x,b)$ and if $\phi(y,b)$ then $x=y$. However formulas are not an object of ZFC so we can't quantify it. This is the reason why we can't apply the cardinality argument directly; we can't form the set of formulas.

There is another way to define a definability: we could use a truth predicate $\models$, a relation over takes a natural number (which works as a coded formula) and parameter sets as inputs. We can avoid previous problem by using the truth predicate, because we can substitute a quantifier over formulas to that of natural numbers. It would be happy if we have a truth predicate... However, Tarski's undefinability theorem shows a theory can't define its own truth predicate. Thus our attempt to formalize the definability stucks.

In fact, NBG has a model that every class is definable. Of course, the term definability is not defined internally but externally, that is, outside a model.

There is no such complex obstable in your last question. You can formalize it easily. However extensions of ZF(C) such as NBG or MK also proves the transfinite induction for any classes. Therefore the answer of your last question seems negative.

• What do you mean, "the answer to your last question seems negative"? Being provable in NBG or MK does not imply that the negation is inconsistent with ZFC, does it? – Christian Matt Jan 30 '17 at 13:01
• @ChristianMatt Yes, provability in NBG or MK does not imply it. However your question is not formalizable in ZFC in full detail, so we must extend ZFC by adding a notion of class. There might be other choices and the answer depends on it. – Hanul Jeon Jan 30 '17 at 14:29
• @ChristianMatt However, I think NBG, MK or the second-order ZFC are natural choices and they imply the transitive induction for classes. – Hanul Jeon Jan 30 '17 at 14:30