# A question about Transfinite Induction

The Transfinite Induction says: Let $\mathbf{P}(x)$ is a property, assume that, for all ordinal numbers $\alpha$ : If $\mathbf{P}(\beta)$ holds for all $\beta < \alpha$, then $\mathbf{P}(\alpha)$ holds. Then $\mathbf{P}(\alpha)$ holds for all ordinals $\alpha$.

My question is: What is the problem if I replace ordinals with cardinals？ I mean could I say that If $\mathbf{P}(\kappa)$ holds for all cardinals $\kappa< \lambda$, then $\mathbf{P}(\lambda)$ holds. Then $\mathbf{P}(\lambda)$ holds for all cadinals $\lambda$.

-
Sure. Any cardinal is an ordinal. The usual version easily implies this one. – Andrés E. Caicedo Nov 19 '10 at 2:32
@Andres: Even without AC? – Nate Eldredge Nov 19 '10 at 2:51
@Nate: AC has nothing to do with this, in the context of this question, where "cardinal" means "initial ordinal". The result is an easy consequence of well-orderability. But, now that you mention this, I suppose one could ask the ZF question, where P is a property of (not necessarily well-ordered) "cardinalities". Then the answer is no, in general. I think an example would be to assume that there is an infinite Dedekind-finite set, and let P be the statement "the cardinalities are well-founded below me". – Andrés E. Caicedo Nov 19 '10 at 2:55
Andres: what can one say about well-founded cardinalities that are not well-ordereable? For example, suppose $X$ is a set and all smaller cardinalities are well-orderable---must $X$ be well-orderable? – Joel David Hamkins Nov 19 '10 at 3:24
your questions is similar to the following: are the set of cardinals well-ordered? but I think in practice it would be difficult to use this in place of ordinal induction because we often use induction to prove a statement about objects defined by recursion. – Kaveh Nov 25 '10 at 17:03

If by cardinal you mean an initial ordinal (an ordinal not equinumerous with any smaller ordinal), then your new scheme is merely an instance of the scheme for ordinals. Indeed, you can see it clearly as a special case, if you realize that under AC every cardinal is $\aleph_\alpha$ for some ordinal $\alpha$, and so your proposed cardinal scheme is asserting that if $P(\aleph_\beta)$ for all $\beta\lt\alpha$, then $P(\aleph_\alpha)$ holds. (And actually, the new scheme is equivalent to the old scheme, if you consider replacing $\alpha$ with $\aleph_\alpha$.)

Without AC, however, there is a more general concept of cardinal, by which is meant something like the equinumerosity class of a set. If $Y$ is a set, then a smaller cardinality amounts to a set $X$ such that $X$ injects into $Y$ but not conversely. Without AC, these cardinals are not necessarily well-founded. Thus, the transfinite induction scheme fails for these more general types of cardinals.

For example, it is consistent with ZF that there are infinite sets that are Dedekind finite, so that they are not bijective with any proper subset of themselves. Let $P(X)$ assert that $X$ is not infinite Dedekind finite. If $Y$ is any set and is infinite Dedekind finite, then for any $a\in Y$ the set $X=Y-\{a\}$ is strictly smaller in size (else there is a countable subset of $Y$ by iterating the bijection) and $X$ is also infinite Dedekind finite. In other words, the property $P(X)$ satisfies the induction scheme for cardinalities, but does not hold of all cardinalities (if there are some infinite Dedekind finite sets). So transfinite induction for cardinalities can fail without the Axiom of Choice.

-
It looks like Andres made the same point in a comment while I was writing my answer.... – Joel David Hamkins Nov 19 '10 at 3:18

@Dong:

1. As I pointed out in comments, and Pete mentioned in his answer, well-orderability is all you need, so yes, if $P$ is a property of cardinals as you describe, then it holds of all cardinals. You can see this by taking $P'(\alpha)$ to be: "$\alpha$ is not a cardinal, or else, it is a cardinal and $P(\alpha)$", and applying the usual transfinite induction theorem to $P'$.

2. In 1., I took "cardinal" to mean "initial-ordinal". Several questions come to mind immediately if we remove choice from the picture:

a. Suppose $P$ is a property of (not necessarily well-ordered) cardinalities, and it has the property you mention: If for all smaller sizes it holds, it holds for the size under consideration.

This does not suffice for $P$ to hold at all sizes. For example, suppose there is an infinite Dedekind-finite set, and let $P(X)$ be the statement:

"Either $X$ is not infinite Dedekind-finite, or else, the cardinalities are well-founded below the size of $X$".

Being Dedekind-finite means that any proper subset has smaller size. It follows that if any smaller set satisfies $P$, so does $X$. But $P(X)$ is plain false if $X$ is infinite Dedekind-finite (and it is consistent with ZF that there are such sets).

b. Suppose that all sets of smaller cardinality than that of $X$ are well-orderable. It does not follow that $X$ itself is well-orderable. For example, consider Solovay's model, and take $X={\mathbb R}$. Since the perfect set property holds, any subset of the reals either has the same size as ${\mathbb R}$, or else it is countable, in which case it is well-orderable. But ${\mathbb R}$ itself is not well-orderable.

c. A significantly harder question is whether, if cardinalities are well-founded, then choice holds. This is an open problem. It was asked independently by T. Forster and D. Savaliev, and I have thought about it on and off for a while.

-
Thanks for (b) and (c), which address my comment above. – Joel David Hamkins Nov 19 '10 at 10:54

An answer from a non-set theorist (beware!):

It is not necessary to talk about ordinals or cardinals at all to discuss transfinite induction. It is something that makes sense with respect to any well-ordered set. (I do know that each well-ordered set is order-isomorphic to a unique von Neumann ordinal. However, I didn't know this until relatively recently, and it didn't stop me from proving things by transfinite induction.) Since any subset of a well-ordered set is again well-ordered, you have a lot of choices in terms of ordinal / cardinal induction.

-
I agree with Pete, it is enough to cook up any well ordered set to make transfinite induction work. – Leo Alonso Nov 19 '10 at 11:25