Order type of infinite products?

98 Views Asked by At

Let $X$ and $Y$ be two totally ordered sets with order types $\alpha$ and $\beta$, respectively ($\alpha$ and $\beta$ are ordinals). The set of functions $X\to Y$ is given by the product...

$$Y^X=\prod_{x\in X}Y$$

What is the order type of $Y^X$? Is it the same as the order type of $\displaystyle \beta^\alpha=\prod_{i\in\alpha}\beta$?


Specifically, how does the order type of this infinite product differ from how we define the product order for smaller sets. As an example, consider the set of sequences of natural numbers...

$$\Bbb{N}^\Bbb{N}=\prod_{n\in\Bbb{N}}\Bbb{N}$$

For each finite subset $[n]=\{m\in\Bbb{N}\mid m\le n\}$, we have that the order type of the product...

$$otp(\Bbb{N}^{[n]})=otp(\prod_{i\in[n]}\Bbb{N})=otp(\Bbb{N})^n$$

...is the same as the product of the order type (namely $\omega\cdot\omega\cdots\omega=\omega^n$), given the product order. Clearly the order type of $\Bbb{N}^\Bbb{N}$ cannot be regarded as the limit of the sequence $\omega^2,\omega^3,\cdots$, because this would suggest that the set of all infinite sequences of natural numbers is countable, which it is not.

1

There are 1 best solutions below

7
On BEST ANSWER

The simplest is to look at the least point of difference (lexicographic order): given $f,g:\alpha\rightarrow\beta$ with $f\not=g$, there is some smallest $\gamma\in\alpha$ with $f(\gamma)\not=g(\gamma)$ - call this "$\mu_{f,g}$." Then we set $$f\triangleleft g\iff f(\mu_{f,g})<g(\mu_{f,g}),$$ where "$<$" refers to the usual ordering on $\beta$.

Note that the existence of such a $\gamma$ (and hence the definition of $\triangleright$) relies on the assumption that $\alpha$ is well-ordered. In general, there's no "explicit" way to put a linear ordering on the set of maps between linear orders in general (even if the target is assumed to be well-ordered): it is consistent with ZF that the powerset of $\mathbb{R}$ is not linearly orderable.

Also, note that this is quite different from ordinal exponentiation. Remember, in ordinal exponentiation we have $2^\omega=\omega$ - the point being that ordinal exponentiation is defined so that $$\alpha^\beta=\sup\{\alpha^\gamma: \gamma<\beta\}.$$ (It's only half-continuous, by the way - it's not true that $\alpha^\beta=\sup\{\gamma^\beta:\gamma<\alpha\}$, and you can see that by considering $\alpha=\omega,\beta=2$.)