Let $a\ne0$ be any ordinal
By transfinite recursion theorem, we can define a function f:OR→OR such that
i) $f(0)=1$
ii) $f(b^+)=f(b)a$
iii) $f(b)=\sup\{f(r)|r<b\}$ if $b$ is a limit ordinal.

Then how can I show that $f(b)$ defined as above is equal to $a^b$ which is an ordinal that is similar to a set of 'functions from $b$ to $a$' ?

  • $\begingroup$ How can i type 'myu-small a' here? $\endgroup$ – Katlus May 24 '12 at 11:08
  • $\begingroup$ The exponent $a^b$ of ordinals doesn't have a lot to do with the set of functions from $a$ to $b$. For example, $2^\omega=\sup\{2^n:n<\omega\}=\omega$. $\endgroup$ – Egbert May 24 '12 at 11:09
  • $\begingroup$ @Katlus Do you mean $\mu_a$ $\mu_a$? $\endgroup$ – Martin Sleziak May 24 '12 at 11:12
  • $\begingroup$ The notation $b^+$ is the next cardinal and not the successor ordinal. Are you sure this is an ordinal function and not a cardinal function? Furthermore ordinal exponentiation does not correspond to the set of functions from $a$ to $b$. $\endgroup$ – Asaf Karagila May 24 '12 at 11:22
  • $\begingroup$ In my book, b+ designates the successor ordinal of b...What else notation is there? $\endgroup$ – Katlus May 24 '12 at 11:25

The thing which you want to prove is not true. (Also it is not correctly formulated. If you write ordinal similar to the set of all functions from $b$ to $a$, you should also write some well-ordering for this set.)

The important thing here is to understand the diference between ordinal exponentiantion and cardinal exponentiation.

If $a$, $b$ are cardinals then by $a^b$ we mean the cardinality of the set of all maps from $b$ to $a$.

If $a$, $b$ are ordinals then by $a^b$ we mean an ordinal, which is usually defined in the way you described in your question.

These two things are different, e.g. $\omega^\omega$ (as ordinal power) has cardinality $\aleph_0$ which is less than $\aleph_0^{\aleph_0}=\mathfrak c$.

I don't think that there is some natural well-ordering on the set of all maps from $b$ to $a$ for ordinals $a$, $b$.

To see that cardinality of $\omega^\omega$ is $\aleph_0$ we can:

  • Show by induction that each $\omega^n$ for $n<\omega$ is countable.

  • Notice that $\omega^\omega=\sup\{\omega^n; n<\omega\}=\bigcup_{n<\omega} \omega^n$ is a union of countably many countable sets.

Quote from Wikipedia:

Warning: Ordinal exponentiation is quite different from cardinal exponentiation. For example, the ordinal exponentiation $2^\omega = \omega$, but the cardinal exponentiation $2^{\aleph_0}$ is the cardinality of the continuum which is larger than $\aleph_0$. To avoid confusing ordinal exponentiation with cardinal exponentiation, one can use symbols for ordinals (e.g. $\omega$) in the former and symbols for cardinals (e.g. $\aleph_0$) in the latter.

I am not sure to which extent it's useful here, but I'll add one possible graphical representation of $\omega^\omega$, since I've mentioned this ordinal a few times.

Imagine all finite sequences of non-negative integers ordered as in the picture: first from left to right (by the length) and in each column from bottom to top (lexicographically). The symbol $\varepsilon$ represents empty sequence, each point represents the sequence given by the path from root to this dot.

It should be at least clear that in the first column we have $\omega$, in the second column $\omega^2$ etc. (Since $\omega+\omega^2=\omega^2$, if we take all points up to second column, we get still $\omega^2$.) So clearly the ordinal in the picture is at least $\sup\{\omega^n; n<\omega\}$. If you think about it a little bit, you'll find out that this ordinal is the union of $\omega^n$'s, if $\omega^n$ is represented by the first $n$ columns.

omega to omega

  • $\begingroup$ I have a problem understanding your example. Let a be an initial ordinal equiptent with aleph_null. Then how could i know that a^a (set of functions from a to a) is an initial ordinal for (aleph_null)^(aleph_null)? $\endgroup$ – Katlus May 24 '12 at 11:23
  • $\begingroup$ The smallest infinite ordinal is usualy denoted $\omega$. It is not true that $\omega^\omega$ is the smallest ordinal of cardinality $\aleph_0^{\aleph_0}$. Of course it depends on the definition of ordinal exponentiation, I use the definition using transfinite recursion, which is described in your question. $\endgroup$ – Martin Sleziak May 24 '12 at 11:26
  • $\begingroup$ Im curious to know that why omega^omega is not the smallest ordinal of (alephnull)^(alephnull), use the definition in my question.. Help $\endgroup$ – Katlus May 24 '12 at 11:33
  • $\begingroup$ I've added a paragraph about cardinality of $\omega^\omega$. It's the paragraph which starts with To see that cardinality of $\omega^\omega$ is $\aleph_0$... $\endgroup$ – Martin Sleziak May 24 '12 at 11:40
  • $\begingroup$ @Katlus: You may want to also read my answer here $\endgroup$ – Asaf Karagila May 24 '12 at 12:34

To complement Martin's answer, I would like to give a concrete well-ordering having order type $\alpha^\beta$ for ordinals $\alpha$ and $\beta$. We consider the finitely supported functions from $\beta$ to $\alpha$, i. e. we set \[ E_{\alpha,\beta} := \{f\colon \beta \to \alpha \mid f^{-1}[\alpha - \{0\}] \text{ is finite} \}. \] To define an ordering on it, for $f\ne g \in E_{\alpha, \beta}$ let $\delta_{f,g} := \max\{\delta < \beta \mid f(\delta) \ne g(\delta)\}$ (note that this is well-defined as the set in question is finite). Now define \[ f < g \iff f(\delta_{f,g}) < g(\delta_{f,g}) \] Obviously for $\beta \le \gamma$ we have an obvious order respecting injection $\imath\colon E_{\alpha, \beta} \to E_{\alpha, \gamma}$, mapping $f\in E_{\alpha,\beta}$ to the function which is $0$ on all $\delta \not\in \beta$ and agrees on $\beta$ with $f$. Let $f_\beta \in E_{\alpha,\gamma}$ given by $f_\beta(\beta) = 1$, and 0 otherwise. Then $\imath(E_{\alpha,\beta}) = \{f \in E_{\alpha,\gamma} \mid f < f_\beta\}$, hence $E_{\alpha,\beta}$ is an initial segment of $E_{\alpha,\gamma}$. We will identify $E_{\alpha,\beta}$ with its image from now on.

We will show by transfinite induction on $\beta$ that $E_{\alpha, \beta}$ is isomorphic to $\alpha^\beta$:

  • For $\beta = 0$, $E_{\alpha,0}$ consits of only one element, namely $\emptyset\colon 0 \to \alpha$, hence is isomorphic to $1 = \alpha^0$.

  • Now lets consider $E_{\alpha, \beta+1}$, we definie $\phi\colon E_{\alpha,\beta+1} \to E_{\alpha,\beta} \times \alpha$ wia $f \mapsto \bigl(f|_\beta, f(\beta)\bigr)$, $\phi$ is bijective and we have for $f,g \in E_{\alpha,\beta + 1}$ denoting the components of $\phi$ with $\phi_1$ and $\phi_2$ respectively \begin{align*} f < g &\iff \bigl(\delta_{f,g} < \beta \wedge (f|_\beta < g|_\beta) \bigr) \vee \bigl( f(\beta) < g(\beta)\bigr)\\\ &\iff \bigl(\phi_2(f) = \phi_2(g)\wedge \phi_1(f) < \phi_1(g)\bigr) \vee \bigl(\phi_2(f) < \phi_2(g)\bigr)\\\ &\iff \phi(f) < \phi(g) \end{align*} when the product is given the usual product ordering for ordinal multiplication. So $E_{\alpha,\beta+1} \cong E_{\alpha,\beta} \cdot \alpha \cong \alpha^\beta \cdot \alpha = \alpha^{\beta + 1}$.

  • If $\lambda$ is a limit ordinal we have $E_{\alpha,\lambda} = \bigcup_{\beta<\lambda} E_{\alpha, \beta}$ under the above mentioned identification: Let $f \in E_{\alpha,\lambda}$, set $\beta := 1+\max f^{-1}[\alpha -\{0\}]$. Then $\beta < \lambda$ as $\lambda$ is a limit and $f \in E_{\alpha,\beta}$. Now the isomorphisms $E_{\alpha,\beta} \cong \alpha^\beta$ for $\beta < \lambda$ are compatible with the inclusions, we have \[E_{\alpha,\lambda} = \bigcup_{\beta < \lambda} E_{\alpha,\beta} \cong \sup_{\beta < \lambda} \alpha^\beta = \alpha^\lambda \]


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.