16
$\begingroup$

I am reading Philosophy, not Set Theory, so please excuse the naivety of my question.

My question concerns the wildly different character of ordinal arithmetic versus cardinal arithmetic.

The "initial" set of ordinals (upto omega-1), defined using succession and limit supremum, contains only countable ordinals. Thus, omega, omega squared, ... epsilon-nought (the omega'th tetrate of omega), ... these are all countable sets. I understand why these sets are countable.

Yet, when we consider cardinal numbers, 2 to the power aleph-nought is not countable. I understand why it is not a countable cardinal.

What is it about the character of cardinal arithmetic that leads to such wildly different result from that of ordinal arithmetic. After all, cardinal numbers are defined to be certain types of ordinal number. Omega and aleph-nought are the same set. Yet (as cardinals) 2 to the aleph-0 is uncountable, while (as ordinals) 2 to the omega, to the omega, to the omega,... is countable.

$\endgroup$
4
  • 3
    $\begingroup$ One approach is to ask why we can't define ordinal exponentiation in the same way as cardinal exponentiation. Given well-ordered sets $a$ and $b$, why don't we have a "natural" well-ordering on the set of all functions from $b$ to $a$? It's easy to show that the lexicographic order doesn't work. I'm not sure how to formulate or prove the general result, although I gather that it's possible. Maybe someone can address that? $\endgroup$ Aug 6, 2013 at 22:27
  • 1
    $\begingroup$ The definition of the ordinal arithmetic actually gives you a set and a well-ordering of that set. In the definition of the cardinal exponential, you only get a set. Then the value of the cardinal exponential is the smallest ordinal that well-orders that set. Without the axiom of choice, even one such well-ordering may not exist. $\endgroup$
    – William
    Aug 6, 2013 at 22:32
  • $\begingroup$ Please be more precise about the "wild difference" that concerns you? Your question reads as if you think that ordinals are all countable. $\endgroup$
    – Rob Arthan
    Aug 6, 2013 at 22:36
  • $\begingroup$ @William and ChrisCulter : Thanks to you both for your interesting and helpful comments. The definition of cardinal exponentiation in terms of the smallest well-ordering is especially helpful. I honestly believed that there was no widely accepted definition. The role of AC is also very revealing. $\endgroup$
    – gamma
    Aug 6, 2013 at 22:44

2 Answers 2

23
$\begingroup$

The reason is that the definitions of ordinal arithmetics and cardinal arithmetics are very different.

Whereas the ordinal arithmetics operations are concerned with order types, the cardinal arithmetics are concerned with certain sets.

For example, $\alpha+\beta$ as ordinals is the order type of $\alpha$ concatenated with $\beta$. Whereas cardinality strips naked any possible structure, and considering the cardinality of the set $\{0\}\times\alpha\cup\{1\}\times\beta$, which is equal to the maximum of $|\alpha|$ and $|\beta|$ (granted one is infinite).

Exponentiation, which is the strangest one, is defined very differently, again, from ordinals and cardinals.

  • In cardinals $\alpha^\beta$ is the cardinality of the set of all functions from $\beta$ to $\alpha$.
  • In the ordinals, we care about the order, so $\alpha^\beta$ is the order type of the reverse lexicographic order of functions from $\beta$ into $\alpha$ which are non-zero only in finitely many coordinates.

    Equivalently, and perhaps more clearly, we can define this by induction, $\alpha^0=1$, $\alpha^{\beta+1}=\alpha^\beta\cdot\alpha$, and for a limit ordinal $\delta$, $\alpha^\delta=\sup\{\alpha^\beta\mid\beta<\delta\}$.

    Now we easily see that $2^\omega=\omega$ when we are talking about ordinal exponentiation. $2^\omega$ is the limit of $2^n$ for finite $n$, but $2^n$ has a finite order type, and it's a strictly increasing sequence. The limit of a strictly increasing sequence of finite ordinals is $\omega$ itself.

Well, it sounds weird, isn't it? But it's not really weird. We have this sort of phenomenon in other - more familiar - systems of arithmetics.

In the natural numbers $n\cdot m$ can be defined as repeated addition of $n$, $m$ times. Addition itself can be defined as repeated successor operation. On the other hand, when we consider the real numbers $\sqrt2\cdot\sqrt2$ cannot be thought as repeated addition. What does it even mean to add something $\sqrt2$ times? It is true that in this case, if we restrict back to the natural numbers then the operations become repeated application of the "previous operation", but this is because of the nature of the natural numbers as a corner stone of modern mathematics (in many many ways). For infinite, and less-corner stoney this is not the case, as exhibited in ordinals and cardinals.

$\endgroup$
1
  • 3
    $\begingroup$ Wow! That is as clear and helpful an answer as I could have ever hoped for. You have also answered so many questions I have considered but did not here pose. Also, I love the analog you give with systems of arithmetic. Many thanks. $\endgroup$
    – gamma
    Aug 6, 2013 at 23:03
1
$\begingroup$

Well, to be frank, the distinction between $2^\omega$ and $2^{\aleph_0}$ is weirder, since we do have a quite natural link between $\omega$ and $\aleph_0$, whereas we do not have that between any natural number and $\sqrt2$.

The former case is using two homomorphic structures, with cardinalities being easily isomorphically embedded into ordinals, and the exact same syntactical operator, yielding non-isomorphic results. That is truly weird.

NOTE: this was intended as a comment to the very nice answer above, not the original question. Sorry.

$\endgroup$
5
  • $\begingroup$ That is weird. In fact, it's so weird I can't quite make sense of it. Are you saying : The (order preserving) isomorphism we use to embed the cardinals into the ordinals becomes a non-isomorphism when viewed as a syntactical operator. I'm still a bit green with this stuff, so sorry if that's a dumb question. $\endgroup$
    – gamma
    Oct 30, 2014 at 16:09
  • $\begingroup$ @Nick: If it's any consolation, I have no idea what's going on here either. $\endgroup$
    – Asaf Karagila
    Oct 30, 2014 at 16:29
  • $\begingroup$ The difference being that the example @AsafKaragila brought up was that of a pure extension, i.e., multiplication of reals is just an extension of multiplication of integers, i.e., $N * N$ is still the same, for any integers, in that extended field. I.e., the semantics of multiplication doesn't change just extend... This is not the case for exponentials of ordinals vs cardinals. I.e., an $2^x$ [in the class of cardinals] =/= $2^{iso(x)}$ [in the class of ordinals], where 'iso' is mapping cardinals into ordinals, such as $iso(\aleph_0) = \omega$. $\endgroup$
    – davber
    Oct 30, 2014 at 18:08
  • $\begingroup$ Again, it is very rare that the same syntactical operator stands for entirely distinct operations, in domains being mutually homomorphic. So, I am a bit saddened by getting two down votes on pointing this out. Would be happier to see what exact terms I used were not accurate, so I can learn to get to the level of acuity as @AsafKaragila. $\endgroup$
    – davber
    Oct 30, 2014 at 18:19
  • 1
    $\begingroup$ Your answer doesn't appear to address the confusion the OP is having that since $\aleph_0 = \omega$, that must mean that also $2^{\aleph_0} = 2^{\omega}$, yet we can also prove by the two different definitions of exponentation that that's not the case. Also, I'm not sure this answer adds anything to Asaf Karagila's answer even if it is fixed up. $\endgroup$
    – Timothy
    Feb 6, 2019 at 4:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .