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 \alphath cardinal and the \alphath 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
Leave a comment

[…]  It should be mentioned that topology, for the most part, doesn’t really care about large cardinals — at most, we’re dealing with , the cardinality of our favorite counterexample , and , […]

Pingback by Countability Axioms « Gracious Living

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: