10
$\begingroup$

This is my understanding of ordinal arithmetic - two ordinals are the same as one another if there is an order-preserving bijection between them. So for instance

$$1+\omega = \omega$$

because if

$$f(\langle x,y\rangle)=\begin{cases}y+1 & x=1\\ 1 &\text{otherwise}\end{cases}$$

Then $f$ is an order-preserving bijection between $\{ 0 \} \times 1 \cup \{ 1 \} \times \omega$ and $\omega$, where $\{ 0 \} \times 1 \cup \{ 1 \} \times \omega$ is endowed with the addition order.

Likwise if

$$g(\langle x,y \rangle)=2 \times x+y$$

Then $g$ is an order-preserving bijection between $2 \times \omega$ and $\omega$, where $2 \times \omega$ is endowed with the multiplication order, and so $2 \cdot \omega =\omega$ , whereas $\lnot 2 \cdot \omega =\omega \cdot 2$ because $< 0,1 >$ is a limit of $\omega \times 2$ under the multiplication order whereas $2 \cdot \omega$ has no limit ordinals.

On Wikipedia's page, Exponentiation is described for ordinals, where in particular, it says that $2^{\omega} = \omega$. How can this be when $\omega$ does not even have the same cardinality as $2^{\omega}$ - to wit, isn't $2^{\omega}$ uncountable, with the same cardinality as the reals?

$\endgroup$
  • 2
    $\begingroup$ You can find some good starting points on how to format mathematics on the site here. This AMS reference is very useful. If you need to format more advanced things, there are many excellent references on LaTeX on the internet, including StackExchange's own TeX.SE site. $\endgroup$ – Zev Chonoles Mar 2 '13 at 19:30
  • 4
    $\begingroup$ This is one reason why sensible people don't use $\omega$ to mean the cardinal $\aleph_0$. $\endgroup$ – Chris Eagle Mar 2 '13 at 20:19
  • $\begingroup$ @Chris: I think it's really context dependent. If you don't refer to ordinals or at least ordinal arithmetics then it's fine and causes no harm. But I generally agree that $\aleph_0$ is a better notation for the cardinal. $\endgroup$ – Asaf Karagila Mar 2 '13 at 20:26
14
$\begingroup$

$2^\omega$ means two different things, depending on whether you’re doing cardinal exponentiation or ordinal exponentiation. You’re thinking of cardinal exponentiation: for that it’s perfectly true that $2^\omega>\omega$. For ordinal exponentiation, however, $2^\omega$ is simply $\bigcup_{n\in\omega}2^n=\omega$.

$\endgroup$
  • 3
    $\begingroup$ This is why one should write $2^{\aleph_0}$ when speaking of cardinal arithmetic, and $2^\omega$ when speaking of ordinal arithmetic.. $\endgroup$ – GEdgar Jul 14 '15 at 13:47
  • $\begingroup$ @GEdgar: That's a matter of taste; context is almost always an adequate guide. In the great majority of cases I prefer omega for the cardinal. $\endgroup$ – Brian M. Scott Jul 14 '15 at 14:31
13
$\begingroup$

Ordinal exponentiation is not cardinal exponentiation.

The cardinal exponentiation $2^\omega$ is indeed uncountable and has the cardinality of the continuum.

The ordinal exponentiation $2^\omega$ is the supremum of $\{2^n\mid n\in\omega\}$ which in turn is exactly $\omega$ again.

Also related:

  1. How is $\epsilon_0$ countable?
  2. Do $\omega^\omega=2^{\aleph_0}=\aleph_1$?
$\endgroup$
7
$\begingroup$

Note that $2^\omega$ is not the powerset of $\omega$, and $|2^\omega|\ne2^{|\omega|}$, where the alatter is cardinal arithmetic. If you read on in that Wikipedia article, you'll see that $2^\omega$ is obtained by taking the maps $\omega\to 2$ with finite support, not arbitrary such maps. That corresponds to the finite subsets rather than arbitrary subsets, thus to terminating binary sequences (esp. ratioanl numbers) instead of arbitrary binary sequences (real numbers) if you like.

$\endgroup$
  • 2
    $\begingroup$ Isn't $|\omega|$ equal to $\omega$? I don't think you can rely on the presence of $|\cdot |$ in the exponent to distinguish cardinal arithmetic from ordinal arithmetic. I think the only way to be sure is to tell the reader "this is ordinal arithmetic" or "this is cardinal arithmetic" $\endgroup$ – Trevor Wilson Mar 2 '13 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.