I'm starting to learn set theory. I've already learned transfinite induction and I started to wonder if we could do the same on a well-ordered proper class, like the class of all ordinal numbers. It seems intuitive to me that we should be able to prove statements about all ordinal numbers by induction. But I'm not sure what theory I need to do this. I don't know anything about set theories other than ZFC, and I still don't really know much about ZFC, so I'm not sure what is and what isn't allowed in ZFC regarding proper classes. For example, I don't know if it's possible to say in ZFC that the class of all ordinal numbers exists. I think it might not be possible. But then maybe I don't need to talk about this class to perform induction over it. Maybe I just need to know what an ordinal number is, and this I know to be sayable.

Could you help me understand this? Please, if there is the slightest chance I won't understand a term or a notion, assume that I won't. I'm new to set theory.

  • $\begingroup$ I'm confused about your question. I only know transfinite induction in the context of the class of all ordinals. Do you mind typing into the question what you mean by transfinite induction? $\endgroup$ – Git Gud Mar 5 '13 at 17:54
  • 3
    $\begingroup$ @GitGud: Transfinite induction and recursion are often done over a specific ordinal, often a cardinal, e.g., $\omega_1$, or $2^\omega$. $\endgroup$ – Brian M. Scott Mar 5 '13 at 17:57
  • $\begingroup$ @BrianM.Scott Thanks, I had no idea. $\endgroup$ – Git Gud Mar 5 '13 at 17:57

ZF(C) doesn’t have proper classes, but as you say, it is possible to write down a predicate $\varphi(x)$ that ‘says’ that $x$ is an ordinal. We can then write $x\in\mathbf{ON}$ with the understanding that it really means $\varphi(x)$. Similarly, if $\varphi(x,y)$ is some two-place predicate, we might be able to prove $$\forall x,y,z\big(\varphi(x,y)\land\varphi(x,z)\to y=z\big)\;,$$ in which case we could write $y=\mathbf{F}(x)$ as an abbreviation for $\varphi(x,y)$ and think of $\mathbf{F}$ as a function, albeit one that might be a proper class (if ZF(C) actually had such things formally).

Yes, it’s possible to do transfinite induction over all ordinals. It’s even possible to do recursive constructions over all ordinals. The theorems, which already hold in ZF, can be stated as follows, where boldface indicates ‘proper classes’ of the definable sort that I described above:

Theorem (Transfinite Induction): If $\varnothing\ne\mathbf{C}\subseteq\mathbf{ON}$, then $\mathbf{C}$ has a least element.

Theorem (Transfinite Recursion): If $\mathbf{F}:\mathbf{V}\to\mathbf{V}$, then there is a unique $\mathbf{G}:\mathbf{ON}\to\mathbf{V}$ such that $\forall\alpha\big(\mathbf{G}(\alpha)=\mathbf{F}(\mathbf{G}\upharpoonright\alpha)\big)$.

(These formulations are essentially the ones used in K. Kunen’s Set Theory.)

  • $\begingroup$ Thank you. When you use the word "even" in "it's even possible...", do you mean that being able to do recursive constructions is something more than being able to do induction? That is, are there things over which we can do induction but can't do recursive constructions? $\endgroup$ – Bartek Mar 5 '13 at 23:01
  • $\begingroup$ @Bartek: I’m not at all sure that there are, but for some reason the ability to do recursive constructions strikes me as more ... impressive, for want of a better word ... than the ability to prove by induction. Probably I should just have said also instead of even. $\endgroup$ – Brian M. Scott Mar 6 '13 at 13:29

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.