7
$\begingroup$

Given well-ordered sets $\alpha$ and $\beta$, define $\left(\!\!{\alpha\choose \beta}\!\!\right)$ to be the set of weakly decreasing functions from $\beta$ to $\alpha$, ordered lexicographically; this is in fact a well-ordering, so we get an operation on ordinals.

(I denote it by multichoose since for $n$, $k$ finite, $\left(\!\!{n\choose k}\!\!\right)$ is indeed $\left(\!\!{n\choose k}\!\!\right)$ in the usual sense.)

We can also order reverse-lexicographically and get a well-order; I'm calling that \left(\!\!{\alpha\choose \beta}\!\!\right)'. Same questions about that. (And we can restrict to strictly decreasing functions to get $\binom{\alpha}{k}$ and \binom{\alpha}{k}', but obviously $k$ has to be finite for that to be interesting.)

What are these operation ordinarily called? Where could I look up more information about them?

1 Answers 1

3

I have never seen either ordinal operation used; I’m not at all sure that I’ve even seen either linear order used in any substantial way. They caught my interest, however, so I played with the first one a bit; you may already know all of this, but if not, perhaps it will be of some use in lieu of a reference.

I will write $\,^{\beta\downarrow}\alpha$ for the set of weakly decreasing $\beta$-sequences in $\alpha$ and $\prec$ for the (strict) lexicographic order on ordinal sequences. All arithmetic is ordinal arithmetic (and with luck I made no serious errors in it!).

A weakly decreasing $\beta$-sequence $\sigma$ in $\alpha$ can be encoded as a finite sequence $\Big\langle\langle\xi_k,\eta_k\rangle:k<\ell\Big\rangle\;,\tag{1}$ where $\langle\xi_k:k<\ell\rangle$ is a strictly decreasing sequence in $\alpha$, $\eta_0+\dots+\eta_{\ell-1}=\beta$, and each $\eta_k>0$: the $\xi_k$ are the terms of the sequence, and $\eta_k$ is the order type of the subsequence of $\xi_k$ terms; I will call these the $k$-th term and the $k$-th length of $\sigma$, respectively. It will be convenient to rewrite the code $(1)$ as $\langle\xi_0,\eta_0,\xi_1,\eta_1,\dots,\xi_{\ell-1},\eta_{\ell-1}\rangle$ and denote this by $c(\sigma)$. It’s not hard to see that \sigma\prec\sigma' iff c(\sigma)\prec c(\sigma').

Consider first the case $\beta=\omega^\lambda$ for some ordinal $\lambda$. This is equivalent to the assertion that if $\beta=\alpha+\gamma$, then $\gamma=\beta$, so the last length of any $\beta$-sequence must be $\beta$, while the other lengths may be any ordinals less than $\beta$.

Clearly $\left(\!\!\binom1{\beta}\!\!\right)=1$. The code of a $\beta$-sequence in $2$ is either $\langle 0,\beta\rangle$, of the form $\langle 1,\eta,0,\beta\rangle$ for some $\eta$ such that $0<\eta<\beta$, or $\langle 1,\beta\rangle$, so $\left(\!\!\binom2{\beta}\!\!\right)=\beta+1$. In general suppose that $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\gamma$. Clearly $\,^{\beta\downarrow}\alpha$ is an initial segment of $\,^{\beta\downarrow}(\alpha+1)$ with respect to $\prec$. If $\sigma\in\,^{\beta\downarrow}(\alpha+1)\setminus{^{\beta\downarrow}\alpha}$, the first term of $\sigma$ must be $\alpha$. Let $\eta$ be the first length of $\sigma$, and suppose that $\eta<\beta$. What’s left of $c(\sigma)$ when $\alpha$ and $\eta$ are stripped from it is the code of some member of $\,^{\beta\downarrow}\alpha$, so the set of $\sigma\in\,^{\beta\downarrow}(\alpha+1)$ with first term $\alpha$ and first length $\eta$ has order type $\gamma$, and it follows easily that $\left(\!\!\binom{\alpha+1}{\beta}\!\!\right)=\gamma\cdot\beta+1\;.$

Now let $\beta=\omega^{\lambda_1}+\omega^{\lambda_2}+\dots+\omega^{\lambda_m}$, where $\lambda_1\ge\lambda_2\ge\ldots\ge\lambda_m$; this representation, which is a variant of Cantor normal form, is unique. Suppose that $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\gamma$. As before, $\,^{\beta\downarrow}\alpha$ is an initial segment of $\,^{\beta\downarrow}(\alpha+1)$. Suppose that $\sigma\in\,^{\beta\downarrow}(\alpha+1)\setminus{^{\beta\downarrow}\alpha}$, so that the first term of $\sigma$ is $\alpha$, and let $\eta$ be the first length of $\sigma$. If $\eta<\omega^{\lambda_1}$, what’s left of $c(\sigma)$ when $\alpha$ and $\eta$ are stripped off the front is the code of some member of $\,^{\beta\downarrow}\alpha$. Thus, if $c(\tau)=\langle\alpha,\omega^{\lambda_1},0,\omega^{\lambda_2}+\dots+\omega^{\lambda_m}\rangle$, the set of predecessors of $\tau$ in $\,^{\beta\downarrow}(\alpha+1)$ has order type $\gamma\cdot\omega^{\lambda_1}$. An easy induction now shows that $\begin{align*} \left(\!\!\binom{\alpha+1}{\beta}\!\!\right)&=\gamma\cdot\omega^{\lambda_1}+\gamma\cdot\omega^{\lambda_2}+\dots+\gamma\cdot\omega^{\lambda_m}+1\\ &=\gamma\cdot\Big(\omega^{\lambda_1}+\omega^{\lambda_2}+\dots+\omega^{\lambda_m}\Big)+1\\ &=\gamma\cdot\beta+1\;.\tag{2} \end{align*}$

Henceforth I assume that $\lambda_1\ge 1$. It follows from $(2)$ that the dominant term in the Cantor normal form of $\left(\!\!\binom{n+1}{\beta}\!\!\right)$ is $\omega^{\lambda_1\cdot n}$ for $n\in\omega$. (It’s entirely possible to write out the whole expansion, but it’s rather messy.)

If $\alpha$ is a limit ordinal, the sets $\,^{\beta\downarrow}\lambda$ for $\lambda<\alpha$ are increasing initial segments of $\,^{\beta\downarrow}\alpha$, so $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\sup_{\lambda<\alpha}\left(\!\!\binom{\lambda}{\beta}\!\!\right)\;.\tag{3}$

It particular, $\left(\!\!\binom{\omega}{\beta}\!\!\right)=\omega^{\lambda_1\cdot\omega}$, and it follows from $(2)$ and $(3)$ that for $\alpha\ge\omega$ the dominant term in the Cantor normal form of $\left(\!\!\binom{\alpha}{\beta}\!\!\right)$ is $\omega^{\lambda_1\cdot\alpha}$, with $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\omega^{\lambda_1\cdot\alpha}$ when $\alpha$ is a limit ordinal.

  • 0
    Having looked at the problem of computing these some more, I'm now quite certain that this answer is wrong. As I noted above, it fails when α and β are finite, but it also fails in many other cases. For instance, "ω multichoose ω+1" is $\omega^\omega$, but "ω+1 multichoose ω+1" is $\omega^{\omega+1}+\omega+1$, not $\omega^{\omega+1}+1$. Your recursion is correct when β is a power of ω, though. (I actually have a rule for computing these in general, but it is unfortunately quite complicated...)2015-01-25