Given arbitrary sets $A$ and $B$, the notation $A^{B}$ is mostly clear from context to mean $A^{B} = \{f : f : B \rightarrow A\}$.

However, when these sets are ordinal or cardinals, especially $\omega$, the notation is not consistent even among subfields of logic.

For example $2^\omega$ in one sense can denote ordinal exponentiation. Hence $2^\omega = \lim_{n < \omega} 2^n = \omega$.

However, you can also consider $2^{\aleph_0}$. By using the cardinal $\aleph_0$, some people may consider it clear that $2^{\aleph_0}$ denotes the cardinal of the set $\{f : \aleph_0 = \omega_0 = \omega \rightarrow 2\}$.

In the above paragraph $2^{\aleph_0}$ is a cardinal, (in ZFC) it is a special ordinal. However, it descriptive set theory, you may want to consider not the cardinal but Cantor Space (or Baire Space), i.e. the set of functions from $\omega \rightarrow 2$. When you want the set of functions as oppose to the ordinal, is there a notation for that.

In recursion theory, I have found that $2^\omega$ or $\omega^\omega$ most frequently refers to Cantor or Baire space, and not the ordinal or cardinal. In Mostovachis book, he uses $\text{}^\omega2$ to denote Cantor Space.

Does anyone know of any establish custom to distiguish between ordinal exponentiation, cardinality of the set of functions between ordinals, and the actual set of functions between ordinals. I was thinking perhaps the left right exponent like $\text{}^\omega2$ and $2^\omega$ could be used as distinction, but from reference to recursion theory and Moschivakis's book, it seems that this is not the case.

Thanks for any help you can provide.

  • $\begingroup$ Language nit: Sets are neither ordinals nor cardinals. You mean when $A$ and $B$ are taken to be ordinals or cardinals, not when the sets are "ordinals" or "cardinals." $\endgroup$ – Thomas Andrews Aug 8 '12 at 17:25
  • 2
    $\begingroup$ $2^{\aleph_0}$ is cardinal regardless to the axiom of choice. In fact specifying $\aleph_0$ in the exponent means that it is implied that the interpretation is the cardinal of the power set of any set of size $\aleph_0$. Yes, cardinals make sense without the axiom of choice. $\endgroup$ – Asaf Karagila Aug 8 '12 at 17:33
  • $\begingroup$ It's not clear that $2^\omega = \omega$ since there is one order-preserving map from $\omega$ to (the ordinal) $2$ that is greater than all other such maps, the maximal constant function. So $2^\omega = \omega + 1$ $\endgroup$ – Thomas Andrews Aug 8 '12 at 17:36
  • 1
    $\begingroup$ @ThomasAndrews The third paragraph, I am referring explicitly to ordinal exponentiation. By definition (since $\omega$ is a limit ordinal), $2^\omega = \lim_{\alpha < \omega} 2^\alpha = \omega$. Refer to en.wikipedia.org/wiki/Ordinal_arithmetic#Exponentiation $\endgroup$ – William Aug 8 '12 at 17:53
  • 1
    $\begingroup$ It's probably too much to expect an unambiguous notation that everyone would understand, but if you're going to develop one for yourself, you might want to take a hint from computer science and let "$A\to B$" itself mean the set of all functions with domain $A$ and codomain $B$. You can then decorate the arrow in various ways when you need to consider only special kind of functions (e.g. hom(e)omorphisms). $\endgroup$ – Henning Makholm Aug 8 '12 at 17:55

My experience tells me that there is no "good" way of discerning the uses except your own experience in guessing the correct context. Especially in the ordinal-cardinal exponentiation. It takes some time to get used to, but that's just one of the problems working with a limited set of characters (while trying to be as succinct as possible).

Sometimes one has to read a sentence or two, holding in one's head a few possible interpretations until the correct one has been chosen. Sometimes one is wrong and later comes the "Ohhhhhh, so that was ordinal exponentiation" but with some experience this is almost completely eliminated.

[Good] writers will usually try to ensure the context is set when setting the notation "consider Cantor space, denoted by $2^\omega$, ..." or something of this kind.

That been said, when $\aleph$ numbers are in the exponent this is always the cardinal version of exponentiation.

There is also a common notation of $^AB$ as the set of all functions from $A$ into $B$, in this aspect $^\omega\omega$ can be seen as the Baire space (as its underlying set is exactly this). Note also that $\left|^AB\right|=|B|^{|A|}$.

Mildly related: Do $\omega^\omega=2^{\aleph_0}=\aleph_1$?


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.