Gracious Living

Cardinal Arithmetic
December 8, 2010, 03:23
Filed under: Math, Set Theory | Tags: , , , ,

Let’s get tricky!  Unlike ordinal arithmetic, the arithmetic of cardinals isn’t really an extension of Peano arithmetic.  Rather, it’s a consequence of the set model of ordinals, with the sum of two ordinals being the order type of their disjoint union, and their product being the order type of their Cartesian product.

Part of the reason for this is that cardinals have a vastly different notion of “successor.”  See, the ordinals are well-ordered, so any subset has a least element, and thus we can identify each cardinal with the least ordinal of its cardinality.  So we’ll say $\aleph_0=\omega,\aleph_1=\omega_1,\dotsc$.  (Exercise: these are all limit ordinals.)  Then the cardinals, as a subset of the ordinals, are also well-ordered, and thus we can define the successor of a cardinal as the least cardinal greater than it, and the limit of a set of cardinals as their least upper bound.

Since the cardinals, as aleph numbers, are also indexed by the ordinals, we have $\aleph_{S\alpha}=S\aleph_\alpha,\aleph_{\lim\alpha}=\lim\aleph_\alpha$.  We can treat the map $\alpha\mapsto\aleph_\alpha$ as a function $\aleph:\mathbf{On}\rightarrow\mathbf{On}$; then this function is normal.  So in particular it has a fixed point (indeed, an unbounded class of them): this is an ordinal $\alpha$ such that $\omega_\alpha=\alpha$.  Even though the cardinals increase a lot “faster” than the ordinals, this number is simultaneously the $\alpha$th cardinal and the $\alpha$th ordinal!  The first such ordinal is $\omega_{\omega_{\omega_{\dotsc}}}$.

This fills me with the greatest glee.

We won’t be assuming the generalized continuum hypothesis for the first part of this, so we won’t mention the beth numbers (which are $\beth_0=\aleph_0,\beth_{S\alpha}=2^{\beth_\alpha},\beth_{\lim\alpha}=\lim\beth_\alpha$).  If you do assume it, the beth numbers are the aleph numbers; if you don’t, it’s difficult to say anything about them arithmetic-wise.

Like Devlin, I’ll use $\kappa,\lambda,\mu$ for cardinals, $\alpha,\beta,\gamma$ for ordinals.

We define the sum of two cardinals to be the cardinality of their disjoint union, and their product to be the cardinality of their Cartesian product, both as sets.  From the definition, it’s obvious that they’re both associative and commutative — this basically follows from the associativity of unions and products up to bijection.  Likewise, it isn’t hard to show that the distributive property and appropriate identities hold.  For exponentiation, $\kappa^\lambda$ should be the cardinality of the set of functions from $\lambda$ to $\kappa$.  With a little work, you can show that $\kappa^{\lambda+\mu}=\kappa^\lambda\kappa^\mu,(\kappa^\lambda)^\mu=\kappa^{\lambda\mu}$, and $(\kappa\lambda)^\mu=\kappa^\lambda\kappa^\mu$.  These are all identical to the properties of natural number exponentiation.

Addition and multiplication immediately extend to products indexed by arbitrary ordinals/cardinals: let $\sum_{\alpha<\beta}\kappa_\alpha=|\bigcup_{\alpha<\beta}\kappa_\alpha\times\{\alpha\}|$ and $\prod_{\alpha<\beta}\kappa_\alpha=|\prod_{\alpha<\beta}\kappa_\alpha|$, where the second product means “Cartesian product of sets.”  I don’t immediately see how to do something similar for exponentiation.  But note that we have $\kappa\times\lambda=\sum_{\alpha<\lambda}\kappa,\kappa^\lambda=\prod_{\alpha<\lambda}\kappa$.  So multiplication is repeated addition, exponentiation is repeated multiplication.

The ironic thing about all these nice properties is that once we hit infinity, cardinal arithmetic becomes utterly trivial!  The following fact is the germ of all this, and is nontrivial enough that I’ll prove it.

Proposition.  An infinite cardinal times itself is itself.

Proof.  Suppose not, and let $\kappa$ be the least cardinal such that $\kappa\cdot\kappa\ne\kappa$.  Since multiplication by a number is normal, we must have $\kappa\cdot\kappa>\kappa$, and $\lambda\cdot\lambda=\lambda$ for all $\aleph_0\le\lambda<\kappa$.

Let $K=\kappa\times\kappa$.  This is $\{(\alpha,\beta)\in\mathbf{On}\times\mathbf{On}:\alpha,\beta<\kappa\}$.  For all ordinals $\gamma$, let $K_\gamma=\{(\alpha,\beta)\in\mathbf{On}\times\mathbf{On}:\alpha+\beta=\gamma\}$.  Let $\gamma<\kappa$: then $(\alpha,\beta)\in K_\gamma$ has $\alpha,\beta\le\alpha+\beta<\gamma<\kappa$, so $K_\gamma\subset K$.  On the other hand, let $(\alpha,\beta)\in K$ and $\lambda=\max(|\alpha,\beta|)$.  Then $|\alpha+\beta|=|\alpha|+|\beta|<\lambda+\lambda=2\cdot\lambda\le\lambda\cdot\lambda=\lambda<\kappa$.  So $\alpha+\beta<\kappa$, and $(\alpha,\beta)\in K_{\alpha+\beta}\subset K$.  Thus, $K_\gamma$ partitions $K$.

