Welcome to MathOverflow

Question

2

The Cantor Normal Form Theorem states that every ordinal $\alpha > 0$ can be uniquely expressed in the form $$\omega^{\beta_1}k_1 + \omega^{\beta_2}k_2 + \dots + \omega^{\beta_n}k_n$$ for some $n \ge 1$, positive integers $k_1,k_2,\dots,k_n$ and ordinals $\alpha \ge \beta_1 > \beta_2 > \dots > \beta_n$.

If I understand this correctly, then every countable ordinal's Cantor Normal Form is a finite-degree polynomial in $\omega$. My reasoning is that if $\beta$ is infinite, then $\omega^{\beta}$ is uncountable. This must be incorrect because it would imply that there are only countably many countable ordinals. Since $\aleph_1$ is the set of all countable ordinals and is uncountable, this is a contradiction.

My main question is where did I go wrong? If every countable set can't be written as a polynomial in $\omega$, what is a counter-example?

Thank you for your time.

flag	asked Apr 5 2012 at 3:00 Emily Sergel 61●4

4

No, exponentiation here is in the ordinal sense, it is not cardinal exponentiation. This is defined so $\alpha^\beta=\sup\{\alpha^\gamma\mid\gamma<\beta\}$ when $\beta$ is limit. But this easily gives (by an inductive argument) that $\alpha^\beta$ is countable if $\alpha$ and $\beta$ are countable. – Andres Caicedo Apr 5 2012 at 3:03

Well, $\omega^\omega = \sup \{\omega^n | n \in \omega \}$ but it is not countable. What am I missing? – Emily Sergel Apr 5 2012 at 3:18

2

$\omega^\omega$ is countable, as is any countable limit or countable ordinals. – Henry Towsner Apr 5 2012 at 3:24

1

@Emily: ...it's a countable union of countable sets – Pietro Majer Apr 5 2012 at 3:30

$\omega^\omega$ here does not mean the set of functions from $\omega$ to $\omega$, rather here it means the set of polynomials in $\omega$ of finite degree with integer coefficients. – David Feldman Apr 5 2012 at 3:33

show 3 more comments

Emily Sergel · Accepted Answer · 2012-04-05 03:48:54Z UTC

As per the many comments, the issue is confusing ordinal and cardinal arithmetic. The number of such expressions that yield countable ordinals is uncountable, as it should be. This is because the $\beta$ can range over all countable ordinals (of which there $\aleph_1$ many). Thank you to all commenters for replying so quickly.

Cantor’s Normal Form and Aleph_1

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.