A question about Transfinite Induction

Question

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$.

Answer 1

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.

Answer 2

@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.

Answer 3

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.