We can then well-order $K$ via a sort of “double dictionary ordering”: let $(\alpha,\beta)\in K_\gamma<(\alpha^\prime,\beta^\prime)\in K_{\gamma^\prime}$ if $\gamma<\gamma^\prime$, or $\gamma=\gamma^\prime,\alpha<\alpha^\prime$, or $\gamma=\gamma^\prime,\alpha=\alpha^\prime,\beta<\beta^\prime$.  This stacks all the sets of the partition in a well-ordering and then well-orders each of them in the dictionary ordering.

Let $\delta$ be the order type of this set (the unique ordinal order-isomorphic to it).  Then $|\delta|=|K|>\kappa$.  But then there must be an element $(\alpha_0,\beta_0)$ inside $K$ such that the order type of $S=\{(\alpha,\beta)\in K:(\alpha,\beta)<(\alpha_0,\beta_0)\}$ is equal to $\kappa$.  Let $\gamma_0=\alpha_0+\beta_0$, so $(\alpha,\beta)\in S$ has $\alpha,\beta\le\gamma_0$.  So $S\subset(\gamma_0+1)\times(\gamma_0+1)$, and $|S|=|\gamma_0+1|^2=|\gamma_0|^2=|\gamma_0|<\kappa$.  This is a contradiction, since the order type of $S$ is equal to $\kappa$.

To summarize: we partitioned $K=\kappa\times\kappa$ diagonally, used this partition to give a well-ordering, and found a point inside where, assuming $\kappa$ was the least cardinal with $\kappa^2>\kappa$, the set of elements $S$ before that point had order type $\kappa$.  $S$ had to end in some element of the partition, so its was an (unordered) subset of the corresponding ordinal squared, and its cardinality was then equal to the corresponding cardinal squared, which was the same as the corresponding cardinal, so less than $\kappa$, contradicting the order type.  $\square$

As a corollary, if $\aleph_0\le\kappa\le\lambda$, then $\lambda\le\kappa+\lambda\le\lambda+\lambda= 2\lambda\le\lambda\lambda=\lambda$.  Likewise, $\lambda\le\kappa\cdot\lambda\le\lambda\cdot\lambda=\lambda$.  Thus, $\kappa+\lambda=\kappa\lambda=\max(\kappa,\lambda)$!

A side effect of this is that we can’t define cardinal arithmetic in the same inductive way ordinal arithmetic is defined.  If we had $\kappa+S\lambda=S(\kappa+\lambda)$, this would be strictly greater than $\kappa+\lambda$, which is untrue if $\kappa>\lambda\ge\aleph_0$.  In fact, since $S\aleph_\alpha=\aleph_{S\alpha}$, we would have $\aleph_\alpha+\aleph_\beta=\aleph_{\alpha+\beta}$ and the whole situation would reduce to the image of ordinal arithmetic under $\alpha\mapsto\aleph_\alpha$.  This would be exceedingly dull.  The problem is that we don’t have transfinite recursion any more… I mean, clearly if we have $P(\aleph_0),P(\aleph_\alpha)\Rightarrow P(S\aleph_\alpha),$ and $(\forall\beta<\gamma)P(\aleph_\beta)\Rightarrow P(\aleph_\gamma)$, then transfinite induction on the indices gives $P(\aleph_\alpha)$ for all $\alpha$, but these properties are much harder to prove than for ordinals.

Now let’s look at exponentiation.  For ordinals, since this is a normal function, we’ll always have $\alpha^\beta=\beta$ for some $\beta$ if $\alpha>1$.  For example, $2^\omega=\lim\{2,4,8,\dotsc\}=\omega$.  But for cardinals, $2^{\aleph_0}=\beth_1$ by definition — indeed, we proved that $|2^A|=|\mathcal{P}(A)|>|A|$ for all sets $A$.

But the arithmetic still sort of trivializes.  If $1<\kappa\le\lambda$ and $\lambda$ is infinite, then $\kappa^\lambda$ is the cardinality of the set of maps $\lambda\rightarrow\kappa$.  Each map is a subset of $\lambda\times\kappa$, which has cardinality $\lambda\kappa=\lambda$, so $\kappa^\lambda\le|\mathcal{P}(\lambda)|=2^\lambda$.  But clearly $2^\lambda\le\kappa^\lambda$, so $2^\lambda=\kappa^\lambda$.

We can even prove that $(S\lambda)^\lambda=2^\lambda$.  But this requires more set theory than we have so far.  I’ll leave you with this, and perhaps return to the more advanced topics later on.

1 Comment so far